Estilo de passagem de continuação - Continuation-passing style

Na programação funcional , o estilo de passagem de continuação ( CPS ) é um estilo de programação no qual o controle é passado explicitamente na forma de uma continuação . Isso é contrastado com o estilo direto , que é o estilo usual de programação. Gerald Jay Sussman e Guy L. Steele, Jr. cunharam a frase em AI Memo 349 (1975), que apresenta a primeira versão da linguagem de programação Scheme . John C. Reynolds dá um relato detalhado das numerosas descobertas de continuações.

Uma função escrita no estilo de passagem de continuação leva um argumento extra: uma "continuação" explícita; ou seja , uma função de um argumento. Quando a função CPS calcula seu valor de resultado, ela o "retorna" chamando a função de continuação com esse valor como argumento. Isso significa que, ao invocar uma função CPS, a função de chamada deve fornecer um procedimento a ser invocado com o valor de "retorno" da sub-rotina. Expressar código nesta forma torna várias coisas explícitas que estão implícitas no estilo direto. Isso inclui: retornos de procedimento, que se tornam aparentes como chamadas para uma continuação; valores intermediários, que são todos nomes dados; ordem de avaliação do argumento, que é explicitada; e chamadas finais , que simplesmente chamam um procedimento com a mesma continuação, sem modificações, que foi passado para o chamador.

Os programas podem ser transformados automaticamente de estilo direto em CPS. Compiladores funcionais e lógicos geralmente usam o CPS como uma representação intermediária onde um compilador para uma linguagem de programação imperativa ou procedural usaria o formulário de atribuição única estática (SSA). SSA é formalmente equivalente a um subconjunto do CPS (excluindo o fluxo de controle não local, que não ocorre quando o CPS é usado como representação intermediária). Compiladores funcionais também podem usar a forma normal A (ANF) (mas apenas para linguagens que requerem avaliação rápida), em vez de ' thunks ' (descrito nos exemplos abaixo) no CPS. O CPS é usado com mais frequência por compiladores do que por programadores como um estilo local ou global.

Exemplos

No CPS, cada procedimento leva um argumento extra que representa o que deve ser feito com o resultado que a função está calculando. Isso, junto com um estilo restritivo que proíbe uma variedade de construções normalmente disponíveis, é usado para expor a semântica dos programas, tornando-os mais fáceis de analisar. Esse estilo também facilita a expressão de estruturas de controle incomuns, como pegar / lançar ou outras transferências de controle não locais.

A chave para o CPS é lembrar que (a) cada função leva um argumento extra conhecido como continuação e (b) cada argumento em uma chamada de função deve ser uma variável ou uma expressão lambda (não uma expressão mais complexa). Isso tem o efeito de virar as expressões "de dentro para fora" porque as partes mais internas da expressão devem ser avaliadas primeiro, portanto, o CPS torna explícita a ordem de avaliação, bem como o fluxo de controle. Alguns exemplos de código no estilo direto e o CPS correspondente aparecem abaixo. Esses exemplos são escritos na linguagem de programação Scheme ; por convenção, a função de continuação é representada como um parâmetro denominado " k":

Estilo direto
Estilo de passe de continuação
 
(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))

(define (factorial n)
 (if (= n 0)
     1     ; NOT tail-recursive
     (* n (factorial (- n 1)))))

(define (factorial& n k)
 (=& n 0 (lambda (b)
          (if b                    ; growing continuation
              (k 1)                ; in the recursive call
              (-& n 1 (lambda (nm1)
                       (factorial& nm1 (lambda (f)
                                        (*& n f k)))))))))

(define (factorial n)
 (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a        ; tail-recursive
     (f-aux (- n 1) (* n a))))

(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
 (=& n 0 (lambda (b)
          (if b                    ; unmodified continuation
              (k a)                ; in the recursive call
              (-& n 1 (lambda (nm1) 
                       (*& n a (lambda (nta)
                                (f-aux& nm1 nta k)))))))))

Observe que nas versões CPS, os primitivos usados, como +&e *&são eles próprios CPS, não estilo direto, portanto, para fazer os exemplos acima funcionarem em um sistema Scheme, precisaríamos escrever essas versões CPS dos primitivos, com, por exemplo, *&definido por: 

(define (*& x y k)
 (k (* x y)))

