Pergunta

Eu tentei várias vezes para entender o conceito de continuações e chamada / cc . Cada tentativa foi um fracasso. Pode alguém por favor me explicar esses conceitos, de preferência com exemplos mais realistas do que estes no Wikipedia ou em outros lugares assim.

Eu tenho experiência em programação web e OOP. Eu também entendo 6502 montagem e tinha um menor randez-vous com Erlang. No entanto, ainda assim, eu não posso envolver minha cabeça em torno de chamada / cc.

Foi útil?

Solução

Olha, eu encontrei este Continuação Passando Estilo melhor descrição sobre este tema.

Aqui está despojado de detalhes copiar desse artigo:

Autor: Marijn Haverbeke Data: 24 de julho de 2007

O Esquema call-com-presente de continuação de função torna possível capturar um cálculo, um estado da pilha de chamadas por assim dizer, e retomar esse mesmo estado em um momento posterior. No topo de uma vária forma tão primitiva, de tratamento de exceção e C-like truques Longjmp podem ser implementadas. 

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);

Isto pode ser transformado da seguinte forma: Nós adicionar um argumento extra para cada função, que será usado para passar continuação da função. Esta continuação é um valor da função que representa as ações que devem acontecer após a função 'retorna'. O (call) pilha torna-se obsoleto no estilo de passagem de continuação - quando uma função chama outra função, que é a última coisa que ele faz. Em vez de esperar para a função chamado para retornar, ele coloca qualquer trabalho que quer fazer depois em uma continuação, que ele passa para a função. 

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});

Imagine que temos um documento huuuuge para capitalizar. Apenas atravessá-lo de uma só vez leva cinco segundos, e congelar o navegador durante cinco segundos é bastante mau estilo. Considere esta simples modificação da capitaliseText (não prestar atenção ao feio global): 

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}

Agora, a cada vinte nós, o cálculo é interrompido por centenas de milissegundos para dar o navegador interface de um momento para responder a entrada do usuário. Uma forma muito primitiva de rosqueamento -. Você ainda pode executar vários cálculos ao mesmo tempo como este

A aplicação mais comumente útil deste está relacionada com XMLHttpRequests, ou os vários IFRAME e hacks marca de script usado para simular los. Estes exigem sempre um para trabalhar com algum tipo de mecanismo de call-back para lidar com os dados que o servidor envia de volta. Em casos simples, uma função trivial vai fazer, ou alguns globals pode ser usado para armazenar o estado da computação que deve ser retomada após os dados de volta. Com casos complexos, por exemplo, quando os dados está sendo usado por uma função que deve retornar algum valor para seu chamador, continuações simplificar as coisas consideravelmente. Você acabou de registrar a continuação como o call-back, e seu cálculo é retomado quando o pedido de acabamentos.

Outras dicas

Para compará-lo com C, a continuação atual é como o estado atual da pilha. Ele tem todas as funções de espera para o resultado da função atual ao fim para que eles possam continuar a execução. A variável capturada como a continuação atual é usada como uma função, exceto que ela assume o valor fornecido e retorna para a pilha de espera. Este comportamento é semelhante à função C longjmp , onde pode voltar a reduzir porções da pilha imediatamente . 

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Uma diferença fundamental entre a pilha C e uma continuação é que uma continuação pode ser usado em qualquer ponto no programa, mesmo se o estado da pilha mudou. Isso significa que você pode essencialmente restaurar versões anteriores da pilha e usá-los de novo e de novo, levando a algum fluxo de programa único. 

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

A capacidade de salvar e restaurar o estado de um programa tem muito em comum com multithreading. Na verdade, você pode implementar seu próprio agendador segmento usando continuações, como eu tentei ilustrar aqui .

Um exemplo trivial de usar continuação seria a implementação de um thread (fibra, se quiser) gerente em uma máquina com um único processador. O programador iria interromper o fluxo de execução periodicamente (ou, no caso das fibras, ser invocado em vários pontos estratégicos no código), senão o estado continuação (correspondente ao thread atual ), em seguida, mudar para um diferente estado continuação (correspondente a um segmento diferente cujo estado foi salvo anteriormente.)

No que se refere ao seu fundo de montagem, o estado continuação possa capturar detalhes como ponteiro de instrução, registros, eo contexto pilha (ponteiro) , para ser salvo e restaurado à vontade.

