Lambda Calculus

A Functional Programming Language.

The complete grammar of a small functional programming language follows. It allows the manipulation of integer, boolean, character, empty, list and function values. In programming language terms, type-checking is done at run-time when a program is executed. Note that most modern functional languages have static (compile-time) type checkers.

The empty value `( )' is principally used as a parameter to functions with no "proper" value, as in C. It is an unnecessary value in a lazy language and is only included for use with the strict version of the interpreter which accepts the same syntax.

<program> ::= <Exp>

<Exp> ::= <ident> | <numeral> | '<letter>' | () | true | false | nil |
          ( <Exp> ) | <unopr> <Exp> | <Exp> <binopr> <Exp> |
          if <Exp> then <Exp> else <Exp> |
          lambda <param> . <Exp> |  <Exp> <Exp> |
          let [rec] <decs> in <Exp>

<decs>  ::= <dec>,<decs> | <dec>
<dec>   ::= <ident>=<Exp>

<param> ::= () | <ident>

<unopr> ::= hd | tl | null | not | -
<binopr> ::= and | or | = | <> | < | <= | > | >= | + | - | * | / | ::

priorities:   ::                1  cons list (right associative)
              or                2
              and               3
              = <> < <= > >=    4  scalars only
              + -               5  (binary -)
              * /               6
              application       7
              - hd tl null not  8  (unary -)

Grammar for a Functional Programming Language.