基于 Prolog 的解释器

Question

我已经开始接触函数式编程了；我熟悉（虽然不精通）Haskell 和 PLT 方案。我使用 PLT 方案为玩具语言构建了小型解释器（参考 PLAI）——我更擅长命令式语言。

谁能指导我使用 Prolog 来构建我选择的玩具语言的小型解释器的资源？

Answer 1

我主要使用 SWI-Prolog，所以我所说的大部分内容都与 SWI-Prolog 相关。然而，其他 Prolog 实现可能有类似的谓词/库（可能名称略有不同），因此您可以搜索他们的手册并找到它们。另外，我正在序言中编写编译器，而不是解释器，所以也许某些部分与解释器不太相关。

SWI-Prolog 的文档站点 非常适合查找内容：使用搜索框查找任何谓词或进行典型搜索。有大量的库，但您可能想自己实现一些东西来获得经验。你可能最终会重新发明轮子，但这会很有用。

《The Art of Prolog》（Sterling、Shapiro）一书有一章专门讨论在 Prolog 中构建编译器（这也是一本关于 Prolog 的好书）。

也许有一些类似于 lex/bison for Prolog 的工具；我从来没有真正搜索过。
恕我直言，词法分析器在普通 Prolog 中非常简单；当然，它将很大程度上基于模式匹配。

对于解析器，我建议使用 DCG：定语子句语法： SWI-Prolog 文档，谷歌了解更多详细信息。
问题是您必须解析整个文件（或者至少我还没有找到其他方法）。
顺便说一句，词法分析器也可以用 DCG 来完成，但我不认为它真的更好。

如果您选择使用中间代码，则很容易从解析器生成抽象语法树（您也可以在解析期间评估很多内容）。
关于语义检查：在我的玩具语言编译器中，我在解析期间进行了大部分语义检查（范围相关、函数调用），其余的则在单独的步骤中进行。 其他有用的东西有点混乱

：检查 assert/1、全局变量、元谓词（maplist/\[2-6\]）。
不是纯粹的 Prolog，你可能会通过滥用它们使你的代码变得过于命令式（然后你可能会产生一些非常讨厌的副作用）

对于符号表（如果你需要它）你可以只使用 assert/1添加谓词：SWI-Prolog 对动态谓词使用动态哈希表。警告：动态谓词比静态谓词慢，因此，当您完成表并且不打算进行任何更改时，请使用compile_predicates/1 使其静态。例如，当我完成解析时，我的 ST 就准备好了，所以我编译它。
ST 的另一个解决方案是使用 关联列表。它们是用AVL树实现的，所以成本是O(log(N))。

Answer 2

Markus Triska（此处他的主页）展示了一些您可能感兴趣的内容：例如 玩具 LISP，或一些元解释器。

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

同样，可以编写命令式编程语言的解释器序言。