How to bridge theory and implementation for while loops?

Question

I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - and from what I understand, unnecessary. But reading through the books I have and google searches, I can't find the elegant solution.

So, the problem is that I'm building off basic lambda calculus as I understand it. I have defined true/false as abstraction terms. I can combine these with functions to do if/then/else sort of behavior. The problem comes with loops. I can define a basic while loop via recursion, but in practice, that causes a stack overflow. As I understand it, the usual solution would be to perform Tail Call Optimization, but I don't see how I can - conditionals are defined in-language. Because of that, the compiler doesn't know that the body of the while loop is in tail position.

The dragon book focuses on implementing the loop assuming there is labels and gotos. I could certainly do that. It looks as though other languages that don't build in looping constructs at least build in conditionals and then do TCO. And I could certainly do that too. But my understanding is that as long as I can apply abstractions and perform reductions, then loops (and everything else) should be able to be built from those basic blocks.

So what am I missing? Or is this one of those cases where "you can model anything once you have X and Y" isn't the same as "you can model anything once you have X and Y on a real computer" and built-ins are necessary for practical purposes?

Answer 1

So I managed to solve this issue today. The code for my while loop:

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

When I go to build this into CIL (a stack based runtime, important for the psuedocode, not important for the answer) it looks like:

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

The important thing I was missing is that in the while code, the conditional was the thing in tail position. From the compiler's perspective, the block and the while function are two separate functions, with two separate "tails". Each of those are easily evaluated for tail position, making the optimization viable despite the lack of built-in conditionals.

Answer 2

I think you're missing the notion of continuation. Although your compiler may not rely on that notion, as a compiler designer with a functional language as source or intermediate (or target) language, it's important to understand that notion and keep this in mind.

The continuation of a piece of code describes what the code exits to. In imperative terms, it embodies not only the location to which the code jumps or falls through, but also the program state (stack and heap) at that point. In lambda calculus terms, the continuation of a subterm is the context in which it is evaluated.

When you translate imperative code into a functional language, one of the difficulties is coping with code that can exit in several different ways. For example, code can return or raise an exception. Or, the body of a loop can either go on to checking the condition again or exit the loop altogether (break construct). There are two main ways to cope with this:

• Multiplexing: make the code return a sum type for all the possible exits. In the case of a loop body, that would be Continue | Break.
• Continuation-passing style: translate code to a function that takes an extra parameter which is the function to execute next. This extra parameter is the function's continuation. Code which can exit in different ways receive one such parameter for each of the ways.

Continuation-passing style is how data structures get embedded into the pure lambda calculus. For example, when you represent true as $\lambda x,y. x$ and false as $\lambda x,y. y$, the arguments $x$ and $y$ are the two possible continuations, and the boolean is an “if” statement that selects either one or the other continuation.

In continuation-passing style,

while (condition) body

gets translated to

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

In the translation of a program in a typical imperative language in continuation-passing style, the continuation is always the last thing that a piece of code executes. For example, the continuation of body above is executed after all the code of body, so tail call optimization results in freeing all the local variables of body just before executing the continuation.

Some languages offer first-class continuations with a construct like call-with-current-continuation. Call/cc is not in general amenable to tail call optimization — it can in fact be a rather expensive operation since it can lead to duplicating the whole program state.