Is INTERPRETER an anti-pattern?

Question

To me, the Interpreter patten sounds very much like an anti-pattern known as 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.

That is, if you need to use Interpreter, you're likely to create something that's slow, ad-hoc and poorly specified. The right solution is to use the right language from the beginning.

Or, alternatively, embed a well known and well specified language into your application, such as Guile (the GNU embeddable scheme). Or use Haskell as an embedded domain-specific language.

But I haven't seen this in practice--what are your experiences regarding building your own embedded languages? Is it a good idea? Is it better than embedding an already existing language?

(I'm not particularly a lisp fanboy. It's nice, but so's C and Haskell and python and a lot of other languages.)

Answer 1

There's nothing in the interpreter pattern that says it has to be another programming language's syntax that you're interpreting. If you need to parse a simple mathematical expression, then interpreter is just the thing.

Knowing when to use a pattern is what prevents it from being an anti-pattern.

Answer 2

Any design pattern is an anti-pattern if misused.

Good uses of the Interpreter Pattern:

• Software compiler
• SQL evaluation engine
• Graphing calculator input parser
• XML parser

These are all programs that solve the problem of evaluating words in a language, whatever that language may be.

Answer 3

Keep in mind that the 'interpreter pattern' is a specific design pattern in OOP.

It has nothing to do with 'Interpreters' or their uses in general.

Answer 4

At some point or another, a project is probably going to need a configuration system. something simple is usually all that is needed at first, something like key-value pairs so that the system can connect to the local database, or some such. If this is all that's needed, its common to just hack up a simple parser for a dialect of INI or CSV and move on. But as the system grows and matures, more significance is placed on configuration. This is normal and healthy, refactoring functionality and responsibility to the correct layer of abstraction. From here it won't be long for the developers or even the (gasp) users to want a more expressive configuration language. Before anyone even notices, the system has a turing complete language built in and in use.

This is the basic pattern of Greenspunning. Everything was well engineered up to that last bit, where an ad-hoc language was thrust into the realm of real computational work.

Any system of a decent size probably should contain at least half of clisp.

Knowing that in advance is a big step. A very convenient way to write large systems is to pick a nice, easily hacked interpretive language and write your system in it. This happens to be exactly what TCL is designed to do, but these days it's hard to get anyone behind a large project in that language. On the other hand there are plenty of other languages which now offer all these benefits.

The benefit of doing things this way is the Active File Pattern. Simple configurations are written in a way that is compatible with a language parser that is available to the system. Since the file is being parsed by the language, more complex logic can be embedded easily.

An example of this in the wild is django's settings.py. For some reason, django isn't very smart about guessing where the django project is installed. Using a smattering of standard python in the configuration file, this can be handled in the general case in a portable way, that will suit almost every possible user. In spite of that, most of the settings.py file looks like plain old key=value pairs typical of .ini style config files.

The relationship to the interpreter pattern is that these mature languages are likely to get the pattern right for even some pathological uses. As soon as you know you need to parse something, come up with a very good reason not to use an existing language for it.

Answer 5

The interpreter pattern doesn't imply writing a complete general scripting language. If you need that, obviously it would make more sense to use a well-known language that people have already written good books about (or best of all, to allow the user to pick the language).

The interpreter pattern is more about the idea of persisting an object graph but choosing a persistence format that is human-readable and human-editable (such as 2 + 3 representing an Addition object with pointers to a couple of Integer objects). Even if this is never exposed to customers as a "language", it still aids debugging, support, on-site hacking and so forth. Other common examples would be query languages such as HQL in [N]Hibernate - no existing language would have been quite as good for the purpose of describing a query at that abstraction level.

As others have suggested, XML is commonly used as a basic syntax for this (especially when conceiving of the persisted object graph as a "configuration file", and see also Microsoft's XAML), but it's actually a sub-optimal choice. JSON in UTF-8 (or similar) would be cleaner, easier to parse, more readable and editable, and so probably better for most applications. But there are some great lightweight parser libraries which take a BNF-like syntax description and can then parse text into a DOM-like walkable structure, all at runtime, so cooking up a highly-specific succinct syntax is no problem.

Answer 6

You obviously aren't a Lisp "fanboy", because the boys and girls that fit that description can usually be relied upon to know that Lisp is a compiled language. Lisp appeared in 1958. The 1961-dated Lisp 1 manual already describes compiling.

Interpreting is useful; it gives us semantics without having to write a compiler first. This semantics provides a reference model for the compiled semantics: ideally, interpreted and compiled programs do the same thing. When we find they don't, we either resolve it, or somehow delineate and justify the situation.

Interpreting can be used to bootstrap a compiled Lisp system without requiring an existing Lisp implementation, but instead using another language such as C. Interpreting avoids the need to write a Lisp compiler in the bootstrapping language.

The CLISP implementation of ANSI Common Lisp is a good example of this. To build CLISP you need only a C compiler. CLISP's Lisp compiler is written in Lisp. So, of course, you have nothing to run that compiler with. The solution is to interpret the compiler using an interpreter written in C.

While running interpreted, the compiler compiles much of the Lisp library. The result of this is what CLISP calls a "half-compiled memory image": an image which contains compiled routines, but some interpreted routines. (I think, the compiler itself is still interpreted code).

This half-compiled image is then used to compile the remaining code, resulting in the fully compiled image.

Without the interpreter, CLISP's compiler could only be bootstrapped by insisting on another Lisp implementation to be installed first. (The way you need a C compiler to boostrap GCC). Or else, CLISP's compiler would have to be written in C, so that the compiler is compiled using the existing C compiler, and then applied to Lisp code to compile it before it can be run.

Nobody in their right mind wants to write a Lisp compiler in C, and requiring a Lisp implementation to build a Lisp implementation is a big disadvantage in a world in which Lisp isn't ubiquitous. What would happen under the Lisp-compiler-in-C boostrapping model is that the Lisp compiler written in C would be a completely minimal and possibly incomplete one that emits poor quality code, only good enough to initiate the boostrapping, and a "real" compiler would still be written in Lisp.

Answer 7

Maybe the the implementation of the Lisp compiler includes an example of the Interpreter pattern.

I don't think you should say that "wheel", for example, is an anti-pattern, even though you should usually buy wheels ready-made instead of reinventing them.

Answer 8

Interpreter is the idea behind the JavaCC parser generator. I think it works fine.

Interpreter is a far more respectable GoF pattern than Singleton. That's the one that needs to be voted off the island. Maybe Memento as well.

Answer 9

One of the reasons XML was invented was to save us from all writing EDI interpreters; but at least the scope was well defined, and we all did it approximately equally (at least sufficiently) efficiently. At least I'm still sufficiently deluded to think it was the right thing to do.

Sounds like you're trying to start a new urban legend? Are you congenitally opposed to Domain Specific Languages?

Answer 10

Generally the phases of a compiler/interpreter looks like this:

1. Syntax
2. Parse Tree
3. AST
4. Compile or Interpret

In Lisp, 1 and 2 are combined into 3.

Therefore it is a bit obvious that complex programs might have a custom language embedded in them that is "an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp".

However I would have to say that hand writing AST trees is unpleasant and is not the end all language no matter how many Lispers claim it to be.