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

I am trying to write a tiny recursive rewrite system inspired by Aristid Lindenmayers L-System basically to learn Prolog as well as to think about generative concepts in Prolog. I would like to achieve this without DCG. Due to the initial generate. and output predicate with side effects it is not a 100% pure prolog idea. Don´t hesitate to take the concept apart.

My main problem is at the end of the listing. Matching the rule for every element in the original list and creating a new list with the result of each substitution.

[a] the Axiom becomes [a,b] becomes [a,b,a] and so on. Or better as a list of lists [[a,b],[a]] to keep it more flexible and comprehensible and then flatten it later?

Basic example without constants, which could be added in a similar way. The Axiom is just used one time at the start. The idea is to encode the rule name or symbol to exchange and the symbols it should be exchanged with, as a fact/relation. Start with generate. would repeat it 20 times with a counter.

% 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

Solution

Yes, you want lists of lists. Each character can then map cleanly to one corresponding expansion list:

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

(This is simpler and shorter than with a DCG for the same thing, BTW.)

For example:

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

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

Then flatten this to a flat list before expanding the next generation.