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

I wrote a simple interpreter for a functional programming language in Prolog. The full implementation is shown here with an example of its usage:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :- functional_syntax((
            writeln(factorial(3)+factorial(4)),
            Concatenated_string = "hello" + " " + "world",
            writeln(Concatenated_string),
            writeln(length(Concatenated_string)),
            writeln(type(Concatenated_string)),
            writeln(nth0(0,Concatenated_string)),
            writeln(msort([1,3,2,15,-1]))
        ),true).

factorial(N,Output) :-
    functional_syntax((
        (N=1 -> Output = 1);
        Output = N*factorial(N-1)
    )).

type(A,B) :-
    functional_syntax(A,A1),
    (number(A),B='number';
    is_list(A),B='list';
    atom(A),B='atom').

functional_syntax(A) :- functional_syntax(A,true).
functional_syntax(A,A) :- number(A);var(A);atom(A).
functional_syntax(not(X),Output) :-
    functional_syntax((X = false),Output).
functional_syntax(writeln(A),true) :-
    functional_syntax(A,A1),writeln(A1).
functional_syntax(A+B,C) :-
    functional_syntax([A,B],[A1,B1]),
    ((number(A1),number(B1)) ->
        C is A1+B1;
    (is_list(A1),is_list(B1)) ->
        append(A1,B1,C)).
functional_syntax(A-B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1-B1.
functional_syntax(A*B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1*B1.
functional_syntax(A/B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1/B1.
functional_syntax(A=B,Result) :-
    functional_syntax(B,B1),
    (A=B1,Result=true;dif(A,B1),Result=false).
functional_syntax(A->B,Result) :-
    (functional_syntax(A,A1),A1=true) -> (functional_syntax(B,B1),Result=true,B1=true);
    Result=false.
functional_syntax([],[]).
functional_syntax([A|B],[A1|B1]) :-
    functional_syntax(A,A1),functional_syntax(B,B1).
functional_syntax((A,B),Result) :-
    functional_syntax([A,B],[A1,B1]),
    (A1,B1,Result=true;([A1,B1]=[true,false];[A1,B1]=[false,true]),Result=false).
functional_syntax((A;B),Result) :-
    (functional_syntax(A,A1),call(A1);
    functional_syntax(B,B1),call(B1)) -> (Result = true);
    (functional_syntax(A,A1),A1=false,Result=false).
functional_syntax(Input,Output1) :-
    not(number(Input)),
    Input =.. [Name|Params],
    \+member(Name,['=','->',not,'[|]',',',';',+,-,*,/]),
    length(Params,Params_length),
    Params_length > 0,
    functional_syntax(Params,Params1),
    append([Name|Params1],[Output1],Input0),
    Input1 =.. Input0,
    call(Input1).

Similarly, it is possible to write interpreters for imperative programming languages in Prolog.

Answer 3

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