Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Yet Another Perl-to-Lambda-Calculus Translator

by withering (Monk)
on Mar 19, 2014 at 03:19 UTC ( #1078890=CUFP: print w/replies, xml ) Need Help??

There is an old post about Perl (maybe perl?) and (untyped) lambda calculus . 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 ( 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

Replies are listed 'Best First'.
Re: Yet Another Perl-to-Lambda-Calculus Translator
by zentara (Archbishop) on Mar 19, 2014 at 11:01 UTC
    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?

    I'm not really a human, but I play one on earth.
    Old Perl Programmer Haiku ................... flash japh

      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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://1078890]
Front-paged by Arunbear
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (6)
As of 2017-03-29 20:00 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (353 votes). Check out past polls.