(defprimitive < < 2)
今の実装だと、<が素のschemeの#t, #f を返すので、俺実装系のTrue、Falseを返すようにしなさい。
俺実装系では真偽値として#t, #fではなくt, fを使うようにすると、こう書けます。
(definitial t #t) (definitial f #f) (defprimitive > (lambda (x y) (if (> x y) 't 'f)) 2) (defprimitive < (lambda (x y) (if (< x y) 't 'f)) 2)
あとはevaluateの中に手を入れる必要があるのですが、戻り値のt、fを一回lookupしたら#t, #fになるので、やっつけ実装ですがこうしたら動きました。
[(if) (if (lookup (evaluate (cadr e) env) env)
経営理念大事。頑張ろう
Stackを使ったshallow bindingを実装しなさいという問題。
とりあえず実装してみたのですが、練習問題にしてはヘビーでした。
https://github.com/natsutan/Lisp_in_Small_Pieces/blob/master/chap1/exer1.4.scm
1.6.2 Deep or Shallow Implementationはすっ飛ばしたので、戻って整理しなおしました。
環境が一つの連想リストで表現されているとき、変数の値を検索するコスト(lookup関数のコスト）はリストの長さに対して線形に増えます。これがdeep binidingと呼ばれる実装方法です。一方、環境とは独立して、変数単位で値を保存する方法がshallow bindingです。この場合、間接参照に基づくアクセスになるので、変数の値を検索するコストが一定になります。
なぜか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
というわけで、あまり気にせず先に進むことにします。
これだけ安いと普段買うのがばからしくなるので、そこそこにしておいて欲しい
(add-load-path "../../src/" :relative) (use npsv) ; initialize (npsv-initialize! "npsv_top") ; instancation (define inp (make-inmem-from-file "./setting/inmem.scm")) (define sinrom (make-rom-from-file "./setting/sin.scm")) (define outp (make-outmem-from-file "./setting/outmem.scm")) ; wire connection (connect inp sinrom) (connect sinrom outp) ; output (make-all-rtl "./output/rtl") (make-initialize-file inp) (make-top-testbench "./output/tb") (make-dataflow)
こんな感じでschemeを書くとVerilogを出してくれる。
データフロー図では、データ入力用のメモリと、ROM引きのsin関数、データ出力用のメモリが接続されている。データ入力用のメモリとROMのアドレスが直結できないので変換のモジュールが自動的に入る。
入力メモリに-4～+4までの値を入れて、sinを求めた結果
それっぽい。
モジュール間のプロトコルは単純で、データの有効なときはvoがH、処理が終わったらfoがHになる。これを順番に渡していくと、最後のメモリに値が書き終わったときに、最後のfoがHで終了通知になる。
後は、加算とか行列計算とかのモジュールを必要な分だけ作っていけば、複雑な計算で必要な精度の試行錯誤が楽にできそう。
extendをこのように定義した場合、lookupとupdate!を定義して、元のバージョンと比較しなさい。
(define exntend (lambda (env names values) (cons (cons names values) env)))
pass というかリナザウでやるのが辛かったので挫折。
メリットは環境の拡張が早い、デメリットは検索（と更新）が面倒。
definitial が、
(set! (env.global (cons (cons 'name valus) env.global)))
なので、definitial も変えないと整合が取れない。
(car env)で先頭を取り出して、listならextendで拡張した変数、そうじゃなかったらdefinitialで定義した変数とすればいけるが、そこを頑張る意味が無さそうなのでPASS。
作ったsin関数って、精度が悪くて使い物にならないことに気が付いた。二次の補正くらい欲しい。まあ、精度ひどくても動くところまで頑張ろう
GDG神戸のLTどうしよっかな。
