EoPL reading (22) 1.3.1 Free and Bound Variables

1.20 な問題を、と思ったんですが何が言いたいのかが微妙に分からず。おそらくは occurs free の定義がきちんと理解できてないのが原因かと。
例示されているのは以下の式で

((lambda (x) x) y)

x occurs bound で y occurs free との事。これをテストケイスにして例示されている手続きを試験してみる事に。
以下な試験を書きました。

(use gauche.test)

(add-load-path ".")
(load "occurs-free-bound")

(test-start "occurs-bound")
(test-section "occurs-bound")
(test* "(occurs-bound? 'x '((lambda (x) x) y)) should return #t"
       #t
       (occurs-bound? 'x '((lambda (x) x) y)))
(test-end)

なんとなくファイルを分割してます。もう一つ。

(use gauche.test)

(add-load-path ".")
(load "occurs-free-bound")

(test-start "occurs-free")
(test-section "occurs-free")
(test* "(occurs-free? 'y '((lambda (x) x) y)) should return #t"
       #t
       (occurs-free? 'y '((lambda (x) x) y)))
(test-end)

手続き定義は別途として、試験はパス。

$ cat test.log 
Testing occurs-bound ==========================================================
<occurs-bound>-----------------------------------------------------------------
test (occurs-bound? 'x '((lambda (x) x) y)) should return #t, expects #t ==> ok
passed.
Testing occurs-free ===========================================================
<occurs-free>------------------------------------------------------------------
test (occurs-free? 'y '((lambda (x) x) y)) should return #t, expects #t ==> ok
passed.
$

例示されているナニでもう少し試験を追加。

(test* "(occurs-bound? 'y '(lambda (y) ((lambda (x) x) y))) should return #t"
       #t
       (occurs-bound? 'y '(lambda (y) ((lambda (x) x) y))))
(test* "(occurs-bound? 'f '(lambda (f) (lambda (x) (f x)))) should return #t"
       #t
       (occurs-bound? 'f '(lambda (f) (lambda (x) (f x)))))
(test* "(occurs-bound? 'x '(lambda (f) (lambda (x) (f x)))) should return #t"
       #t
       (occurs-bound? 'x '(lambda (f) (lambda (x) (f x)))))

とか

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

とか。試験には当たり前ですがパスしてます。とりあえず、lambda 式の occurs free とか occurs bound の定義と照らしつつ手続きの定義を確認。
まず occurs-free? から、面倒なのでコメント付けます

(define occurs-free?
  (lambda (var exp)
    (cond
;; E is a variable reference and E is the same as x
     ((symbol? exp) (eqv? exp var))
;; E is of the form (lambda (y) E'), 
     ((eqv? (car exp) 'lambda)
;; where y is different from x
      (and (not (eqv? (caadr exp) var))
;; and x occurs free in E'
	   (occurs-free? var (caddr exp))))
;; E is of the form (E1 E2) and x occurs free in E1 or E2
     (else
      (or (occurs-free? var (car exp))
	  (occurs-free? var (cadr exp)))))))

定義そのまんまに手続きを書いているのが分かる。lisp/scheme ってこのあたりが明快ですわな。あるいは occurs-bound? が以下。

(define occurs-bound?
  (lambda (var exp)
    (cond
     ((symbol? exp) #f)
;; E is of the form (lambda (y) E'),
     ((eqv? (car exp) 'lambda)
;; where x occurs bound in E' or
      (or (occurs-bound? var (caddr exp))
;; x and y are the same variable and
	  (and (eqv? (caadr exp) var)
;; y occurs free in E'
	       (occurs-free? var (caddr exp)))))
     (else
;; E is of the form (E1 E2) and x occurs bound in E1 or E2
      (or (occurs-bound? var (car exp))
	  (occurs-bound? var (cadr exp)))))))

む。こっちは定義がそのまま手続きになってる訳ではないのか。もう少し理解を深めるための試験 (UT) が必要ッスね。とりあえずエントリ投入。