Qualcuno sa se call/cc può essere implementato con solo lambda e chiusure?La call-with-current-continuation può essere implementata solo con lambdas e chiusure?
Sembra che call/cc interrompa il flusso del programma (come un'eccezione) ma lambda e chiusure non possono farlo. Quindi penso che call/cc non possa essere implementato tramite lambda e chiusure.
Altre idee?
La domanda non è particolarmente chiara, dal momento che cosa significa "implementato solo con lambda e chiusure"?
In ogni caso, le continuazioni possono essere utilizzate in qualsiasi lingua con chiusure scrivendo manualmente in continuation passing style. Quindi la traduzione automatica in questo modulo può essere implementata estendendo il compilatore, che i Lisps in genere consentono a livello utente tramite macro. Per esempio vedere cl-cont, una libreria che implementa le continuazioni per Common Lisp, che è una lingua che non le ha incorporate.
Le continuazioni pervasive efficienti come in Scheme sono probabilmente implementate su un livello inferiore che riguarda direttamente il programma stack, ma questo non è un requisito, solo un'ottimizzazione.
CPS funzionerà solo se la lingua sottostante supporta le chiamate tail (che dovrebbe, nel caso di Scheme). – leppie
Generalmente vero, ma in linea di principio è possibile cancellare manualmente il frame dello stack restituendo la continuazione e gli argomenti in alto a un ciclo "CPS-driver". – Ramarren
CPS funzionerà, ma il problema è che funziona * solo * per il codice che controlli (e può CPS). Ad esempio, occuparsi di librerie diventa difficile, dal momento che è necessario trattarle come chiamate straniere, anche se sono nella tua lingua. (E a proposito, questi "circuiti SPC-driver" sono di solito indicati come "tampolanti".) –
In Scheme è possibile implementare call/cc utilizzando lambdas durante la conversione in stile passaggio continuo (CPS). Quando la conversione in CPS, ogni occorrenza di call/cc può essere sostituito con il seguente equivalente:
(lambda (f k) (f (lambda (v k0) (k v)) k))
dove k è la continuazione da salvare, e (lambda (v k0) (k v)) è la procedura fuga che ripristina questa continuazione (qualunque continuazione k0 che è attivo quando viene chiamato, viene scartato).
Quindi, per rispondere alla domanda per Schema: sì, può essere fatto.
In questo modo call/cc viene solitamente implementato in una lingua ottimizzata per la coda chiamata come Scheme? Come una macro? – Byte
No, per il supporto per la continuazione completa (iow non quelli a scatto singolo) è necessario acquisire stack e heap. Tutto ciò accade a un livello molto basso. – leppie
@leppie Sarei felice di revocarlo come risposta. –
@Frank Shearar: vorrei se li avessi effettivamente implementati con successo :) Le continuazioni sono difficili, andiamo a fare shopping! – leppie