1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

; From Definition 1.3.3:
; A variable x occurs free in a lambda calculus expression E if and only if one of the following is true:
;   1. E is a variable reference and E is the same as x
;   2. E is of the form (lambda (x') E'), where x' is different from x and x occurs free in E'
;   3. E is of the form (E1 E2) and x occurs free in E1 or E2
(define occurs-free?
  (lambda (var exp)
    (cond
      ((symbol? exp) (eqv? var exp))
      ((eqv? (car exp) 'lambda)
       (and (not (eqv? (caadr exp) var))
            (occurs-free? var (caddr exp))))
      (else (or (occurs-free? var (car exp))
                (occurs-free? var (cadr exp)))))))

; From Definition 1.3.3:
; A variable x occurs bound in a lambda calculus expression E if and only if one of the following is true:
;   1. E is of the form (lambda (x') E'), where x occurs bound in E' or x and x' are the same variable and x' occurs free in E'
;   2. E is of the form (E1 E2) and x occurs bound in E1 or E2
(define occurs-bound?
  (lambda (var exp)
    (cond
      ((symbol? exp) #f)
      ((eqv? (car exp) 'lambda)
       (or (occurs-bound? var (caddr exp))
           (and (eqv? (caadr exp) var)
                (occurs-free? var (caddr exp)))))
      (else (or (occurs-bound? var (car exp))
                (occurs-bound? var (cadr exp)))))))