Por Que Continuations São Tão Legais?

A maneira usual de controlar o fluxo de execução de um programa de computador é via chamadas e retornos de procedimentos; uma pilha estrutura de dados é como linguagens de programação de alto nível mantém rastreamento do ponto ao qual cada sub-rotina ativa deve retornar o controle quando termina de executar.

Infelizmente, você precisará de mais do que isso se pretende escrever programas úteis para resolver problemas do mundo real. É por isso que a maioria das linguagens de programação de alto nível também fornecem outras primitivas de fluxo de controle, como a declaração goto, loops e tratamento de exceções.

Não estou dizendo que implementar uma linguagem de programação é uma tarefa fácil, mas deixando isso de lado por um momento, é como se as linguagens de programação em geral lutassem o máximo que podem para tornar a pilha de chamadas algo tão oculto e intangível quanto possível - algo que ninguém além dela mesma tem permissão para controlar.

O que aconteceria se algumas linguagens de programação, em vez de manter a pilha de chamadas dentro de um cofre de aço sólido de 2", na verdade dessem aos programadores a habilidade de “capturá-las” como funções que podem ser invocadas, armazenadas e passadas como valores?

Neste post, espero mostrar o que continuations são e como podem ser usadas em situações práticas. Então pegue o Racket e vamos lá!

Atualização (20 de jun, 2014): Mudei algumas coisas neste post em resposta a alguns ótimos comentários nesta discussão no Reddit e neste post de blog por jecxjo.

Primeiro Exemplo

Nota: O problema a seguir é solucionável sem continuations, mas gostaria de começar com algo simples o suficiente.

Suponha que você está escrevendo código que faz interface com alguma API sobre HTTP. Também suponha que esta API requer que um header SessionId seja enviado junto com a requisição para evitar ataques CSRF.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#lang racket/base