Para fazer isso em geral, podemos escrever uma rotina de conversão: 

(define (cps-prim f)
 (lambda args
  (let ((r (reverse args)))
   ((car r) (apply f
             (reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))

Para chamar um procedimento escrito no CPS a partir de um procedimento escrito no estilo direto, é necessário fornecer uma continuação que receberá o resultado calculado pelo procedimento CPS. No exemplo acima (assumindo que primitivas de estilo CPS foram fornecidas), podemos chamar (factorial& 10 (lambda (x) (display x) (newline))).

Existe alguma variedade entre os compiladores na maneira como as funções primitivas são fornecidas no CPS. Acima, usamos a convenção mais simples; no entanto, às vezes são fornecidos primitivos booleanos que levam dois thunks para serem chamados nos dois casos possíveis, de modo que a (=& n 0 (lambda (b) (if b ...)))chamada dentro da f-aux&definição acima seria escrita em vez de (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). Da mesma forma, às vezes a ifprópria primitiva não é incluída no CPS e, em vez disso, if&é fornecida uma função que leva três argumentos: uma condição booleana e os dois thunks correspondentes aos dois braços da condicional.

As traduções mostradas acima mostram que o CPS é uma transformação global. O fatorial de estilo direto leva, como era de se esperar, um único argumento; o fatorial CPS e leva dois: o argumento e uma continuação. Qualquer função que chame uma função ed CPS deve fornecer uma nova continuação ou passar a sua própria; quaisquer chamadas de uma função ed CPS para uma função não CPS usarão continuações implícitas. Assim, para garantir a ausência total de uma pilha de funções, todo o programa deve estar no CPS.

CPS em Haskell

Nesta seção, escreveremos uma função pythque calcula a hipotenusa usando o teorema de Pitágoras . Uma implementação tradicional da pythfunção se parece com isto: 

pow2 :: Float -> Float
pow2 a = a ** 2

add :: Float -> Float -> Float
add a b = a + b

pyth :: Float -> Float -> Float
pyth a b = sqrt (add (pow2 a) (pow2 b))

Para transformar a função tradicional em CPS, precisamos mudar sua assinatura. A função obterá outro argumento do tipo de função, e seu tipo de retorno depende dessa função: 

pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function
-- may be viewed as a higher order function
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)

pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))

Primeiro calculamos o quadrado de a em pyth'função e passamos uma função lambda como uma continuação que aceitará um quadrado de a como primeiro argumento. E assim por diante até chegarmos ao resultado de nossos cálculos. Para obter o resultado desta função podemos passar idfunção como um argumento final que retorna o valor que foi passado para ele inalterada: pyth' 3 4 id == 5.0.

A biblioteca mtl, que é enviada com o GHC , tem o módulo Control.Monad.Cont. Este módulo fornece o tipo Cont, que implementa Monad e algumas outras funções úteis. O snippet a seguir mostra a pyth'função usando Cont: 

pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

Não apenas a sintaxe se tornou mais limpa, mas esse tipo nos permite usar uma função callCCcom tipo MonadCont m => ((a -> m b) -> m a) -> m a. Esta função possui um argumento de um tipo de função; esse argumento de função também aceita a função, o que descarta todos os cálculos posteriores à sua chamada. Por exemplo, vamos interromper a execução da pythfunção se pelo menos um de seus argumentos for negativo, retornando zero: 

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do -- $ sign helps to avoid parentheses: a $ b + c == a (b + c)
  when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

Continuações como objetos

Veja também: Callback (programação de computador)

A programação com continuações também pode ser útil quando um chamador não deseja esperar até que o receptor seja concluído. Por exemplo, na programação da interface do usuário (IU), uma rotina pode configurar campos de caixa de diálogo e passá-los, junto com uma função de continuação, para a estrutura da IU. Essa chamada retorna imediatamente, permitindo que o código do aplicativo continue enquanto o usuário interage com a caixa de diálogo. Assim que o usuário pressiona o botão "OK", o framework chama a função de continuação com os campos atualizados. Embora este estilo de codificação use continuações, não é CPS completo. 

function confirmName() {
    fields.name = name;
    framework.Show_dialog_box(fields, confirmNameContinuation);
}

function confirmNameContinuation(fields) {
    name = fields.name;
}

Uma ideia semelhante pode ser usada quando a função deve ser executada em um thread diferente ou em um processador diferente. A estrutura pode executar a função chamada em um thread de trabalho e, em seguida, chamar a função de continuação no thread original com os resultados do trabalhador. Isso está em Java usando a estrutura de IU Swing : 

void buttonHandler() {
    // This is executing in the Swing UI thread.
    // We can access UI widgets here to get query parameters.
    final int parameter = getField();

    new Thread(new Runnable() {
        public void run() {
            // This code runs in a separate thread.
            // We can do things like access a database or a 
            // blocking resource like the network to get data.
            final int result = lookup(parameter);

            javax.swing.SwingUtilities.invokeLater(new Runnable() {
                public void run() {
                    // This code runs in the UI thread and can use
                    // the fetched data to fill in UI widgets.
                    setField(result);
                }
            });
        }
    }).start();
}

Usar a notação lambda Java 8 acima encurta o código para (a finalpalavra-chave pode ser ignorada): 

void buttonHandler() {
    int parameter = getField();

    new Thread(() -> {
        int result = lookup(parameter);
        javax.swing.SwingUtilities.invokeLater(() -> setField(result));
    }).start();
}

Chamadas de cauda

Cada chamada no CPS é uma chamada final e a continuação é explicitamente passada. Usar o CPS sem otimização de chamada final (TCO) fará com que não apenas a continuação construída aumente potencialmente durante a recursão, mas também a pilha de chamadas . Isso geralmente é indesejável, mas tem sido usado de maneiras interessantes - consulte o compilador Chicken Scheme . Como o CPS e o TCO eliminam o conceito de um retorno de função implícito, seu uso combinado pode eliminar a necessidade de uma pilha de tempo de execução. Vários compiladores e interpretadores para linguagens de programação funcionais usam essa capacidade de novas maneiras.

Uso e implementação

O estilo de aprovação de continuação pode ser usado para implementar continuações e operadores de fluxo de controle em uma linguagem funcional que não apresenta continuações de primeira classe, mas tem funções de primeira classe e otimização de chamada final . Sem a otimização de chamada de cauda, ​​técnicas como trampolim , ou seja, usando um loop que invoca iterativamente funções de retorno de conversão , podem ser usadas; sem funções de primeira classe, é até possível converter chamadas finais em apenas gotos em tal loop.

Escrever código em CPS, embora não seja impossível, costuma estar sujeito a erros. Existem várias traduções, geralmente definidas como conversões de uma ou duas passagens de cálculo lambda puro , que convertem expressões de estilo direto em expressões CPS. Escrever no estilo trampolim, no entanto, é extremamente difícil; quando usado, geralmente é o alvo de algum tipo de transformação, como compilação .

Funções que usam mais de uma continuação podem ser definidas para capturar vários paradigmas de fluxo de controle, por exemplo (no Esquema ): 

(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err (list "div by zero!" x y))
                (ok (/ x y))))))

