如何在 L 系统启发的重写系统中进行递归，无需 DCG

Question

我正在尝试编写一个受 Aristid Lindenmayers L-System 启发的小型递归重写系统，基本上是为了学习 Prolog 以及思考 Prolog 中的生成概念。我想在没有 DCG 的情况下实现这一目标。由于最初的

generate.

和

output

谓词具有副作用，它不是 100% 纯粹的 prolog 想法。不要犹豫，把这个概念拆开。

我的主要问题是在列表的末尾。匹配原始列表中每个元素的规则，并使用每次替换的结果创建一个新列表。

[a]

公理变为

[a,b]

变为

[a,b,a]

等等。或者更好地作为列表的列表

[[a,b],[a]]

保持其更加灵活和易于理解，然后再将其扁平化？

没有常量的基本示例，可以以类似的方式添加。 Axiom 一开始只使用一次。这个想法是将要交换的规则名称或符号以及应该与之交换的符号编码为事实/关系。从

generate.

开始，用计数器重复 20 次。

% The rules
axiom(a, [a]).           
rule(a, [a, b]).
rule(b, [a]). 

% Starts the program
generate :- 
    axiom(a, G), 
    next_generation(20, G).

% repeats it until counter 0. 
next_generation(0, _) :- !. 
next_generation(N, G) :- 
    output(G),                     
    linden(G, Next), 
    succ(N1, N),                           
    next_generation(N1, Next). 

% Concatenates the list to one string for the output
output(G) :- 
    atomic_list_concat(G,'',C),
    writeln(C).

% Here I am stuck, the recursive lookup and exchange. 
% How do I exchange each element with the according substitution to a new list

linden([],[]).             % Empty list returns empty list.
linden([R],Next) :-        % List with just one Element, e.g. the axiom 
   rule(R, Next).          % Lookup the rule and List to exchange the current
linden([H|T], Next) :-     % If more than one Element is in the original list
   rule(H,E),              % match the rule for the current Head/ List element
   % ?????                 % concatenate the result with the result of former elements 
   linden(T, Next).        % recursive until the original list is processed.
                           % Once this is done it returns the nw list to next_generation/2

Answer 1

是的，您想要列表的列表。然后，每个角色都可以清晰地映射到一个相应的扩展列表：

linden([], []).
linden([H|T], [E | Next]) :-
   rule(H, E),
   linden(T, Next).

（对于同样的事情，这比 DCG 更简单、更短，顺便说一句。）

例如：

?- linden([a], Expansion).
Expansion = [[a, b]].

?- linden([a, b, a], Expansion).
Expansion = [[a, b], [a], [a, b]].

然后在扩展下一代之前将其扁平化为扁平列表。