如何在没有DCG的L系统启发的重写系统中进行递归

Question

我正试图写一个受Aristid Lindenmayers L-system启发的小型递归重写系统，主要是为了学习Prolog以及思考Prolog中的生成概念。我希望在没有DCG的情况下实现这一目标。由于最初的generate.和output谓词有副作用，它不是一个100%纯粹的序言思想。不要犹豫，把这个概念拆开。

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

[a]Axiom变成[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]].

然后在扩展下一代之前将其展开为一个平面列表。