% fringe(Tree,List) -> succeed iff List == fringe of Tree
% Eric Auer 12 maart 2002

% ---------------------------------------------------------

% SICStus does not predefine this, SWI does:
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :-
    append(Xs,Ys,Zs).

% ---------------------------------------------------------

fringe([],[]).                % empty tree, cut (!) avoids
% fringe([],[]) :- !.           % empty tree, cut (!) avoids
                              % hitting the rules below...

fringe([],_X) :-              % an unparseable rest was found
% %  write('NIL -> '), write(_X), nl,
  fail.

fringe(_X,[]) :-              % tree without a string found
% %  write(_X), write(' -> []'), nl,
  fail.

fringe(leaf(X),[X]).          % a leaf on the tree

fringe(node(_A,Ls),Xs) :-     % descending...
                              %     "_A -> Xs ?", probe
% %  write(_A), write(' -> '), write(Xs), write(' ?'), nl,
  fringe(Ls,Xs)               % recursion
                              % *** "_A -> Xs !", success ***
% % ,write(_A), write(' -> '), write(Xs), write(' !'), nl
  .

fringe([L|Ls],Xs) :-          % not a tree but a list of them
  fringe(L,Xs1),
  fringe(Ls,Xs2),             % trying to compose the list
  append(Xs1,Xs2,Xs).         % nondeterministic!

% ---------------------------------------------------------

atree( node(s, [node(np,[node(det,[leaf(a)])
               ,node(n,[leaf(program)])
               ,node(optrel,[]) ])
      ,node(vp,[node(iv,[leaf(halts)]) ]) ]) ).

sentence(1) :-
  atree(X),
  fringe(X, [a, program,halts]).

sentence(2) :- 
  atree(X),
  append([X], [node(bar,[leaf(baz)])], Z),
  fringe(node(foo,Z), [a,program,halts]).

sentence(3) :-
  atree(X),
  fringe(X,[a,program,halts,never]).