I\'m working on my own little programming language for educational purposes, and
ID: 649288 • Letter: I
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?
Explanation / Answer
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 ?x,y.x and false as ?x,y.y, the arguments x and y are the two possible continuations, and the boolean is an