=begin comment Lambda-Calculus in Perl M-J. Dominus Copyright 1999 M-J. Dominus =end comment Pure Untyped Lambda Calculus and Real-World Programming Languages The Lambda Calculus can be viewed as a very simple programming language, one which is a subset of, for example, Scheme. In fact the list of features necessary for a language to contain LC is very short: =over 4 =item 1. First-class function values =item 2. Lexical closure =item 3. No interfering semantic contraints =back It must be possible to construct function values dynamically and pass them as arguments to other functions. Lexical closure is necessary to prevent conflict between formal parameter names in different functions. A language may also fail to contain the Lambda Calculus if it has certain kinds of constraints on function application. For example, the type system of Standard ML, does not permit values as flexible as lambda terms must be. In languages with these properties, writing an interpreter for lambda calculus expressions is trivial, because the language itself is already such an interpreter. Instead of representing lambda terms as strings or more complex data structures, and instead of building an evaluation function, one represents lambda terms as the function values already supplied by the language, and uses the language's own built-in evaluation semantics. Of the three properties, first-class function values are the hardest to come by in the commercial and industrial programming world. For example, none of the popular languages C, Fortran, or COBOL has first-class function values, and so none contains the lambda calculus. However, in the past ten years, a popular language has emerged which I have these features: Perl. Originally developed in 1987 by Larry Wall as a cross between AWK and C, it was used for many years as a systems programming language for Unix systems. Since then, it has become very widely used in many environments, most notable in programs that deliver dynamic content to Web browsers. Perl 5, released in late 1994, introduced first-class function values with lexically scoped variables. This version of Perl contains the Lambda Calculus as a subset, as this note will demonstrate. The following program is an implementation of a lambda-calulus-style recursive addition function using no Perl features other than function abstraction and application. Because of this, the code should be intelligible to anyone who understands these four syntactic features of Perl: =over 4 =item 1. <$x> is a variable. =item 2. C is the lambda-term (lambda I . I) =item 3. C<$P-E($Q)> applies the lambda-term I

to the lambda-term I. =item 4. C<#> introduces a comment that continues to the end of the line. =back Perl uses call-by-value semantics, so delaying tactics are used to prevent premature evaluation of the consequents of the C function and premature expansion of recursive function calls. To express IF CONDITION x y we write instead (IF CONDITION (%q.x) (%q.y)) FORCE where C is arbitrary. (In the code, it is taken to be the identity function.) In the comments that follow, the symbol C<%> represents the lowercase lambda, so, for example, the identity function is represented as %x.x The implementation uses a list representation of numerals rather than Church numerals. In this representation, the numerals are represented as follows: =over 4 0 (true, true) 1 (false, (true, true)) 2 (false, (false, (true, true))) ... ... =back This is just to provide an excuse to demonstrate a recursive addition function. Church Numerals may also be implemented in the Perl Lambda-Calculus subset in the usual way; an implementation appears on my web site at http://www.plover.com/~mjd/perl/lambda/. ################################################################ # # Lambda Calculus demonstration in Perl # 23 March 1999 # M-J. Dominus (mjd-perl-lc@plover.com) # http://www.plover.com/~mjd/perl/lambda/ # ############ # # Truth and truth testing # IF = %btf.btf $IF = sub { my $b = shift; sub { my $t = shift; sub { my $f = shift; ($b)->($t)->($f); } } } ; # TRUE = %xy.x $TRUE = sub { my $x = shift; sub { my $y = shift; $x; } } ; # FALSE = %xy.y $FALSE = sub { my $x = shift; sub { my $y = shift; $y; } } ; ############ # # Pairs (conses) # PAIR = %xyb.bxy $PAIR = sub { my $x = shift; sub { my $y = shift; sub { my $b = shift; ($b)->($x)->($y); } } } ; # FIRST = %p.(p TRUE) $FIRST = sub { my $p = shift; ($p)->($TRUE); } ; # SECOND = %p.(p FALSE) $SECOND = sub { my $p = shift; ($p)->($FALSE); } ; ############ # # Numerals # $ZERO = ($PAIR)->($TRUE)->($TRUE); $SUCC = sub { my $n = shift; ($PAIR)->($FALSE)->($n); } ; $ONE = ($SUCC)->($ZERO); $TWO = ($SUCC)->($ONE); $IS_ZERO = sub { my $n = shift; ($FIRST)->($n); } ; $PRED = sub { my $n = shift; ($SECOND)->($n); } ; ############ # # We use this utility function only for checking to see if the # addition was done correctly # sub convert_to_perl_number { my $n = shift; my $o = 0; until ($IF->($IS_ZERO->($n))->(1)->(undef)) { $o++; $n = $PRED->($n); } $o; } ############ # # Fixed-point combinator # YM has the property that # (YM f Q) = f(YM f Q) # for any Q # # YM = %f.(%x.(%y.f (x x)))(%x.(%y.f (x x))) $YM = sub { my $f = shift; (sub { my $x = shift; sub { my $y = shift; $f->($x->($x)); }; })-> (sub { my $x = shift; sub { my $y = shift; $f->($x->($x)); }; }) } ; # Q is arbitrary, so we use something simple: %x.x $FORCE = sub { my $x = shift; $x }; ############ # # Here's the basis for our addition function # R = %g.(%mn.(IF (IS_ZERO m) # (%q.n) # (%q.(g FORCE) (PRED m) (SUCC n)) # ) FORCE # ) $R = sub { my $g = shift; sub { my $m = shift; sub { my $n = shift; $IF->($IS_ZERO->($m)) ->(sub { my $q = shift; $n} ) ->(sub { my $q = shift; ($g->($FORCE)) ->($PRED->($m)) ->($SUCC->($n)); })->($FORCE); } } } ; # This constructs the actual addition function $ADD = $YM->($R)->($FORCE); # Add 1+1 with recursive addition function $mystery_result = $ADD->($ONE)->($ONE); print "1+1 = ", convert_to_perl_number($mystery_result), "\n";