Y Combinator

Y コンビネータを思い出すために、いくつかの言語で実際に作ってみます。
このトピックは不定期更新で、一番最後のプログラムが最新の投稿となっています。また、どの言語でYコンビネータを作成するかはその時の思いつきで決めています。以下で取り上げている言語は
  • Scheme
  • Common Lisp
  • Ocaml (断念)
  • Haskell
  • Erlang
  • Javascript
  • Ruby
  • Python
  • PHP
  • Smalltalk
  • Perl
  • Go (中断、調査中)
  • Lua
  • Io (断念)
  • C
今後計画している言語は、C++, Java, Vala, Scalaです。
それでは、本題に入っていきます。
Scheme
(define Y
  (lambda (f)
    ((lambda (proc) (f (lambda (arg) ((proc proc) arg))))
      (lambda (proc) (f (lambda (arg) ((proc proc) arg)))))))
(define fact
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))
(print ((Y fact) 5))
Common Lisp
(defun Y (f)
  ((lambda (proc)
    (funcall f (lambda (arg) (funcall (funcall proc proc) arg))))
  (function
    (lambda (proc)
      (funcall f (lambda (arg) (funcall (funcall proc proc) arg)))))))
(defun fact (f)
  (function
    (lambda (n)
      (if (zerop n)
        1
        (* n (funcall f (1- n )))))))
(print (funcall (Y 'fact) 5))
Scheme版と結構違ったものになってしまいました。入門Common LispではもっとシンプルなY combinatorの例が掲載されています。ただし、factを定義するために、Yを使用しています。それをSchemeで書くと
(define Y
  (lambda (f n) ((f f) n)))
(define fact
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (Y f (- n 1)))))))
(print (Y fact 5))
OCaml
次はOCamlの場合 ... と思ったのですが、
Error: This expression has type 'a -> 'b
       but an expression was expected of type 'a
に悩まされて、どうにも作れませんでした。調べてみると、
http://diaspar-journal.blogspot.com/2009/04/8-y.html#lang-ocaml
http://d.hatena.ne.jp/camlspotter/20100520
どうもOCaml では Yは作れないようです。(Zを勉強して、combinatorをいくつか作ってみるという方向性にかえるべきか...いや、他の不動点コンビネータについては別の記事にしよう)
Haskell
そして、Haskellでは、いや「でも」型が決まらないので定義できないようです。
http://blog.livedoor.jp/dankogai/archives/50463152.html
二つ前のURLでも触れられています。
newtype Rec a = In { out :: Rec a -> a}

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

fact :: (Integer -> Integer) -> Integer -> Integer
fact = \f -> (\n -> if n==1 then 1 else (n * (f (n-1))))
wikipediaの受け売りですが、再帰型にレコード構文を使って簡略化している所がニクいです。
Erlang
今度は、Erlangで挑戦してみます。
#!/usr/bin/env escript
y(F) -> (fun(Proc) -> F(fun(Arg)-> (Proc(Proc))(Arg) end) end)
        (fun(Proc) -> F(fun(Arg)-> (Proc(Proc))(Arg) end) end).
main([]) -> Fact = fun(F) -> (fun(N)->(if
                    N==0 -> 1;
                    true -> (N*F(N-1))
                  end)end)end,
            io:format("~w~n",[(y(Fact))(5)]).
となります。yに階乗の本体部分を渡さなければならないため、factではなくFactとして変数になるよう定義しています。
JavaScript
JavaScriptの場合は簡単に関数そのものを渡すことができるので、
var y = function(f) {
  return function (proc) { return f(function(arg){return (proc(proc))(arg);}); }
        (function (proc) { return f(function(arg){return (proc(proc))(arg);}); });
};
var fact = function(f) { return function(n) { return n==0 ? 1 : n*f(n-1); }; };
document.writeln((y(fact))(5));
と、Schemeのように簡単に作成することができます。
Ruby
関数の適用にはcallメソッドを使用します。
def y
  lambda {|f|
    lambda {|proc| f.call(lambda{|arg| proc.call(proc).call(arg)})}.call(
      lambda {|proc| f.call(lambda{|arg| proc.call(proc).call(arg)})}) }
end

def fact
  lambda {|f| lambda {|n| n==1 ? 1 : n*f.call(n-1)} }
end

