名づけのない再帰 fixed-point combinator

p.65 Types and Programming Languages より。

afact は、引数に階乗関数を渡されたとき階乗関数になる関数。
つまり、階乗関数に適用すると階乗関数が帰ってくる関数。

#! /usr/bin/env perl
use strict;
use warnings;
use integer;
my $afact = sub { my $f = shift;
                  sub { my $n = shift; print "*$n\n";
                        $n == 0 ? 1 : $n * $f->($n - 1); } };
# afact = L[f]. L[n]. n==0 ? 1 : n * f (n-1)

my $fix = sub { my $f = shift;
                my $f1 = sub { my $x = shift;
                               $f->( sub { my $y = shift;
                                           $x->( $x )->( $y );  } ) };
                $f1->($f1); };
# fix = L[f]. f1 f1   where f1 = L[x]. f ( L[y]. x x y )

my $fact = $fix->($afact);
# fact = fix afact
#   -> f1 f1  where f1 = L[x]. afact( L[y]. x x y )
#   -> afact( L[y]. f1 f1 y )    where f1 = L[x]. afact( L[y]. x x y )
#   <-*- afact( L[y]. fact y ) = afact( fact )
print $fact->(4), "\n";

上記のコードでも名前を使ってはいるが、
どの名前も、実体と置き換えて消去できるので、
再帰に使ってるわけではない。
# 再帰に使う名前は、置き換えを無限に続けられる

消去すると、こうなる。

print 
    sub { my $f = shift;
  my $f1 = sub { my $x = shift;
                 $f->( sub { my $y = shift;
                             $x->( $x )->( $y );  } ) };
  $f1->($f1); } ->
    (
     sub { my $f = shift;
   sub { my $n = shift; print "*$n\n";
         $n == 0 ? 1 : $n * $f->($n - 1); } }
    )->(4), "\n";

再帰を含む処理を1文で書けました。

$f1 も消せるけど、あまりに可読性が低くなるので、消さずにおいた。

sub { my $x = shift;

は、lambda x のこと。
これは名前にカウントしないことにする。