How can I write a quick and dirty interpreter?

Question

I have an interview where one of the areas I was told I might brush up on is "dynamic programming languages". So I figured I might spend this weekend writing one to bring as sample code. :-)

Of course, given the time constraints, I plan on writing something very basic and preferably using a language and/or toolset that will make it extremely easy to do. Most of my experience is in Python, but I'm willing to spend a little time learning something new if it will make the task easier (and won't take too long). Does anyone have any advice for me in terms of tools or languages that will make this easier?

Answer 1

You'll probably want to check out Lex and Yacc for lexing and parsing, and their python implementations

Answer 2

I used spark to write a pretty full featured DSL to express complicated conditionals for an old project of mine in 2 or 3 days (including unit tests).

It should be quite trivial in Python since spark (and other such modules) will give you tools you need to write a lexical and syntax analyser. You can implement a simple symbol table easily using a python dictionary and can either translate it into Python and eval or move it to some lower level language to run.

Answer 3

If you want to write a a very simple interpretive language, you should take a look at FORTH. The lexer is trivial (tokens are space separated) and the interpreter is also very simple. And if FORTH is too retro, take a look at Scheme - you can build a tiny Scheme interpreter very quickly.

Answer 4

An interpreted language != a dynamic language, though the opposite is not always true.

If you are quite versed in Python (== dynamic) then I think you should do well in your interview unless they ask the difference between interpreted and dynamic languages.

Answer 5

I'd recommend using Haskell with parsing combinators. To bone up on parsing combinators, don't use the Wikipedia article; it's very theoretical and will likely confuse you. Instead use the paper by Graham Hutton, which is excellent.

Interpreters and compilers are the "killer app" for the ML/Haskell family of languages, and I think you'll be amazed at how quickly you can build something interesting.

For getting started I recommend you read Phil Wadler's paper The Essence of Functional Programming, which contains a number of sample interpreters organized using monads. I think the example interpreters are well organized and easy to follow, although the explanation of monads in that paper may make your head hurt.

There's also a very nice blog entry that goes through a single example in much more detail; it describes a Lisp interpreter written in Haskell. That writeup also contains a few comparisons between Haskell and Java, which may give you a feel for why many compiler writers prefer a functional language over an OO language for writing compilers and interpreters.

Have fun!!!!

Answer 6

The typical toy example for an interpreter is the Brainfuck language.