Czym są kontynuacje Scala i po co ich używać?

Właśnie skończyłem programowanie w Scali i przyglądałem się zmianom pomiędzy Scalą 2.7 i 2.8. Wydaje się, że najważniejsza jest wtyczka do kontynuacji, ale nie rozumiem, do czego jest przydatna i jak działa. Widziałem, że jest to dobre dla asynchronicznych operacji we / wy, ale nie byłem w stanie dowiedzieć się, dlaczego. Oto niektóre z bardziej popularnych zasobów na ten temat:

• Ograniczone kontynuacje i Scala
• Idź do Scali
• Smak 2,8: kontynuacje
• Wyjaśnienie ograniczonych kontynuacji (w Scali)

I to pytanie na temat przepełnienia stosu:

• Jakie są największe różnice między Scalą 2.8 a Scalą 2.7?

Niestety, żadne z tych odniesień nie próbuje zdefiniować, do czego służą kontynuacje ani do czego mają służyć funkcje shift / reset, i nie znalazłem żadnych odniesień, które to robią. Nie byłem w stanie odgadnąć, jak działają przykłady w połączonych artykułach (ani co robią), więc jednym ze sposobów, aby mi pomóc, może być przejście przez jedną z tych próbek. Nawet ten prosty artykuł z trzeciego artykułu:

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

Dlaczego wynik jest 8? To prawdopodobnie pomogłoby mi w rozpoczęciu.

Mój blog wyjaśnia, co reseti co shiftrobić, więc możesz przeczytać to jeszcze raz.

Innym dobrym źródłem, na które również wskazuję na swoim blogu, jest wpis w Wikipedii dotyczący stylu przekazywania kontynuacji . To jest zdecydowanie najbardziej jasne na ten temat, chociaż nie używa składni Scala, a kontynuacja jest jawnie przekazywana.

Artykuł o ograniczonych kontynuacjach, do którego odsyłam na moim blogu, ale wydaje się być zepsuty, podaje wiele przykładów użycia.

Ale myślę, że najlepszym przykładem koncepcji rozgraniczonych kontynuacji jest Scala Swarm. W nim biblioteka zatrzymuje wykonywanie kodu w pewnym momencie, a pozostałe obliczenia stają się kontynuacją. Biblioteka wtedy coś robi - w tym przypadku przekazuje obliczenia do innego hosta i zwraca wynik (wartość zmiennej, do której uzyskano dostęp) do obliczeń, które zostały zatrzymane.

Teraz nie rozumieją nawet prosty przykład na stronie Scala, więc nie czytać mojego bloga. W nim zajmuję się tylko wyjaśnieniem tych podstaw, dlaczego jest taki wynik 8.

Uznałem, że istniejące wyjaśnienia są mniej skuteczne w wyjaśnianiu koncepcji, niż bym miał nadzieję. Mam nadzieję, że ten jest jasny (i poprawny). Nie korzystałem jeszcze z kontynuacji.

Gdy cfwywoływana jest funkcja kontynuacji :

1. Wykonywanie przeskakuje resztę shiftbloku i rozpoczyna się ponownie na jego końcu
   • przekazany parametr cfjest tym, do czego shiftblok „ocenia” w miarę kontynuacji wykonywania. to może być inne dla każdego połączenia docf
2. Wykonywanie trwa do końca resetbloku (lub do wywołania, resetjeśli nie ma bloku)
   • zwracany jest wynik resetbloku (lub parametru do reset(), jeśli nie ma bloku)cf
3. Wykonywanie trwa cfdo końca shiftbloku
4. Wykonywanie przeskakuje do końca resetbloku (czy wywołanie resetowania?)

W tym przykładzie postępuj zgodnie z literami od A do 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

To drukuje:

11
101

Biorąc pod uwagę kanoniczny przykład z artykułu badawczego dla ograniczonych kontynuacji Scali, zmodyfikowany nieznacznie, aby dane wejściowe funkcji shiftmiały nazwę, fa zatem nie są już anonimowe.

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

