|
|
-
| <Exp> | ::=
| <identifier> | | | |
| ( <Exp> ) | | | |
| <Exp> <Exp> | | | --application |
| λ<identifier>.<Exp> | | --abstraction |
- -- Syntax of the λ-calculus --
-
- The syntax of the λ-calculus is very simple, comprising
just four kinds of expression but surprisingly
it is sufficient to define any computable function.
- Constants including integers, booleans and so on can all be defined
using just the syntax above,
as some of the examples demonstrate.
Because of this it is sometimes convenient to extend the
syntax with a fifth option of constants
(0, 1, 2, ..., true, false, and, +, ...) but,
if that is done, it is only a convenience and does not
increase the power of the language.
- Note that an abstraction defines an anonymous function.
- The pure λ calculus appears to lack recursion
(or equivalently iteration)
but recursive functions can in fact be defined,
as examples also demonstrate.
-
-
- NB. The applet above needs Java on.
-
- The introduction describes
the semantics of λ calculus and programming techniques, and
the interpreter shows how it can be made to work.
|
|