# ANN: church 1.0 -- Lambda calculus explorer

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

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

http://www.alcyone.com/pyos/church/

Summary

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:
http://www.alcyone.com/pyos/church/church-1.0.tar.gz.

The official URL for this Web site is
http://www.alcyone.com/pyos/church/.

Notation

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
expressions:

**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 alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/  \ Laws are silent in time of war.
\__/ Cicero
Esperanto reference / http://www.alcyone.com/max/lang/esperanto/
An Esperanto reference for English speakers.

```