;; Object to keep the session-id across requests
(struct session [id #:mutable])

(define (perform-request! session method params)

  ;; Performs the request
  (define headers  (session-id-headers session))
  (define response (http-request API-URL headers method params))

  ;; Retries the request with the given Session-Id
  ;; if necessary
  (when (request-denied? response)
    (update-session-id! session response)
    (perform-request! session method params))

  (parse-json response))

Quando a primeira requisição é enviada - sem o header SessionId - o servidor responde com um erro, i.e. HTTP 409, caso no qual o procedimento atualiza session com o session id fornecido pelo servidor e retenta a requisição.

O código faz sentido, mas está quebrado.

A chamada recursiva não é feita em posição de cauda. Então, quando acontece, outro stack frame é empurrado para a pilha de chamadas e mesmo que a requisição retentada tenha sucesso, o que é retornado ao chamador é a resposta àquela primeira requisição não autorizada.

Se apenas tivéssemos a chance de retornar aquela segunda resposta direto ao chamador em vez de ter a pilha se desenrolando…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(define (perform-request! session method params)
  ;; ...

  (when (request-denied? response)
    (update-session-id! session response)

    ;; Something like this
    (return (perform-request! ...)))

  (parse-json response))

Conheça call/cc

Uma continuation pode ser vista como o contexto de avaliação ao redor de uma expressão ou, em outras palavras, um snapshot do estado de controle atual do programa.

Aqui está um exemplo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#lang racket/base

;; We'll keep the captured continuation here
(define cc #f)

;; This function returns the value 3 *and* stores the
;; continuation that represents the execution context
;; in which this function was called
(define (val!)
  (call/cc
   (lambda (k)
     (set! cc k)
     3)))

;; Stored continuation for this expression: (+ 1 (* 2 ?))
(+ 1 (* 2 (val!))) ;-> 7

;; Replays the continuation with different arguments
(cc 2) ;->  5, or (+ 1 (* 2 2))
(cc 6) ;-> 13, or (+ 1 (* 2 6))

Acontece que, se renomearmos k para return, isso é exatamente o que precisamos para corrigir aquele exemplo de cliente de API quebrado:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

(define (perform-request! session method params)
  (let/cc return ; same as (call/cc (lambda (return) body...))
    ;; ...

    ;; Retries the request and gives the control
    ;; back to the caller if request-denied?
    (when (request-denied? response)
      (update-session-id! session response)
      (return (perform-request! session method params)))

    (parse-json response)))

Agora a função captura a continuation atual no momento em que o procedimento perform-request! é chamado pela primeira vez. Então, se o servidor nega uma requisição, re-enviamos a requisição com o SessionId fornecido e usamos aquela continuation capturada para transferir o controle de volta ao chamador.

Legal, não acha? É como se estivéssemos congelando o tempo em let/cc, fazendo algumas coisas, e então resumindo de lá.

Este é um caso de uso comum de continuations. Confira este projeto se você quiser ler o código que inspirou este exemplo.

Generators

Generators podem ser vistos como rotinas especiais que se comportam como iteradores. Se você está familiarizado com Python, provavelmente viu código como este:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def iterate(list):
  "Generator function that iterates through list."
  for item in list:
    yield item

# Usage
it = iterate(range(2))

it.next() # -> 0
it.next() # -> 1
it.next() # -> raises StopIteration error

Você vê alguma semelhança entre este exemplo e o anterior? Embora Python não forneça uma facilidade call/cc-like na linguagem, pode-se argumentar que seus generators são como uma continuation de pobre.

Vamos fingir por um momento que Racket não tinha uma biblioteca de generator que faz exatamente isso. Como isso poderia ser implementado em Racket usando continuations?

O que precisamos é uma função que retorna outra função que, quando chamada, produz um item de cada vez, até que a lista esteja esgotada.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(define (iterate lst)
  (lambda ()
    (let/cc return
      (for-each
       (lambda (item)
         (return item))
       lst))))

;; Usage
(define next (iterate (range 3)))
(next) ;-> 0
(next) ;-> 0

Este código segue o mesmo padrão dos anteriores, mas não parece funcionar da maneira que você esperaria. A razão deve estar clara: iterate retorna um lambda que usa a continuation capturada para produzir o primeiro item da lista.

Para fazer este código funcionar, precisamos capturar a continuation atual de dentro de for-each e armazená-la para que possa ser usada para resumir a computação quando next for chamada novamente.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

(define (iterate lst)

  ;; Defines `state` as being a function that starts the
  ;; iteration via `for-each`
  (define (state return)
    (for-each
     (lambda (item)

       ;; Here, we capture the continuation that represents the
       ;; current state of the iteration
       (let/cc item-cc

         ;; Before the item is yielded, we update `state` to
         ;; `item-cc` so the computation is resumed the next
         ;; time the generator is called
         (set! state item-cc)

         ;; Yields the current item to the caller
         (return item)))
     lst)

    ;; Yields 'done when the list is exhausted
    (return 'done))

  ;; Returns a function that calls the stored `state` with the
  ;; current continuation so we can yield one item at a time
  (define (generator)
    (call/cc state))
  generator)

;; Usage
(define next (iterate '(0 1)))

(next) ;-> 0
(next) ;-> 1
(next) ;-> 'done

Se você está tendo problemas para entender como este código funciona, o seguinte diagrama pode ajudar.

Outros Exemplos

Passando para coisas de mais alto nível, em este exemplo Matthew Flatt explica como construir um servidor web baseado em continuations em Racket. Ainda no reino de continuation-based-web-sei-lá-o-que, se você está em Smalltalk, não esqueça de conferir Seaside, um framework de aplicação web que usa continuations para modelar múltiplos fluxos independentes entre diferentes componentes.

Se você não programa em Scheme ou Smalltalk para ganhar a vida, não se preocupe. As chances são de que sua linguagem suporte algum sabor de continuations, seja nativamente ou via alguma biblioteca de terceiros.

Conclusão

Parece que continuations podem ser usadas para implementar uma ampla variedade de construções de controle avançadas incluindo non-local exits, tratamento de exceções, backtracking e coroutines.

Neste post, espero ter esclarecido alguns dos aspectos chave sobre continuations. Se você tem alguma sugestão sobre como melhorar este texto, por favor me avise.