EoPL reading (27) 1.3.1 Free and Bound Variables

scheme EoPL

昨晩のエントリな occurs-free? は正しくは以下。

(define occurs-free?
  (lambda (var exp)
    (define (self-evaluating? s)
      (or (number? s)
	  (string? s)
	  (eq? #t s)
	  (eq? #f s)))

    (cond
     ((null? exp) #f)
     ((self-evaluating? 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))))
     ((eqv? (car exp) 'if)
      (or (occurs-free? var (cadr exp))
	  (occurs-free? var (cddr exp))))
     (else
      (or (occurs-free? var (car exp))
	  (occurs-free? var (cdr exp)))))))

occurs-free? は再起的に呼び出されるので、self-evaluating? 手続きで exp を扱っていたとしても結果オーライだった模様。こーゆーケイスでは引数渡さなくても問題なく判断可能なのか。これはこれで凄いな。
とりあえず、もう少し試験を書いてみる方向で。ってか昨晩の試験項目をまず精査。

  • (occurs-free? 'x '(lambda (x) (if (= x 1) #f #t))) は #f で OK
  • (occurs-free? 'x '(lambda (y) (if (= x 1) #f #t))) は #t で OK
  • (occurs-free? 'x '(lambda (x) (if (= y 1) #f #t))) は #f で OK
  • (occurs-free? 'x '(lambda (y) (if (= y 1) #f x))) は #f か
  • (occurs-free? 'x '(lambda (y) (if (= y 1) x #f))) も #f ですか

って下二つは試験によると #t が戻るべき、ってなってるな。あ、occurs free だから #t か。どうもいかんな。てーコトは

  • (occurs-free? 'x '(lambda (y) (if (= y 1) ((lambda (x) x) y) #f))) は #t?

ってコトで試験追加。あ、またナチュラル君だ。上記は occurs bound ですな。なので #f ッスか。これって

  • (occurs-free? 'x '(lambda (y) (if (= y 1) ((lambda (x) x) #t) #f)))

でも良いのかな。当たり前ですが試験パス。逆も同様でしょうな。

  • (occurs-free? 'x '(lambda (y) (if (= y 1) #t ((lambda (x) x) #f))))

試験パス。上記 2 点は occurs bound。む、これって occurs free になる?

  • (occurs-free? 'x '(lambda (y) (if (= y 1) #t ((lambda (x) x) x))))

わはは。あるいはこれも free?

  • (occurs-free? 'x '(lambda (y) (if (= y 1) #t ((lambda (x) 1) #f))))

あ、#f が戻ってきた。これはバグだな。

     ((self-evaluating? exp) #f)

これは #t を戻さないと駄目なのか。なんか試験が肥大してるんですが、このあたりの試験は完全スルー状態のはず。で、#t を戻す形に修正したら以下な試験がダウト。

test (occurs-free? 'x '(lambda (y) (if (= y 1) ((lambda (x) x) y) #f))) should retuen #f: expects #f => got #t
test (occurs-free? 'x '(lambda (y) (if (= y 1) ((lambda (x) x) #t) #f))) should retuen #f: expects #f => got #t
test (occurs-free? 'x '(lambda (y) (if (= y 1) #t ((lambda (x) x) #f)))) should retuen #f: expects #f => got #t

むむ。or で聞いてるから微妙なの? あ、if の中は or じゃ駄目ですね。

     ((eqv? (car exp) 'if)
      (or (occurs-free? var (cadr exp))
	  (occurs-free? var (cddr exp))))

でも上記って

     ((if な式なら)
      (or (条件式 が occurs free?)
          (残りの式が occurs free?)))

な意味で、残りは else な節で評価されるので or で評価されるな。これって

(occurs-free? 'x '(((lambda (x) x) 1) #f))

だと #t が戻ってくる?
試験したら上記の通り。よく考えたら

((lambda (x) x) x)

が #t 戻すのか。てーコトは

(occurs-free? 'x '(((lambda (y) y) x) ((lambda (x) x) 1)))

も、#t なんですが以下は?

(occurs-free? 'x '(((lambda (y) y) x) (lambda (x) x)))

む。これも #t だな。あらら。なんかおかしいな。あ、car な式が #t なのか。どうもいかん。この迷走っぷりは微妙だぞ。リトライ。本来以下が試したかったもの。

(occurs-free? 'x '(((lambda (x) x) y) ((lambda (x) x) 1)))
(occurs-free? 'x '(((lambda (x) x) y) (lambda (x) x)))

上記だと上側は #t で下側は #f になります。これは良いのか。こうだったらどうなの?

(occurs-free? 'x '((lambda (x) x) (lambda (x) x)))

これはアタマの式が #t だもんな。そのまんまか。こうなってたら occurs free?

(occurs-free? 'x '((lambda (x) x) (lambda (x) x) ((lambda (x) x) 1)))

ビンゴ。でも若干微妙。このあたりの微妙な部分はスルーします。
そーゆー意味では式が self-evaluating だった場合は #f 戻す。で、試験したら failed ってどーゆーコトだ。

test (occurs-free? 'x '(lambda (y) (if (= y 1) #t ((lambda (x) x) x)))) should retuen #t: expects #t => got #f
test (occurs-free? 'x '(((lambda (x) x) 1) #f)) should retuen #t: expects #t => got #f
test (occurs-free? 'x '((lambda (x) x) x)) should retuen #f: expects #f => got #t
test (occurs-free? 'x '(((lambda (x) x) y) ((lambda (x) x) 1))) should retuen #t: expects #t => got #f
test (occurs-free? 'x '((lambda (x) x) (lambda (x) x) ((lambda (x) x) 1))) should retuen #t: expects #t => got #f
r

駄目だ。このエントリ滅茶苦茶ってか、occurs free の定義が理解できてない。大体が

((lambda (x) x) x)

は occurs free じゃんか。なんかイチから試験書きたい気分で一杯です。職場にカタメて送ってやる。

迷走

駄目だ。なんの為に試験書いてるのかワケワカな位の迷走っぷり。