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

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?

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.

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$\lambda x,y. x$ e falso como $\lambda 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.