Continuação - Continuation

Para outros usos, consulte Continuação (desambiguação) .

Na ciência da computação , uma continuação é uma representação abstrata do estado de controle de um programa de computador . Uma continuação implementa ( reifica ) o estado de controle do programa, ou seja, a continuação é 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 . Continuações são úteis para codificar outros mecanismos de controle em linguagens de programação, como exceções , geradores , corrotinas e assim por diante.

A " continuação atual " ou "continuação da etapa de cálculo" é a continuação que, da perspectiva do código em execução, seria derivada do ponto atual na execução de um programa. O termo continuações também pode ser usado para se referir a continuações de primeira classe , que são construções que fornecem a uma linguagem de programação a capacidade de salvar o estado de execução em qualquer ponto e retornar a esse ponto em um ponto posterior do programa, possivelmente várias vezes.

História

A primeira descrição das continuações foi feita por Adriaan van Wijngaarden em setembro de 1964. Wijngaarden falou na Conferência de Trabalho da IFIP sobre Linguagens de Descrição de Linguagem Formal realizada em Baden bei Wien, Áustria. Como parte de uma formulação para um pré-processador Algol 60 , ele pediu uma transformação dos procedimentos apropriados em um estilo de passagem de continuação , embora não tenha usado esse nome, e sua intenção era simplificar um programa e, assim, tornar seu resultado mais claro.

Christopher Strachey , Christopher P. Wadsworth e John C. Reynolds trouxeram o termo continuação em destaque em seu trabalho no campo da semântica denotacional que faz uso extensivo de continuações para permitir que programas sequenciais sejam analisados ​​em termos de semântica de programação funcional .

Steve Russell inventou a continuação em sua segunda implementação do Lisp para o IBM 704 , embora não tenha dado o nome.

Reynolds (1993) dá uma história completa da descoberta de continuações.

Continuações de primeira classe

As continuações de primeira classe são a capacidade da linguagem de controlar completamente a ordem de execução das instruções. Eles podem ser usados ​​para pular para uma função que produziu a chamada para a função atual ou para uma função que já foi encerrada. Pode-se pensar em uma continuação de primeira classe como salvando o estado de execução do programa. É importante notar que continuações verdadeiras de primeira classe não salvam dados do programa - ao contrário de uma imagem de processo - apenas o contexto de execução. Isso é ilustrado pela descrição do "sanduíche de continuação":

Digamos que você esteja na cozinha em frente à geladeira, pensando em um sanduíche. Você pega uma continuação ali e enfia 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 em seu bolso e se vê novamente 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 sanduíche faz parte dos dados do programa (por exemplo, um objeto no heap) e, em vez de chamar uma rotina de "fazer sanduíche" e retornar, a pessoa chamou uma rotina de "fazer sanduíche com continuação de corrente", que cria o sanduíche e continua de onde a execução parou.

Scheme foi o primeiro sistema de produção completo (1969-1970), fornecendo primeiro "catch" e depois call / cc . Bruce Duba introduziu call / cc no SML .

Continuações também são usadas em modelos de computação, incluindo semântica denotacional , o modelo de ator , cálculos de processo e cálculo lambda . Esses modelos contam com programadores ou engenheiros de semântica para escrever funções matemáticas no chamado estilo de passagem de continuação . Isso significa que cada função consome uma função que representa o restante do cálculo em relação a essa chamada de função. Para retornar um valor, a função chama esta "função de continuação" com um valor de retorno; para abortar o cálculo, ele retorna um valor.

Os programadores funcionais que escrevem seus programas no estilo de passagem de continuação ganham o poder expressivo de manipular o fluxo de controle de maneiras arbitrárias. O custo é que eles devem manter os invariantes de controle e continuações manualmente, o que pode ser um empreendimento altamente complexo (mas consulte 'estilo de passagem de continuação' abaixo).

Usos

As continuações simplificam e esclarecem a implementação de vários padrões de design comuns , incluindo corrotinas / threads verdes e tratamento de exceções , fornecendo o primitivo básico de baixo nível que unifica esses padrões aparentemente desconectados. As continuações podem fornecer soluções elegantes para alguns problemas difíceis de alto nível, como a programação de um servidor da web que ofereça suporte a várias páginas, acessadas pelo uso dos botões avançar e voltar e pelos links seguintes. O framework da Web Smalltalk Seaside usa continuações com grande efeito, permitindo programar o servidor da Web em estilo procedural, alternando as continuações ao alternar as páginas.

Construções mais complexas para as quais "continuações fornecem uma descrição elegante" também existem. Por exemplo, em C , longjmp pode ser usado para pular do meio de uma função para outra, desde que a segunda função esteja mais abaixo na pilha (se estiver esperando o retorno da primeira função, possivelmente entre outras). Outros exemplos mais complexos incluem co - rotinas em Simula 67 , Lua e Perl ; tasklets em Stackless Python ; geradores em Icon e Python ; continuações em Scala (começando em 2.8); fibras em Ruby (começando em 1.9.1); o mecanismo de retrocesso no Prolog ; mônadas em programação funcional ; e tópicos .

