What are the main issues in designing an interpreter for a functional language?

Question

Suppose I want to implement an interpreter for a functional language. I would like to understand the issues involved in doing so and suitable literature that is available. This is a new language that is in early design stages, that is why the question is broad in scope.

For the purpose of this discussion we can assume that the purpose of the language is not important and that its functional features can be changed (even drastically) if it makes a significant difference in the ease of writing an interpreter.

The MIT website has an online copy of Structure and Interpretation of Computer Programs as well as videos of the MIT 6.001 lectures using Scheme, recorded at HP in 1986. These form a great introduction to language design.

Answer 1

I would highly recommend Structure and Interpretation of Computer Programs (SICP) as a starting point. This book will introduce the idea of what it means to write an interpreter (and a compiler), and is generally a must-read for anybody designing languages.

Implementing an interpreter for a functional language isn't likely to be too much different from implementing an interpreter for any other general purpose language. There's lexical analysis, parsing, AST construction, semantic analysis, plus execution (for a pure interpreter) or code generation and optimisation (for a compiler, even compiling to bytecode like Java/Perl/Python). SICP will introduce the difference between "applicative order" and "normal order" evaluation, which may be important for you in a pure functional context.

Answer 2

The main issue is having a semantics for the language you're implementing -- with that, the implementation becomes straightforward. Otherwise, this question is incredibly broad and hard to answer.

Answer 3

For just about any language interpreter or compiler, the main issues are the same, I think.

You need to decide certain basic characteristics of the language (semantics, not syntax), and the bulk of the design of the thing follows from that.

• For example, does your language have a type system? If so, what sorts of types does it have? Is it going to be statically typed, dynamically typed, duck-typed?

• What sort of expressions are you planning to support? Do you need to define an order of operations? Will you even have operators?

• What will you use as the run-time representation of the program? Will you convert the text to a byte-code representation, or an AST, or a tokenized form of the source text?

There are toolkits available to help take some of the tedium out of the actual parsing of text (ANTLR and Bison, to name two), but I don't know of anything that helps with the actual interpretation part of the task. I'm sure somebody will suggest something.

Answer 4

See http://www.cs.cornell.edu/courses/cs312/2005sp/lectures/lec17.asp

Answer 5

I'd recommend Essentials of Programming Languages as a good complement to SICP, particularly if you're interested in interpreters: Official EOPL site. You may want to check out the third edition-- the site hasn't been updated for it yet.

Edit: spam prevention is making me choose between links, so the official page is now unheated. It's easily Google-able, though.