Shameless plug for the programming language course I'm TAing. It covers how to write a similar interpreter, with more detail about evaluation and less about parsing. The book and all of the assignments are online.
The "interpreter" assignment has a similar end-goal as this tutorial.
Many of the other assignments (the ones prefixed "ML-") are "mystery languages", where you try to tell the difference between two programming languages that have the same syntax but different semantics. It's a fun way to explore the consequences of language design, I think.
I can vouch for the mystery language assignments at least -- we worked through several at this year's Racket summer school (https://summer-school.racket-lang.org/2017/), and they were interesting and very engaging. (Hi Justin!)
This course looks awesome! Do you (or those scrolling by) know of any other courses like this? By this I mean short but focused burst of learning done in person.
Yes, there seem to be a number of summer schools every year on a variety of topics, although the ones I'm familiar with are based more in academia than in industry. I think they tend to get announced on the Types mailing list (https://lists.seas.upenn.edu/mailman/listinfo/types-announce).
I took the course a few years ago and can't overstate how much I learned implementing the interpreter assignments. They entirely revamped my thinking about programming and even prepared me for the real world a bit (my team at work just built a custom scheme interpreter for a deep learning DSL)
IMHO Lisp-like languages are good for showing off the "back-end" of a compiler/interpreter, because tokenisation/parsing is completely trivial. On the other hand, you miss out a lot of the fun of parsing a "real" language, with precedences and a more nontrivial grammar.
One of the most enlightening points about interpreters/compilers is that, to a first approximation, the only difference between an interpreter and compiler is what it does when it walks the tree --- an interpreter executes the actions immediately, while a compiler generates code which executes those actions.
(Aside: I happened to glance at the URL at the same time as I was reading the Tokenisation section, and thought "Francis Tokes? How appropriate..." before looking more closely at the page title.)
Hey - author here. You're completely right, but I hope the basic understanding will whet peoples appetites to try some more exotic stuff! Really I was just trying to lift the veil of what can be a quite intimidating subject if you haven't grazed past it before. Thanks for checking it out!
> One of the most enlightening points about interpreters/compilers is that, to a first approximation, the only difference between an interpreter and compiler is what it does when it walks the tree --- an interpreter executes the actions immediately, while a compiler generates code which executes those actions.
For something else in a similar vein, I've always liked:
I suppose implementing brainfuck is more like writing a vm, than a language - but I still think the article is a surprisingly straightforward implementation of a compiler.
If you have an interpreter, you can obtain a native executable by attaching the interpreter code to the source file, and then removing all the unnecessary parts (optimizing). This is called the first Futamura projection.
Discovering the nature of second and third Futamura projections is left as an exercise to the reader ;)
Yes! I was looking for something similar to create a basic database in order to really understand the underlying concepts, but couldn't really find anything.
Using a Lisp-like language is great for creating a new language because of the S-expressions that Lisp depends on.
S-expressions are very compact and are easy to parse. There was actually some support for using S-expressions over XML and JSON as a serialization language.[1]
Ron Rivest even proposed S-expressions as a standard.[2]
I still prefer JSON over them though. As the old joke goes, LISP stands for "Lots of Irritating Silly Parentheses."
After grokking the tokenisation, parsing and eval of lisp like languages, what's the next step up?
I usually have a bit of fun mocking out a language I'd like but end up getting into details like type systems. I never really get to expressing as a CFG.
I'm wondering if the best course is to say right, keys now build a small, procedural language or some kind of barely typed C lookalike as the best step up?
At a glance, you could make a very unsafe not-really C without too much thought. I probably wouldn't make it too C like, just so I could avoid worrying about parsing etc.
As to type systems, that's a completely different can of worms (One which I do not have much expertise in). Type systems can range from the simple e.g C to the formal study of type systems (e.g. Hindley-Milner). Personally, I don't really know the formal side very well (I can't recall details from memory the same way I can with (say) Lagrangian mechanics), so I can't recommend one particular book.
This intuitively makes a lot of sense. The short variable names with the legend at the top makes it a little harder to understand but you can see what's going on from a macroscopic view. Perhaps translating this to another language with clearer variable names would be a good exercise for me.
quote from article: "As a side note: if Lel ever becomes popular enough that people argue about tabs vs spaces, or if function bodies belong on a newline always, that will absolutely make my life."
http://cs.brown.edu/courses/cs173/2016/index.html
http://cs.brown.edu/courses/cs173/2016/assignments/programmi...
http://cs.brown.edu/courses/cs173/2016/assignments.html
The "interpreter" assignment has a similar end-goal as this tutorial.
Many of the other assignments (the ones prefixed "ML-") are "mystery languages", where you try to tell the difference between two programming languages that have the same syntax but different semantics. It's a fun way to explore the consequences of language design, I think.
Next year we might do a MOOC.