Wtyczka Scala przekształca ten przykład w taki sposób, że obliczenia (w argumencie wejściowym reset) zaczynające się od każdego shiftwywołania funkcji resetsą zastępowane przez funkcję (np. f) Dane wejściowe do shift.

Zastąpione obliczenia są przenoszone (tj. Przenoszone) do funkcji k. Funkcja fwprowadza funkcję k, w której k zawiera wymieniony obliczeń, kwejść x: Inti obliczeń w kreplaces shift(f)z x.

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

Co daje taki sam efekt jak:

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

Zwróć uwagę, że typ Intparametru wejściowego x(tj. Sygnatura typu k) został nadany przez sygnaturę typu parametru wejściowego f.

Innym pożyczonym przykładem z koncepcyjnie równoważną abstrakcją, tj. readJest wejście funkcji do 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)
}

Uważam, że można to przełożyć na logiczny odpowiednik:

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)
  }
}

Mam nadzieję, że to wyjaśnia spójną wspólną abstrakcję, która została nieco zaciemniona przez wcześniejszą prezentację tych dwóch przykładów. Na przykład kanoniczny pierwszy przykład został przedstawiony w artykule badawczym jako funkcja anonimowa, a nie moja nazwana f, więc dla niektórych czytelników nie było od razu jasne, że jest on abstrakcyjnie analogiczny do tego readw drugim pożyczonym przykładzie.

Tak ograniczone kontynuacje tworzą iluzję odwrócenia kontroli od „wzywasz mnie z zewnątrz reset” do „wzywam cię do wewnątrz reset”.

Zwróć uwagę, że typ zwracany fjest, ale knie jest, taki sam jak typ zwracany przez reset, tj. fMa swobodę deklarowania dowolnego typu zwracanego, kdopóki fzwraca ten sam typ co reset. Jak wyżej dla readi capture(patrz także ENVponiżej).

Ograniczone kontynuacje nie odwracają niejawnie kontroli stanu, np. readI callbacknie są czystymi funkcjami. Tak więc obiekt wywołujący nie może tworzyć referencyjnie przezroczystych wyrażeń, a zatem nie ma deklaratywnej (czyli przezroczystej) kontroli nad zamierzoną imperatywną semantyką .

Możemy jawnie osiągnąć czyste funkcje z ograniczonymi kontynuacjami.

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)
  }
}

Uważam, że można to przełożyć na logiczny odpowiednik:

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)
    }
  }
}

Robi się głośno z powodu wyraźnego otoczenia.

Uwaga styczna, Scala nie ma wnioskowania o typie globalnym Haskella, a zatem, o ile wiem, nie może obsługiwać niejawnego podnoszenia do monady stanu unit(jako jednej z możliwych strategii ukrywania jawnego środowiska), ponieważ wnioskowanie typu globalnego (Hindley-Milner) Haskella zależy od nieobsługiwania wielokrotnego wirtualnego dziedziczenia diamentów .

Kontynuacja przechwytuje stan obliczenia, który zostanie wywołany później.

Pomyśl o obliczeniu między pozostawieniem wyrażenia shift a pozostawieniem wyrażenia resetującego jako funkcji. W wyrażeniu shift ta funkcja nazywa się k, jest kontynuacją. Możesz to przekazać, przywołać później, nawet więcej niż raz.

Myślę, że wartość zwracana przez wyrażenie resetowania jest wartością wyrażenia wewnątrz wyrażenia shift po znaku =>, ale co do tego nie jestem do końca pewien.

Tak więc z kontynuacjami można zawrzeć w funkcji raczej dowolny i nielokalny fragment kodu. Można to wykorzystać do implementacji niestandardowego przepływu sterowania, takiego jak korekta lub cofanie.

