Hacker News Reader

Comment by nene | Hacker News Reader

I'm a bit disappointed, that the author didn't built a turing-complete interpreter. Frankly I've seen several of such articles which tell you how to build this kind of deterministic evaluator, but they all seem to stop before loops and branching.

And then there are articles about building compilers which do support loops etc, but the trick is that these constructs are implemented by some other already existing machine.

So I feel like there's some gap in my education. Pointers, anybody?

View on HN

I'm not sure I'd be so quick to say it's not turing complete--the language includes building functions (not first-class functions though), but it might be possible that they can be used to emulate conditionals and branching.

Anyway, I'm pretty sure it wouldn't be that hard to extend the language to add some looping and branching constructs to the language, there's nothing really special there to add, it's just another simple type of construct to evaluate.

In my understanding, loops are implemented at the lowest level with jump instructions, but I've never really done much low-lever programming so maybe someone else can explain that better.

There is no conditional, and without a conditional you can't get a conditional.

However modifying it to support conditionals is easy. Just add a built-in function if(condition, expr1, expr2). Now you can build if's. Since the language already properly supports recursive function calls, now it is possible to implement loops through recursion, and you're off and running.

If you have function application, then you don't truly need a primitive conditional. You can represent Boolean values and conditional functions with the Church encoding [1]. This is how conditionals are represented in, for instance, the lambda calculus.

[1] http://en.wikipedia.org/wiki/Church_encoding#Church_booleans

Good point. But you need to have first class functions for that. This toy language does not. And converting from "this native number equals that native number" to your encoding of "true" is going to be an interesting trick.

There is a slight snag that arguments to a function are eagerly evaluated. A built-in if function would be more useful as a special form.

> There is no conditional, and without a conditional you can't get a conditional.

A two element array of function pointers (or code addresses) and an operator that turns true/false into 0/1 is enough to do conditionals.

All loops and branching logic has to ultimately come down to machine language instructions that your computer chip interprets as conditional, if this do that.

To get an example of what can be done at the lowest level, see http://zsmith.co/intel.html for the instructions that a Pentium chip accepts. In particular look at http://zsmith.co/intel_j.html and http://zsmith.co/intel_l.html#loop.

A classic, "Let's Build a Compiler," by Jack Crenshaw:

http://compilers.iecc.com/crenshaw/

edit: BTW, https://www.coursera.org/course/compilers just started...

Reply on news.ycombinator.com