Domanda

Ho provato più volte a comprendere il concetto di continuazioni e call / cc . Ogni singolo tentativo è stato un fallimento. Qualcuno può spiegarmi questi concetti, idealmente con esempi più realistici di questi su Wikipedia o in altri post SO.

Ho esperienza nella programmazione web e OOP. Capisco anche l'assemblea 6502 e ho avuto un piccolo incontro con Erlang. Tuttavia, non riesco ad avvolgere la mia testa in call / cc.

È stato utile?

Soluzione

Guarda, ho trovato questa Continuing Passing Style la migliore descrizione su questo argomento.

Ecco la copia spogliata dei dettagli di quell'articolo:

  

Autore: Marijn Haverbeke   Data: 24 luglio 2007

     

La funzione di chiamata con continuazione corrente dello schema consente di acquisire un calcolo, lo stato dello stack di chiamate per così dire, e riprendere lo stesso stato in un secondo momento. Oltre a una tale primitiva, possono essere implementate varie forme di gestione delle eccezioni e trucchi longjmp simili a C. 

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);
     

Questo può essere trasformato come segue: aggiungiamo un argomento in più ad ogni funzione, che sarà usato per passare la continuazione della funzione. Questa continuazione è un valore di funzione che rappresenta le azioni che devono avvenire dopo che la funzione "ritorna". Lo stack (chiamata) diventa obsoleto nello stile di passaggio di continuazione & # 8213; quando una funzione chiama un'altra funzione, questa è l'ultima cosa che fa. Invece di aspettare che la funzione chiamata ritorni, mette qualsiasi lavoro che vuole fare in seguito in una continuazione, che passa alla funzione. 

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});
     

Immagina di avere un documento enorme da capitalizzare. Attraversarlo in una sola volta richiede cinque secondi e congelare il browser per cinque secondi è uno stile piuttosto brutto. Considera questa semplice modifica di capitaliseText (non prestare attenzione al brutto globale): 

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}
     

Ora, ogni venti nodi, il calcolo viene interrotto per cento millisecondi per dare all'interfaccia del browser un momento per rispondere all'input dell'utente. Una forma molto primitiva di threading & # 8213; puoi anche eseguire più calcoli contemporaneamente in questo modo.

     

Un'applicazione più comunemente utile di questo è correlata a XMLHttpRequests, o ai vari hack di tag IFRAME e SCRIPT usati per simularli. Questi richiedono sempre di lavorare con un qualche tipo di meccanismo di richiamata per gestire i dati che il server invia. In casi semplici, una funzione banale farà, o alcuni globi possono essere utilizzati per memorizzare lo stato del calcolo che deve essere ripreso dopo il ritorno dei dati. Con casi complessi, ad esempio quando i dati vengono utilizzati da una funzione che deve restituire un valore al suo chiamante, le continuazioni semplificano notevolmente le cose. Basta registrare la continuazione come richiamata e il calcolo viene ripreso al termine della richiesta.

Altri suggerimenti

Per confrontarlo con C, la continuazione corrente è come lo stato corrente dello stack. Ha tutte le funzioni in attesa che il risultato della funzione corrente finisca in modo che possano riprendere l'esecuzione. La variabile acquisita come continuazione corrente viene utilizzata come una funzione, tranne per il fatto che accetta il valore fornito e lo restituisce allo stack in attesa. Questo comportamento è simile alla funzione C longjmp dove è possibile tornare immediatamente a parti inferiori dello stack . 

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Una differenza chiave tra lo stack C e una continuazione è che una continuazione può essere utilizzata in qualsiasi punto del programma, anche se lo stato dello stack è cambiato. Ciò significa che puoi essenzialmente ripristinare le versioni precedenti dello stack e usarle ancora e ancora, portando a un flusso di programma unico. 

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

La possibilità di salvare e ripristinare lo stato di un programma ha molto in comune con il multithreading. In effetti, puoi implementare il tuo thread scheduler usando le continuazioni, come ho tentato di illustrare qui .

Un banale esempio di utilizzo della continuazione sarebbe l'implementazione di un thread manager (fibra se lo si desidera) su una macchina a singolo processore. Lo scheduler interromperebbe periodicamente il flusso di esecuzione (o, nel caso delle fibre, sarebbe invocato in vari punti strategici nel codice), salvando lo stato di continuazione (corrispondente al thread corrente ), quindi passa a un stato di continuazione diverso (corrispondente a un thread diverso il cui stato è stato salvato in precedenza.)

Facendo riferimento allo sfondo dell'assembly, lo stato di continuazione acquisirà dettagli come puntatore di istruzioni, registri e contesto dello stack (puntatore) , da salvare e ripristinare a piacimento.