Exemplos

A linguagem de programação Scheme inclui o operador de controle call-with-current-continuation (abreviado como: call / cc) com o qual um programa Scheme pode manipular o fluxo de controle: 

 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; call/cc calls its first function argument, passing
     ; a continuation variable representing this point in
     ; the program as the argument to that function.
     ;
     ; In this case, the function argument assigns that
     ; continuation to the variable the-continuation.
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; The next time the-continuation is called, we start here.
     (set! i (+ i 1))
     i))

Usando o acima, o seguinte bloco de código define uma função testque define the-continuationo estado de execução futura de si mesma: 

 > (test)
 1
 > (the-continuation)
 2
 > (the-continuation)
 3
 > ; stores the current continuation (which will print 4 next) away
 > (define another-continuation the-continuation)
 > (test) ; resets the-continuation
 1
 > (the-continuation)
 2
 > (another-continuation) ; uses the previously stored continuation
 4

Para uma introdução mais suave a esse mecanismo, consulte call-with-current-continuation .

Corrotinas

Este exemplo mostra um possível uso de continuações para implementar co-rotinas como threads separados. 

 ;;; A naive queue for thread scheduling.
 ;;; It holds a list of continuations "waiting to run".

   (define *queue* '())

   (define (empty-queue?)
     (null? *queue*))

   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))

   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

   ;;; This starts a new thread running (proc).

   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

   ;;; This yields the processor to another thread, if there is one.

   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

   ;;; This terminates the current thread, or the entire program
   ;;; if there are no other threads left.

   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

As funções definidas acima permitem definir e executar threads por meio de multitarefa cooperativa , ou seja, threads que fornecem controle para o próximo em uma fila: 

   ;;; The body of some typical Scheme thread that does stuff:

   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (+ n 1)))))

   ;;; Create two threads, and start them running.
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)

O código anterior produzirá esta saída: 

 This is AAA 0
 Hello from BBB 0
 This is AAA 1
 Hello from BBB 1
 This is AAA 2
 Hello from BBB 2
 ...

Implementação

Um programa deve alocar espaço na memória para as variáveis ​​que suas funções usam. A maioria das linguagens de programação usa uma pilha de chamadas para armazenar as variáveis ​​necessárias porque permite uma alocação rápida e simples e desalocação automática de memória. Outras linguagens de programação usam um heap para isso, o que permite flexibilidade a um custo mais alto para alocar e desalocar memória. Essas duas implementações têm vantagens e desvantagens no contexto de continuações.

Suporte a linguagem de programação

Muitas linguagens de programação exibem continuações de primeira classe sob vários nomes; especificamente:

Em qualquer linguagem que suporte fechamentos e chamadas finais adequadas , é possível escrever programas no estilo continuation-pass e implementar manualmente call / cc. (No estilo de passagem de continuação, call / cc torna-se uma função simples que pode ser escrita com lambda .) Esta é uma estratégia particularmente comum em Haskell , onde é fácil construir uma " mônada de passagem de continuação " (por exemplo, a Contmônada e ContTtransformador monad na mtlbiblioteca). O suporte para chamadas finais adequadas é necessário porque no estilo de passagem de continuação nenhuma função retorna; todas as chamadas são chamadas de cauda.

Em desenvolvimento web

Uma área que viu o uso prático de continuações é a programação da Web . O uso de continuações protege o programador da natureza sem estado do protocolo HTTP . No modelo tradicional de programação web, a falta de estado se reflete na estrutura do programa, levando ao código construído em torno de um modelo que se presta muito mal para expressar problemas computacionais. Assim, as continuações habilitam o código que tem as propriedades úteis associadas à inversão de controle , evitando seus problemas. Invertendo a inversão de controle ou Continuações versus programação centrada na página, é um artigo que fornece uma boa introdução às continuações aplicadas à programação web.

Alguns dos servidores Web com reconhecimento de continuação mais populares são Racket Web Server , UnCommon Web Framework e Weblocks Web framework para Common Lisp , Seaside framework para Smalltalk , Ocsigen / Eliom para OCaml , Continuity for Perl , Wee for Ruby , Tales Framework para Fantom e o framework Nagare para Python , Wt para C ++ , MFlow para Haskell . A estrutura do aplicativo da Web Apache Cocoon também fornece continuações (consulte o manual do Cocoon ).

Tipos

O suporte para continuações varia amplamente. Uma linguagem de programação suporta continuações re-invocáveis se uma continuação pode ser invocada repetidamente (mesmo depois de já ter retornado). Continuações re-invocáveis ​​foram introduzidas por Peter J. Landin usando seu operador J (para Jump) que poderia transferir o fluxo de controle de volta para o meio de uma invocação de procedimento. Continuações re-invocáveis ​​também foram chamadas de "reentrantes" na linguagem Racket . No entanto, esse uso do termo "reentrante" pode ser facilmente confundido com seu uso em discussões de multithreading .

