18 ms·
Let’s Build a Simple Interpreter, Part 1
- amelius 11y ago> “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.
- mozumder 11y agoMost electrical engineers do go through quantum mechanics in their modern physics classes, in order to understand how transistors work...
- JustSomeNobody 11y agoComputer engineering degrees get some too.
- ChuckMcM 11y agoI 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.
- andrewchambers 11y agoI think what you said is reasonable. We only approximately know how most stuff works.
- arethuza 11y agoI 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.
- gedrap 11y agoI 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.
- noelwelsh 11y agoYou'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/ 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.
- Someone 11y ago"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.
- jdmichal 11y ago> 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."
- js2 11y agoIt 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."
- deleted 11y ago[deleted]
- JoeAltmaier 11y agoInterpreters 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?
- aikah 11y agoI like this article: http://lisperator.net/pltut/ http://lisperator.net/pltut/ it's in javascript and does a good job at teaching writing interpreters withtout regex tricks. There is even a compiler tutorial at the end.
- jussij 11y agoHere is a link to the source code for a C like interpreter that I many years ago: http://www.zeusedit.com/tools.html 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!!!
- yoklov 11y agoA 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.
- sklogic 11y agoCompilers are much simpler than interpreters, unless you go into some really complicated optimisations.
- pjmlp 11y agoAround 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 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.
- ufo 11y agoI am a huge fan of using functional programming languages to implement interpreters. Algebraic data types makes working with syntax-trees much more pleasant.
- sklogic 11y agoAnd yet, it's a lot of boilerplate to write recursive ast walkers manually. ADTs are not enough, some (ideally, compile-time) reflection is also needed.
- ufo 11y agoThats true, reflection tools like Haskell's Uniplate and SYB are very helpful. But its still possible to get very far with just ADTs if you use "parameterized functors" instead of recursive data types for the syntax tree and write some reusable fold functions for the walkers. Another neat thing about this approach is that its super easy to add metadata to the syntax tree (for example, line numbers for error messages). http://lambda-the-ultimate.org/node/4170#comment-63836 http://lambda-the-ultimate.org/node/4170#comment-63836
- pjmlp 11y agoThat is why for prototyping it is much better to use tools like JavaCC, ANTLR, attribute grammars,... than doing everything from scratch.