Yet Another Perl-to-Lambda-Calculus Translator

[withering]

There is an old post about Perl (maybe perl?) and (untyped) lambda calculus http://perl.plover.com/lambda/ . However, even from the perspective of a small compiler, we may reach almost the same simplicity.

The code below is written in yapp (Parse::Yapp) grammar and should be compiled with yapp utilities:

%token CONST
%token VAR
%token IMP
%token FUN
%token LPAREN
%token RPAREN
%token APP

%nonassoc FUN
%nonassoc VAR CONST LPAREN
%left APP

%%

expr: CONST { my $litval = $_[1]; sub { $litval } }
    | VAR { my $varname = $_[1]; sub { my %args_ = @_; $args_{$varname
+} } }
    | FUN VAR IMP expr { my ($param, $term) = ($_[2], $_[4]); sub { my
+ %args = @_; sub { $args{$param} = shift; $term->(%args) } } }
    | LPAREN expr RPAREN { $_[2] }
    | expr expr %prec APP { my ($op, $arg) = ($_[1], $_[2]); sub { my 
+%args_ = @_; $op->(%args_)->($arg->(%args_)) } }
;

%%

Constants are compiled to functions with trivial return values. Variables, abstraction terms and application terms are handled with some trick, which is similar to lambda lifting (http://en.wikipedia.org/wiki/Lambda_lifting). All bound variables are saved in a hash context and passed to any term in the current scope. Thus, a bound variable is accessed by getting the value of the hash entry with its variable name as the key. Abstraction and application terms are quoted in a function to separate the passing of context and arguments.

Here is a test case, with lexical analysis utilities:

#!/usr/bin/perl

# These are only decoration. The superiors hardly understand this.

use strict;
use warnings;

use Parse::Lex;
use utlc;

my @tokens = (
    qw (
        LPAREN      [\(]
        RPAREN      [\)]
        FUN         [\\\\]
        IMP         [.]
        VAR         [A-Za-z_][A-Za-z_0-9]*
        CONST       [1-9][0-9]*
    )
);

our $lexer = Parse::Lex->new(@tokens);
$lexer->skip('\s+');

sub lexana {
    my $token = $lexer->next;
    if (not $lexer->eoi) {
        return ($token->name, $token->text);
    } else {
        return ('', undef);
    }
}

# $lexer->from(\*STDIN);
$lexer->from('\f.(\x.(f (\y.x x y))) (\x.(f (\y.x x y)))');

my $parser = utlc->new();
my $expr = $parser->YYParse(yylex => \&lexana);

#print $expr->(), "\n";

# \f.\x.(=0 x) 1 (* x (f (- x 1)))
sub fac {
    my $f = shift;
    sub {
        my $x = shift;
        ($x) ? ($x * $f->($x - 1)) : (1)
    }
}

# \f.(\x.(f (\y.x x y))) (\x.(f (\y.x x y)))
print $expr->()->(\&fac)->(5), "\n";

The test is a factorial function, implemented by using a typical call-by-value Y combinator (for references on Y combinator, see http://en.wikipedia.org/wiki/Fixed-point_combinator#Strict_fixed_point_combinator).

[zentara]

Not to be obtuse, but this looks like a great way to obfuscate. :-) I think you could present this at a Perl conference, and everyone would just stand in awe, nobody admitting that they didn't understand what the f*ck this useful for, or even how the code works. :-)

Would you care to give an explanation why this lambda calculator is a useful tool?

[withering]

Well I just think it's interesting... Just like what the author of Perl Contains the Lambda-Calculus. Actually I'm working on CPS transformation for untyped lambda calculus in Perl and these pieces of code are by-products. Though they seem to fail to please those who are not interested in functional programming...

Thanks for the reply :D