Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Yet Another Perl-to-Lambda-Calculus Translator

by withering (Scribe)
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 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).

Comment on Yet Another Perl-to-Lambda-Calculus Translator
Select or Download Code
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?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://1078890]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (11)
As of 2015-07-03 13:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (53 votes), past polls