Prolog Interpreter

Question

I already got feet from functional programming; I am familiar (although not in control) with Haskell and PLT Scheme. I used PLT Scheme to create small interpreters for toy languages ​​(link to PLAI) - I am better off with imperative languages.

Can someone direct me to resources that I could use to create a small interpreter of the toy language of my choice using Prolog?

Answer 1

I mainly use swi-prolog, so most of what I say will be related to swi-prolog. However, other prolog implementations may have similar predicates / libraries (perhaps with a slightly different name) so you can search for their guides and find them. In addition, I write the compiler, not the interpreter, in the prologue, so maybe some parts are not related to the interpreter.

The SWI-Prolog documentation site is really good for finding things: use the search box to find a predicate or perform a typical search. There are many libraries, but you can implement some things yourself to gain experience. You could eventually reinvent the wheel, but that would be helpful.

The book "The Art of Prologue" (Sterling, Shapiro) has a chapter on creating a compiler in the prologue (and this is a good book for the prologue).

Perhaps there are some lex / bison equivalent prolog tools; I never looked. IMHO, the lexer is quite simple in the prologue; Naturally, it will be based on comparison with the sample.

For the analyzer, I suggest using DCG: specific grammatical expressions: swi-prolog doc , google for more details.
The problem is that you have to parse the whole file (or at least I found a way to do it differently). Btw, lexer could also be done with DCG, but I don't think it is really better.

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

other useful stuff: check assert / 1, global variables, meta predicates (maplist / [2-6]).
not a pure prologue, and you can make your code too demanding by abusing them (and then you may have some unpleasant side effects)

For a character table (if you need one), you can simply 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 populate a 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 ST is to use association lists . they are implemented using AVL trees, so the cost is O (log (N)).

Answer 2

Marcus Triska ( here on his home page) shows that you may be interested in several things: for example, a LISP toy or some attributes for meta-amplifiers .

Answer 3

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

:- 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(AB,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). 

In the same way, you can write interpreters for imperative programming languages in Prolog.