2011年8月28日日曜日

Scheme修行12章



学園祭の準備をしつつ12章を読みました。学園祭が無事終了したのでブログのエントリをあげます。

11章では必要があれば一つ前の要素や今までの加算の結果や逆順のリストなど付加的な引数を渡す、第11の戒律を学びました。

JavaScriptのreduce - MDNと似た感じの印象を受けました。

12章ではletrecについて。

再帰する時に変化しない引数をletrecを使って除く方法、第12の戒律を学びます。

この章の名前は「避難しましょう」です。letrecのもう1つの使い方として、補助関数を守るための第13の戒律が出てきます。




メモなど




  • multiremberのYコンビネータを使った定義では一番外側のlambdaでaが束縛されるのでYコンビネータに渡す関数の中でaを使う事が出来る。

  • p18の動かないmrの定義


    • mrの中のaは束縛されていない自由変数

    • Schemeは静的スコープなのでmrが定義された時にaが値に束縛されてないとunbound variableとエラーが出て動かない。

    • mrを呼び出しているmultiremberの中の変数aはmrの定義時にはスコープの外、mrからはaが見えていない。

    • 試しにElispで書いたら動いた。Elispは動的スコープなので呼び出し元の環境の変数aを参照するため動く。

(defun mr (lat)
(cond ((null lat) '())
((eq a (car lat)) (mr (cdr lat)))
(t (cons (car lat) (mr (cdr lat))))))

(defun multirember (a lat)
(mr lat))

(multirember 'pie '(apple custard pie linzer pie torte))




  • p19にてα変換、α同値の話が出てくる。

  • p20 「再起関数」typo発見

  • p20 「(letrec ...)の名前づけ部分で定義された関数は囲まれている全ての(lambda ...)式の全ての引数を知っています。」


    • (letrec ( (mr ...) ) mr)はmrという名前の関数を定義して、その再帰関数を返している。

    • letrec中のmrは外側のlambdaの引数aを知っている。

  • letrecを使ったmultirember


    • mr pieを定義してlatに用いたように見える

    • p21下線のついたdefineは実際には存在しないけれどそのように想像することで理解の助けになる

    • mr pieはdefineを使って定義した関数と違って外側からは見えない!

  • 第12の戒律「再帰を適用している間に変化せぬ引数を除くには(letrec ...)を用いるべし。」

  • p23~p26でletrecを使ってmultirember-fを定義している。letrecの使い方は同じ。関数を定義して返す。

  • member?やunionなどを第12の戒律に従い書き直し。


    • member?の中のyes?で引数の名前がlなのはlatと被らないように?それとも短い名前がよかったから?

  • 関数を守る


    • unionの中のUは、unionが知っている事はすべて知っている。

    • unionの中にmember?の定義は出てこない

    • unionの動作はmember?に依存してる。member?の引数の順番が変わったら動かなくなってしまう。

    • letrecはかっこで囲んだ関数定義を複数おける。(condの条件みたいに)

    • そこで、unionの内側のletrecでmember?を定義する

  • 第13の戒律「関数を隠し、守るには、(letrec ...)を用いるべし。」


    • 補助関数はその関数にとって特別な値に使う。だから補助関数の定義が変わって変な値を返さないようにその場に隠す。

感想


letrecと(define (hoge) (define (fuga) ...) ...)

SICPでは補助関数はdefineの中でdefineを書いてた気がします。

defineの中にdefineだとどうなるんだろう、気になったので調べてみると

letrec - karetta.jp

letrecを使うか、defineの中にdefineを書くかは好みの問題です。

本当に好みの問題なのか気になったのでR5RSを読んでみると

Revised(5) Report on the Algorithmic Language Scheme

内部での定義を含む<ボディ>は、完全に等価なletrec式に必ず変換できる。例えば上記のlet式は次の式に等価である。

だそうで、やっぱり好みの問題らしい。

印象に残った部分

p28の

Q.

そのとおり。AはUとまったく同じ名前です。
どんな名前でもかまいませんよね。

A.

かまいませんが、定義を楽しみたい人にとって名前の選び方は大切です。

と書いてあったのがちょっと印象的。やっぱり関数の名前付けは大事。

Aじゃよく分からなくてもUだったらUnionのUだなって分かるので。

テスト

今まで

$ gosh test11.scm

とやってたのを

$ for i in `ls test*.scm`; do gosh $i; done

とするようにした。今回11.scmの中身も書き換えたのでいちいちgosh test11.scm、gosh test12.scmと2回やるのが面倒だったので。

シェルスクリプトも覚えないと orz

少し残った疑問と次章への期待

関数をどこらへんまで守るべきなんだろうか。

他にもmember?を使う関数があったらその関数も内部で同じmember?を持つので無駄な気もするんだけど。

member?が引数を決まった順序で取るという仮定が崩れないなら使ってもいいのかな…

とりあえず



  • 関数が他の関数の定義に依存すると、依存している関数の定義を変えたとき動かなくなってしまう

  • 動かなくなると困る関数はletrecで守る。隠す。

というのをしっかり頭に置きながら残りの章を読んで行きたいと思います。

どうやら次章でついに継続が出て来る! call/cc! call/cc!

楽しみです :)




0 件のコメント:

コメントを投稿