, immediately. But if instead we try to evaluate the argument first, we don't get anywhere. A Perl analogue of the same thing would be something like this: sub loop_forever { while (1) { 1; } } sub return_Q { my $arg = shift; return "Q" } In Perl, the expression return_Q(loop_forever()) does indeed loop forever, even though Cnever uses its argument, because Perl has I semantics: This means that a function's arguments are always fully evaluated before the function is called. The other option is I , in which the argument is passed to the function I being evaluated, and is only evaluated later if it is required. You might think that since call-by-value is workable for Perl, it will work in practice in Lambda Calculus also. But you'd be wrong: call by value I always work in Perl; there are some essential places where Perl (and every other language) uses call by name instead. To see why, suppose you were to try to write your own function to replace Perl's C construction: sub my_if { my ($condition, $then_part, $else_part) = @_; if ($condition) { $then_part } else { $else_part } } Then you'd write $max = my_if($x > $y, $x, $y); and in fact this works, for this example. But it doesn't work in general: sub factorial { my $n = shift; return my_if($n == 0, 1, $n*factorial($n-1)); } =for MJD A better example here is to use something like my_if(..., 1, die); This function loops forever on I input. When I =0, it's important that we I make another recursive call---but this function I try to evaluate C<0*factorial(-1)> and pass this result to C ; it doesn't matter that C would eventually have chosen the other branch, which was 1; with call by value we have to compute both branches I we can ask which one we want. And that defeats the whole point of C which is to compute one or the other, but not both. =head Delayed Action What we'd like to do is somehow express C in a way that delays the evaluation of I and I until after the C has selected one or the other of them. As we saw in my lazy streams article back in TPJ #7, the simplest way to delay evaluation is to wrap up C<$x> and C<$y> into functions: %q.x does I evaluate C , but rather creates a function that will evaluate it sometime in the future, when we apply the function to an argument; the argument is ignored, and out pops C . Instead of writing C<(IF b x y)> this way: (%b.(%x.(%y.b x y))) b x y as we have been doing, we'll write it this way: (%b.(%x.(%y.b x y))) b (%q.x) (%q.y) q The C part will yield either C<%q.x> or C<%q.y>, and then when we apply that to the dummy argument C , we'll have our result. To see how this works, let's suppose Cis C: (%b.(%x.(%y.b x y))) FALSE (%q.x) (%q.y) q (%x.(%y.FALSE x y)) (%q.x) (%q.y) q (%y.FALSE (%q.x) y) (%q.y) q (FALSE (%q.x) (%q.y)) q ((%x.(%y.y)) (%q.x) (%q.y)) q ( (%y.y) (%q.y)) q ( (%q.y)) q y =head1 Punch Line OK, now we're finally ready for the punch line of the entire article. By now I bet you're expecting me to write a Perl program that evaluates Lambda Calculus expressions. Nope, wrong. Here's the punch line: Perl already has that feature built-in. If you wanted to investigate Turing machines, you'd have to start by writing a simulator; then you'd have to write Turing machine programs to perform functions like addition and multiplication, and that soon becomes impossibly difficult. But to investigate Lambda Calculus, you don't need a simulator. Lambda calculus isn't a machine; it's more like a programming language. In fact, it I a programming language. It's programming language with a syntax for defining functions and invoking them, and nothing else. The language is so simple that you can view it as a subset of Perl. =head2 Lambda-expressions in Perl If we want to write C<%x.B>, we'll just say sub { my $x = shift; B } C<%x.B> means to create a function, which, when applied to an argument I, substitutes it into C in place of C, and yields the result. And that's exactly what C _{ does do. In Lambda Calculus, C<(p q)> means to apply a function C to an argument C; Perl has that too. We'll just say: $p->($q) That's all we need; we can translate our Lambda Calculus expressions directly into Perl and have the Perl interpreter evaluate them immediately. Only the syntax is different, and not even very different at that. So, for example, the straightforward Perl translation of IF = %b.(%x.(%y.(b x) y)) is: $IF = sub { my $b = shift; sub { my $x = shift; sub { my $y = shift; $b->($x)->($y); } } } (Provided you also use the trick above to delay evaluation of C and C.) Here are a few other basic definitions: # TRUE = %x.(%y.x) $TRUE = sub { my $x = shift; sub { my $y = shift; $x; } } # FALSE = %x.(%y.y) $FALSE = sub { my $x = shift; sub { my $y = shift; $y; } } Let's try that out to see that it works right: print $IF->($TRUE)->("then")->("else"); (prints "then") print $IF->($FALSE)->("then")->("else"); (prints "else") We didn't need to use the delayed-evaluation trick here because it didn't matter that the strings C and C were evaluated before the C was called. Here are some other definitions, translated into Perl directly from the Lambda Calculus: # PAIR = %a.(%b.(%f.f a b)) $PAIR = sub { my $a = shift; sub { my $b = shift; sub { my $f = shift; $f->($a)->($b); } } } ; # FIRST = %p.(p TRUE) $FIRST = sub { my $p = shift; $p->($TRUE); } ; # SECOND = %p.(p FALSE) $SECOND = sub { my $p = shift; $p->($FALSE); } ; # ZERO = PAIR TRUE TRUE $ZERO = $PAIR->($TRUE)->($TRUE); # IS_ZERO = %n.(FIRST n) $IS_ZERO = sub { my $n = shift; $FIRST->($n); } ; =head2 Debugging Lambda Calculus Programs in Perl Let's check to make sure that this works: print $IS_ZERO->($ZERO); # prints CODE(0x81179cc) Oops! This anonymous function that we got might be the C function C<%x(%y.x)>, or it might be something else, and there's no simple way to peek inside to see. Let's define a utility function that analyzes a Lambda Calculus boolean and tells us which it is: sub print_bool { my $f = shift; print $IF->($f)->("It's true")->("It's false"); } print_bool($IS_ZERO->($ZERO)); # prints "It's true" Now we go on with the arithmetic: # SUCC = %n.(PAIR FALSE n) $SUCC = sub { my $n = shift; $PAIR->($FALSE)->($n); } ; # ONE = SUCC ZERO $ONE = $SUCC->($ZERO); # TWO = SUCC ONE $TWO = $SUCC->($ONE); print_bool($IS_ZERO->($ONE)); # prints "It's false" # PRED = %n.(SECOND n) $PRED = sub { my $n = shift; $SECOND->($n); } ; Here's a utility function that converts Lambda Calculus numbers into Perl numbers: sub convert_to_perl_number { my $n = shift; return "OOPS($n)" unless ref $n eq 'CODE'; my $o = 0; until ($IF->($IS_ZERO->($n))->(1)->(undef)) { $o++; $n = $PRED->($n); } $o; } sub print_number { print "If this is a number, its value is ", convert_to_perl_number(shift()), "\n" ; } print_number($SUCC->($TWO)); # prints: "If this is a number, its value is 2." The peculiar C<($IF-E($IS_ZERO-E($n))-E(1)-E(undef))> expression tests a Lambda Calculus number with C<$IS_ZERO>, then converts the Lambda Calculus-style boolean result into a Perl-style boolean value, either 1 or C, for use in the C loop. =head2 Lambda Arithmetic in Perl Now we're ready to try addition. Addition is recursive, and we need a version of the C operator that will work under a call-by-value semantics. The existing one won't, because it wants to make the recursive call right away; we need to delay this. We can solve this problem the same way we did for C: Instead of Y = %f.((%x.f (x x))(%x.f (x x))) we'll use YM = %f.(%x.(%y.f (x x)))(%x.(%y.f (x x))) This C operator is a little different from the C operator. Instead of generating the fixed point immediately, as C does: Y f = f (Y f) It delays the computation, and performs it on demand: YM f = %y.f (YM f) Then when you actually want to make the recursive call to C, you apply the result to some dummy argument C, which is thrown away. $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)); }; }) } ; =head2 Forcing a Delayed Computation For documentation purposes, we'll name the dummy argument C. It doesn't matter what it is, so let's use the simplest thing we can: C<%x.x>. $FORCE = sub { my $x = shift; $x }; Now here's our addition function again, with delays and forces to make it work with call-by-value: # R = %g.(%m.(%n.( # (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); } } } ; If we apply C to C, the result is a recursive addition function; we have to force the result because C always delays delivering its result: $ADD = $YM->($R)->($FORCE); =head2 We Win! Now let's give it a try: print_number($ADD->($ONE)->($ONE)); # prints: "This number is actually 2." You are now invited to execute the program in C and verify that this is indeed what it prints out. }