È possibile utilizzare call/cc per implementare la ricorsione?

Question

Mi chiedo se sia possibile definire una funzione ricorsiva senza chiamare la funzione stessa nel suo corpo ma in qualche modo usare call/cc invece? Grazie.

Answer 1

È possibile implementare un combinatore Y utilizzando call/cc, as described here. (! Molte grazie a John Cowan per menzionare questo post pulito) Citando quel post, ecco l'implementazione di Oleg:

Corollario 1. combinatore Y tramite call/cc - Y Combinator senza un auto-esplicita richiesta.

(define (Y f) 
    ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n))))) 
    (call/cc (call/cc (lambda (x) x))))) 

Qui, abbiamo usato un fatto che

((lambda (u) (u p)) (call/cc call/cc)) 

e

((lambda (u) (u p)) (lambda (x) (x x))) 

sono osservativamente equivalenti.

Answer 2

La tua domanda è un po 'vaga. In particolare, sembra che tu voglia un sistema che modella le chiamate ricorsive senza effettuare chiamate ricorsive, usando call/cc. Risulta, tuttavia, che è possibile modellare le chiamate ricorsive senza effettuare chiamate ricorsive e senza utilizzare call/cc. Ad esempio:

#lang racket 

(define (factorial f n) 
    (if (= n 0) 1 (* n (f f (- n 1))))) 

(factorial factorial 3) 

Questo può sembrare un imbroglio, ma è la base del combinatore Y. Forse puoi rafforzare il set di restrizioni a cui stai pensando?

P.S .: se questo è compito, per favore citatemi!

Answer 3

Ho paura che lo call/cc non abbia molto a che fare con questo. Esistono solo due modi per definire una funzione ricorsiva:

• Supponiamo che la lingua consenta la definizione di funzioni ricorsive; Ad esempio, un corpo di funzione può fare riferimento alla funzione di chiusura, oppure il corpo di una funzione f può fare riferimento a una funzione g il cui corpo fa riferimento a f. In questo caso, beh, basta scriverlo nel solito modo.
• Se la tua lingua vieta entrambi, ma ha ancora funzioni di prima classe e lambda, puoi usare uno fixed-point combinator come il combinatore Y. Scrivi la tua funzione in modo che consideri come argomento aggiuntivo una funzione che intende rappresentare il passo ricorsivo; ogni posto in cui dovresti recitare, invece invochi quell'argomento.

Così per factorial, si scrive così:

(define (factorial-step recurse n) 
    (if (zero? n) 
     1 
     (* n (recurse (- n 1))))) 

La magia del combinatore Y è che si costruisce la funzione recurse che sarebbe alimentato factorial-step.