O que são continuações do Scala e por que usá-las?

Acabei de terminar a programação em Scala e estive examinando as mudanças entre Scala 2.7 e 2.8. O que parece ser o mais importante é o plugin de continuação, mas não entendo para que ele é útil ou como funciona. Percebi que isso é bom para E / S assíncrona, mas não consegui descobrir o porquê. Alguns dos recursos mais populares sobre o assunto são:

• Continuações delimitadas e Scala
• Ir para o Scala
• A Taste of 2.8: Continuations
• Continuações delimitadas explicadas (em Scala)

E esta pergunta no Stack Overflow:

• Quais são as maiores diferenças entre Scala 2.8 e Scala 2.7?

Infelizmente, nenhuma dessas referências tenta definir para que servem as continuações ou o que as funções shift / reset devem fazer, e não encontrei nenhuma referência que o faça. Não consegui adivinhar como nenhum dos exemplos nos artigos vinculados funciona (ou o que eles fazem), então uma maneira de me ajudar poderia ser examinando uma dessas amostras, linha por linha. Mesmo este simples do terceiro artigo:

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

Por que o resultado é 8? Isso provavelmente me ajudaria a começar.

Meu blog explica o que resete o que shiftfazer, então você pode querer ler isso novamente.

Outra boa fonte, que também aponto no meu blog, é a entrada da Wikipedia sobre estilo de passagem de continuação . Esse é, de longe, o mais claro sobre o assunto, embora não use a sintaxe Scala e a continuação seja explicitamente passada.

O artigo sobre continuações delimitadas, para o qual faço um link em meu blog, mas parece ter ficado quebrado, dá muitos exemplos de uso.

Mas acho que o melhor exemplo do conceito de continuações delimitadas é Scala Swarm. Nele, a biblioteca interrompe a execução de seu código em um ponto e o cálculo restante se torna a continuação. A biblioteca então faz alguma coisa - neste caso, transfere o cálculo para outro host e retorna o resultado (o valor da variável que foi acessada) para o cálculo que foi interrompido.

Agora, você não entende mesmo o simples exemplo na página Scala, de modo que ler o meu blog. Nele estou apenas preocupado em explicar esses fundamentos, de por que o resultado é 8.

Achei as explicações existentes menos eficazes para explicar o conceito do que eu esperava. Espero que este esteja claro (e correto.) Não usei continuações ainda.

Quando uma função de continuação cfé chamada:

1. A execução pula o resto do shiftbloco e começa novamente no final dele
   • o parâmetro passado cfé o que o shiftbloco "avalia" à medida que a execução continua. isso pode ser diferente para cada chamada paracf
2. A execução continua até o final do resetbloco (ou até uma chamada para resetse não houver bloqueio)
   • o resultado do resetbloco (ou o parâmetro para reset() se não houver bloco) é o que cfretorna
3. A execução continua cfaté o final do shiftbloco
4. A execução salta até o final do resetbloco (ou uma chamada para reiniciar?)

Portanto, neste exemplo, siga as letras de A a 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

Isso imprime:

11
101

Dado o exemplo canônico do artigo de pesquisa para as continuações delimitadas de Scala, foi ligeiramente modificado para que a função de entrada para shiftreceba o nome fe, portanto, não seja mais anônima.

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

O plugin Scala transforma este exemplo de forma que a computação (dentro do argumento de entrada de reset) começando de cada shiftpara a invocação de resetseja substituída pela função (por exemplo f) entrada para shift.

O cálculo substituído é deslocado (ou seja, movido) para uma função k. A função finsere a função k, onde k contém o cálculo substituído, as kentradas x: Inte o cálculo em ksubstitui shift(f)com x.

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

Que tem o mesmo efeito que:

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

Observe que o tipo Intdo parâmetro de entrada x(ou seja, a assinatura de tipo de k) foi fornecido pela assinatura de tipo do parâmetro de entrada de f.

Outro exemplo emprestado com a abstração conceitualmente equivalente, ou seja, readé a entrada da função para 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)
}

Eu acredito que isso seria traduzido para o equivalente lógico de:

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

Espero que isso elucide a abstração comum coerente que foi um tanto ofuscada pela apresentação anterior desses dois exemplos. Por exemplo, o primeiro exemplo canônico foi apresentado no trabalho de pesquisa como uma função anônima, em vez do meu chamado f, portanto, não estava claro imediatamente para alguns leitores que era abstratamente análogo ao readdo emprestado segundo exemplo.

