我正在重写这个问题,因为它的格式很差。
(define (reduce f)
((lambda (value) (if (equal? value f) f (reduce value)))
(let r ((f f) (g ()))
(cond ((not (pair? f))
(if (null? g) f (if (eq? f (car g)) (cadr g) (r f (caddr g)))))
((and (pair? (car f)) (= 2 (length f)) (eq? 'lambda (caar f)))
(r (caddar f) (list (cadar f) (r (cadr f) g) g)))
((and (not (null? g)) (= 3 (length f)) (eq? 'lambda (car f)))
(cons 'lambda (r (cdr f) (list (cadr f) (gensym (cadr f)) g))))
(else (map (lambda (x) (r x g)) f))))))
; (reduce '((lambda x x) 3)) ==> 3
; (reduce '((lambda x (x x)) (lambda x (lambda y (x y)))))
; ==> (lambda #[promise 2] (lambda #[promise 3] (#[promise 2] #[promise 3])))
; Comments: f is the form to be evaluated, and g is the local assignment
; function; g has the structure (variable value g2), where g2 contains
; the rest of the assignments. The named let function r executes one
; pass through a form. The arguments to r are a form f, and an
; assignment function g. Line 2: continue to process the form until
; there are no more conversions left. Line 4 (substitution): If f is
; atomic [or if it is a promise], check to see if matches any variable
; in g and if so replace it with the new value. Line 6 (beta
; reduction): if f has the form ((lambda variable body) argument), it is
; a lambda form being applied to an argument, so perform lambda
; conversion. Remember to evaluate the argument too! Line 8 (alpha
; reduction): if f has the form (lambda variable body), replace the
; variable and its free occurences in the body with a unique object to
; prevent accidental variable collision. [In this implementation a
; unique object is constructed by building a promise. Note that the
; identity of the original variable can be recovered if you ever care by
; forcing the promise.] Line 10: recurse down the subparts of f.
我有上面的代码,它对 lambda 表达式(这是我想要的)进行 lambda 缩减。我的问题是,有人可以帮我重写这个实现(因为我对Scheme没有那么经验),以便我从正文中提取进行alpha转换的部分并将其放在单独的函数中,以及执行的部分β-减少也是如此。函数 reduce 是递归的,所以两个新创建的函数需要是单步的,这意味着它们将只转换一个有界变量并只减少一个表达式。