I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.

PL is a formal language endowed with two structures: a translator and an abstract machine.

Translator defines a mapping from program strings, as defined by BNF grammar, into a representation of programs as hierarchies of directed graphs.

Abstract machine is a mathematical model of computation.

Is it an appropriate and full definition? Do you have another?

  • 8
    $\begingroup$ Your formal definition seems to be taken from a very specific source. I don't think there's an agreed upon formal definition of programming language. $\endgroup$ Oct 30 '19 at 21:51
  • $\begingroup$ You say that you found this definition in a published paper yet your title says my definition of programming language. What gives? Anyway there is no formal definition of programming language, only the languages part has definitions that are widely accepted. Also keep in mind that a definition is correct if it is well defined, so most definitions are correct. If I start my paper saying "Let's define a programming language as an integer between 3 and 7 inclusive" then 5 is a programming language. $\endgroup$ Oct 31 '19 at 11:48
  • 1
    $\begingroup$ Your sources are very old fashioned. How about somethng that is a bit more relevant nowadays, e.g., Benjamin Pierces Types and Programming Languages? $\endgroup$ Oct 31 '19 at 16:30
  • $\begingroup$ I bet “hierarchies of directed graphs” serve the same purpose as abstract syntax trees (AST) and “mathematical model of computation” is semantics. I think your definition is correct. Both components (syntax and semantics) may have formal definitions. Semantics is mapping from the AST of a program to a function or relation that expresses what the program computes. $\endgroup$
    – beroal
    Dec 15 '20 at 18:52
  • $\begingroup$ See also this answer: cs.stackexchange.com/a/129706/69135 . $\endgroup$
    – beroal
    Dec 15 '20 at 18:57

It is certainly not a full definition; one might reasonably expect a "real" programming language to have not merely an abstract mathematical model defining the language's semantics, but also a concrete implementation of a compiler or an interpreter which runs on an actual computer. Then again, one might reasonably not expect this. Is lambda calculus, for example, a programming language? Wikipedia doesn't define it as one, but if somebody else does then I can't say they are wrong.

There are many aspects of what makes a language a "programming language"; reasonable people might disagree on whether a certain aspect (say, Turing completeness) is strictly necessary for something to count as a true programming language. It is unlikely that any list of such aspects would ever be agreed by all computer scientists, or even just the academic computer science community, to be both correct and complete.

The concept of a "programming language" is not in the same category as mathematical concepts such as "group". It is possible for a formal definition of a group to be correct or incorrect, but a formal definition of a programming language can merely be useful or not useful (or, more useful or less useful) relative to the use at hand. Presumably, the definition you quoted was useful for the author of the paper you found it in.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.