Assim, continuações delimitadas criam a ilusão de uma inversão de controle de "você me chama de fora de reset" para "eu te chamo de dentro reset".

Observe que o tipo de retorno de fé, mas knão é, obrigatório que seja o mesmo que o tipo de retorno de reset, ou seja, ftem a liberdade de declarar qualquer tipo de retorno kdesde que fretorne o mesmo tipo que reset. Idem para reade capture(veja também ENVabaixo).

Continuações delimitadas não invertem implicitamente o controle de estado, por exemplo, reade callbacknão são funções puras. Assim, o chamador não pode criar expressões referencialmente transparentes e, portanto, não tem controle declarativo (também conhecido como transparente) sobre a semântica imperativa pretendida .

Podemos alcançar funções puras explicitamente com continuações delimitadas.

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

Eu acredito que isso seria traduzido para o equivalente lógico de:

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

Isso está ficando barulhento, por causa do ambiente explícito.

Observe tangencialmente, Scala não tem inferência de tipo global de Haskell e, portanto, até onde eu sei, não poderia suportar o levantamento implícito para uma mônada estadual unit(como uma estratégia possível para ocultar o ambiente explícito), porque a inferência de tipo global de Haskell (Hindley-Milner) depende de não suportar herança virtual múltipla de diamante .

A continuação captura o estado de um cálculo, para ser invocado mais tarde.

Pense no cálculo entre deixar a expressão shift e deixar a expressão reset como uma função. Dentro da expressão shift esta função é chamada de k, é a continuação. Você pode distribuí-lo e invocá-lo mais tarde, até mais de uma vez.

Acho que o valor retornado pela expressão de reset é o valor da expressão dentro da expressão shift após =>, mas sobre isso não tenho certeza.

Assim, com continuações, você pode agrupar um pedaço de código bastante arbitrário e não local em uma função. Isso pode ser usado para implementar o fluxo de controle não padrão, como co-roteamento ou retrocesso.

Portanto, as continuações devem ser usadas no nível do sistema. Espalhá-los no código do aplicativo seria uma receita certa para pesadelos, muito pior do que o pior código espaguete usando goto poderia ser.

Isenção de responsabilidade: eu não tenho um entendimento profundo das continuações no Scala, apenas inferi olhando os exemplos e sabendo das continuações do Scheme.

Do meu ponto de vista, a melhor explicação foi dada aqui: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Um dos exemplos:

Para ver o fluxo de controle com um pouco mais de clareza, você pode executar este snippet de código:

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

Esta é a saída que o código acima produz:

A
B
D
E
G
F
C

Outro artigo (mais recente - maio de 2016) sobre continuações de Scala é:
" Viagem no tempo em Scala: CPS em Scala (continuação de scala) " por Shivansh Srivastava ( shiv4nsh) .
Também se refere a Jim McBeath do artigo mencionado no Dmitry Bespalov 's resposta .

Mas antes disso, ele descreve continuações assim:

Uma continuação é uma representação abstrata do estado de controle de um programa de computador .
Então, o que realmente significa é que é uma estrutura de dados que representa o processo computacional em um determinado ponto da execução do processo; a estrutura de dados criada pode ser acessada pela linguagem de programação, em vez de ficar oculta no ambiente de execução.

Para explicar melhor, podemos ter um dos exemplos mais clássicos,

Digamos que você esteja na cozinha em frente à geladeira, pensando em um sanduíche. Você pega uma continuação ali mesmo e a coloca no bolso.
Então você pega um pouco de peru e pão da geladeira e faz um sanduíche, que agora está no balcão.
Você invoca a continuação no bolso e se vê de novo diante da geladeira, pensando em um sanduíche. Mas, felizmente, há um sanduíche no balcão e todos os materiais usados ​​para fazê-lo se foram. Então você come. :-)

Nesta descrição, o sandwichfaz parte dos dados do programa (por exemplo, um objeto na pilha), e em vez de chamar uma make sandwichrotina “ ” e depois retornar, a pessoa chamou uma make sandwich with current continuationrotina “ ”, que cria o sanduíche e continua onde a execução deixado de fora.

Dito isso, conforme anunciado em abril de 2014 para Scala 2.11.0-RC1

