EoPL reading (30) 1.3.1 Free and Bound Variables

scheme EoPL

なんと言えば良いか分かりませんが、凄く進捗が悪い。落ち着けと自分に言い聞かせつつだらだらと土曜日を過ごしてます。(何
とりあえず lambda 式の場合の試験に微妙に拘り続けてるんですが、自分でも何故だか分かってなかったりなんかして。
直前エントリにも書いた通り、lambda 式が occurs bound な条件としては

  • lambda body が occurs bound
  • 引数列に var と eqv な要素があって、lambda body が occurs free

という形なんですが、基本的に lambda body が occurs bound でない場合というのは

  • null
  • symbol

のみ、という訳ではないよな。var が y だとすると

  • (lambda () y)
  • (lambda (x) ())
  • (lambda (x) x)
  • (lambda (y) x)

とかは occurs bound ではない。一応上二つを試験に追加しといて ex.1-22 は終了という事にします。なんとなく再帰にアタマがついてけてないカンジがしてます。

Exercise.1-23

1.22 のヤツを元に再度試験などを追加。まず以下のソースに対して 1.22 な試験を実施。

(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 (let f ((l (cadr exp)))
	     (cond ((null? l) #t)
		   ((eqv? (car l) var) #f)
		   (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)))))))

(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)))))))

試験はパス。if の試験を追加してけば良いな。って良く見たら occurs-bound 側には if の盛り込みが無いですな。現時点での理解では 

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

を盛り込めば OK なはず、との認識ッス。occurs-free? 側から試験を書くのですが、とりあえず今からフロに入ります。
ってよく考えたら微妙だなぁ。

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

って #t が戻る。あ、成程。こうなら #f が戻る?

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

あるいはこんなのは?

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

#f 戻す試験を書いてしまった。これはどうなるのか

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

これなら #f が戻る。あるいは lambda 式の場合は、という事で追加したのが以下の試験。まだ戻り値の誤解があって、いくつか間違えた。

(test* "(occurs-free? 'x '(lambda (x) (if (= x 1) #t #f))) should return #f"
       #f
       (occurs-free? 'x '(lambda (x) (if (= x 1) #t #f))))
(test* "(occurs-free? 'x '(lambda (x) (if (= y 1) #t #f))) should return #f"
       #f
       (occurs-free? 'x '(lambda (x) (if (= y 1) #t #f))))
(test* "(occurs-free? 'x '(lambda (y) (if (= x 1) #t #f))) should return #t"
       #t
       (occurs-free? 'x '(lambda (y) (if (= x 1) #t #f))))
(test* "(occurs-free? 'x '(lambda (y) (if (= y 1) #t #f))) should return #f"
       #f
       (occurs-free? 'x '(lambda (y) (if (= y 1) #t #f))))

こうして見ると lambda 式の場合は

  • 引数列に var が無い
  • かつ body に var が存在

したら occurs free なのか (今更
次の Ex.1-24 は let と let* との事。いまから検討。