kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

Reasoned Schemer (44) 10章 walkまで

10章は処理系を書く話っぽいので

ここからひさしぶりに写経モードで
そういえば、ここで書く処理系はminiKanrenと呼ばれるものらしい
ファイル名つけようと思った時にふと名前が気になった

変数を定義

(define (var name) (vector name))
(define (var? x) (vector? x))

使ってみる

> (define u (var 'u))
> u
#(u)
> (var? u)
#t

値を'uにしてるのは特に意味はないらしい
vectorとしての使い方もあまりしなさそうだけどちらっと調べておいた
困ったらちゃんと調べる

``(,z . a)は変数zaとの association
用語の訳は考えない方向で
carが変数ならcdrは変数か値(0個以上の変数を含む)、って書いてあるけど
carが変数じゃないこともあるってことなのかな

associationのリストは substitution
associationのcdrが変数の場合、carの変数とcdrの変数がfuseされていることを表す

からっぽのsubstitution

(define empty-s '())

substitutionにはcdrが同じのassociationが含まれていてはいけない

walk
substitution中のassociationをたどれるだけたどった先のcdrを返す

(define (walk v s)
  (let ((a (and (var? v) (assv v s))))
    (cond
      ((pair? a) (walk (cdr a) s))
      (else v))))

(assv v s)sの中からcarがvであるものを探す関数
なければ#f

> (walk z `((,z . a) (,x . ,w) (,y . ,z)))
a
> (walk y `((,z . a) (,x . ,w) (,y . ,z)))
a
> (walk x `((,z . a) (,x . ,w) (,y . ,z)))
#(w)
> (walk x `((,x . ,y) (,v . ,x) (,w . ,x)))
#(y)
> (walk v `((,x . ,y) (,v . ,x) (,w . ,x)))
#(y)
> (walk w `((,x . ,y) (,v . ,x) (,w . ,x)))
#(y)
> (walk w `((,x . b) (,z . ,y) (,w . (,x e ,z))))
(#(x) e #(z))

変数の値に意味はない、と言っても
実行したときに表示される値でどの変数かわかるのはありがたいな

たどれるだけたどった先と言っても、
変数を含むリスト内の変数までは追いかけない

(walk v s)が変数を返したときはvがまだfreshだということを示す

ぼんやりとは使われそうなイメージがある
まだ双方向にはなってないな