10 ms·
Why I wrote a book about interpreters
- CarolineW 10y agoDupe: https://news.ycombinator.com/item?id=13079250 https://news.ycombinator.com/item?id=13079250 And again: https://news.ycombinator.com/item?id=13071939 https://news.ycombinator.com/item?id=13071939 Edit: To those who downvoted me, let me just point out that this was submitted less than an hour after the previous submission, hence my pointing at that (barely) earlier item.
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- alayne 10y agoPlease don't post previous submissions without comments, they are worthless.
- CarolineW 10y agoSo let me ask a serious question here. Suppose someone submits a story. The following day it has few points, and no comments. If someone then submits the same story, fair enough. Now suppose the story is submitted, has few points, no comments, and then 30 seconds later someone submit the same story. Is it fair to point at the one that's only 30 seconds old? I would say yes, you might disagree, I would be interested to know what you think. If it's reasonable to point at a submission that's only 30 seconds older, then we have a question: How old should a previous submission be to declare that it's fair enough to give it a second chance? I would say that an hour isn't long enough, so if something is submitted a second time within an hour then it's perfectly reasonable to point at the previous submission. If you disagree, fine, say so. If you think it's reasonable that something is submitted within seconds of a previous submission, say so. I'd be interested to know what you think is reasonable. It's plausible that we have different opinions about what is reasonable in this context. If so, I'd like to know what you think.
- alayne 10y agoIf you have issues with the site functionality, you should contact hn@ycombinator.com.
- CarolineW 10y agoSo it's OK for you to tell me what to do, and what not to do: > Please don't post previous > submissions without comments, > they are worthless. ... and yet you decline to answer my question, or to tell me your opinion on these matters. That's a pity. I'd've liked to have known your thoughts as to whether it's reasonable to have multiple submissions within minutes without indicating the duplication.
- deleted 10y ago[deleted]
- ThreadCap 10y agoThe only pity here is you thread crapping on someone else's work. Its obviously apparent that your highly disgruntled and most likely suffering from lack of real world socialization. If your looking for authoritative responsibilities please ensure that there actually wanted before naming your self as the enforcer. Further, I would recommend you crawl back into the hole from which you came, as your comments provide no value to the public discussion at hand.
- CarolineW 10y agoThank you.
- OJFord 10y agoI've tried to submit before, and it's stopped me by detecting it's a dupe before accepting it. How did this submission get through that check within an hour of the previous one?
- deleted 10y ago[deleted]
- nickpsecurity 10y ago[Ignoring the dupes since they got no attention. Good reason to resubmit if material is worthwhile.] The author seems to be doing a good thing. Like he said, most of the write-ups on this subject are either ultra-heavy with theory or basically nothing with code examples. Doing interpreters piece-by-piece like in SICP or The Little Schemer series in an accessible language gradually giving them the code and theory they need is a good idea. It could also help in my verifiable builds scheme where people show no subversion exist by building from ASM to small language (or interpreter) then to bigger one then whole compiler. I was debating p-code, Oberon, Scheme, MiniML... Biggest problem is that the best stuff, eg Scheme's or ML's, is least likely for imperative programmers to try to understand. Something like this could help if I use an imperative base.
- CarolineW 10y agoAt the time I pointed out that this is a dupe the previous submission had been less than an hour earlier, scarcely giving it enough time to get any attention. But screw that, let's just submit things every 10 minutes until they get upvotes.
- nickpsecurity 10y agoOh I overlooked that. Guessed that the others were older. My bad on that.
- agumonkey 10y agoPersonal story only, I never liked Imp, nor OO that much (all my OO code tried to be lisp or caml without knowing it). I learned lisp eval, then lc, typed lc.. recently prolog; where the machine vanishes quite a lot. Yet the very high abstraction view that path led to makes the understanding of systems and languages very coherent even if thinking in an imperative POV. But I can't suggest doing that to anybody since it may fail miserably for them.
- nickpsecurity 10y agoHere's the one I always drop for people like you: http://lambda-the-ultimate.org/node/1752 http://lambda-the-ultimate.org/node/1752 It stays low-level and builds the components of a Scheme at same time. Piece by piece with ability to understand and verify. The resulting language could be used to build better LISP's, ML's, Prolog's, etc. sklogic's DSL toolkit illustrates that nicely where he mix and matches on top of a foundation of a LISP custom-designed for it. Taking it further, you might like FLEX and Ten15 VM that unified higher-level languages: https://en.wikipedia.org/wiki/Ten15 https://en.wikipedia.org/wiki/Ten15
- gekkonier 10y agoExcept the dupe story, does anyone gave the book a closer look and can say if it's suitable for beginning programmers? By that I mean if it's suitable to study and implement an interpreter in other language without a degree in computer sience? Programming is one of my hobbies and my dream is to do an interpreter on my own, but most books are so heavy to understand if you know what I mean. Thank you very much for your opinion.
- steveklabnik 10y agoI haven't given the book a look, but in general, if you pick a small enough language, you can absolutely build an interpreter without needing a CS degree. A couple of years ago, I wrote https://github.com/steveklabnik/mojikun https://github.com/steveklabnik/mojikun , which is an implementation of Brainfuck. I specifically over-engineered it to be more like a real interpreter than the smallest possible code, so it's actually split into parser/lexer/runtime/interpreter. I also made it have a more strongly-typed AST, which in retrospect is a little silly, at least the way that I did it. A bunch of those files have empty classes for this purpose. Anyway, my overall point is, this project has the same structure as a "real" interpreter, and it's like 160 lines of code for the core functionality, no complex algorithms. And you can move on to harder languages fairly easily, and learn as you go.
- marcpaq 10y ago(Somewhat of a repost, but I'm a fan of these things.) I had the same feeling, so I tried it out myself. Inspired by Jonesforth (highly recommended), I wrote an arguably complete Lisp interpreter in a single, heavily commented ARM assembly language file. Lisp is an obvious target, with its minimal syntax and simple concepts. The first Lisp was written in assembly on a machine with comparable capacity to your laptop keyboard's microcontroller, after all. I hope you find it useful: https://github.com/marcpaq/arpilisp https://github.com/marcpaq/arpilisp
- misternugget 10y agoDisclaimer: I'm the author of the book and thus pretty biased. As a matter of fact, I wrote this book specifically for people like you and me: no CS degree, highly interested in interpreters and compilers, but intimidated by the existing literature. (If you studied compilers in college, this book will probably teach you nothing new.) There's a sample on the landingpage that should give you an impression of the difficulty - my guess is, that if you already know how to program and know the basics of Go, you'll get along just fine.
- ChicagoDave 10y agoI like these kinds of books a lot. I'm not at all interested in Go, so I'll probably convert the code to C# for my own amusement...but I dig it. I've mucked with lexers for text editing purposes and have always wanted to build my own compiler. It's somewhere down on the bucket list.
- zellyn 10y agoI highly recommend the Coursera compilers class: you don't have to work though it in synch with a class; just sign up and work at your own pace. If you have to watch the same video two or three times, you can. None of this stuff actually turns out to be that complicated: it just takes a little while to get the lingo and concepts. I implemented the entire parser, typechecker, and compiler in Go here: https://github.com/zellyn/gocool https://github.com/zellyn/gocool I then went back and hand-wrote a recursive descent parser, just for fun: Cool is such a simple language that it really wasn't difficult.
- riffraff 10y agoFWIW, I think the coursera class is now gone, but the course should have matched this http://web.stanford.edu/class/cs143/ http://web.stanford.edu/class/cs143/
- zellyn 10y agoThat's a pity: the lecture videos were worthwhile, and I got all the unit tests by dissecting the auto-checking scripts that the class supplied :-/
- riffraff 10y agoit's possible they are available in the internet archive backup, but I don't have idea how to inspect those without downloading tens of gigabytes of stuff. https://archive.org/details/archiveteam_coursera https://archive.org/details/archiveteam_coursera
- tzs 10y agoA fun and fairly simple project, with a surprisingly high ratio of usefullness to effort, is to write an interpreter for a concatenative language. Concatenative languages, like FORTH, can do a lot with very limited resources, making them good candidates for embedded systems. If you want to play around with making your own concatenative language, it is actually surprisingly simple. Here is an overview of a step-by-step approach that can take you from a simple calculator to a full language with some optimization that would actually be quite reasonable to use in an embedded system. So let's start with the calculator. We are going to have a data stack, and all operations will operate on the stack. We make a "dictionary" whose entries are "words" (basically names of functions). For each word in the dictionary, the dictionary contains a pointer to the function implementing that word. We'll need six functions for the calculator: add, sub, mul, div, clr, and print. The words for these will be "+", "-", "x", "/", "clr", and "print". So our dictionary looks like this in C: struct DictEntry { char * word; int (*func)(void); } dict[6] = { {"+", add}, {"-", sub}, {"x", mul}, {"/", div}, {"clr", clr}, {"print", print} }; We need a main loop, which will be something like this (pseudocode): while true token = NextToken() if token is in dictionary call function from that dict entry else if token is a number push that number onto the data stack Write NextToken, making it read from your terminal and parse into whitespace separated strings, implement add, sub, mul, div, clr, and print, with print printing the top item on the data stack on your terminal, and you've got yourself an RPN calculator. Type "2 3 + 4 5 + x print" and you'll get 45. OK, that's fine, but we want something we can program. To get to that, we first extend the dictionary a bit. We add a flag to each entry allowing us to mark the entry as either a C code entry or an interpreted entry, and we add a pointer to an array of integers, and we add a count telling the length of that array of integers. When an entry is marked as C code, it means that the function implementing it is written in C, and the "func" field in the dictionary points to the implementing function. When an entry is marked as interpreted, it means that the pointer to an array of integers points to a list of dictionary offsets, and the function is implemented by invoking the functions of the referenced dictionary entries, in order. A dictionary entry now looks something like this: struct DictEntry { char * word; bool c_flag; void (*func)(void); int * def; int deflen; } (continued in reply)
- 10y ago
- haberman 10y agoThe way I would sum up interpreters and compilers, trying to put it as concisely as possible: Step 1. Write a program that reads the input program into a data structure that exactly represents the language. You just wrote a parser. Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter. Step 3 (Optional): Write a program that converts the data structure from (1) into a different data structure that you can interpret more efficiently. You just wrote an optimizer. Step 4 (Optional): Keep iterating on (3) until the output of your optimizer is machine code. You just wrote a compiler. Not saying the above obviates the need for a book like this one (at all), I just had never thought of it in quite this way and wanted to write it down. :)
- Arnavion 10y agoNit: The output does not have to be machine code to be considered a compiler.
- nickpsecurity 10y agoIt can even be source code: source-to-source compiler.
- cestith 10y agoThat's technically true. Those are also known as translators, although they are technically no different from compilers. Something that compiles to an executable format for your environment is most likely to be actually called a compiler. Some "interpreters" are actually compiling to opcodes for a virtual machine then running on the virtual machine.
- clusmore 10y agoYes, it took me a while to "realise" (or perhaps "accept") this as well. What is machine code? Code that a machine can execute natively? What if I built a machine that had primitive instructions for JavaScript? Then JavaScript would be machine code, and an X->JavaScript "transpiler" could be considered a "compiler". Now what if before building such a machine, I wanted to simulate one? I could write a "virtual" machine, which is really just a program that acts like a physical machine with native JavaScript instructions. Also known as a JavaScript interpreter.
- nv-vn 10y agoAwesome! As someone interested in compilers and interpreters who has not completed a degree in computer science it was quite hard to get any of the background. This post is spot on: you'll either read a 1000 page book about it or you're stuck reading tiny blog posts. Notation also sucks for beginners, few books ever bother explaining it at all. My favorite/most helpful text I've found so far is Essentials of Programming Languages, which covers a wide variety of topics and introduces them as parts of (complete) interpreters. The code is written in very readable Scheme (so much so that I was able to understand everything despite not knowing Scheme or Lisp at the time I began reading it).