Scheme修行16章

scheme the seasoned schemer

TheSeasonedSchemer (5) - /var/log/messages
自分も!をbangと呼ぶの知らなくて今まで「setびっくり!」とか「setびっくら!」って読んでました。
#!をshebangと呼ぶのと似た感じですね。
letでつけた名前は内側のlambdaからしか見えなかったりするので確かに属性みたいな感じ。

15章は1ステップずつ読まないと前の問いが後ろに影響することもあって(define した値にset!してたり)結局テスト書いてないです。
16章もそんな感じでがんがんset!してたのでテスト中途半端にしか書けてないです orz
本に書いてあるコードを1つずつ実行したログを編集して16.logとしてまとめました。

感想

途中まではメモ化にset!を使う話をしている気がしました。

  • まずは普通に再帰
  • 再帰の結果をメモ
  • (deep n)は(cons (deep (- n 1)) '())なので(deep (- n 1))がないか調べる
  • deepの再帰の中でもメモ化したdeepMを呼び出すようにする

その流れで第19の戒律

関数の二度の呼び出しにまたがり貴重なものを覚えておく際には(set! ...)を使用して貴重なものをおぼえておくべし。

が出てきました。
後半はletrecの仕組みとY!コンビネータ、YとY!の違いについて、といった感じがします。
YとY!の違いを理解するのにちょっと時間かかりました orz
この章も深い。

メモ

  • この章もset!ばかりで、テストどうかこう orz
    • 結局中途半端にテスト書きました。
  • deepやsweet-toothの実行結果をset!でlistに保存していく
  • 第19の戒律が出てきた。
    • 1回の呼び出し内で複数回使われる値はletで、複数回にまたがる場合はset!で覚えておく
  • deepM
    • findは値が見つかる場合に呼ばれる
      • 後ほどfindに値が見つからない場合を1行追加
    • findが呼び出せるかはあらかじめdeepMがmember?で調べる
    • この役割分担がいいなぁ
    • deepRを内側に取り込んで簡素化
  • p120まではメモ化の話かな?
  • p121、第17の戒律最終版、xの新しい値がx(自分自身?)を参照する関数のとき、が追加
  • 「架空の名前h1を通して自分自身の再帰的コピーを参照しているだけです」
  • Y!コンビネータ
    • 再帰的な部分だけ残してlengthに特徴的な部分を切り出す
    • Lに(lambda (arg) (h arg))を渡してる
      • hをそのまま渡すと(set! h (L h))になってしまう
      • それだと(L h)となり、hが先に評価される
      • 新しいhになる前のhの値そのものをLに渡してしまわないように、lambdaでくるんでる?
  • letrecはletとset!からなる式の省略らしい。letrecを使ったバージョンがY-bang
  • この流れが適用順手続き的Yコンビネータの導出、らしい

YとY!の違い

「Y!はこの形をした全てのfに対してYと同じ再帰関数を作り出す」
biz関数をYに適用した場合と、Y!に適用した場合とで結果が違う。
違いを確かめるために2つのことを試してみました。

  • biz関数の(lambda (a)の下に(print x)つけたら、Y!だとxがずっと1のままだった。
  • biz関数の(set!の下に(print x)つけるとYは毎回表示、Y!だと1回しか表示されない

よくよく定義を見ると

  • Yは(biz (lambda (arg) ((f f) arg)))の(f f)で自分自身を得る際に毎回bizを呼び出してる
  • Y!は(set! hする時、1回しか(biz (lambda (arg) (h arg)))を呼び出さない

(Y biz)には再帰に(set!の部分が含まれてるけど(Y! biz)では含まれてない、という違い。
Y!だとxは1のままなので終わらないです。

気になること

「ありがとう、Peter J.Landin」とあったので名前で検索したら
関連する項目でISWIM - Wikipediaを見つけ
「J演算子は継続を可能としたもので、Scheme の call/cc は J 演算子を簡略化したものである」
という興味深い記述を見つけました。J演算子…
他にもScheme手習いのYコンビネータの前半部分(lambda (f) (f f))のUコンビネータ、SKIコンビネータなど
そこらへんがっつり調べたり、いい資料あったら教えてもらいたいです。

JavaScript

JavaScriptも手続きオブジェクトがあって面白いですよね。
A re-introduction to JavaScript (JS tutorial) - JavaScript | MDNやってみます。
JavaScriptでクロージャを云々だとhttp://nathansjslessons.appspot.com/lesson?id=1000のレッスンも面白かったです。