Estamos procurando mantenedores para assumir os seguintes módulos: scala-swing , scala-continuations .
2.12 não os incluirá se nenhum novo mantenedor for encontrado .
Provavelmente continuaremos mantendo os outros módulos (scala-xml, scala-parser-combinators), mas a ajuda ainda é muito apreciada.

Continuações de Scala por meio de exemplos significativos

Vamos definir o from0to10que expressa a ideia de iteração de 0 a 10:

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

Agora,

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

estampas:

0 1 2 3 4 5 6 7 8 9 10 

Na verdade, não precisamos x:

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

imprime o mesmo resultado.

E

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

imprime todos os pares:

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

Agora, como isso funciona?

Há o código de chamada , from0to10e o código de chamada . Nesse caso, é o bloco que se segue reset. Um dos parâmetros passados ​​para o código chamado é um endereço de retorno que mostra qual parte do código de chamada ainda não foi executada (**). Essa parte do código de chamada é a continuação . O código chamado pode fazer com aquele parâmetro tudo o que decidir: passar o controle para ele, ou ignorar, ou chamá-lo várias vezes. Aqui from0to10chama essa continuação para cada inteiro no intervalo de 0 a 10.

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

Mas onde termina a continuação? Isso é importante porque o último returnda continuação retorna o controle para o código chamado from0to10,. No Scala, termina onde o resetbloco termina (*).

Agora, vemos que a continuação é declarada como cont: Int => Unit. Por quê? Chamamos from0to10as val x = from0to10()e Inté o tipo de valor que vai para x. Unitsignifica que o bloco posterior não resetdeve retornar nenhum valor (caso contrário, haverá um erro de tipo). Em geral, existem 4 tipos de assinaturas: entrada de função, entrada de continuação, resultado de continuação, resultado de função. Todos os quatro devem corresponder ao contexto de invocação.

Acima, imprimimos pares de valores. Vamos imprimir a tabuada de multiplicação. Mas como fazemos a saída \napós cada linha?

A função backnos permite especificar o que deve ser feito quando o controle retorna, desde a continuação até o código que o chamou.

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

backprimeiro chama sua continuação e, em seguida, executa a ação .

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

Ele imprime:

   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 

Bem, agora é hora de alguns quebra-cabeças. Existem duas invocações de from0to10. Qual é a continuação do primeiro from0to10? Ele segue a invocação de from0to10no código binário , mas no código-fonte também inclui a instrução de atribuição val i =. Ele termina onde o resetbloco termina, mas o final do resetbloco não retorna o controle para o primeiro from0to10. O final do resetbloco retorna o controle para o segundo from0to10, que por sua vez eventualmente retorna o controle para back, e é ele backque retorna o controle para a primeira invocação de from0to10. Quando o primeiro (sim! 1º!) from0to10Sai, todo o resetbloco é encerrado.

Esse método de retorno de controle é chamado de backtracking , é uma técnica muito antiga, conhecida pelo menos desde os tempos de Prolog e derivados Lisp orientados para IA.

Os nomes resete shiftsão errôneos. Esses nomes deveriam ter sido deixados para as operações bit a bit. resetdefine limites de continuação e shiftobtém uma continuação da pilha de chamadas.

Notas)

(*) Em Scala, a continuação termina onde o resetbloco termina. Outra abordagem possível seria deixar terminar onde termina a função.

(**) Um dos parâmetros do código chamado é um endereço de retorno que mostra qual parte do código de chamada ainda não foi executada. Bem, no Scala, uma sequência de endereços de retorno é usada para isso. Quantos? Todos os endereços de retorno colocados na pilha de chamadas desde a entrada no resetbloco.

UPD Parte 2 Descartando Continuações: Filtragem

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

Isso imprime:

0 2 4 6 8 10 

Vamos fatorar duas operações importantes: descartar a continuação ( fail()) e passar o controle para ela ( 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() }

Ambas as versões de succ()(acima) funcionam. Acontece que shifttem uma assinatura engraçada e, embora succ()não faça nada, deve ter essa assinatura para o equilíbrio do tipo.

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

como esperado, ele imprime

0 2 4 6 8 10

Dentro de uma função, succ()não é necessário:

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

novamente, imprime

0 2 4 6 8 10

Agora, vamos definir onOdd()via 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 ")
}

Acima, se xfor par, uma exceção é lançada e a continuação não é chamada; se xfor ímpar, a exceção não é lançada e a continuação é chamada. O código acima é impresso:

1 3 5 7 9