=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";
}