Let’s Build a Simple Interpreter, Part 1 | Hacker News Reader

Let’s Build a Simple Interpreter, Part 1

ruslanspivak.com

134 pointsrspivak53 comments

> “If you don’t know how compilers work, then you don’t know how computers work. If you’re not 100% sure whether you know how compilers work, then you don’t know how they work.”

What nonsense. If you don't know how quantum mechanics works, you don't know how transistors work. If you don't know how transistors work, you don't know how computers work, etcetera.

Most electrical engineers do go through quantum mechanics in their modern physics classes, in order to understand how transistors work...

Computer engineering degrees get some too.

I was thinking that same thing, and because I was minoring in CS during my EE degree I also got to do the compilers class with the rest of the CS majors (and a class on interpreters).

But I get that you can understand a lot about computation without understanding compilers. Just as you can understand a lot about circuits without understanding quantum mechanics.

I think what you said is reasonable. We only approximately know how most stuff works.

I would doubt that it is even possible for an individual to completely understand a modern computer from the transistor level up to the top of the software stack - so we have to work with abstractions and their occasional leaks.

I agree with both of you, to some extent.

I agree with you, as yes there's a line somewhere to be drawn and I didn't exactly like the tone of the quote.

But there is some truth in the quote. Knowing how abstraction layers work, a couple of levels below the one you are working with, even if it is not something you would use in your day-to-day job, is extremely rewarding.

You're correct, but I think the utility of knowing about compilers is underrated. There have been a few front page posts recently that demonstrate very naive machine models. E.g. a few days ago there was this post

> Writing Go took me a little longer since I had to implement a lot of functionality provided for me in Ruby. However, for every task it also made me think about what the computer actually does.

http://jorin.me/textstat/

Building a naive cost model for Ruby isn't so difficult if you know how compilers work. Believing that Go provides a model of what the computer actually does is rather naive. Both of these can be addressed by spending a bit of time studying compilers.

"Building a naive cost model for Ruby isn't so difficult if you know how compilers work"

You also need to know all of ruby. In particular, if you do not know how flexible the language is, you may make the mistake of thinking that function call targets can be resolved at compilation time. With duct typing, that gets considerably harder.

Another example is that you may have to know the way integer overflow works. Wrap around, throw, or silently convert to bigint all have different performance characteristics (luckily that's an edge case for most programs)

Also, if you aren't naive, it gets really hard to build a naive cost model for Ruby. You start thinking "will they have complicated things by doing X (e.g. assuming that x.f is a function, and recompiling if that assumption gets invalidated) to get performance here?" all the time.

> With duct typing, that gets considerably harder.

Your hypercorrection from duct tape is bleeding into your duck typing. So named because "if it looks like a duck, it must be a duck."

It so happens that the tape was originally called duck tape, so named because it was made by applying adhesive to duck cloth. The name duct tape came later, when it started being used in construction to seal duct work. Amusingly, modern duct tape is not certified for that use. None of this has anything to do with the duck referred to in duck typing. But I am now curious about the etymology of "duck cloth" and whether it has any relation to water fowl that quack. edit: "strong, untwilled linen (later cotton) fabric," used for sails and sailors' clothing, 1630s, from Dutch doeck "linen cloth" (Middle Dutch doec), related to German Tuch "piece of cloth," Danish dug, Old Frisian dok, Old High German tuoh, all of unknown origin."

I thought it was ammo-case waterproof tape developed in WWII, affectionately called 'duck tape' by GI Joe.

Etymology is fascinating some times. It appears that the use of "duck" as a type of fabric is still alive in English, though a lot of technical fabric terms aren't really well known in the general populous anymore.

https://en.wikipedia.org/wiki/Cotton_duck

http://www.merriam-webster.com/dictionary/duck (4)

Here is a link to the source code for a C like interpreter that I many years ago:

http://www.zeusedit.com/tools.html

Is it any good? Not really. There are many far better interpreters out there to choose from.

But it was my first and last ever interpreter, written some 20+ years ago, written when I was fresh out of university.

Was it hard to write?

I did not think so and I only had an engineering degree ;)

Now lets try to write a compiler. Suddenly things get far more difficult!!!

A compiler isn't actually that much more difficult than an interpreter. Extending an interpreter to compile instead of interpret is not that much code, and the code won't be that difficult or complex either.

The hard part is making the generated code perform well, which requires much more work.

Compilers are much simpler than interpreters, unless you go into some really complicated optimisations.

Around the same time as you wrote yours I did this one with a friend

It was a basic exercise for our CS compiler classes in 1998, written in the newly introduced Java language and generates bytecode and native.

https://github.com/pjmlp/L98

The code is actually pretty basic, and I did some improvements (Makefile to Maven, Java 1.0 to 7, replaced C runtime by pure Asm) in the last couple of years just for fun.

If anything, it taught me a very interesting trick for writing compilers as if they were interpreters.

Create bytecodes as intermediate language that can be easily mapped into Assembly macros. Then instead of interpreting, just make them go through the macro assembler.

It won't generate the fastest code in the world, the register allocator will be pretty stupid, but hey it compiles straight to native.

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.

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.

'interplet' is not googleable. Any link?

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.

You are referring to an AST interpreter, right?