2011年9月25日日曜日

Scheme修行16章



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 - MDNやってみます。


JavaScriptでクロージャを云々だとWhat’s a Closure?のレッスンも面白かったです。





0 件のコメント:

コメントを投稿