Como implementar continuações?

Question

Estou trabalhando em um interpretador de Scheme escrito em C.Atualmente ele usa a pilha de tempo de execução C como sua própria pilha, o que apresenta um pequeno problema com a implementação de continuações.Minha solução atual é copiar manualmente a pilha C para o heap e copiá-la de volta quando necessário.Além de não ser o padrão C, esta solução dificilmente é ideal.

Qual é a maneira mais simples de implementar continuações para Scheme em C?

Answer 1

Lembro-me de ter lido um artigo que pode ser útil para você: Cheney no M.T.A. :-)

Algumas implementações do Scheme que conheço, como SISC, aloque seus frames de chamada no heap.

@ollie:Você não precisa fazer o içamento se todos os seus frames de chamada estiverem no heap.Há uma compensação no desempenho, é claro:o tempo de elevação versus a sobrecarga necessária para alocar todos os quadros no heap.Talvez devesse ser um parâmetro de tempo de execução ajustável no interpretador.:-P

Answer 2

Um bom resumo está disponível em Estratégias de implementação para continuações de primeira classe, um artigo de Clinger, Hartheimer e Ost.Eu recomendo observar a implementação do Chez Scheme em particular.

A cópia de pilha não é tão complexa e há diversas técnicas bem compreendidas disponíveis para melhorar o desempenho.Usar quadros alocados em heap também é bastante simples, mas você compensa criar sobrecarga para situações "normais" em que não está usando continuações explícitas.

Se você converter o código de entrada em estilo de passagem de continuação (CPS), poderá eliminar completamente a pilha.No entanto, embora o CPS seja elegante, ele adiciona outra etapa de processamento no front-end e requer otimização adicional para superar certas implicações de desempenho.

Answer 3

Se você está começando do zero, você realmente deveria dar uma olhada na transformação do Continuation Passing Style (CPS).

Boas fontes incluem "LISP em pequenos pedaços" e Esquema de Marc Feeley em apresentação de 90 minutos.

Answer 4

Parece que a tese de Dybvig não foi mencionada até agora.É uma delícia ler.O modelo baseado em heap é o mais fácil de implementar, mas a pilha é mais eficiente.Ignore o modelo baseado em string.

R.Kent Dybvig.“Três modelos de implementação para esquema”.http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Verifique também os documentos de implementação em ReadScheme.org.http://library.readscheme.org/page8.html

O resumo é o seguinte:

Esta dissertação apresenta três modelos de implementação para a linguagem de programação do esquema.O primeiro é um modelo baseado em heap usada de alguma forma na maioria das implementações de esquema até o momento;O segundo é um novo modelo baseado em pilha que é consideravelmente mais eciente que o modelo baseado em heap na execução da maioria dos programas;E o terceiro é um novo modelo baseado em string destinado ao uso em uma implementação do esquema de múltiplos processadores.

O modelo baseado em heap aloca várias estruturas de dados importantes em uma pilha, incluindo listas de parâmetros reais, ambientes de ligação e quadros de chamada.

O modelo baseado em pilha aloca essas mesmas estruturas em uma pilha sempre que possível.Isso resulta em menos alocação de heap, menos referências de memória, sequências de instruções mais curtas, menos coleta de lixo e uso mais eciente da memória.

O modelo baseado em string aloca versões dessas estruturas diretamente no texto do programa, que é representado como uma sequência de símbolos.No modelo baseado em string, os programas de esquema são traduzidos em uma linguagem FFP projetada especificamente para suportar o esquema.Os programas neste idioma são executados diretamente pela máquina FFP, um computador de redução de string de múltiplos processadores.

O modelo baseado em pilha traz benefícios práticos imediatos;É o modelo usado pelo sistema CHEZ Scheme do autor, uma implementação de esquema de alto desempenho.O modelo baseado em string será útil para fornecer esquema como uma alternativa de alto nível ao FFP na máquina FFP assim que a máquina for realizada.

Answer 5

Além das boas respostas que você obteve até agora, recomendo as de Andrew Appel Compilando com Continuações.Está muito bem escrito e embora não lide diretamente com C, é uma fonte de ideias muito boas para escritores de compiladores.

O Chicken Wiki também tem páginas que você achará muito interessantes, como estrutura interna e processo de compilação (onde o CPS é explicado com um exemplo real de compilação).

Answer 6

Exemplos que você pode ver são: Frango (uma implementação de Scheme, escrita em C que suporta continuações);Paulo Graham No Lisp - onde cria um transformador CPS para implementar um subconjunto de continuações em Common Lisp;e Blocos da Web - uma estrutura web baseada em continuação, que também implementa uma forma limitada de continuações em Common Lisp.

Answer 7

As continuações não são o problema:você pode implementá-los com funções regulares de ordem superior usando CPS.O problema com a alocação ingênua de pilha é que as chamadas finais nunca são otimizadas, o que significa que você não pode ser um esquema.

A melhor abordagem atual para mapear a pilha de espaguete do esquema na pilha é usar trampolins:essencialmente infraestrutura extra para lidar com chamadas e saídas de procedimentos não-C.Ver Estilo trampolim (ps).

Há algum código ilustrando ambas as ideias.

Answer 8

A maneira tradicional é usar setjmp e longjmp, embora haja ressalvas.

Aqui está um explicação razoavelmente boa

Answer 9

As continuações consistem basicamente no estado salvo da pilha e dos registros da CPU no ponto das trocas de contexto.No mínimo, você não precisa copiar a pilha inteira para o heap ao alternar; você só pode redirecionar o ponteiro da pilha.

As continuações são implementadas trivialmente usando fibras. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29.As únicas coisas que precisam de encapsulamento cuidadoso são a passagem de parâmetros e os valores de retorno.

No Windows, as fibras são feitas usando a família de chamadas CreateFiber/SwitchToFiber.em sistemas compatíveis com Posix isso pode ser feito com makecontext/swapcontext.

boost::coroutine possui uma implementação funcional de corrotinas para C++ que pode servir como ponto de referência para implementação.

Answer 10

Use uma pilha explícita.

Answer 11

Patrick está correto, a única maneira de realmente fazer isso é usar uma pilha explícita em seu intérprete e colocar o segmento apropriado da pilha na pilha quando precisar converter para uma continuação.

Isso é basicamente o mesmo que é necessário para suportar fechamentos em linguagens que os suportam (fechamentos e continuações sendo de alguma forma relacionados).

Answer 12

Como soegaard apontado, a referência principal permanece Este

A ideia é que uma continuação seja um encerramento que mantém sua pilha de controle de avaliação.A pilha de controle é necessária para continuar a avaliação a partir do momento em que a continuação foi criada usando call/cc.

Freqüentemente, invocar a continuação demora muito tempo de execução e preenche a memória com pilhas duplicadas.Eu escrevi esse código estúpido para provar que, no esquema mit, ele faz o esquema falhar,

O código soma os primeiros 1000 números 1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

Se você mudar de 1.000 para 100.000, o código gastará 2 segundos e, se você aumentar o número de entrada, ele travará.