Prolog-based interpreter

Question

I've already gotten my feet wet with functional programming; I am familiar (though not proficient) in Haskell and PLT Scheme. I've used PLT Scheme to build little interpreters for toy languages (referencing PLAI)--I'm better with imperative languages.

Could anyone direct me to resources I could use to build a small interpreter of a toy language of my choosing with Prolog?

Answer 1

I mainly use SWI-Prolog so most of what I say will be SWI-Prolog related. However, other Prolog implementations may have similar predicates/libraries (perhaps with a bit different name) so you may search their manuals and find them. Also, I am writing a compiler, not an interpreter, in prolog so maybe some parts are not so interpreter-related.

SWI-Prolog's documentation site is really good for finding stuff: use the search box to find any predicate or do a typical search. There is a plethora of libraries but you might want to implement some stuff yourself to gain experience. You might end up re-inventing the wheel but it would be useful.

The book "The Art of Prolog" (Sterling, Shapiro) has a chapter dedicated to building a compiler in Prolog (and it's a nice book on Prolog too).

Maybe there are some tools equivalent to lex/bison for Prolog; I never really searched.
Imho, the lexer is quite easy in plain Prolog; naturally, it will be based heavily on pattern matching.

For the parser I suggest using DCG: definite clause grammars: SWI-Prolog doc, google for more details.
The problem is that you will have to parse the whole file (or at least I haven’t found a way to do it otherwise). Btw, the lexer could also be done with DCGs but I don’t think it's really better.

If you choose to have intermediate code, an abstract syntax tree is easy to produce from the parser (you could evaluate a lot of stuff during the parsing too).
About semantic checks: in my compiler for a toy language I do most of the semantic checks (scope related, function calls) during the parsing and the rest at a separate step. It's a bit messy

other useful stuff: check assert/1, global variables, meta predicates (maplist/\[2-6\]).
not pure Prolog and you might make your code too imperative by abusing them (and then you could have some really nasty side-effects)

For symbol table (if you need it) you could just use assert/1 to add predicates: SWI-Prolog uses dynamic hash tables for dynamic predicates. Warning: dynamic predicates are slower than static so, when you complete the table and are not going to make any changes use compile_predicates/1 to make them static. For example, when I finish parsing my ST is ready so I compile it. Another solution for the ST is to use association lists. they are implemented with AVL trees so the cost is O(log(N)).

Answer 2

Markus Triska (here his homepage) show several things could be interesting to you: for instance a toy LISP, or some toughts to meta interpreters.