Cosa sono le continuazioni di Scala e perché usarle?

Question

ho appena finito Programmazione in Scala, e ho esaminato le modifiche tra Scala 2.7 e 2.8.Quello che sembra essere il più importante è il plugin di continuazione, ma non capisco a cosa serva o come funzioni.Ho visto che va bene per l'I/O asincrono, ma non sono riuscito a scoprire il motivo.Alcune delle risorse più popolari sull'argomento sono queste:

• Continuazioni delimitate e Scala
• Vai a Scala
• Un assaggio di 2,8:Continuazioni
• Spiegazione delle continuazioni delimitate (in Scala)

E questa domanda su Stack Overflow:

• Quali sono le maggiori differenze tra Scala 2.8 e Scala 2.7?

Sfortunatamente, nessuno di questi riferimenti tenta di definire a cosa servono le continuazioni o cosa dovrebbero fare le funzioni di spostamento/ripristino e non ho trovato alcun riferimento che lo faccia.Non sono riuscito a indovinare come funzionano gli esempi negli articoli collegati (o cosa fanno), quindi un modo per aiutarmi potrebbe essere quello di esaminare riga per riga uno di quegli esempi.Anche questo semplice dal terzo articolo:

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

Perché il risultato è 8?Questo probabilmente mi aiuterebbe a iniziare.

Answer 1

Mio blog spiega cosa reset E shift farlo, quindi potresti volerlo leggere di nuovo.

Un'altra buona fonte, che indico anche nel mio blog, è la voce di Wikipedia su stile di passaggio continuo.Questo è di gran lunga il più chiaro sull'argomento, sebbene non utilizzi la sintassi Scala e la continuazione sia passata esplicitamente.

Il documento sulle continuazioni delimitate, a cui mi collego nel mio blog ma sembra non funzionare più, fornisce molti esempi di utilizzo.

Ma penso che il miglior esempio di concetto di continuazioni delimitate è Scala Swarm.In esso, la biblioteca fermate l'esecuzione del codice a un certo punto e il calcolo rimanente diventa la continuazione.La libreria quindi fa qualcosa, in questo caso trasferendo il calcolo a un altro host e restituisce il risultato (il valore della variabile a cui si è avuto accesso) al calcolo che è stato interrotto.

Ora, non capisci nemmeno il semplice esempio sulla pagina Scala, quindi Fare leggi il mio blogIn esso sono soltanto interessato a spiegare queste basi, il motivo per cui il risultato è 8.

Answer 2

Ho trovato le spiegazioni esistenti per essere meno efficace a spiegare il concetto di quanto mi auguro. Spero che questo sia chiaro (e corretta). Non ho ancora utilizzato continuazioni.

Quando un cf funzione di continuazione viene chiamata:

1. Esecuzione salta sopra il resto del blocco shift e inizia di nuovo alla fine di esso
   • il parametro passato a cf è ciò che il blocco shift "elabora" ad come l'esecuzione continua. questo può essere diverso per ogni chiamata a cf
2. L'esecuzione continua fino alla fine del blocco reset (o fino a quando una chiamata a reset se non c'è blocco)
   • il risultato del blocco reset (o il parametro per reset () se non v'è alcun blocco) è ciò che cf rendimenti
3. L'esecuzione continua dopo cf fino alla fine del blocco shift
4. Esecuzione salta fino alla fine del blocco reset (o una chiamata a ripristinare?)

Quindi in questo esempio, seguire le lettere dalla A alla Z

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

Questo stampa:

11
101

Answer 3

Dato l'esempio canonico del documento di ricerca per le continuazioni delimitate di Scala, leggermente modificata in modo che la funzione input to shift viene dato il nome f e quindi non è più anonimo.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

Il plugin Scala trasforma questo esempio in modo tale che il calcolo (all'interno dell'argomento di input di reset) a partire da ciascuno shift all'invocazione di reset È sostituito con la funzione (ad es. f) ingresso a shift.

Il calcolo sostituito è spostato (cioè.spostato) in una funzione k.La funzione f immette la funzione k, Dove k contiene il calcolo sostituito, k input x: Int, e il calcolo in k sostituisce shift(f) con x.

f(k) * 2
def k(x: Int): Int = x + 1

Che ha lo stesso effetto di:

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

Nota il tipo Int del parametro di input x (cioè.la firma del tipo di k) è stato dato dalla firma del tipo del parametro di input di f.

Un altro preso in prestito esempio con l'astrazione concettualmente equivalente, cioè read è l'input della funzione shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

Credo che questo sarebbe tradotto nell'equivalente logico di:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

Spero che questo chiarisca l’astrazione comune coerente che era in qualche modo offuscata dalla precedente presentazione di questi due esempi.Ad esempio, il primo esempio canonico è stato presentato nel documento di ricerca come funzione anonima, invece del mio nome f, quindi ad alcuni lettori non fu immediatamente chiaro che fosse astrattamente analogo al read nel preso in prestito secondo esempio.

Le continuazioni così delimitate creano l'illusione di un'inversione del controllo da "mi chiami dall'esterno". reset" a "Ti chiamo dentro reset".

Prendere nota del tipo di restituzione di f è, ma k non è necessario che sia uguale al tipo restituito di reset, cioè. f ha la libertà di dichiarare qualsiasi tipo di reso per k fino a quando f restituisce lo stesso tipo di reset.Idem per read E capture (Guarda anche ENV sotto).

---

Le continuazioni delimitate non invertono implicitamente il controllo dello stato, ad es. read E callback non sono funzioni pure.Pertanto il chiamante non può creare espressioni referenzialmente trasparenti e quindi non ha dichiarativo (anchetrasparente) controllo sulla semantica imperativa prevista.

Possiamo ottenere esplicitamente funzioni pure con continuazioni delimitate.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

Credo che questo sarebbe tradotto nell'equivalente logico di:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

Questo sta diventando rumoroso, a causa dell'ambiente esplicito.

Nota tangenzialmente, Scala non ha l'inferenza del tipo globale di Haskell e quindi, per quanto ne so, non potrebbe supportare il sollevamento implicito a una monade di stato unit (come una possibile strategia per nascondere l'ambiente esplicito), perché l'inferenza di tipo globale (Hindley-Milner) di Haskell dipende da non supporta l'eredità virtuale multipla di diamanti.

