11

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.

4

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).

5

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.

  • 1
    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 Feb 28 '12 at 5:09
  • 1
    I am now tempted to compile my language into my own dialect of Lisp! – Austin Henley Feb 28 '12 at 5:30
  • 1
    See also Lisp in Small Pieces – coredump Jul 27 '16 at 5:19
0

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,

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.