É importante notar que a transformação CPS é conceitualmente uma incorporação de Yoneda . Também é semelhante à incorporação do cálculo lambda no cálculo π .

Use em outros campos

Fora da ciência da computação , o CPS é de interesse mais geral como uma alternativa ao método convencional de composição de expressões simples em expressões complexas. Por exemplo, dentro da semântica linguística , Chris Barker e seus colaboradores sugeriram que a especificação das denotações de sentenças usando o CPS pode explicar certos fenômenos na linguagem natural .

Em matemática , o isomorfismo de Curry-Howard entre programas de computador e provas matemáticas relaciona a tradução do estilo de passagem de continuação a uma variação das incorporações de dupla negação da lógica clássica na lógica intuicionista (construtiva) . Ao contrário da tradução de dupla negação regular , que mapeia as proposições atômicas p para (( p → ⊥) → ⊥), o estilo de passagem de continuação substitui ⊥ pelo tipo da expressão final. Consequentemente, o resultado é obtido passando a função de identidade como uma continuação para a expressão do estilo CPS, como no exemplo acima.

A própria lógica clássica está relacionada à manipulação da continuação de programas diretamente, como no operador de controle de continuação de chamada com corrente de Scheme , uma observação devida a Tim Griffin (usando o operador de controle C intimamente relacionado).

Veja também

Notas

Referências