Dlatego kontynuacje powinny być używane na poziomie systemu. Spryskanie ich kodem aplikacji byłoby pewną receptą na koszmary, znacznie gorsze niż najgorszy kod spaghetti, jaki może być przy użyciu goto.

Zastrzeżenie: nie mam dogłębnego zrozumienia kontynuacji w Scali, po prostu wywnioskowałem to na podstawie spojrzenia na przykłady i znając kontynuacje ze Scheme.

Z mojego punktu widzenia najlepsze wyjaśnienie znalazło się tutaj: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Jeden z przykładów:

Aby lepiej zobaczyć przepływ sterowania, możesz wykonać ten fragment kodu:

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")
}

Oto dane wyjściowe otrzymane przez powyższy kod:

A
B
D
E
G
F
C

Kolejny (nowszy - maj 2016) artykuł na temat kontynuacji Scali to:
" Podróż w czasie w Scali: CPS w Scali (kontynuacja scali shiv4nsh) " autorstwa Shivansha Srivastavy ( ) .
Dotyczy to również Jim McBeath 's artykule wymienionym w Dmitry Bespalov ' s odpowiedź .

Ale wcześniej opisuje Kontynuacje w następujący sposób:

Kontynuacja jest abstrakcyjną reprezentacją stanu sterowania programu komputerowego .
Tak więc w rzeczywistości oznacza to, że jest to struktura danych, która reprezentuje proces obliczeniowy w danym momencie wykonywania procesu; do utworzonej struktury danych można uzyskać dostęp za pomocą języka programowania, zamiast być ukrytym w środowisku wykonawczym.

Aby dokładniej to wyjaśnić, możemy posłużyć się jednym z najbardziej klasycznych przykładów,

Powiedzmy, że jesteś w kuchni przed lodówką i myślisz o kanapce. Bierzesz kontynuację i wkładasz ją do kieszeni.
Następnie wyjmujesz z lodówki indyka i chleb i robisz sobie kanapkę, która teraz leży na blacie.
Wzywasz kontynuację w kieszeni i znowu stoisz przed lodówką, myśląc o kanapce. Ale na szczęście na blacie leży kanapka i wszystkie materiały użyte do jej wykonania zniknęły. Więc jesz. :-)

W tym opisie sandwichjest częścią danych programu (np. Obiekt na stercie) i zamiast wywoływać procedurę „ make sandwich”, a następnie zwracać, osoba nazywana procedurą „ make sandwich with current continuation”, która tworzy kanapkę i kontynuuje wykonywanie odpuścić.

To powiedziawszy, jak ogłoszono w kwietniu 2014 r. Dla Scala 2.11.0-RC1

Poszukujemy opiekunów do przejęcia następujących modułów: scala-swing , scala-continuations .
2.12 nie uwzględni ich, jeśli nie zostanie znaleziony nowy opiekun .
Prawdopodobnie będziemy nadal utrzymywać pozostałe moduły (scala-xml, scala-parser-combinators), ale pomoc jest nadal bardzo ceniona.

Kontynuacje Scali poprzez znaczące przykłady

Zdefiniujmy, from0to10co wyraża ideę iteracji od 0 do 10:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Teraz,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

wydruki:

0 1 2 3 4 5 6 7 8 9 10 

W rzeczywistości nie potrzebujemy x:

reset {
  print(s"${from0to10()} ")
}
println()

drukuje ten sam wynik.

I

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

drukuje wszystkie pary:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Jak to działa?

Jest to nazywane kod , from0to10oraz kod wywołujący . W tym przypadku jest to następny blok reset. Jednym z parametrów przekazywanych do wywoływanego kodu jest adres zwrotny, który pokazuje, która część kodu wywołującego nie została jeszcze wykonana (**). Ta część kodu wywołującego jest kontynuacją . Wywołany kod może zrobić z tym parametrem wszystko, co zdecyduje: przekazać mu kontrolę, zignorować lub wywołać go wiele razy. Tutaj from0to10wywołuje tę kontynuację dla każdej liczby całkowitej z zakresu 0..10.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

