19
$\begingroup$

In programming language theory, people study the theory behind programming languages. But I have never heard any formal definition of programming languages themselves. What is the formal definition, not of a particular programming language like Python or C++, but of programming languages themselves?

$\endgroup$
  • 2
    $\begingroup$ You only need such a definition if you want to formulate theorems that talk about all programming languages (or maybe the existence of a language with certain properties). I do not know enough about CS to know whether many of those theorems exist. $\endgroup$ – Carsten S Aug 31 at 11:06
36
$\begingroup$

To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no less, any convention that is used for describing instructions for computers to execute. This includes, for example, not just C++ and Python, but also things like Nondeterministic programming, where we actually don't tell the computer exactly what to do, but give it several alternatives and allow it to choose any one of them; declarative logic languages like Datalog where we give the computer a set of logical axioms and ask it to deduce all the true statements from those axioms; and even very low-level descriptions like Turing machines and electrical circuits, where we give the program explicitly as electrical or mechanical components. All of these are ways of describing instructions to computers, so all are valid programming langauges at very different levels of abstraction.

However, programming languages researchers do generally agree on some common formal components of programming languages that should always be present, and these serve as a general definition. Namely: every programming language is defined by a syntax and a semantics.

  • Syntax. This is a formal grammar which gives the set of programs that can be written. Importantly, the formal grammar consists of finitely many syntax elements, which are described in terms of other syntax elements. For example a simple grammar is:

    Variable := x | y | z
    Term := 0 | 1 | Term + Term | Variable
    Program := set Variable = Term | return Term | Program; Program
    

    In this simple language, we have three syntax elements: Variables, Terms, and Programs. In a formal grammar, each syntax element has finitely many cases for how it can be constructed via other syntax elements. For example, a program is either an assignment (setting a variable to equal a term, e.g. set x = x + 1), a return statement, or a sequence of two programs which should be executed one after the other.

  • Semantics. Syntax is just describing the set of valid programs; but it doesn't say anything about what those programs mean. Semantics is a way of assigning meaning to programs. Unlike syntax, which is almost always given as a formal grammar as above, semantics can be given in at least two different ways: these include "denotational semantics", where we assign a mathematical object such as a function to each program, or "operational semantics", where we describe the execution of a program in a more true-to-life way as a sequence of steps.

    To illustrate this, starting with denotational semantics: we would say that the term 3 + 5 + 8 is assigned the meaning of 16. More interestingly, the program set x = x + 3 + 5 is assigned the meaning of the mathematical function mapping every integer to that integer plus 8.

    Operational semantics, on the other hand, is very different. We would say that the term 3 + 5 + 8 evaluates to 8 + 8 which in turn evaluates to 16. We would also say that the program set x = x + 3 + 5 in a context where x = 5 evaluates to a context where x = 13. So, instead of giving a meaning to each term or program itself, we give a meaning between terms called "evaluates to": we give a formal definition of what it means for A to evaluate to B in the context C.

    In any case, the semantics of a language, whether denotational or operational (or something else) gives meaning to the symbols and allows us to make sense of what programs compute, not just what they look like.

Putting these together, we get the following definition.

Definition: A programming language consists of (1) a syntax, given as a formal grammar; and (2) a semantics, given either as denotational semantics which gives a meaning to each syntax element, or an operational semantics which says when two programs or program contexts relate.

| cite | improve this answer | |
$\endgroup$
  • 15
    $\begingroup$ Note that "formal grammar which gives the set of programs that can be written" should be interpreted broadly. There are programming languages like Piet in which programs look like abstract paintings by Piet Mondrian, or more serious visual programming languages like Scratch and Thyrd. $\endgroup$ – Jörg W Mittag Aug 31 at 6:42
  • 3
    $\begingroup$ @RBarryYoung A popular language is Verilog, you can see an example in that link. More generally such languages are called "hardware description languages". Although a bit simplified, you can imagine that the program consists in just listing out the gates in the circuit and connections between them. $\endgroup$ – 6005 Aug 31 at 15:19
  • 1
    $\begingroup$ .. since ladder diagrams has its roots as an electrician's wiring diagram. Interestingly ladder diagrams are Turing complete as in you can draw a ladder diagram of a Turing machine. I've written ladder logic compilers myself where the textual syntax is not ASCII art but instead look like C/C++ logic: a = a & b & ( c | d ). The only operators in the language are | for OR, & for AND, = to assign the output of a line and brackets () for grouping. This is Turing-complete given the rules of ladder logic (an implicit forever loop surrounding your "program") $\endgroup$ – slebetman Sep 1 at 5:27
  • 1
    $\begingroup$ @6005 I like your definition, but I think it needs a (3) along the lines of "intended to describe a program for an electronic computer". Otherwise the definition given could, at a stretch, apply to cookery recipes, musical scores... $\endgroup$ – Mark Morgan Lloyd Sep 1 at 15:22
  • 2
    $\begingroup$ @Jörg W Mittag The mention of a formal grammar (implied to be textual) could apply to a graphical language. The fact that a programming language is graphical doesn't imply that its syntax description has to be graphical, that its semantics have to be describable graphically, or that it must be implemented using another graphical language. $\endgroup$ – Mark Morgan Lloyd Sep 1 at 15:28
