Developing a dynamic language

Question

I have created several hand written compilers for very simple languages but now I want to try my hand at developing a dynamic language, similar to a simplified Python or Ruby. However, it was easy for me to wrap my head around how compilers work. Primitive compilers just translate. But I can't do this if the language is dynamic. I have to write an interpreter or VM that keeps track of information at runtime and puts a lot more work on me.

In short, are there any resources I should check out considering I know how compilers work but want to migrate to creating an interpreter? There are a few VMs out there for dynamic languages, but I have no problem with rolling my own. This is all just for my personal experience.

I am seeking information on how to go from a compiler to an interpreter. If I have already made a compiler for language X but now what to write an interpreter, what needs to be done and are there any resources that go over the process?

I do not want broad or abstract resources that go over how compilers or virtual machines work. I have plenty of textbooks on the subject. All of the resources I found online either assume you have 0 experience and thus start you off with lexical or syntactic analysis or they are extremely abstract. I have a working compiler, but I now want to turn this into an interpreter and add dynamic features to the language.

I could not find resources on this process, it may be too limited in scope, or resources on the "back end" of an interpreter without being too theoretical which is why I posted here.

• Robert Harvey: There are tons of resources like this. Note that the line between compiler and interpreter is more blurred than you think it is; the C# 4.0 compiler supports dynamic programming, as do a number of other compilers.
• Austin Henley: @RobertHarvey Yes, what I am asking is for resources to make my own run time/interpreter/virtual machine. The .Net interpreter is far too complicated for me to base mine off of!
• yannis: Writing Compilers and Interpreters: A Software Engineering Approach, (How to Write a (Lisp) Interpreter (in Python)), Virtual Machine Showdown: Stack Versus Registers (PDF), The design of the Inferno virtual machine, Parrot: A Virtual Machine For Everyone
• yannis: And check out this SO question, there are a couple of comments with references to other questions that are quite interesting...

Answer 1

First learn about implementing interpreters. I recommend PLAI (Programming Languages: Application and Interpretation). It gets to the meat of interpretation quickly without dwelling overlong on syntax.

For your language, you'll be able to reuse the compiler's front-end (parser, mostly) and run-time library (GC, data structures, primitive operations, etc).

Of course, you can also implement a dynamic language with a compiler that produces code that manipulates (some of) the same data structures that you would use in an interpreter. For example, in an interpreter you might implement global variables as a string-indexed hash table. In a compiler, you would compile global variable references into the code that does the lookup using the same table. In contrast, you could compile lexical variables into a more efficient representation ("native" arguments and closure structure references).

Answer 2

If you want to learn the basics of implementing an interpreter for a dynamic language, I can't imagine a better place to start than the origins of the very first dynamic, interpreted programming language: Lisp.

In his original 1960 paper, John McCarthy defined 5 primitive functions necessary to a Lisp. Of course, McCarthy only intended his paper on Lisp as an academic exercise; it was a graduate student who implmented eval in assembly and created the first Lisp interpreter. Paul Graham identifies seven primitives: quote, atom, eq, cons, car, cdr, and cond.

The thing is, you can really implement Lisp in any language; once you implement eval, it's easy to set up a REPL, and you have an interactive interpreter. People have been bored or curious enough to implement Lisps in C, Java, Ruby, Python, and many other languages. And not always on purpose; it's important to remember Greenspun's Tenth Rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

I'm not saying your end-goal should be a Lisp implementation; but homoiconicity has its benefits when learning to implement a dynamic language; why deal with syntax issues when you can learn on a language in which the idiomatic syntax is identical toe the AST of a language that uses a lexer/parser?

Anyhow... just a suggestion. But it is with good reason that most of the great programming languages since C have at least a little of the Lisp-nature.

• Austin Henley: I wish I could accept two answers. Thanks, I think I really will implement a Lisp interpreter. It is easy to parse, has ton of documentation and existing code, and should give me a foundation to work with. Unfortunately I took an undergraduate class that used Scheme and it made me pull my hair out ;)
• Austin Henley: I am now tempted to compile my language into my own dialect of Lisp!
• coredump: See also Lisp in Small Pieces

Answer 3

I've put this (~ 600 lines of C#) in the public domain, which supports quote / list / apply / eval / test / etc, and allows to customize a Lisp-like syntax and/or the semantic builtins easily:

https://repl.it/CdjV/3

E.g.:

 var factorial = (Lambda)language.
 Evaluate
 (@"
 ( => ( n ) (
 ? ( != n 0 )
 ( * n ( this ( - n 1 ) ) )
 1
 )
 )
 ");
 var sw = new System.Diagnostics.Stopwatch();
 var n = 12;
 var r = 0;
 int k;
 sw.Start();
 for (k = 0; k < 10000; k++)
 {
 r = (int)factorial.Invoke(null, n);
 }
 sw.Stop();
 Console.WriteLine("{0}! = {1}", n, r);
 Console.WriteLine();
 Console.WriteLine("in {0} ms (for {1} times)", sw.ElapsedMilliseconds, k.ToString("0,0"));

'HTH,

Answer 4

Assuming you know a bit of Scheme (e.g. have read SICP) or Lisp, I recommend Queinnec's Lisp In Small Pieces book. It explains several variants of Lisp-like interpreters & compilers (including to bytecode or to C).

Also, read Scott's Programming Language Pragmatics, the latest Dragon Book, the GC handbook, Pierce's Types & programming languages.

I am seeking information on how to go from a compiler to an interpreter.

Then, partial evaluation (& Futamura projections) and continuation-passing style could be relevant.