title: References Needed for Implementing an Interpreter in C/C++
body: <p>I find myself attached to a project to integerate an interpreter into an existing application. The language to be interpreted is a derivative of Lisp, with application-specific builtins. Individual 'programs' will be run batch-style in the application.</p>
  
  <p>I'm surprised that over the years I've written a couple of compilers, and several data-language translators/parsers, but I've never actually written an interpreter before. The prototype is pretty far along, implemented as a syntax tree walker, in C++. I can probably influence the architecture beyond the prototype, but not the implementation language (C++). So, constraints:</p>
  
  <ul>
  <li>implementation will be in C++</li>
  <li>parsing will probably be handled with a yacc/bison grammar (it is now)</li>
  <li>suggestions of full VM/Interpreter ecologies like NekoVM and LLVM are probably not practical for this project. Self-contained is better, even if this sounds like NIH.</li>
  </ul>
  
  <p>What I'm really looking for is reading material on the fundamentals of implementing interpreters. I did some browsing of SO, and another site known as <a href="http://www.lambda-the-ultimate.org" rel="nofollow noreferrer">Lambda the Ultimate</a>, though they are more oriented toward programming language theory.</p>
  
  <p>Some of the tidbits I've gathered so far:</p>
  
  <ul>
  <li><p><a href="https://rads.stackoverflow.com/amzn/click/com/0521545668" rel="nofollow noreferrer" rel="nofollow noreferrer">Lisp in Small Pieces</a>, by Christian Queinnec. The person recommending it said it "goes from the trivial interpreter to more advanced techniques and finishes presenting bytecode and 'Scheme to C' compilers."</p></li>
  <li><p><a href="http://nekovm.org/" rel="nofollow noreferrer">NekoVM</a>. As I've mentioned above, I doubt that we'd be allowed to incorporate an entire VM framework to support this project.</p></li>
  <li><p><a href="http://mitpress.mit.edu/sicp/full-text/book/book.html" rel="nofollow noreferrer">Structure and Interpretation of Computer Programs</a>. Originally I suggested that this might be overkill, but having worked through a healthy chunk, I agree with @JBF. Very informative, and mind-expanding.</p></li>
  <li><p><a href="http://paulgraham.com/rootsoflisp.html" rel="nofollow noreferrer">On Lisp</a> by Paul Graham. I've read this, and while it is an informative introduction to Lisp principles, is not enough to jump-start constructing an interpreter.</p></li>
  <li><p><a href="http://www.sidhe.org/~dan/presentations/Parrot_Implementation.pdf" rel="nofollow noreferrer">Parrot Implementation</a>. This seems like a fun read. Not sure it will provide me with the fundamentals.</p></li>
  <li><p><a href="http://peter.michaux.ca/articles/scheme-from-scratch-introduction" rel="nofollow noreferrer">Scheme from Scratch</a>. Peter Michaux is attacking various implementations of Scheme, from a quick-and-dirty Scheme interpreter written in C (for use as a bootstrap in later projects) to compiled Scheme code. Very interesting so far.</p></li>
  <li><p><a href="http://pragprog.com/book/tpdsl/language-implementation-patterns" rel="nofollow noreferrer">Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages</a>, recommended in the comment thread for <a href="https://stackoverflow.com/questions/2853412/books-on-creating-interpreted-languages">Books On Creating Interpreted Languages</a>. The book contains two chapters devoted to the practice of building interpreters, so I'm adding it to my reading queue.</p></li>
  <li><em>New</em> (and yet <em>Old</em>, i.e. 1979): <a href="http://books.google.com/books?id=d6cpAQAAIAAJ&amp;q=writing+interactive+compilers+and+interpreters&amp;dq=writing+interactive+compilers+and+interpreters&amp;hl=en&amp;ei=FzorTsDzFIj0swOb_4XMCg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCkQ6AEwAA" rel="nofollow noreferrer">Writing Interactive Compilers and Interpreters</a> by P. J. Brown. This is long out of print, but is interesting in providing an outline of the various tasks associated with the implementation of a Basic interpreter. I've seen mixed reviews for this one but as it is cheap (I have it on order used for around $3.50) I'll give it a spin.</li>
  </ul>
  
  <p>So how about it? Is there a good book that takes the neophyte by the hand and shows how to build an interpreter in C/C++ for a Lisp-like language? Do you have a preference for syntax-tree walkers or bytecode interpreters?</p>
  
  <p>To answer @JBF:</p>
  
  <ul>
  <li><p>the current prototype is an interpreter, and it makes sense to me as we're accepting a path to an arbitrary code file and executing it in our application environment. The builtins are used to affect our in-memory data representation.</p></li>
  <li><p>it should not be hideously slow. The current tree walker seems acceptable.</p></li>
  <li><p>The language is <em>based</em> on Lisp, but is not Lisp, so no standards compliance required.</p></li>
  <li>As mentioned above, it's unlikely that we'll be allowed to add a full external VM/interpreter project to solve this problem.</li>
  </ul>
  
  <p>To the other posters, I'll be checking out your citations as well. Thanks, all!</p>