Qual è un esempio di continuazione non implementato come procedura?

15

Una interessante discussione sulla distinzione tra callbacks e continuazioni su SO hanno richiesto questa domanda. Per definizione, una continuazione è una rappresentazione astratta della logica necessaria per completare un calcolo. Nella maggior parte delle lingue questo si manifesta come una procedura a un argomento a cui si passa qualunque valore ha bisogno di elaborazione continua.

In un linguaggio puramente funzionale (in cui tutte le funzioni sono cittadini puri e di prima classe), penserei che una continuazione potrebbe essere interamente modellata come una funzione. Dopotutto, questo è il modo in cui ho precedentemente compreso le continuazioni fino a questo punto. Tuttavia, il mondo è pieno di stato (sospiro ..) e quindi la definizione generale non richiede uno stato del programma di acquisizione di continuazione - deve solo comprendere l'intento.

Per aiutare la mia comprensione, può essere fornito un esempio in un linguaggio funzionale in cui la continuazione è espressa in un modo più astratto di una funzione? So che Scheme ti permette di afferrare l'attuale continuazione in un modo di prima classe (call / cc), ma anche così, sembra che la procedura a un argomento passata a chiamare / cc sia semplicemente data la continuazione corrente nella forma di un altro argomento della procedura a cui la funzione call / cc'd può applicare il risultato.

    
posta David Cowden 20.09.2013 - 10:29
fonte

2 risposte

11

tl; dr; Il tipo è l'astrazione globale su una continuazione

Una continuazione è il tipo di input e output

La cosa più vicina che troverai in una continuazione non procedurale è probabilmente la monad di continuazione in Haskell come è espresso come un tipo, per il quale molte funzioni possono essere utilizzate per interagire con il tipo di interruzione, ripresa, backtrack, et al.

Puoi incapsulare quella chiusura in un tipo come il tipo Cont in Haskell in cui ottieni l'astrazione di monade come "astrazione di livello superiore", e ci sono altre forme di astrazione sulle continuazioni che ottieni quando guardi il continuazione come tipo invece di una semplice procedura , ad esempio

  • Puoi prendere due continuazioni e fare un'alternativa tra di loro se il tipo segue le leggi per essere un monoid
  • Puoi astrarre il tipo per modificare i tipi di input o output della continuazione se incapsuli la chiusura in un tipo che rispetta le leggi di un funtore
  • Puoi arbitrariamente e parzialmente applicare o decorare la tua continuazione con funzionalità come la convalida dell'input o la conversione dell'input se incapsuli la chiusura in un tipo che segue le leggi di un functor applicativo

Chiusura contro procedura

Alla fine della giornata hai fondamentalmente ragione; una continuazione è una "procedura", anche se preferirei fare riferimento ad essa come una chiusura. Spesso le continuazioni dei tempi sono meglio espresse come chiusure di prima classe che hanno racchiuso un ambiente vincolato. In un linguaggio puramente funzionale potresti dire che questo non è particolarmente ragionevole perché ti mancano dei riferimenti; questo è vero ma è possibile allegare valori e l'assegnazione singola rende racchiudendo il valore rispetto al riferimento la stessa identica cosa. Questo dà origine a Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

Un linguaggio che non ha la capacità di racchiudere un ambiente vincolante può tecnicamente mancare chiusure di prima classe, ma anche in quel caso c'è un qualche ambiente (generalmente globale) che è disponibile alla chiusura.

Quindi direi che è più accurato descrivere una continuazione come: Una chiusura usata in un modo particolare.

Conclusione

Alla domanda di "Una continuazione è implementabile in un modo diverso da una procedura?" No. Se non hai funzioni di prima classe in realtà non si possono avere continuazioni in quanto tali (sì i puntatori di funzione contano come funzioni di prima classe, quindi l'accesso alla memoria in modo arbitrario può essere sufficiente).

Ora alla domanda di "Esistono modi per esprimere una continuazione in un modo più astratto rispetto a una procedura?" Esprimerlo come tipo ti offre un'astrazione molto più ampia, che ti consente di trattare la continuazione in modi molto generali tali che è possibile interagire con la continuazione in molti più modi rispetto alla semplice esecuzione.

    
risposta data 20.09.2013 - 17:20
fonte
2

Un esempio che potrebbe piacerti sono le coroutine. Ad esempio, le Coroutine da Lua o gli iteratori / generatori di Python o C # hanno un potere simile alle continuazioni one-shot (continuazioni a cui è permesso chiamare solo una volta) ma la continuazione non è esplicitamente trasformata in una funzione. Invece, hai i modi per far avanzare la coroutine fino alla successiva dichiarazione di "rendimento".

Ad esempio, considera il seguente programma Python:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

È simile al seguente programma Javascript con callback espliciti:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

L'esempio di Javascript è un po 'rumoroso perché ogni passo deve restituire la continuazione successiva oltre a restituire il valore restituito (nel Python tiene traccia della continuazione all'interno di ite

    
risposta data 21.09.2013 - 02:58
fonte