Hacker News Reader

Comment by JoeAltmaier | Hacker News Reader

Interpreters are fun, but still too complicated. There's a simpler form, which is called 'interplets' around here. It has a parser, then directly generates an object instance for every semantic element e.g. variable, control statement etc. The objects get linked, and they have an 'execute' method. Voila! Runs about 10X as fast as an interpreter.

View on HN

'interplet' is not googleable. Any link?

Well, if you want a really simple interpreter there is always the option to go Reverse Polish (e.g. Forth/PostScript).

Of course, this makes the implementation simple while arguably pushing some of the work onto the programmer using the language - but RPN languages can be rather fun in a Lisp kind of way.

For beginners, I would go for a recursive descent interpreter (just made up that term) that implements a 'little language'. That is something on the complexity of a shell without looping or variables or of parsing argv:

  - read a line
  - do a switch on the first word of the line
  - inside each switch, make up your own syntax, parse the
    remainder of the line, and execute it or issue an error
    message and abort.
    Feel free to cheat by using scanf to parse integers.

Iteration 2 can add printing the line number in error messages.

Iteration 3 can add if/then and looping: keep the lines in an array, and add 'goto' to the list of commands, and hack the jump into the interpreter loop by adjusting a global variable from inside the 'goto' statement.

Iteration 4 can add the 'let' command and variables. Naming them A through Z for simplicity is an option.

Then, add simple assignments of the form

  let a = x <op> y

where x and y are liberals or variables. For now, don't bother with expressions with multiple operators.

Next, add statements of the form

  y = f(x)

That gives you a sort-of 70's Basic that can be quite useful and fun to use.

Only then would I start introducing grammars, the word 'parse', etc.

And what's a point in such a complex approach, if a proper interpreter (or, even better, compiler) is much simpler?

Complex? Its building up from almost nothing, and shows how simple an interpreter can be.

If you start with a grammar, you lose half your audience within 5 minutes (numbers made up)

If you start with a program that reads a text file and plays notes for lines contaning do, re, and mi, part of that lost audience will get drawn in, complete the scale, add 'fart' commands, etc.

Also, smart kids may figure out they can easily add single-statement loops on their own, by adding a case 'repeat' that scans for the number of iterations, removes the 'repeat' and that number of iterations from the line, and then calls the 'processALine' code.

It's "learn by playing" vs "learn through study".

You do not have to do such clumsy things to build from nothing. Split the input by whitespaces, lookup word definitions in a table (linked list is ok), push the addresses of the found words to the output stream as call instructions or execute immediately if marked so. That's it, a minimal direct threaded Forth compiler is done.

You are referring to an AST interpreter, right?

More like this variant:

http://lafo.ssw.uni-linz.ac.at/papers/2012_DLS_SelfOptimizin...

Its a natural extension to derive objects optimized for common cases e.g. integer increment vs generic add expression. The bytecode idea adds complexity and doesn't actually speed up unless you add JIT conversion to native, which makes it a compiler again.

The virtual method penalty is way overstated. Its still 10X faster than an interpreter. And 10X slower than a compiler. A decent compromise, and easily written in a weekend for any simple language.

Do you have benchmarks for this? The linked paper only evaluates performance of optimizations applied on top of this idea, and the idea vs. Rhino.

Besides, not all bytecode interpreters are made equal: http://vvm.lip6.fr/publications/9806PLDI.ps.gz.

My data is old - various control languages, BASIC, RPN style expression engine. Each time about the same performance.

Go ahead and implement a bytecode machine, but you lose two ways: the time to write that extra engine, and the loss of semantics. In the interplet (ok, AST) interpreter, you can add debugging features that 'understand' the intent e.g. still know a loop is a loop. That's cool and powerful.

It's better to know that loop is a loop just from a CFG, even if it's implemented with a goto and if. In this case stripping source language semantics may be useful.

So true! A peephole optimizer can operate on constructs no matter how they're generated, and streamline them (use custom objects for common/slow cases). But for debugging, its nice to offer diagnostic or control features (e.g. execute 1000 times then break).

You still have your loops in CFG, identifying back edges and extracting loop induction variables is mechanical. And you can lower any amount of debugging information out of your high level AST structures. No need to stay in AST to have it all.

> The bytecode idea adds complexity and doesn't actually speed up unless you add JIT conversion to native, which makes it a compiler again.

In every language implementation I've worked with, bytecode led to a large improvement in performance.

> The virtual method penalty is way overstated.

This makes me think your data is outdated. It's more about the loss of locality today than it is virtual method dispatch. With a tree-walk interpreter, your "code" is spread all throughout memory and executing involves jumping all over the address space. That kills your cache.

> Its still 10X faster than an interpreter. And 10X slower than a compiler.

Those numbers don't mean anything without context. What are the semantics of the language? What's the object representation? The memory model? How are local variables managed?

> easily written in a weekend for any simple language.

Call me crazy, but I don't think a bytecode compiler takes any more time than that either.

How is that not an interpreter?

Sure it is. A traditional interpreter executes via generate-synthetic-code-and-emulate-cpu technique. This other method uses the native compiler to generate code (i.e. compiles the 'Execute' methods).

Ok, now I get what you mean. I was a bit confused, because it sounded like simply building an AST and processing that, which for me is the "obvious" form of an interpreter (without the generating machine code)

Another interpreter scheme: create a token form of the source, then pass over that constantly reinterpreting the tokens (re-parsing from tokens) and with massive switch() statements execute from a symbol table. That's the slowest, and how interpreters were done years ago.

It sounds like you are describing either a JIT compiler or a direct AST interpreter.

JIT compilers are indeed fast, but AST interpreters are usually slower than bytecode interpreters.

Pascal got a very nice property - it can be compiled in one pass, literally, by spitting out code while parsing. Nothing can be simpler than that. Interpretation is significantly more complicated.

IIRC tcc, Bellard's tiny c compiler, works this way. It emits very naive native code, but it chomps source code fast enough to boot linux 2.4 from source under 10 seconds years ago.

Ideally it does one pass, except under the following conditions:

    For initialized arrays with unknown size, a first pass is done to count the number of elements.
    For architectures where arguments are evaluated in reverse order, a first pass is done to reverse the argument order.

From: http://bellard.org/tcc/tcc-doc.html

This great code to read. I need to get back to playing with it again.

Ha, I tried to poke inside tcc, aiming at booting linux 3.x, and missed that link.

ps: it's also still under development http://lists.nongnu.org/archive/html/tinycc-devel/ .. impressive.

----

"tcc still compiles around 10x faster but runs x3.5 times slower." from tcc homepage 3rd benchmark URL http://lists.nongnu.org/archive/html/tinycc-devel/2013-02/ms...

That's a good little mailing list. The biggest issue seems to be keeping tcc working across all supported platforms when changing stuff for a single platform.

tcc can actually be made to build Windows executables in the 'old-school' "Programming Windows" way, which is quite fun.

That's a similar idea to one of the interpreters in SICP, where for each node in a lisp expression, you compile a closure with the code that knows how to evaluate itself.

This way you can save on parsing the same structure multiple times, and it makes it simpler to implement certain optimizations like compile-time lexical binding.

Reply on news.ycombinator.com