Um tipo mais limitado é a continuação de escape que pode ser usada para escapar do contexto atual para um contexto circundante. Muitas linguagens que não suportam explicitamente continuações suportam tratamento de exceção , que é equivalente a escapar de continuações e pode ser usado para os mesmos propósitos. C's setjmp/longjmptambém são equivalentes: eles só podem ser usados ​​para desenrolar a pilha. As continuações de escape também podem ser usadas para implementar a eliminação da chamada final .

Uma generalização de continuações são continuações delimitadas . Os operadores de continuação, como call/cccapturar todo o cálculo restante em um determinado ponto do programa, não fornecem nenhuma maneira de delimitar essa captura. Os operadores de continuação delimitados tratam disso fornecendo dois mecanismos de controle separados: um prompt que delimita uma operação de continuação e um operador de reificação como shiftou control. Continuações capturadas usando operadores delimitados, portanto, representam apenas uma parte do contexto do programa.

Desvantagens

Continuações são a expressão funcional da instrução GOTO , e as mesmas advertências se aplicam. Embora sejam uma opção sensata em alguns casos especiais, como programação da web, o uso de continuações pode resultar em um código difícil de seguir. Na verdade, a linguagem de programação esotérica Unlambda inclui call-with-current-continuation como um de seus recursos unicamente porque as expressões que a envolvem "tendem a ser extremamente difíceis de rastrear". Os links externos abaixo ilustram o conceito com mais detalhes.

Linguística

Em "Continuações e a natureza da quantificação", Chris Barker introduziu a "hipótese de continuação", que

algumas expressões linguísticas (em particular, QNPs [sintagmas nominais quantificacionais]) têm denotações que manipulam suas próprias continuações.

Barker argumentou que esta hipótese poderia ser usada para explicar fenômenos como dualidade de significado de NP (por exemplo, o fato de que o QNP "todos" se comporta de maneira muito diferente do sintagma nominal não quantificado "Bob" ao contribuir para o significado de uma frase como "Alice vê [Bob / todos]"), deslocamento do escopo (por exemplo, que "uma gota de chuva caiu em todos os carros" é interpretado normalmente como e não como ) e ambigüidade do escopo (que uma frase como "alguém viu todos" pode ser ambígua entre e ). Ele também observou que essa ideia é, de certa forma, apenas uma extensão natural da abordagem de Richard Montague em "O Tratamento Adequado da Quantificação em Inglês Comum" (PTQ), escrevendo que "com o benefício da retrospectiva, uma forma limitada de passagem de continuação é claramente discernível no núcleo do tratamento PTQ de Montague (1973) de NPs como quantificadores generalizados ".

Até que ponto as continuações podem ser usadas para explicar outros fenômenos gerais na linguagem natural é um tópico de pesquisa atual.

Veja também

Referências

Leitura adicional

  • Peter Landin . Relatório de generalização de saltos e rótulos . UNIVAC Systems Programming Research. Agosto de 1965. Reimpresso em Ordem Superior e Computação Simbólica, 11 (2): 125-143, 1998, com um prefácio de Hayo Thielecke.
  • Drew McDermott e Gerry Sussman . The Conniver Reference Manual MIT AI Memo 259. Maio de 1972.
  • Daniel Bobrow : Um Modelo para Estruturas de Controle para Linguagens de Programação de Inteligência Artificial IJCAI 1973.
  • Carl Hewitt , Peter Bishop e Richard Steiger . A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
  • Christopher Strachey e Christopher P. Wadsworth . Continuações: a Semântica matemática para lidar com saltos completos Monografia Técnica PRG-11. Laboratório de Computação da Universidade de Oxford. Janeiro de 1974. Reimpresso em Higher Order and Symbolic Computation, 13 (1/2): 135-152, 2000, com um prefácio de Christopher P. Wadsworth.
  • John C. Reynolds . Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, pp. 717–740, 1972. Reimpresso em Higher-Order and Symbolic Computation 11 (4): 363-397, 1998, com um prefácio.
  • John C. Reynolds. Sobre a relação entre os procedimentos de semântica direta e de continuação do segundo colóquio sobre autômatos, linguagens e programação. LNCS Vol. 14, pp. 141–156, 1974.
  • Reynolds, John C. (1993). "As descobertas das continuações" (PDF) . Lisp e computação simbólica . 6 (3/4): 233–248.
  • Gerald Sussman e Guy Steele . ESQUEMA: Um intérprete para Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, dezembro de 1975. Reimpresso em Higher-Order and Symbolic Computation 11 (4): 405-439, 1998, com um prefácio.
  • Robert Hieb , R. Kent Dybvig , Carl Bruggeman . Representando o Controle na Presença de Procedimentos de Continuações de Primeira Classe da Conferência ACM SIGPLAN '90 sobre Design e Implementação de Linguagem de Programação, pp. 66–77.
  • Will Clinger , Anne Hartheimer , Eric Ost . Implementation Strategies for Continuations Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp. 124–131, 1988. Journal version: Higher-Order and Symbolic Computation, 12 (1): 7-45, 1999.
  • Christian Queinnec . Invertendo a inversão de controle ou, Continuações versus programação centrada na página SIGPLAN Avisos 38 (2), pp. 57–64, 2003.

links externos