基于Prolog的解释器

Question

我已经接触过函数式编程；我熟悉(虽然不是很精通) Haskell和PLT Scheme。我曾使用PLT Scheme为玩具语言构建过小解释器(参考PLAI)--我更擅长使用命令式语言。

有没有人可以帮我找到一些资源，我可以用这些资源用Prolog为我选择的一种玩具语言构建一个小的解释器？

Answer 1

我主要使用swi-prolog，所以我说的大部分内容都与swi-prolog相关。但是，其他prolog实现可能具有类似的谓词/库(可能名称略有不同)，因此您可以搜索它们的手册并找到它们。此外，我正在用prolog编写编译器，而不是解释器，所以可能有些部分与解释器不是很相关。

SWI-Prolog's documentation site非常适合查找内容:使用搜索框来查找任何谓词或执行典型的搜索。有太多的库，但你可能想要自己实现一些东西来获得经验。你可能最终会重新发明轮子，但它会很有用。

“prolog的艺术”这本书(Sterling，Shapiro)有一章专门用prolog构建编译器(这也是一本很好的prolog书)。

也许有一些工具等同于prolog的lex/bison；我从来没有真正搜索过。

Imho，词法分析器在纯prolog中非常简单；很自然，它将主要基于模式匹配。

对于解析器，我建议使用DCG: definite子句语法：swi-prolog doc，google获取更多细节。

问题是您必须解析整个文件(或者至少我还没有找到其他方法)。顺便说一句，词法分析器也可以用DCGs完成，但我不认为它真的更好。

如果您选择使用中间代码，那么很容易从解析器中生成抽象语法树(在解析过程中，您也可以计算很多东西)。

关于语义检查:在我的玩具语言编译器中，我在解析期间执行大多数语义检查(与作用域相关，函数调用)，其余的在单独的步骤中执行。有点凌乱

其他有用的东西: check assert/1、全局变量、meta predicates (maplist/[2-6]).

不是纯prolog，你可能会滥用它们使你的代码变得过于命令(然后你可能会有一些非常糟糕的副作用)。

对于符号表(如果需要)，您可以只使用assert/1来添加谓词: swi-prolog使用动态哈希表来表示动态谓词。警告:动态谓词比静态谓词慢，因此，当您完成表并且不打算进行任何更改时，请使用compile_ predicates /1将它们变为静态谓词。例如，当我完成解析时，我的ST就准备好了，所以我编译了它。ST的另一种解决方案是使用association lists。它们是用AVL树实现的，所以成本是O(log(N))。

Answer 2

Markus Triska (here他的主页)展示了一些你可能感兴趣的东西:例如toy LISP，或者meta interpreters的一些toughts。

Answer 3

我用Prolog为函数式编程语言写了一个简单的解释器。完整的实现如下所示，并提供了一个使用示例：

:- 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).

类似地，可以用Prolog编写interpreters for imperative programming languages。