4 ms·
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 o
by JoeAltmaier 11y ago
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.
- arethuza 11y agoWell, 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.
- Someone 11y agoFor 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.
- sklogic 11y agoAnd what's a point in such a complex approach, if a proper interpreter (or, even better, compiler) is much simpler?
- Someone 11y agoComplex? 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".
- sklogic 11y agoYou 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.
- ExpiredLink 11y ago'interplet' is not googleable. Any link?
- sklogic 11y agoPascal 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.
- agumonkey 11y agoIIRC 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.
- watmough 11y agoIdeally 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 http://bellard.org/tcc/tcc-doc.html This great code to read. I need to get back to playing with it again.
- agumonkey 11y agoHa, 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/ 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/msg00043.html http://lists.nongnu.org/archive/html/tinycc-devel/2013-02/ms...
- watmough 11y agoThat'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.
- barrkel 11y agoYou are referring to an AST interpreter, right?
- JoeAltmaier 11y agoMore like this variant: http://lafo.ssw.uni-linz.ac.at/papers/2012_DLS_SelfOptimizingASTInterpreters.pdf 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.
- LnxPrgr3 11y agoDo 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 http://vvm.lip6.fr/publications/9806PLDI.ps.gz.
- JoeAltmaier 11y agoMy 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.
- sklogic 11y agoIt'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.
- detaro 11y agoHow is that not an interpreter?
- JoeAltmaier 11y agoSure 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).
- detaro 11y agoOk, 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)
- JoeAltmaier 11y agoAnother 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.
- blt 11y agoIt 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.
- ehaliewicz2 11y agoThat'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.