ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

Lisp in Small Pieces Exercise 1.4 shallow binding

lisp

Stackを使ったshallow bindingを実装しなさいという問題。
とりあえず実装してみたのですが、練習問題にしてはヘビーでした。

https://github.com/natsutan/Lisp_in_Small_Pieces/blob/master/chap1/exer1.4.scm

shallow bindingとは

1.6.2 Deep or Shallow Implementationはすっ飛ばしたので、戻って整理しなおしました。

環境が一つの連想リストで表現されているとき、変数の値を検索するコスト(lookup関数のコスト）はリストの長さに対して線形に増えます。これがdeep binidingと呼ばれる実装方法です。一方、環境とは独立して、変数単位で値を保存する方法がshallow bindingです。この場合、間接参照に基づくアクセスになるので、変数の値を検索するコストが一定になります。

hashの操作

なぜかGaucheには、この練習問題を解くためにあるような関数hash-table-push!　hash-table-pop! があります。まずは使い方の整理をします。
変数を格納するテーブルを定義して、xを5、yを10に代入します。

(define table (make-hash-table))
(hash-table-push! table 'x 5)
(hash-table-push! table 'y 10)

ここでxの値を取り出してみると、5だけが入ったリストが帰ってきます。

(ref table 'x)
gosh> (5)

この状態でxに４を代入すると、refを使って(4 5)というリストが帰ってきます。carを取ると最新のxの値が取得できます。

(hash-table-push! table 'x 4)
(ref table 'x)
gosh> (4 5)

再帰っぽくxの値を小さくしていきます。

(hash-table-push! table 'x 3)
(hash-table-push! table 'x 2)
(hash-table-push! table 'x 1)
(ref table 'x)
gosh> (1 2 3 4 5)

hash-table-pop!を使うと、リストの先頭から値を取り出し削除します。

(hash-table-pop! table 'x)
gosh> 1
(ref table 'x)
gosh> (2 3 4 5)

後３回値を取り出します。

(hash-table-pop! table 'x)
(hash-table-pop! table 'x)
(hash-table-pop! table 'x)
(ref table 'x)
gosh> (5)

push、popでちょうどスタックになっています。これを使って shallow binding を実装しました。

ソース説明

まずは変数を格納するハッシュテーブルの定義

(define *variable-table* (make-hash-table))

evaluateの中でシンボルを評価するところは、refとcarで値を取り出せます。アクセスのコストは一定に見えますが、ハッシュの検索(ref)が入っています。carのコストは一定なので、変数の参照はハッシュの検索コストに依存します。ハッシュの検索コストについては、この本では説明が無かったです。

  [(symbol? e) (car (ref *variable-table* e))]

変数の更新(set!)は、今の値をpopして、新しい値のpushでOKです。

  [(set!) (let ([id (cadr e)]
                        [value (evaluate (caddr e) env)])
                    (hash-table-pop! *variable-table* id)
                    (hash-table-push! *variable-table* id value)
                    value)]

関数を作るところがこうなりました。
s.make-functionが作っているclosureの中身を見ると、eprogn body '() が関数を呼び出しているところです。関数呼び出しの前に、引数をhash-table-push!を使ってpushしていき、関数呼出し後に、hash-table-pop!で引数の値を元に戻していきます。

(define (s.make-function variables body env)
  (lambda (values)
    (map (lambda (var val) (hash-table-push! *variable-table* var val)) variables values)
    (let ((result (eprogn body '())))
      (dolist (val variables)
              (hash-table-pop! *variable-table* val))
      result)))

実行結果

(chap1-scheme-bat '((+ 3 5)))
YUKI.N> 8

 (chap1-scheme-bat
  '((set! pow (lambda (x) (* x x)))
   (pow 5)))
YUKI.N> #<closure (s.make-function s.make-function)>
YUKI.N> 25

 (chap1-scheme-bat
  '((set! fact
          (lambda (x)
            (if (= x 1)
                1
                (* (fact (- x 1)) x))))
    (fact 5)))

YUKI.N> #<closure (s.make-function s.make-function)>
YUKI.N> 120

それっぽくは動いてます。

メリット、デメリット

Deep bindingのほうが環境の扱いが楽です。例えば環境を切り替えないといけない場合でも、evaluateの引数を変えるだけで対応できます。
shallow bindingは変数の検索が速そうに見えるけども、一概にそうとも言えない気がします。

Deep bindingの場合でも、関数の引数で束縛される変数はリストの先頭に来るので、実際の検索時間はそれほど遅くはならないです。。リストの後ろのほうの変数を参照しにいく時に検索時間が線形で効いてくるデメリットが発生します。shallow bindingの場合は、関数の呼び出しと復帰時にハッシュテーブルの更新が入るので、関数呼び出しのたびにコストがかかります。少なくとも、おもちゃの処理系ではshallow bindingを使うメリットは感じられませんでした。

実用的なアプリケーションの場合はどうなるのかは気になります。

まとめ

1.6.2 Deep or Shallow Implementationの最後から

Remember, finally, that deep binding and shallow binding are merely implementation techniques that have nothing to do with the semantics of binding

というわけで、あまり気にせず先に進むことにします。