Outra maneira de usar continuação seria pensar em substituir chamadas de método com vários thread-como entidades que co-existir em paralelo (em execução ou suspenso) passar o controle entre si usando contextos continuação vez do paradigma 'clássico' call. Eles iriam operar em dados global (compartilhado), em vez de depender de parâmetros. Esta é, em certa medida mais flexível do que call no sentido de que a pilha não tem de acabar, em seguida, para baixo (calls são aninhada ), mas o controle pode passar em torno de forma arbitrária.

Tentar visualizar este conceito em uma linguagem tal C, imagine ter um grande laço com uma única instrução switch(continuation_point) { case point1: ... }, onde cada case corresponde a uma continuação-savepoint, e onde o código dentro de cada case pode alterar o valor de controlo continuation_point e devolver à que continuation_point por breaking do switch e engatar a iteração seguinte no circuito.

Qual é o contexto da sua pergunta? Quaisquer cenários específicos que você está interessado? Qualquer linguagem de programação particular? É o exemplo thread / fibra acima suficiente?

A única coisa que me ajudou é a ideia de que em uma linguagem tradicional com chamadas de função que você passa implicitamente uma continuação qualquer momento que você faz uma chamada de função.

Antes de saltar para o código de uma função de guardar algum estado na pilha (ou seja, você empurra o seu endereço de retorno e a pilha já contém seus habitantes). Esta é essencialmente uma continuação. Quando a função terminar o que tem para determinar para onde enviar o fluxo de execução. Ele usa a continuação armazenado na pilha, aparecendo o endereço de retorno e saltar para ele.

Outros idiomas generalizar esta ideia de continuações que lhe permite especificar explicitamente onde para continuar a execução de código, em vez de implicitamente continuar de onde a chamada de função foi feita.

EDIT baseado em comentário:

A continuação é o estado de execução completa. Em qualquer ponto da execução você pode dividir o programa em duas partes (em tempo, não espaço) - o que foi executado a este ponto, e tudo o que está indo para executar a partir daqui. A "continuação atual" é o "tudo o que está indo para executar a partir daqui" (você pode pensar nisso como uma espécie de função que irá fazer tudo o que o resto do seu programa teria feito). Assim, a função que você fornecer para call/cc é passado a continuação que era atual quando call/cc foi invocado. A função pode usar a continuação de retornar a execução para a declaração call/cc (mais provável que ele vai passar a continuação em torno de outra coisa, porque se usou directamente que poderia fazer um retorno simples em vez disso).

Quando eu estava tentando entender chamada / cc, eu encontrei este call-com-presente-continuation-para-C-programadores página foi útil.

A melhor explicação que eu vi é no livro de Paul Graham, On Lisp .

Imagine o seu roteiro é uma fase de vídeo-game. Call / cc é como uma fase de bônus.

parellel entre fase de bônus e de chamada / cc

Assim que você tocá-lo você são transferidos para a fase de bônus (ou seja, a definição da função passada como argumento para chamadas / cc [f neste caso]).

fases de bônus são diferentes das etapas comuns porque geralmente eles têm um elemento (ou seja, o argumento da função passado para chamada / cc) que se você tocá-lo você perde e são transportados de volta para o palco normal.

parellel entre fase de bônus de saída e chamada / cc função args

Assim, não importa se há muitos args, quando você atingir um deles está acabado. Portanto, a nossa execução atinge (arg 42) e retorna para o (+ 42 10) soma.

Além disso, existem algumas observações merece destaque:

  • Nem todas as funções podem ser utilizadas com a chamada / cc. Desde que espera um continuação (que é uma função), você não pode ter um f assim: (define f (lambda (k) (+ k 42)), porque você não pode sum um função.
  • Além disso, você não pode ter (define f (lambda (k) (f 42 10))) porque a continuação espera apenas um argumento.
  • Você pode terminar sem touching qualquer saída, neste caso, a função procede como qualquer função normal (por exemplo, acabamentos e (define f (lambda (k) 42) retornos 42).

Existem vários níveis de compreensão de chamada / cc. Primeiro você precisa entender os termos e as como funciona o mecanismo. Em seguida, uma compreensão de como e quando chamada / cc é usado na "vida real" é necessária programação.

O primeiro nível pode ser alcançado através do estudo CPS, mas há alternativas.

Para o segundo nível, eu recomendo o seguinte clássico de Friedman.

Daniel P. Friedman. "Aplicações de Continuations: convidado Tutorial". 1988 Princípios de Linguagens de Programação (POPL88). Janeiro de 1988.

O modelo que eu usei para continuações compreensão do ponto de vista fundamental é que é uma cópia da chamada-stack combinado com o um ponteiro para a próxima instrução.

Chamada / cc chama uma função (passado como um argumento) com a continuação como um argumento.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top