Orz日記 by Akio Morita

_ [雑記]後は飛行機が飛べば...

日本に帰れます。

荷物の重量が予想よりかなり重く表示されたので焦りましたが、 オーバーウェイトチャージの要求もなくチェックインは無事終了。 今日は、すごくルーズだった気がする。

_ [KEKB]久しぶりにKEKBの立ち上げに参加

パネルのバグ取りというか、データベースの命名ルール違反への 対応作業をする

_ [雑記]SICP入手

秋葉原にて、Structure and Interpretation of Computer Programsを入手

これで、ON LISPと合わせて、LISP系な関数言語の実装と実践が系統的に学べる...

_ [FreeBSD]Emacs 22.3へ移行

ports/editors/emacsが 22.3になったので、emacsを入れ替えて 3rd partyのelisp packageを再コンパイル

_ [SAD]MacOSX 10.5 for Intelが変？

SFMTのinit_by_array()がなぜか呼び出されない...

MacOSX 10.4 for Intelだと問題ない＆シンボル名を変更すると動くので、 シンボルの衝突が原因か？

一体、実行時に何が起こっている...

_ [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[]ブロックでシンボルに拘束すると、 その瞬間に再帰的展開を開始してしまうので要注意。

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

_ [SAD][Lisp]複数の引数を伴う再帰関数を定義するY-Combinator

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

生成した再帰関数を包むpure functionで、##を 受けとるようにしただけ

アキュムレータを使った再帰関数の例

リストの平均値を求める

avgY = Y[With[{action = #}, Which[
  Length[{##}] < 3, action[#1, 0, 0],
  Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + First[#1]],
  True,             #3 / #2]&]&];

リストの標準偏差を求める

sigmaY = Y[With[{action = #}, Which[
  Length[{##}] < 4, action[#1, 0, 0,
    Y[With[{action = #}, Which[
      Length[{##}] < 3, action[#1, 0, 0],
      Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + First[#1]],
      True,         #3 / #2]&]&][#1]],
  Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + (First[#1] - #4)^2, #4],
  True,                   Sqrt[#3 / (#2 - 1)]]&]&];

最初に平均値を求める部分に avgY相当の無名関数を使っている

_ [SAD][Lisp]factYの末尾再帰への変形

単純な再帰を Y-Combinatorで書いた基本形

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

アキュムレータを導入して、末尾再帰化

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

最初の呼び出し(アキュムレータの初期化)を再帰の外に出した移す

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

_ [FreeBSD]7.1-RELEASEは大丈夫なのかな？

GEOMで mirrorしたディスクを journalしてnewfs -Jしたら カーネルパニックした。

これって、結構致命的な気がするのだが...