################################################################
        #
        # Lambda Calculus demonstration in Perl
        # 4 April 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)
        # 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";