8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think you answered your own question in that last paragraph. Just because the theory says you can do something doesn't mean that it's practical to do it. $\endgroup$ – svick Feb 16 '15 at 21:08
  • 1
    $\begingroup$ Plenty of languages have conditionals and recursion and implement tail-call optimisation. Search beyond the dragon book. $\endgroup$ – Dave Clarke Feb 16 '15 at 21:22
  • $\begingroup$ Let me get this straight: you're starting from pure $\lambda$-calculus? That is, it's got nothing but $\lambda$'s and abstractions? $\endgroup$ – Andrej Bauer Feb 16 '15 at 21:28
  • $\begingroup$ svick - sure, but as the learner, I can't tell if that is the case here or if I am ignorant of something. dave clarke - plenty of languages have built in conditionals and implement tail-call optimization. I've done searches and produced no results for in-language conditional and TCO. If you have a reference I've overlooked... Andrej Bauer - not quite, but close enough. No built in types, no built in functions. You can declare functions and apply functions. Going in depth about my particular situation would make for a shoddy question. $\endgroup$ – Telastyn Feb 16 '15 at 23:40
  • 1
    $\begingroup$ @Raphael Using lambda calculus as an intermediate language was a big thing in the 1970s–1980s. I believe the intent was to detect semantic optimizations. My understanding (beware that I'm not an expert in compilation techniques) is that turns out that semantic optimizations are really difficult, whereas local optimizations can pay a lot and are easier to see on a language with register assignments and moderate use of goto. Nonetheless ideas from lambda calculus are relevant to compiler design, for example the idea of single assignment and the concept of continuation. $\endgroup$ – Gilles 'SO- stop being evil' Mar 8 '15 at 22:47
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.