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

Question

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

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

[a] 公理变成 [a,b] 变成 [a,b,a] 等等。或者更好的列表列表 [[a,b],[a]] 使其更加灵活和易于理解，然后再将其扁平化？

没有常量的基本示例，可以用类似的方式添加。 Axiom 一开始只用了一次。这个想法是将要交换的规则名称或符号以及应该与之交换的符号编码为 fact/relation。从 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]].

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

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

How to do recursion in a L-system inspired rewrite System, without DCG

generative

l-systems

prolog