Como fazer uma ponte entre teoria e implementação para os loops while?

8

Estou trabalhando em minha própria pequena linguagem de programação para fins educacionais e me deparei com um pouco de problema. Existem algumas soluções diferentes para isso, mas todas elas parecem deselegantes - e pelo que entendi, desnecessárias. Mas, lendo os livros que tenho e as pesquisas no Google, não consigo encontrar a solução elegante.

Portanto, o problema é que estou construindo o cálculo lambda básico como o entendo. Eu defini verdadeiro / falso como termos de abstração. Eu posso combiná-los com funções para fazer se / então / outro tipo de comportamento. O problema vem com loops. Eu posso definir um loop while básico via recursão, mas na prática, isso causa um estouro de pilha. Pelo que entendi, a solução usual seria executar a otimização de chamada de cauda, ​​mas não vejo como posso - os condicionais são definidos no idioma. Por isso, o compilador não sabe que o corpo do loop while está na posição de cauda.

O livro do dragão se concentra na implementação do loop, assumindo que há rótulos e gotos. Eu certamente poderia fazer isso. Parece que outras linguagens que não constroem em looping constroem pelo menos em condicionais e depois fazem o TCO. E eu certamente poderia fazer isso também. Mas meu entendimento é que, enquanto eu puder aplicar abstrações e executar reduções, os loops (e tudo o mais) deverão poder ser construídos a partir desses blocos básicos.

Então o que estou perdendo? Ou esse é um daqueles casos em que "você pode modelar qualquer coisa depois de ter X e Y" não é o mesmo que "você pode modelar qualquer coisa depois de ter X e Y em um computador real" e os internos são necessários para fins?

Telastyn
fonte
Eu acho que você respondeu sua própria pergunta no último parágrafo. Só porque a teoria diz que você pode fazer algo não significa que é prático fazê-lo.
svick
1
Muitos idiomas têm condicionais e recursão e implementam a otimização de chamada de cauda. Pesquise além do livro do dragão.
Dave Clarke
Deixe-me ver se entendi: você está começando do puro λ-cálculo? Ou seja, não tem nada além deλe abstrações?
Andrej Bauer
svick - claro, mas como aprendiz, não sei dizer se é esse o caso aqui ou se sou ignorante de alguma coisa. dave clarke - muitas linguagens criaram condicionais e implementam a otimização da chamada de cauda. Eu tenho feito pesquisas e produziu nenhum resultado para no idioma condicional e TCO. Se você tem uma referência que eu esqueci ... Andrej Bauer - não exatamente, mas perto o suficiente. Não há tipos incorporados, nem funções incorporadas. Você pode declarar funções e aplicar funções. Aprofundar-se sobre a minha situação particular faria uma pergunta de má qualidade.
Telastyn
1
@Raphael Usar o cálculo lambda como uma linguagem intermediária foi algo importante nas décadas de 1970 a 1980. Acredito que a intenção era detectar otimizações semânticas. Meu entendimento (cuidado com o fato de não ser especialista em técnicas de compilação) é que as otimizações semânticas são realmente difíceis, enquanto as otimizações locais podem pagar muito e são mais fáceis de serem visualizadas em um idioma com atribuições de registro e uso moderado de goto. No entanto, as idéias do cálculo lambda são relevantes para o design do compilador, por exemplo, a idéia de atribuição única e o conceito de continuação.
Gilles 'SO- stop being evil' em

Respostas:

5

Então, eu consegui resolver esse problema hoje. O código para o meu loop while:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

Quando construo isso no CIL (um tempo de execução baseado em pilha, importante para o psuedocode, não importante para a resposta), ele se parece com:

ldarg 0
<build closure from { body; while condition body; }>
call if

O importante que eu estava perdendo é que, no whilecódigo, o condicional era o que estava na posição de cauda. Do ponto de vista do compilador, o bloco e a função while são duas funções separadas, com duas "caudas" separadas. Cada um deles é facilmente avaliado quanto à posição da cauda, ​​tornando a otimização viável, apesar da falta de condicionais embutidos.

Telastyn
fonte
5

Eu acho que você está perdendo a noção de continuação . Embora seu compilador possa não confiar nessa noção, como um designer de compilador com uma linguagem funcional como linguagem de origem ou intermediária (ou destino), é importante entender essa noção e ter isso em mente.

A continuação de um pedaço de código descreve para onde o código sai. Em termos imperativos, ele incorpora não apenas o local para o qual o código salta ou cai, mas também o estado do programa (pilha e pilha) nesse ponto. Em termos de cálculo lambda, a continuação de um subtermo é o contexto em que é avaliado.

Quando você traduz código imperativo em uma linguagem funcional, uma das dificuldades é lidar com o código que pode sair de várias maneiras diferentes. Por exemplo, o código pode retornar ou gerar uma exceção. Ou, o corpo de um loop pode continuar a verificar a condição novamente ou sair completamente do loop ( breakconstrução). Existem duas maneiras principais de lidar com isso:

  • Multiplexagem: faça com que o código retorne um tipo de soma para todas as saídas possíveis. No caso de um corpo de loop, isso seria Continue | Break.
  • Estilo de passagem contínua : traduza o código para uma função que usa um parâmetro extra, que é a função a ser executada a seguir. Este parâmetro extra é a continuação da função. O código que pode sair de maneiras diferentes recebe um desses parâmetros para cada uma das maneiras.

O estilo de passagem de continuação é como as estruturas de dados são incorporadas ao cálculo lambda puro. Por exemplo, quando você representa true comoλx,y.x e falso como λx,y.y, os argumentos x e y são as duas continuações possíveis e o booleano é uma instrução "se" que seleciona uma ou outra continuação.

No estilo de passagem de continuação,

while (condition) body

é traduzido para

let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

Na tradução de um programa em uma linguagem imperativa típica no estilo de passagem de continuação, a continuação é sempre a última coisa que um pedaço de código executa. Por exemplo, a continuação bodyacima é executada após todo o código de body, portanto, a otimização da chamada de cauda resulta em liberar todas as variáveis ​​locais bodyimediatamente antes de executar a continuação.

Alguns idiomas oferecem continuações de primeira classe com uma construção como chamada com continuação atual . A chamada / cc geralmente não é passível de otimização de chamada - ela pode ser de fato uma operação bastante cara, pois pode levar à duplicação de todo o estado do programa.

Gilles 'SO- parar de ser mau'
fonte