Answer 4

Perfezionamento cattura lo stato di un calcolo, da richiamare in seguito.

Si pensi alla computazione tra lasciare l'espressione spostamento e lasciando l'espressione di reset in funzione. All'interno dell'espressione spostamento questa funzione è denominato k, è la continuazione. È possibile passare in giro, richiamare in un secondo momento, anche più di una volta.

Credo che il valore restituito dall'espressione di reset è il valore dell'espressione all'interno dell'espressione turno dopo l'=>, ma su questo io non sono molto sicuro.

Quindi, con continuazioni si può avvolgere un pezzo piuttosto arbitraria e non locale di codice in una funzione. Questo può essere utilizzato per implementare il flusso di controllo non standard, come coroutining o indietreggiamento.

Quindi continuazioni dovrebbero essere usati a livello di sistema. cospargendoli attraverso il vostro codice di applicazione sarebbe una ricetta sicura per gli incubi, molto peggio del peggiore spaghetti code utilizzando goto potrebbe mai essere.

. Disclaimer: ho alcuna comprensione approfondita delle continuazioni a Scala, ho appena dedotto dal guardare gli esempi e sapendo seguite da Scheme

Answer 5

Dal mio punto di vista, la migliore spiegazione è stata data qui: http : //jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Uno degli esempi:

  

Per visualizzare il flusso di controllo di un po 'più chiaramente, è possibile eseguire questo   frammento di codice:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

  

Ecco l'output del codice precedente produce:

A
B
D
E
G
F
C

Answer 6

Un altro articolo (più recente, maggio 2016) sulle continuazioni di Scala è:
"Viaggio nel tempo a Scala:CPS in Scala (proseguimento della scala)" diShivansh Srivastava (shiv4nsh).
Si riferisce anche a Jim McBeath'S articolo menzionato in Dmitrij Bespalov'S risposta.

Ma prima, descrive le Continuazioni in questo modo:

Una continuazione è una rappresentazione astratta dello stato di controllo di un programma per computer.
Quindi ciò che in realtà significa è che si tratta di una struttura dati che rappresenta il processo computazionale in un dato punto dell’esecuzione del processo;la struttura dati creata è accessibile dal linguaggio di programmazione, invece di essere nascosta nell'ambiente runtime.

Per spiegarlo ulteriormente possiamo fare uno degli esempi più classici,

Supponiamo che tu sia in cucina davanti al frigorifero e pensi a un panino.Prendi una continuazione proprio lì e te la metti in tasca.
Poi prendi un po' di tacchino e pane dal frigorifero e ti prepari un panino, che ora è sul bancone.
Invochi il seguito in tasca e ti ritrovi di nuovo davanti al frigorifero, a pensare a un panino.Ma per fortuna sul bancone c’è un panino e tutti i materiali utilizzati per realizzarlo sono spariti.Quindi lo mangi.:-)

In questa descrizione, il sandwich fa parte del dati del programma (ad esempio, un oggetto nell'heap) e invece di chiamare un "make sandwich" routine e poi tornando, la persona ha chiamato un "make sandwich with current continuation", che crea il sandwich e poi continua da dove si era interrotta l'esecuzione.

Ciò premesso, come annunciato nel Aprile 2014 per Scala 2.11.0-RC1

Cerchiamo manutentori che si occupino dei seguenti moduli: scala-swing, scala-continuazioni.
2.12 non li includerà se non viene trovato un nuovo manutentore.
Probabilmente continueremo a mantenere gli altri moduli (scala-xml, scala-parser-combinators), ma l'aiuto è comunque molto apprezzato.