Un altro modo di usare la continuazione sarebbe quello di pensare di sostituire le chiamate di metodo con diverse entità simili a thread che coesistono in parallelo (in esecuzione o sospese) passando il controllo l'un l'altro usando invece contesti di continuazione del paradigma "classico" call . Opererebbero su dati globali (condivisi) invece di fare affidamento su parametri. Questo è in una certa misura più flessibile di call , nel senso che lo stack non deve essere chiuso, quindi (le chiamate sono nidificate ), ma il controllo può passare arbitrariamente.

Tentativo di visualizzare questo concetto in una lingua come una C, immagina di avere un ciclo grande con un singolo interruttore (punto di continuazione) {case point1: ...} , in cui ogni case corrisponde a un continupoint-savepoint e in cui il codice all'interno di ogni case può modificare il valore di continuation_point e cedere il controllo a quello continuation_point mediante break ing dall'interruttore e impegnando la successiva iterazione nel ciclo.

Qual è il contesto della tua domanda? Qualche scenario particolare che ti interessa? Qualche particolare linguaggio di programmazione? L'esempio di thread / fibra sopra è sufficiente?

La cosa che mi ha aiutato è l'idea che in un linguaggio tradizionale con chiamate di funzione passi implicitamente una continuazione ogni volta che fai una chiamata di funzione.

Prima di passare al codice di una funzione, si salva un po 'di stato nello stack (ovvero si preme l'indirizzo di ritorno e lo stack contiene già i locali). Questa è essenzialmente una continuazione. Al termine, la funzione deve determinare dove inviare il flusso di esecuzione. Utilizza la continuazione memorizzata nello stack, facendo scattare l'indirizzo di ritorno e saltando su di esso.

Altre lingue generalizzano questa idea di continuazioni che consente di specificare esplicitamente dove continuare l'esecuzione del codice, piuttosto che continuare implicitamente da dove è stata effettuata la chiamata di funzione.

MODIFICA in base al commento:

La continuazione è lo stato di esecuzione completo. In qualsiasi punto dell'esecuzione puoi dividere il programma in due parti (nel tempo, non nello spazio) - quello che è corso a questo punto e tutto ciò che verrà eseguito da qui. La "continuazione attuale" è il "tutto ciò che verrà eseguito da qui" (puoi pensarlo come una funzione che farà tutto il resto del tuo programma). Pertanto, la funzione fornita a call / cc viene superata la continuazione che era corrente quando veniva invocato call / cc . La funzione può usare la continuazione per restituire l'esecuzione all'istruzione call / cc (molto probabilmente anche se passerà la continuazione a qualcos'altro, perché se la usasse direttamente potrebbe invece fare un semplice ritorno ).

Quando stavo cercando di capire call / cc, ho trovato questo call-with-current-continuation-for-C-programmers è stato utile.

La migliore spiegazione che ho visto è nel libro di Paul Graham, On Lisp .

Immagina che la tua sceneggiatura sia una fase di videogioco. Call / cc è come una fase bonus.

parallelo tra fase bonus e call / cc

Non appena lo tocchi, si viene trasferiti allo stadio bonus (ovvero la definizione della funzione passata come argomento da chiamare / cc [f in questo caso]).

Gli stadi bonus sono diversi dagli stadi ordinari perché di solito hanno un elemento (cioè l'argomento della funzione passato a call / cc) che se lo tocchi perdi e vengono riportati allo stadio normale.

parallelo tra fase bonus di uscita e args funzione call / cc

Quindi non importa se ci sono molti args , quando ne raggiungi uno, è finito. Quindi la nostra esecuzione raggiunge (arg 42) e la restituisce alla somma (+ 42 10) .

Inoltre ci sono alcune osservazioni degne di nota:

  • Non tutte le funzioni possono essere utilizzate con call / cc. Dal momento che si aspetta a continuazione (che è una funzione), non puoi avere una f in questo modo: (definisci f (lambda (k) (+ k 42)) , perché non puoi sommare a funzione.
  • Inoltre non puoi avere (define f (lambda (k) (f 42 10))) perché la continuazione prevede solo un argomento.
  • Puoi finire senza toccare nessuna uscita, in questo caso la funzione procede come qualsiasi funzione ordinaria (ad esempio (define f (lambda (k) 42) finish e restituisce 42).

Esistono più livelli per comprendere call / cc. Per prima cosa devi capire i termini e il funzionamento del meccanismo. Quindi una comprensione di come e quando call / cc viene utilizzato nella "vita reale" è necessaria la programmazione.

Il primo livello può essere raggiunto studiando CPS, ma ci sono alternative.

Per il secondo livello raccomando il seguente classico di Friedman.

Daniel P. Friedman. " Applicazioni delle continuazioni: esercitazione su invito " ;. 1988 Principi dei linguaggi di programmazione (POPL88). Gennaio 1988.

Dai un'occhiata alla descrizione e all'implementazione di call / cc per FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx

Il modello che ho usato per comprendere le continuazioni da un punto di vista imperativo è che è una copia dello stack di chiamate combinato con un puntatore all'istruzione successiva.

Call / cc chiama una funzione (passata come argomento) con la continuazione come argomento.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top