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.
More information about the Python-list
mailing list