Orz日記 by Akio Morita

_ [SAD][Lisp]Y-Combinator

再帰の勉強成果

Y = With[{core = #},
  With[{procedure = #},
    core[procedure[procedure][#]&]]&[
      With[{procedure = #},
        core[procedure[procedure][#]&]]&]]&;

試してみる

fact[n_] := Which[
  n < 1,  1,
  True,   n * fact[n - 1]];

factY = Y[With[{action = #}, Which[
  # < 1,  1,
  True,   # * action[# - 1]]&]&];

Table[Print["i = ", i,
  " fact[i] = ", fact[i], " factY[i] = ", factY[i]], {i, 10}];

実行結果

i = 1 fact[i] = 1 factY[i] = 1
i = 2 fact[i] = 2 factY[i] = 2
i = 3 fact[i] = 6 factY[i] = 6
i = 4 fact[i] = 24 factY[i] = 24
i = 5 fact[i] = 120 factY[i] = 120
i = 6 fact[i] = 720 factY[i] = 720
i = 7 fact[i] = 5040 factY[i] = 5040
i = 8 fact[i] = 40320 factY[i] = 40320
i = 9 fact[i] = 362880 factY[i] = 362880
i = 10 fact[i] = 3628800 factY[i] = 3628800

正しく、再帰している。

Yを定義するときの注意

再帰コアprocedure[procedure][#]&の[#]&が重要。 procedureは、関数を引数にして再帰定義な関数を返す。 従って、procedure[procedure]の戻り値は関数なので、 一見[#]&が冗長に見えるが、SADは引数を正格評価するので pure functionにしておかないと、Yを作用させた瞬間に procedureを再帰的に展開してしまいスタックを食いつぶす。 また、下手にWith[]ブロックでシンボルに拘束すると、 その瞬間に再帰的展開を開始してしまうので要注意。

多分、すべての引数を遅延評価で評価する処理系の場合、 無くても動くような気がする。