puts y.call(fact).call(5)
Python
pythonのlambdaは一行で書かなければいけないため、yの定義ではバックスラッシを使っています。
y    = lambda f: \
        (lambda proc: f(lambda arg: (proc(proc))(arg))) \
        (lambda proc: f(lambda arg: (proc(proc))(arg)))
fact = lambda f: lambda n: 1 if n==0 else n*f(n-1)
print((y(fact))(5))
PHP
PHPでは、これまでのYに比べてやや複雑になっています。
$y = function($f) {
  $g = function($proc) use($f) {
    $h = function($arg) use($proc) {
      $pp = $proc($proc);
      return $pp($arg);
    };
    return $f($h);
  };
  return $g($g);
};
$fact = function($f) {
  return function($n) use($f) {
    return $n == 0 ? 1 : $n*$f($n-1);
  };
};
$yfact = $y($fact);
echo $yfact(5);
複雑になった理由は2つあります。まず、関数を連続して適用する際に ($y($fact))(5) のような記述ができません。次に、無名関数の外にある変数を使用する場合は use で宣言しなければなりません。このためこれまでより変数が増えたり、無名関数の定義が変わったりしていますが、その他はこれまでと同じです。
Smalltalk
GNU Smalltalk v3.1なら
|y fact|
y := [:f| [:proc| f value: [:arg| (proc value: proc) value: arg]]
    value: [:proc| f value: [:arg| (proc value: proc) value: arg]]].
fact := [:f| [:n| n=0 ifTrue: [1] ifFalse: [n*(f value: (n-1))] ] ].
((y value: fact) value: 5) printNl.
SqueakやPharoなどで実行する場合は、最後のprintNlを削除してから「全体を選択→右クリック→print it」の流れで実行してください。
まだPharoのチュートリアル(ProfStef go)を20ページほどしか読んでいませんが、非常に簡単に作成できて驚いています。注意すべき点は 3 つで、yやfactは事前に宣言する必要があること、関数の適用ではvalue:でメッセージを送ること、ifTrue:やifFalse:にはブロックを渡すこととなっています。
y value: fact value: 5
と書けるような気もしますが、これではyにfactと5の二つの引数が渡されてしまいます。
Perl
Perlでは引数の受け取り方が独特です。shiftが無ければ、一文で書けそうなんですが。
my $y = sub {
  my $f = shift;
  sub {
    my $proc = shift;
    $f->( sub{ my $arg=shift; $proc->($proc)->($arg); });
  }->( sub {
      my $proc = shift;
      $f->( sub{ my $arg=shift; $proc->($proc)->($arg); });
    });
};

my $fact = sub {
  my $f = shift;
  sub {
    my $n = shift;
    $n==0 ? 1 : $n* $f->($n-1);
  };
};

