Qual é o exemplo de uma continuação não implementada como procedimento?

15

Uma discussão interessante sobre a distinção entre retornos de chamada e continuações no SO levou a essa pergunta. Por definição, uma continuação é uma representação abstrata da lógica necessária para concluir um cálculo. Na maioria dos idiomas, isso se manifesta como um procedimento de um argumento para o qual você transmite qualquer valor que precise de processamento contínuo.

Em uma linguagem puramente funcional (onde todas as funções são cidadãos puros e de primeira classe), eu pensaria que uma continuação poderia ser inteiramente modelada como uma função. Afinal, é assim que eu entendi as continuações até esse ponto. No entanto, o mundo está cheio de estado (suspiro) e, portanto, a definição geral não exige que um programa de captura de continuação exiba - ele precisa apenas incluir intenção.

Para ajudar meu entendimento, um exemplo pode ser fornecido em uma linguagem funcional em que a continuação é expressa de uma maneira mais abstrata do que uma função? Eu sei que o Scheme permite que você pegue a continuação atual de uma maneira de primeira classe (call / cc), mas mesmo assim, parece que o procedimento de um argumento passado para chamar / cc recebe simplesmente a continuação atual na forma de outro procedimento de argumento ao qual a função call / cc'd pode aplicar seu resultado.

David Cowden
fonte
Talvez a interseção de continências e a desfuncionalização como: continuações podem ser convertidas em estruturas de dados via desfuncionalização; pode ser uma área interessante de se olhar.
Dan D.
@DanD. você tem alguma sugestão para literatura interessante que eu possa ler? Esse tópico parece útil.
precisa saber é o seguinte

Respostas:

11

tl; dr; O tipo é a abstração abrangente em uma continuação


Uma continuação é o tipo de suas entradas e saídas

A coisa mais próxima que você encontrará de uma continuação não baseada em procedimentos é provavelmente a mônada de continuação em Haskell , pois é expressa como um tipo, para o qual muitas funções podem ser usadas para interagir com o tipo de interrupção, retomada, retorno, etc.

Você pode encapsular esse fechamento em um tipo como o Conttipo em Haskell, onde você obtém a abstração de mônada como uma "abstração de nível superior", e existem outras formas de abstração nas continuações que você obtém quando vê a continuação como um tipo, em vez de simplesmente um procedimento , por exemplo

  • Você pode fazer duas continuações e fazer uma alternativa entre elas se o tipo seguir as leis para ser um monóide
  • Você pode abstrair sobre o tipo para alterar os tipos de entrada ou saída da continuação se você encapsular o fechamento em um tipo que cumpra as leis de um functor
  • Você pode aplicar ou decorar arbitrariamente e parcialmente sua continuação com funcionalidades como validação de entrada ou conversão de entrada se encapsular o fechamento de um tipo que siga as leis de um functor aplicador

Encerramento x Procedimento

No final do dia, você está basicamente certo; uma continuação é um "procedimento", embora eu prefira me referir a ele como um encerramento. Muitas vezes, as continuações são melhor expressas como fechamentos de primeira classe que encerram um ambiente vinculado. Em uma linguagem funcional pura, você pode dizer que isso não é particularmente razoável porque lhe faltam referências; isso é verdade, mas você pode incluir valores e a atribuição única faz com que o valor e a referência sejam exatamente a mesma coisa. Isso dá origem a Haskell:

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

Um idioma que carece da capacidade de incluir um ambiente vinculativo pode tecnicamente carecer de fechamentos de primeira classe, mas mesmo assim há algum ambiente (geralmente o global) disponível para o fechamento.

Então, eu diria que é mais preciso descrever uma continuação como: Um fechamento sendo usado de uma maneira específica.


Conclusão

Para a pergunta "Uma continuação é implementável de alguma maneira que não seja um procedimento?" Não. Se você não possui funções de primeira classe, não pode ter continuações como tal (sim, os ponteiros de função contam como funções de primeira classe, portanto, alternativamente, o acesso arbitrário à memória pode ser suficiente).

Agora, para a pergunta "Existe alguma maneira de expressar uma continuação de uma maneira mais abstrata do que um procedimento?" Expressá-lo como um tipo fornece uma abstração muito maior, permitindo tratar a continuação de maneiras muito gerais, de modo que você possa interagir com a continuação de muitas outras maneiras além de executá-la.

Jimmy Hoffa
fonte
1
Isso generaliza para "Uma continuação pode ser simplesmente qualquer coisa que permita obter o resultado do restante do programa". Como isso normalmente exige um código (o restante do programa), a maioria dos idiomas usa funções. Teoricamente, você pode construir uma continuação de qualquer coisa. Durante a conversão de continuação em meus compiladores, usei árvores parcialmente preenchidas.
Daniel Gratzer
1
As árvores parcialmente preenchidas pelo @jozefg são uma representação adequada de um cálculo como uma expressão, mas no final do dia o código real sendo escrito é uma expressão que não pode ser identificávelmente diferente de um procedimento, como eu o entendo. Além disso, árvores parcialmente preenchidas são a representação do compilador; a representação dos desenvolvedores é, com expectativa, uma expressão computacional normativa com a sintaxe e a semântica da linguagem, que pareceria para 99% dos desenvolvedores como um "procedimento", "função" ou outro. Você está pensando do ponto de vista heh do desenvolvedor do compilador
Jimmy Hoffa
2

Um exemplo que você pode gostar são as corotinas. Por exemplo, as Coroutines de Lua ou os iteradores / geradores de Python ou C # são semelhantes em poder às continuações de uma só vez (continuações que você só pode chamar uma vez), mas a continuação não é explicitamente transformada em função. Em vez disso, você tem maneiras de avançar a corotina até a próxima instrução "yield".

Por exemplo, considere o seguinte programa 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

É semelhante ao seguinte programa Javascript com retornos de chamada explícitos:

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

O exemplo de Javascript é meio barulhento, porque cada etapa precisa retornar a próxima continuação, além de retornar o valor gerado (no Python mantém o controle da continuação dentro do ite

hugomg
fonte