O que é um exemplo de uma continuação não implementada como um procedimento?

15

Uma interessante discussão sobre a distinção entre retornos de chamada e continuações no SO geraram essa pergunta. Por definição, uma continuação é uma representação abstrata da lógica necessária para concluir uma computação. Na maioria das linguagens, isso se manifesta como um procedimento de argumento único para o qual você passa qualquer valor que precise ser processado continuamente.

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. Isto é, afinal, como eu já entendi continuações até este ponto. No entanto, o mundo está cheio de estado (suspiro ..) e, portanto, a definição geral não exige que um estado de programa de captura de continuação - ele só precisa abranger a intenção.

Para ajudar na minha compreensão, um exemplo pode ser fornecido em uma linguagem funcional onde 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 é simplesmente dado a continuação atual na forma de outro procedimento de argumento para o qual a função de chamada / cc pode aplicar o seu resultado.

    
por David Cowden 20.09.2013 / 10:29
fonte

2 respostas

11

tl; dr; O tipo é a abstração abrangente sobre 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 monografia de continuação em Haskell . é expresso como um tipo, para o qual muitas funções podem ser usadas para interagir com o tipo para interromper, retomar, retroceder, et al.

Você pode encapsular esse fechamento em um tipo como o tipo Cont em Haskell, onde você obtém a abstração monad como uma "abstração de nível superior", e há outras formas de abstração sobre as continuações que você obtém quando olha para o 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 monoid
  • Você pode abstrair o tipo para alterar os tipos de entrada ou saída da continuação se você encapsular o fechamento em um tipo que respeite as leis de um functor
  • Você pode aplicar ou decorar sua continuação de forma arbitrária e parcial com funcionalidade, como validação de entrada ou conversão de entrada, se você encapsular o fechamento em um tipo que siga as leis de um aplicativo functor

Encerramento vs. Procedimento

No final do dia, você está basicamente certo; uma continuação é um "procedimento", embora prefira referir-se a ela como um encerramento. Muitas vezes as continuações são melhor expressas como encerramentos de primeira classe que incluíram um ambiente vinculado. Em uma linguagem funcional pura, você pode dizer que isso não é particularmente razoável porque você não tem referências; isso é verdade, mas você pode incluir valores e atribuição única faz colocando o valor vs. a referência exatamente a mesma coisa. Isso dá origem a Haskell:

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

Uma linguagem que não tem a capacidade de incluir um ambiente de ligação pode tecnicamente carecer de fechamentos de primeira classe, mas mesmo assim existe algum ambiente (geralmente o global) disponível para o encerramento.

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

Conclusão

À pergunta de "Uma continuação pode ser implementada de alguma forma que não seja um procedimento?" Não. Se você não tiver funções de primeira classe você realmente não pode ter continuações como tal (os ponteiros de função sim contam como funções de primeira classe, então o acesso à memória alternativamente arbitrário pode ser suficiente).

Agora, para a questão de "Existem maneiras de expressar uma continuação de uma maneira mais abstrata do que um procedimento?" Expressá-la como um tipo oferece uma abstração muito maior, permitindo que você trate 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.

    
por 20.09.2013 / 17:20
fonte
2

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

Por exemplo, considere o seguinte programa em 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, pois cada etapa precisa retornar a próxima continuação, além de retornar o valor obtido (no Python, ele acompanha a continuação dentro do ite

    
por 21.09.2013 / 02:58
fonte