Lambda Calculus

LA home
Computing
FP
 λ-calculus
 PFL (λ-CCS)
 Ind.Prog.(IP)
 Haskell
 SML

 λ-calculus
  Intro.
  Examples
  Syntax
  Interp.(L)
  Interp.(S)

also see
 PFL (λ-CCS)
 Prolog
<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, conditiional, declarations and so on can all be defined using just the syntax above, as demonstrated by examples. Because of this it is sometimes convenient to extend the syntax with options for constants (0, 1, 2, ..., +, -, *, /, =, ≠, ≤, <, ≥, >, true, false, ∧, ∨, ¬, nil, cons, null, hd, tl, if...then...else..., let...in... etc.) 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 also demonstrated by examples.



The introduction describes the semantics of λ calculus and programming techniques, and an interpreter shows how it can be made to work.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 19-Mar-2024 10:58:07 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.