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?のレッスンも面白かったです。