Улучшение сокращения лямбда схемы

Question

Я переписываю этот вопрос, так как он плохо сформировался.

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

У меня есть код выше, который делает сокращение лямбда на лямбда-выражение (что я хочу). Моя проблема заключается в том, может ли кто-то помочь мне переписать эту реализацию (поскольку я не так разбираюсь в Scheme), поэтому я извлекаю из тела часть, которая выполняет альфа-преобразование, и помещает ее в отдельную функцию, а часть, которая выполняет бета-редукция. Функция reduce рекурсивна, поэтому две новые созданные функции должны быть одношаговыми, что означает, что они преобразуют только одну ограниченную переменную и уменьшают только одно выражение.

Answer 1

Ваш набор требований позволяет мне ясно понять, что это домашнее задание; если я ошибаюсь, сообщите мне, откуда берутся ваши ограничения :).

Это звучит так, как будто вам нужно лучше понять вопрос, прежде чем приступать к разработке решения. Первое, что вы упомянули, это альфа-конверсия, и я думаю, что это хорошее место для начала. Можете ли вы написать несколько примеров того, как вы можете назвать функцию альфа-преобразования и что она может вернуться?