EoPL reading (25) 1.3.1 Free and Bound Variables
Exercise-1.20
例えば y が occurs free な lambda 式は以下。
((lambda (x) x) y)
ただ上記の式の値は y の値に依存している。occurs free な変数の値に依存しない、となると、どんな式書けばええんかな。これはふざけすぎ?
((lambda (x) x) (if (symbol? y) 1 1))
y が何でも 1 が戻る。
Exercise-1.21
これはこんなカンジ?
((lambda (x) x) x)
これを occurs-free? とか occurs-bound? に吸わせたらどうなるんでしょ。まず occurs-free? だと #t が戻るはず。(lambda (x) x) と x のどっちかが occurs-free? だと、という判断基準なので。
test (occurs-free? 'x '((lambda (x) x) x)) should return #t, expects #t ==> ok
次、occurs-bound? は、というとこれも or なので #t ですな。
test (occurs-bound? 'x '((lambda (x) x) x)) should return #t, expects #t ==> ok
ビンゴ。ut なツールってこういった使い方ができるのが良いですよね。
Exercise-1.22
例示されている手続きは
- lambda 式の引数が一つ限定
- 手続きに渡す引数も一つ限定
なんですが、これを any number に、との事。とりあえず試験を検討。
(test-section "ex.1-22")
(test* "(occurs-free? 'x '((lambda (x y) (+ x y)) 1 2)) should return #t"
#t
(occurs-free? 'x '((lambda (x y) (+ x y)) 1 2)))を追加して試験実施。
$ make Testing occurs-bound ... passed. Testing occurs-free ... failed. discrepancies found. Errors are: test (occurs-free? 'x '((lambda (x y) (+ x y)) 1 2)) should return #t: expects #t => got #<error "pair required, but got 1"> $
あ、上記は symbol じゃなかったら list としてナニ、な仕様なのか。ここはスルーしよう。もしかしてこれってパスするんかな。
(test-section "ex.1-22")
(test* "(occurs-free? 'x '((lambda (x y) (+ x y)) x z)) should return #t"
#t
(occurs-free? 'x '((lambda (x y) (+ x y)) x z)))パスした。こうしたらどうなるか。
(occurs-free? 'y '((lambda (x y) (+ x y)) x z))
たぶん #f が戻る。あ、これは #f で良いのか。これは?
(occurs-free? 'y '((lambda (x y) (+ x y)) x y))
#f ですな。ちなみに以下だと
(occurs-free? 'x '((lambda (x y) (+ x y)) x y))
#t が戻るはず。挙動もそうなってます。そろそろ実装を、なんですが lambda の引数のナニをどうするか、が悩ましい。else の部分はぶっちゃけ
(else
(or (occurs-free? var (car exp))
(occurs-free? var (cdr exp)))))))いいような気がしてるんですが (直感)、lambda の引数は cadr なリストを全部検査する手続きが必要か。むりくりヤッツけてみると以下?
(define occurs-free?
(lambda (var exp)
(cond
((null? exp) #t)
((symbol? exp) (eqv? exp var))
((eqv? (car exp) 'lambda)
;; (and (not (eqv? (caadr exp) var))
(and (not (let f ((l (cadr exp)))
(cond ((null? exp) #f)
((eqv? (car l) var) #t)
(else
(f (cdr l))))))
;; (occurs-free? var (caddr exp))))
(occurs-free? var (cddr exp))))
(else
(or (occurs-free? var (car exp))
;; (occurs-free? var (cadr exp)))))))
(occurs-free? var (cdr exp)))))))試験にパスせず。まず気がついたのが名前付き let の f な手続きの
(cond ((null? exp) #f)
何故に exp なんだ、という事で (null? l) に修正してもパスせず。もう一点は手続き先頭の以下。
(cond
((null? exp) #t)リスト全部見終わっても何もナシであれば #f じゃねぇか、という事で #f 戻す形にしたら試験パス。いやはや。
現時点の実装は以下。
(define occurs-free?
(lambda (var exp)
(cond
((null? exp) #f)
((symbol? exp) (eqv? exp var))
((eqv? (car exp) 'lambda)
(and (not (let f ((l (cadr exp)))
(cond ((null? l) #f)
((eqv? (car l) var) #t)
(else
(f (cdr l))))))
(occurs-free? var (cddr exp))))
(else
(or (occurs-free? var (car exp))
(occurs-free? var (cdr exp)))))))あと追加した試験を以下に。
(test-section "ex.1-22")
(test* "(occurs-free? 'x '((lambda (x y) (+ x y)) x z)) should return #t"
#t
(occurs-free? 'x '((lambda (x y) (+ x y)) x z)))
(test* "(occurs-free? 'y '((lambda (x y) (+ x y)) x z)) should return #f"
#f
(occurs-free? 'y '((lambda (x y) (+ x y)) x z)))
(test* "(occurs-free? 'y '((lambda (x y) (+ x y)) x y)) should return #t"
#t
(occurs-free? 'y '((lambda (x y) (+ x y)) x y)))
(test* "(occurs-free? 'x '((lambda (x y) (+ x y)) x y)) should return #t"
#t
(occurs-free? 'x '((lambda (x y) (+ x y)) x y)))もう少し複雑なの、と思ったんですが引数と lambda な手続きしか増やせんのか。しかも symbol しか駄目だし。せめてもう一段 lambda をネストさせてみるか。
(occurs-free? 'x '((lambda (x y z) (((lambda (x) x) +)) x y z) a b x))
むむ。一応パスしてますが ...
上記で言えば、+ とか a とか b は occurs free ですか。他はそうではないのか。試験でも確認済み。次は occurs-bound? ッスか。試験は occurs-free? のをコピる。
でっち上がったのは以下。
(define occurs-bound?
(lambda (var exp)
(cond
((null? exp) #f)
((symbol? exp) #f)
((eqv? (car exp) 'lambda)
(or (occurs-bound? var (cddr exp))
(and (let f ((l (cadr exp)))
(cond ((null? l) #f)
((eqv? (car l) var) #t)
(else
(f (cdr l)))))
(occurs-free? var (cddr exp)))))
(else
(or (occurs-bound? var (car exp))
(occurs-bound? var (cdr exp)))))))がしかし試験が NG
<ex.1-22>---------------------------------------------------------------------- test (occurs-bound? 'x '((lambda (x y) (+ x y)) x z)) should return #f, expects #f ==> ERROR: GOT #t test (occurs-bound? 'y '((lambda (x y) (+ x y)) x z)) should return #t, expects #t ==> ok test (occurs-bound? 'y '((lambda (x y) (+ x y)) x y)) should return #f, expects #f ==> ERROR: GOT #t test (occurs-bound? 'x '((lambda (x y) (+ x y)) x y)) should return #f, expects #f ==> ERROR: GOT #t test (occurs-bound? 'x '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #f, expects #f ==> ERROR: GOT #t test (occurs-bound? '+ '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #f, expects #f ==> ok test (occurs-bound? 'a '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #f, expects #f ==> ok test (occurs-bound? 'b '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #f, expects #f ==> ok test (occurs-bound? 'y '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #t, expects #t ==> ok test (occurs-bound? 'z '((lambda (x y z) (((lambda (x) x) +) x y z) a b x)) should return #t, expects #t ==> ok
うーん。これ、lambda 式の body で var が出たら #t が戻らないと駄目なカンジなんですが良いのでしょうか。
