Como implementar uma função recursiva no cálculo lambda usando um subconjunto da linguagem Clojure?

Estou estudando o cálculo lambda com o livro "Uma introdução à programação funcional através do cálculo lambda", de Greg Michaelson.

Eu implemento exemplos no Clojure usando apenas um subconjunto da linguagem. Eu permito apenas:

símbolosfunções lambda de um argumentoaplicação de funçãodefinição de var por conveniência.

Até agora eu tenho essas funções funcionando:

(def identity (fn [x] x))
(def self-application (fn [s] (s s)))

(def select-first (fn [first] (fn [second] first)))
(def select-second (fn [first] (fn [second] second)))
(def make-pair (fn [first] (fn [second] (fn [func] ((func first) second)))))    ;; def make-pair =  λfirst.λsecond.λfunc.((func first) second)

(def cond make-pair)
(def True select-first)
(def False select-second)

(def zero identity)
(def succ (fn [n-1] (fn [s] ((s False) n-1))))
(def one (succ zero))
(def zero? (fn [n] (n select-first)))
(def pred (fn [n] (((zero? n) zero) (n select-second))))

Mas agora estou preso a funções recursivas. Mais precisamente na implementação deadd. A primeira tentativa mencionada no livro é esta:

(def add-1
  (fn [a]
    (fn [b]
      (((cond a) ((add-1 (succ a)) (pred b))) (zero? b)))))

((add zero) zero)

Regras de cálculo Lambda de força de redução para substituir a chamada interna paraadd-1 com a definição real que contém a própria definição ... infinitamente.

No Clojure, que é uma linguagem de pedido de aplicativo,add-1 também é avaliada ansiosamente antes de qualquer execução de qualquer tipo, e recebemos umaStackOverflowError.

Após algumas discussões, o livro propõe uma engenhoca usada para evitar as substituições infinitas do exemplo anterior.

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) (((f f) (succ a)) (pred b)))))))
(def add (add2 add2))

A definição deadd expande para

(def add (fn [a] 
           (fn [b]
             (((zero? b) a) (((add2 add2) (succ a)) (pred b)))))) 

O que é totalmente bom até tentarmos! É isso que Clojure fará (transparência referencial):

((add zero) zero)
;; ~=>
(((zero? zero) zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((select-first zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((fn [second] zero) ((add (succ zero)) (pred zero)))

Na última linha(fn [second] zero) é um lambda que espera um argumento quando aplicado. Aqui o argumento é((add (succ zero)) (pred zero)). Clojure é uma linguagem de "ordem de aplicação", para que o argumento seja avaliado antes da aplicação da função, mesmo que nesse caso o argumento não seja usado. Aqui recorremosadd que ocorrerá emadd... até a pilha explodir. Em uma linguagem como Haskell, acho que seria bom, porque é preguiçoso (ordem normal), mas estou usando o Clojure.

Depois disso, o livro apresenta o saboroso combinador Y que evita o clichê, mas cheguei à mesma conclusão horrível.

EDITAR

Como @amalloy sugere, eu defini o combinador Z:

(def YC (fn [f] ((fn [x] (f (fn [z] ((x x) z)))) (fn [x] (f (fn [z] ((x x) z)))))))

Eu definiadd2 como isso :

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) ((f (succ a)) (pred b)))))))

E eu usei assim:

(((YC add2) zero) zero)

Mas ainda recebo um StackOverflow.

Tentei expandir a função "manualmente", mas após 5 rodadas de redução beta, parece que ela se expande infinitamente em uma floresta de parênteses.

Então, qual é o truque para tornar o Clojure "ordem normal" e não "ordem de aplicação" sem macros. Isso é possível? É mesmo a solução para minha pergunta?

Esta questão está muito próxima desta:Como implementar a iteração do cálculo lambda usando o esquema lisp? . Exceto que o meu é sobre Clojure e não necessariamente sobre o Y-Combinator.

questionAnswers(2)

yourAnswerToTheQuestion