print($y->($fact)->(5),"\n");
関数の適用では"->()"として引数を渡しています。連続して適用する場合に"->()->()"と書けるのは、どことなくかっこいいきがします。
Go
出来ない気がしてきたので、中途の状態で保留にします。
y := func(f func) func{
  return func(proc func) func{return f(func(arg){return (proc(proc))(arg)}}
          (func(proc) {return f(func(arg){return (proc(proc))(arg)}})
}
fact := func(f func(int) int) func{
  return func(n int) int{ if (n==0) { return 1 } else { return n*f(n-1) } }
}

fmt.Printf(strconv.Itoa((y(fact))(5))+"\n");
関数定義で引数も宣言しておく必要があるのですが、正しく宣言するためには
a := func(i int) int{return i+1}
fmt.Printf(strconv.Itoa(a(10))+"\n")
b := func(i func(int) int) int{return i(1)}
fmt.Printf(strconv.Itoa(b(func(i int) int{return i+3}))+"\n")
のように突っ込んだ記述をしなければなりません。これを回避できないか調べた上でまたチャレンジします。
ちなみに、"func hoge() {}"のように関数を定義しても、引数として渡すことができるようです。
本題とは関係有りませんが、意外にも戸惑ったのはリンカを自分で実行しなければならないことです。コンパイルから実行までは以下のようになります。
$ 6g hello.go && 6l hello.6 && ./6.out
Lua
LuaはJavascriptに似た感覚で作成することができました。
y = function(f)
      return ((function(proc)
        return f( function(arg) return((proc(proc))(arg)) end)
      end)(function(proc)
        return f( function(arg) return((proc(proc))(arg)) end)
      end))
end
fact = function(f)
  return function(n)
    if n==0 then
      return 1
    else
      return n*f(n-1)
    end
  end
end
print((y(fact))(5))
luaでの注意点は改行の位置です。同じような、以下のコードはエラーになってしまいます。
y = function(f)
  return (
  (function(proc) return f( function(arg) return((proc(proc))(arg)) end) end)
  (function(proc) return f( function(arg) return((proc(proc))(arg)) end) end))
end
Io
blockで作成しようと試みましたが、どうも正しく動いてくれません。
ycomb := block(f,
 (block(proc, f(block(arg, (proc(proc))(arg)))))(
  block(proc, f(block(arg, (proc(proc))(arg))))))

fact := block(f, block(n, if(n==0 , 1 , n*f(n-1))))

writeln((ycomb(fact))(5))
関数の適用を段階的に行わせてみるなど改善策を試みてみましたが、いまだに期待通りの結果が得られていません。
C
#include <stdio.h>
typedef void *(*generic)(void *p);

generic proc_fact;
generic proc_y;
generic f_func;

int lambda_n(int n)
{
  return n==0 ? 1 : n*(int)proc_fact(n-1);
}

generic fact(generic p)
{
  proc_fact = p;
  return lambda_n;
}

int lambda_arg(int arg)
{
  int (*pp)(int) = proc_y(proc_y);
  return pp(arg);
}

generic g_func(generic p)
{
  proc_y = p;
  return f_func(lambda_arg);
}

generic ycomb(generic f)
{
  f_func = f;
  return g_func(g_func);
}

int main(int argc, char *argv[])
{
  printf("%d\n",(int)((ycomb(fact))(5)));
  return 0;
}
未習得の言語で作成するために調べるべきこと
Yコンビネータを作成して階乗を計算するだけならば、知るべきことは驚くほど少なく、未習得の言語であってもすぐに作成することができます。数少ない知るべきことをまとめると、以下の3つだけになります。
  • 無名関数を作成できるか。
  • 関数の本体を関数に渡すことができるか。
  • あとは基本的な文法。
    • 演算子：掛け算はどう書くか、三項演算子はあるか
    • 条件分岐：三項演算子がない場合、終了条件をどう書くか
    • 関数： 引数の渡し方、受け取り方
参考
http://d.hatena.ne.jp/authorNari/20081130/1227977113
http://d.hatena.ne.jp/keyesberry/20090129/p1
http://blogs.msdn.com/b/madst/archive/2007/05/11/recursive-lambda-expressions.aspx
http://www.loveruby.net/ja/misc/ycombinator.htm
http://www.ibm.com/developerworks/jp/linux/library/l-highfunc/l
http://en.wikipedia.org/wiki/Anonymous_function
http://en.wikipedia.org/wiki/Closure_%28computer_science%29

コメント

コメントを投稿

このブログの人気の投稿

[Java] 母音か子音か

SRM 240 Div2 easyより 変数chrがStringで、小文字一文字だけだった時に、母音(a, i, u, e, o)か子音かを判定したい時、素直に考えて chr.equals("a") || chr.equals("i") || chr.equals("u") || chr.equals("e") || chr.equals("o") と書いていたけど、 "aiueo".indexOf(chr) >= 0 のスマートさに愕然とした。
続きを読む

git-svnでFILE was not found in commit HASH

いつものようにgit-svnで更新していたところ、以下のようなエラーに遭遇した。 $ git svn fetch FILE was not found in commit HASH (REVISION) (FILE, HASH, REVISIONは伏せ字) どうも無視しているディレクトリの中身にコミットがあったらしく、変更を適用しようとしてエラーになっている。 そのファイルを仮に、 hoge/foo.c としておく。 エラーの根本原因となっていたのは .gitignoreで、もともとは hoge と書いていたのだが、 hoge/ とスラッシュまで含めて書くのが正しかったようである。 上記の修正ができない場合でも、 $ git svn fetch --ignore-path hoge のようにオプション指定すればエラーは回避できる。
続きを読む

だらだらと

だらだらと A first look at WebAssembly performance http://www.stefankrause.net/wp/?p=405 WebAssemblyとJavaScript実装との性能比較。 結果としては、速いこともあれば遅いこともある。 一年前ははっきりと遅かった のだから進歩していると解釈できるのかな？ パフォーマンスが同等であればわざわざ手を出すほどでもないかと思いつつも、 バイナリサイズがコンパクトであることを考えると現段階でも優位性が高いといえなくもないか。
続きを読む