Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to bridge theory and implementation for while loops?

, , No Comments
Problem Detail: 

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?

Asked By : Telastyn

Answered By : Telastyn

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback