In grammar, as well as in the theory of programming languages, "syntax" specifies the grammatical nature or construction of a statement. "Semantics" deals with the meaning attached to a well-formed statement. It should be observed that not all syntactically correct statements have a valid meaning--Noam Chomsky, the well-known linguist, constructed the counter-example, "Colorless green ideas sleep furiously," a grammatical but completely meaningless statement in English, to show why.
Thus, the consideration of the semantics of statements in programming language, as in natural language, is an important endeavor in its own right. To this end, it is often useful to use mathematical functions to describe the semantics of programming language statements, since the meaning of a computer program can be thought of as a function that accepts the program's input values and produces their corresponding output values. Functions of course also play a very important role in mathematics, which is one reason why the theory of functions, including the question of computability--that is, exactly which functions are equivalent to some computer program--was largely developed in the days prior to the birth of computer science. These issues are still studied in their own right as parts of mathematical logic and the foundations of mathematics.
In order to study mathematical functions as tools of semantic analysis, it is important to create a formal notation and a "calculus" (a system for formal reasoning) to be applied in forming a theory of functions. This was done in the 1930s by Alonzo Church (he of the Church-Turing thesis fame), by his development of the lambda calculus as a theory of functions that provides rules for manipulating functions in a purely syntactic manner.
Even though Church's original motivation in developing the lambda calculus was to provide a foundation for mathematics by means of creating a special tool for mathematical logic, the results of his work have had considerable application in computer science. There is of course the significant influence from the theory of computation, since the question of computability is as significant to computer science as it is to mathematics. There is also a very great influence in other areas, most significantly in the theory of programming languages.
We may note the important contributions of the lambda calculus to the study of formal semantics of programming languages, as follows:
The lambda calculus has the power to represent all computable functions, but its uncomplicated syntax and semantics provides a fine basis for the specific context of the study of the semantics of programming language concepts.
The class of functional programming languages are those such as Perl, Python, or SML, Scheme, etc., that emphasize evaluations of mathematical expressions, rather than executions of commands as with imperative languages such as C, C++, etc. These languages can all be considered to be syntactic variations on the lambda calculus, so both their semantics and their implementations can be analyzed using the same.
Denotational semantics is one of the foremost areas of research in programming languages, as well as in machine translation and understanding of natural languages (such as English). This important and exciting field of study largely grew out of research using the lambda calculus. Denotational semantics expresses its definitions and results using the higher-order functions provided by the lambda calculus.
A very basic introduction to the lambda calculus may be given as follows. A mathematical function is a mapping from the elements of a domain to the elements of a range (or co-domain), as fixed by a rule--for instance:
cube : Integer Integer, where cube (n) = n3.
The lambda notation created by Church allows the definition of an anonymous function to fit this requirement, as follows:
n.n3 defines the function that maps each n in the domain to n3.
We would say, speaking formally, that the expression represented by n.n3 is the value bound to the identifier "cube."
One of the many important points about the lambda notation is its lack of ambiguity; the number and order of the parameters of the function are strictly specified between the symbol and an expression. To take an easy example, the conventional algebraic notation (n2 + m) is ambiguous as the definition of a function rule, because (3, 4) could either be 32 + 4 = 13, or 42 + 3 = 19. The lambda notation removes the ambiguity by specifying the order of the parameters as one or the other of:
n.m.n2 + m, and
m.n.n2 + m.
This is the complete article, containing 722 words
(approx. 2 pages at 300 words per page).
