Function ParsePredicate takes a list of atoms as argument representing the input words and returns a predicate appropriate for encapsulated search (e.g. as an argument to ExploreAll).

<Parser ParsePredicate>=
fun {ParsePredicate Words}
   N = {Length Words}
   = {Map Words fun {$ W} W#{Lexicon.get W} end}
   Positions = {FS.value.make 1#N}
<Parser ParsePredicate, ParseTree> 

The search predicate applies exactly the distribution strategies that we described.

<Parser ParsePredicate, ParseTree>=
proc {ParseTree Nodes}
<ParseTree create root set> 
<ParseTree create nodes> 
<ParseTree yields and role constraints> 
<ParseTree global partition> 
   {FS.distribute naive AllDtrSets}
   {FD.distribute ff {Map Nodes GetEntryIndex}}

The root set (the set of roots) is a singleton:

<ParseTree create root set>=
RootSet={FS.subset $ Positions}
{FS.cardRange 1 1 RootSet}

Nodes for each word are created by invoking function MakeNode.

<ParseTree create nodes>=
!Nodes = {List.mapInd WordEntriesPairs
          fun {$ I Word#Entries}
             {MakeNode Word I Positions Entries RootSet}

We can now collect the list of yields of all nodes, which allows us to properly constrain the strict yield of each node. For each node N, we consider every possible node M as a potential mother, and express the constraint that states that M is a mother or N iff N is a daughter of M. Furthermore, for each triple (N,M,R) where R is an arbitrary role, we impose a role constraint in the form of disjunctive propagator.

<ParseTree yields and role constraints>=
Yields = {Map Nodes GetYield}
for N in Nodes do 
   N.yieldS = {Select.union Yields N.daughters}
   for M in Nodes do 
      {FS.reified.include M.index N.mother}=
      {FS.reified.include N.index M.daughters}
      for R in AllRoles do 
            or {FS.include N.index M.dtrsets.R}
               N.role=R {Gamma.R M N}
            [] {FS.exclude N.index M.dtrsets.R}

Finally, we impose the condition that the root set together with the daughter sets of all nodes form a partition of the input.

<ParseTree global partition>=
AllDtrSets =
{FoldL Nodes
 fun {$ L N}
    {Append {Record.toList N.dtrsets} L}
 end nil}
{FS.partition AllDtrSets Positions}

Denys Duchier
Version 1.2.0 (20010221)