Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Yet Another Perl-to-Lambda-Calculus Translator

by withering (Sexton)
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 examining the Monastery: (3)
As of 2014-09-20 04:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (152 votes), past polls