ANN: church 1.0 -- Lambda calculus explorer

Erik Max Francis max at
Sat Feb 2 23:33:58 CET 2002

Here's the second of the Alcyone PyOS modules that has been released:


    This module allows simple experimentation with the lambda
    calculus, first developed by Church.  It understands the different
    types of lambda expressions, can extract lists of variables (both
    free and bound) and subterms, and can simplify complicated by
    expression by means of application.

Getting the software

    The software is available in a tarball here:

    The official URL for this Web site is


    Notations for lambda expressions vary slightly, so it is
    instructive to detail the precise notation used by this module.
    A variable is expressed with a string of alphanumeric characters,
    *e.g.*, 'x' or 'abc1'.  There are three types of lambda

    **variable expression** -- A variable expression is simply an
      expression consisting of a single variable, *e.g.*, 'x'.

    **lambda expression** -- A lambda expression consists of a
      backslash ('\'), one or more variables separated by spaces, a
      dot ('.'), and a final expression.  For example, '\x.M' where
      *x* is a variable and *M* is an expression.  Repeated variables
      are equivalent to recursed lambda expressions, so '\x y.M' is
      equivalent to '\x.\y.M'.

    **application expression** -- An application expression consists
      of two or more adjacent expressions surrounded by parentheses:
      '(M N)', where *M* and *N* are expressions.  Applications are
      left associative, so '(M N P)' is equivalent to '((M N) P)'.

 Erik Max Francis / max at /
 __ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/  \ Laws are silent in time of war.
\__/ Cicero
    Esperanto reference /
 An Esperanto reference for English speakers.

More information about the Python-list mailing list