3 ms·

Except 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

Except 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 ago
I 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 ago
Disclaimer: 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.
- senko 10y ago
  On a total tangent, I'd love to get that metacircular interpreter poster, any chance you'd like to sell a print-quality copy? :)
PeCaN 10y ago
Sure, I think I wrote my first interpreter when I was about 15. It's not hard at all. The trick is finding the right resources. IIRC I studied http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html for lexing + parsing (I wouldn't understand LL or LR parsing for years… you really don't need to) and wrote a very naïve AST-walking interpreter (the idea of compiling to bytecode and interpreting that did not occur to me). Now I'm sort of a serial language designer/implementor and pump out virtual machines on a regular basis. This stuff is really easy until you want to make it fast, then it gets really hard. ;-) Just for starting out, I think you should basically make parsing as simple as you can. It's probably the most confusingly computer-sciency part of language implementation… and also probably the least important. So just avoid it. Maybe write a Lisp or Forth if you want. I actually advocate just using a very small simple (pascal-like) syntax though, and writing an operator-precedence parser. You'll learn more that way.
pdpi 10y ago
My suggestion to you is simple: go read about the brainfuck language, and implement an interpreter for it. You'll probably get to the end and find that your first implementation "cheats", whatever that means. That's fine, improve it. Write the memory model as a contained module, and have the interpreter core call into it. Build an internal representation of a program, then make reading the source code a separate step from running it. Once you have that representation, some opportunities arise: e.g. represent increment and decrement as "add 1" and "add -1" instead. Then you can write your first optimiser: turn long runs of increment and decrement instructions in the source code into a single "add n" instruction. At this point, you have modules that turn source code into an internal representation, optimise the internal repr, and execute it. Start thinking of commands you can add to the language. Start thinking of how to handle data in the source code, rather than just instructions. How to build functions. When you get to this point, you'll realise that you're no longer thinking "I wonder how an interpreter works", but rather "I wonder how you implement this particular part of an interpreter", and that is a much easier question to find answers for.
sn9 10y ago
You can read The Little Schemer and The Seasoned Schemer which are deceptively easy to work through but teach you concepts some CS grad students are ignorant of. Following it up with Structure and Interpretation of Computer Programs will make you a much stronger programmer. You can work through Sedgewick's Algorithms course on Coursera to get a stronger foundation for the more technical aspects of compiler writing. You can study Stanford's Compilers course online: https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/...
_mhr_ 10y ago
I suggest http://web.archive.org/web/20160413005246/http://www.norvig.com/lispy.html http://web.archive.org/web/20160413005246/http://www.norvig..... It's extremely easy to understand. Once you start adding features to your Lisp interpreter and extending it, you'll eventually realize that the naive recursive descent approach is getting in the way of your more complicated ideas, but you'll be ready to try more sophisticated approaches to writing an interpreter. Nothing beats Norvig to me for learning how to write an interpreter as a beginner. Lisp isn't as complex as the Monkey programming language from https://interpreterbook.com https://interpreterbook.com, but I argue that that's a good thing. Once you get the basic principles, writing an interpreter for a language like Monkey seems like a much more easily surmountable task.

steveklabnik 10y ago

I 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 ago

Disclaimer: 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.

senko 10y ago
On a total tangent, I'd love to get that metacircular interpreter poster, any chance you'd like to sell a print-quality copy? :)

PeCaN 10y ago

Sure, I think I wrote my first interpreter when I was about 15. It's not hard at all. The trick is finding the right resources. IIRC I studied http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html for lexing + parsing (I wouldn't understand LL or LR parsing for years… you really don't need to) and wrote a very naïve AST-walking interpreter (the idea of compiling to bytecode and interpreting that did not occur to me). Now I'm sort of a serial language designer/implementor and pump out virtual machines on a regular basis. This stuff is really easy until you want to make it fast, then it gets really hard. ;-) Just for starting out, I think you should basically make parsing as simple as you can. It's probably the most confusingly computer-sciency part of language implementation… and also probably the least important. So just avoid it. Maybe write a Lisp or Forth if you want. I actually advocate just using a very small simple (pascal-like) syntax though, and writing an operator-precedence parser. You'll learn more that way.

pdpi 10y ago

My suggestion to you is simple: go read about the brainfuck language, and implement an interpreter for it. You'll probably get to the end and find that your first implementation "cheats", whatever that means. That's fine, improve it. Write the memory model as a contained module, and have the interpreter core call into it. Build an internal representation of a program, then make reading the source code a separate step from running it. Once you have that representation, some opportunities arise: e.g. represent increment and decrement as "add 1" and "add -1" instead. Then you can write your first optimiser: turn long runs of increment and decrement instructions in the source code into a single "add n" instruction. At this point, you have modules that turn source code into an internal representation, optimise the internal repr, and execute it. Start thinking of commands you can add to the language. Start thinking of how to handle data in the source code, rather than just instructions. How to build functions. When you get to this point, you'll realise that you're no longer thinking "I wonder how an interpreter works", but rather "I wonder how you implement this particular part of an interpreter", and that is a much easier question to find answers for.

sn9 10y ago

You can read The Little Schemer and The Seasoned Schemer which are deceptively easy to work through but teach you concepts some CS grad students are ignorant of. Following it up with Structure and Interpretation of Computer Programs will make you a much stronger programmer. You can work through Sedgewick's Algorithms course on Coursera to get a stronger foundation for the more technical aspects of compiler writing. You can study Stanford's Compilers course online: https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/...

_mhr_ 10y ago

I suggest http://web.archive.org/web/20160413005246/http://www.norvig.com/lispy.html http://web.archive.org/web/20160413005246/http://www.norvig..... It's extremely easy to understand. Once you start adding features to your Lisp interpreter and extending it, you'll eventually realize that the naive recursive descent approach is getting in the way of your more complicated ideas, but you'll be ready to try more sophisticated approaches to writing an interpreter. Nothing beats Norvig to me for learning how to write an interpreter as a beginner. Lisp isn't as complex as the Monkey programming language from https://interpreterbook.com https://interpreterbook.com, but I argue that that's a good thing. Once you get the basic principles, writing an interpreter for a language like Monkey seems like a much more easily surmountable task.