Ale gdzie kończy się kontynuacja? Jest to ważne, ponieważ ostatni returnz powrotów do kontynuacji kontrolować zwanego kodu from0to10. W Scali kończy się tam, gdzie kończy się resetblok (*).

Teraz widzimy, że kontynuacja jest zadeklarowana jako cont: Int => Unit. Czemu? Wywołujemy from0to10jako val x = from0to10()i Intjest to typ wartości, do której trafia x. Unitoznacza, że ​​blok po nie resetmoże zwracać żadnej wartości (w przeciwnym razie wystąpi błąd typu). Ogólnie rzecz biorąc, istnieją 4 rodzaje sygnatur: wejście funkcji, wejście kontynuacji, wynik kontynuacji, wynik funkcji. Wszystkie cztery muszą pasować do kontekstu wywołania.

Powyżej wydrukowaliśmy pary wartości. Wydrukujmy tabliczkę mnożenia. Ale jak wyprowadzamy dane \npo każdym wierszu?

Funkcja backpozwala nam określić, co należy zrobić, gdy sterowanie wróci, od kontynuacji do kodu, który ją wywołał.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

backnajpierw wywołuje jego kontynuację, a następnie wykonuje akcję .

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

Drukuje:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Cóż, teraz czas na kilka łamigłówek. Istnieją dwa wywołania from0to10. Jaka jest kontynuacja pierwszego from0to10? Następuje po wywołaniu from0to10w kodzie binarnym , ale w kodzie źródłowym zawiera również instrukcję przypisania val i =. Kończy się tam, gdzie kończy się resetblok, ale koniec resetbloku nie zwraca kontroli do pierwszego from0to10. Koniec resetzwrotu bloku sterowania do 2 from0to10, które z kolei ostatecznie zwraca kontrolę back, a to back, że sterowanie powraca do pierwszej pw from0to10. Kiedy pierwszy (tak! Pierwszy!) from0to10Wyjdzie, następuje wyjście z całego resetbloku.

Taki sposób przywracania kontroli nazywa się cofaniem , jest to bardzo stara technika, znana przynajmniej z czasów Prologu i zorientowanych na AI pochodnych Lispa.

Nazwy reseti shiftsą błędne. Te nazwy lepiej pozostawić dla operacji bitowych. resetdefiniuje granice kontynuacji i shiftpobiera kontynuację ze stosu wywołań.

Uwagi

(*) W Scali kontynuacja kończy się tam, gdzie kończy się resetblok. Innym możliwym podejściem byłoby pozostawienie jej końca tam, gdzie kończy się funkcja.

(**) Jednym z parametrów wywoływanego kodu jest adres zwrotny, który pokazuje, która część kodu wywołującego nie została jeszcze wykonana. Cóż, w Scali używa się do tego sekwencji adresów zwrotnych. Ile? Wszystkie adresy zwrotne umieszczone na stosie wywołań od momentu wejścia do resetbloku.

UPD Część 2 Odrzucanie Kontynuacji: Filtrowanie

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

To drukuje:

0 2 4 6 8 10 

Rozważmy dwie ważne operacje: odrzucenie kontynuacji ( fail()) i przekazanie jej kontroli ( succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

Obie wersje succ()(powyżej) działają. Okazuje się, że shiftma zabawny podpis i chociaż succ()nic nie robi, to musi mieć ten podpis dla balansu typu.

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

zgodnie z oczekiwaniami, drukuje

0 2 4 6 8 10

W ramach funkcji succ()nie jest konieczne:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

znowu drukuje

0 2 4 6 8 10

Teraz zdefiniujmy onOdd()przez onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Powyżej, jeśli xjest równe, zgłaszany jest wyjątek, a kontynuacja nie jest wywoływana; jeśli xjest nieparzyste, wyjątek nie jest zgłaszany i wywoływana jest kontynuacja. Powyższy kod drukuje:

1 3 5 7 9