2
$\begingroup$

I think it is very hard to give a definition that is both general, formal, and not too general. And I don't think I've seen any attempts. Nevertheless, here is an attempt at a mathematical definition.

A programming language consists of a set of programs $P$ such that each element of $P$ is finite and for each element $p$ of $P$ there is triple $m(p) = (I,O,f)$ such that $I$ and $O$ are sets and $f$ is a relation between $I$ and $O$ such that for each $I$ there is at least one related $O$.

The idea is that $m(p)$ is the meaning of program $p$, $I$ is its set of inputs, $O$ is its set of outcomes, $f$ gives, for each input, the set of possible outcomes that might result from that input.

Note that the elements of $I$ and $O$ need not be finite. The restriction that the elements of $P$ be finite is arbitrary and I only put it there, because I don't think that a programming language that has infinitely large programs would be very useful. The restriction that for each input there should be at least one outcome is the "no miracles" healthiness condition. That means that we need one or more outcomes to represent nontermination, at least, when the program might not (or must not) terminate for some inputs.

Here are three objections to this definition.

It's too general: One problem with this definition (and I suspect any improvement to it) is that many things we don't think of as programming languages can be made to fit it. Here are two examples

  • HTML (without JavaScript) is a programming language by this definition. Some people would say that's not right because HTML is formatting language rather than a programming language.
  • We can imagine a programming language that contains a program $h$ such that $m(h) = (T, \{true, false\}, f)$ where $T$ is the set of all Turing Machines, and $f$ maps $t \in T$ to $true$ if $t$ halts when started on an empty tape and maps $t$ to $false$ if $t$ doesn't halt when started on an empty tape; some people would say that's no programming language.

The response is that you can make further restrictions as needed. E.g., you can define the set of all Turing-complete programming languages by making suitable refinements.

It's not general enough: For some things that seem like programming languages it might take some creativity to fit them into this framework. For example for a probabilistic programming language the outcomes would need to be probability distributions. A better approach might be to abandon this definition and use suitable generalization of relations. Similar remarks apply to quantum computing.

The response is that the examples given show it might be awkward to fit some languages to the definition.

It misses that programming languages have variants: Real programming language definitions are often parameterized. For example in C int i = 10 * 1000 * 1000 * 1000 ; has undefined behaviour on some implementations and is well defined on others; it depends on choices that are up to the implementer. My definition doesn't capture that idea.

The response is that it's easy to generalize the definition by adding another input to the $m$ function representing the variant of the language or (by Currying) to think of a language like C as being a function from a set of choices to a language of the sort defined here.

Three books that explore ideas along these lines are

  • Hoare and He, Unifying Theories of Programming
  • Francez, Program Verification
  • Hehner, a Practical Theory of Programming
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Note that programs in a programming language don't need to be written down as text, there are programming languages that use graphs instead. So anything that restricts programming languages to text is not a formal, rigorous description of a programming language.

Note that for many text-based programming languages, the set of programs in the language cannot be described by a grammar alone. Many programming languages have additional rules that cannot or are not expressed by a grammar.

Note that for many text-based programming languages, programs are not described by one string, but by one or more strings, stored in files. For example, static items in C or C++, fileprivate items in Swift, are based on the concept of having multiple files that are combined.

Note that many programming languages include a "standard library", which is part of the language. And many programming languages assume that there is a "standard environment" in which they work.

Note that many programs do not process text based input and produce text based output. Instead the process inputs from a huge range of input mechanisms and produce an effect using a huge range of output mechanism.

So all in all, you will have a very hard time finding a rigorous and formal definition of programming languages, that works with actual programming languages that are in daily use.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Look what I found https://en.wikipedia.org/wiki/Programming_language

A programming language is a formal language comprising a set of instructions that produce various kinds of output. Programming languages are used in computer programming to implement algorithms.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This isn't necessarily a "formal, rigorous" definition which is what the OP is interested in. $\endgroup$ – 6005 Sep 4 at 12:57
0
$\begingroup$

A programming language is one which can be encoded by a formal system; for example, through a Backus-Naur form which is a common technique for describing context-free grammars.

However, I'd say, it is only a potential programming language until there is hardware that can interpret and run it. At bottom this is a Turing machine. Theoretically speaking, we can identify the two.

It's worth noting that a programming language by this definition may not be very practical and which is an important consideration for programming languages in practise. However, the point of describing programming languages theoretically is to theorise with them, so the simplest possible definition here is usually the most effective. After all, this is one reason why we use a Turing Machine to model computation and not some more complex machine.

| cite | improve this answer | |
$\endgroup$

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.