Set Generators

coatta@cs.ubc.ca (Terry Coatta)
Thu, 20 Aug 1992 18:32:36 GMT

          From comp.compilers

Related articles
Set Generators coatta@cs.ubc.ca (1992-08-20)
Re: Set Generators macrakis@osf.org (1992-08-21)
| List of all articles for this month |

Newsgroups: comp.compilers
From: coatta@cs.ubc.ca (Terry Coatta)
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Date: Thu, 20 Aug 1992 18:32:36 GMT
Keywords: question, theory

In a system that I am working on, sets of objects are often specified via
membership predicates. In order to generate the sets involved the
membership predicate is essentially evaluated for all objects in the
system, and when it evaluates to true, the object is added to the set
being generated. For many of the predicates I can, however, generate (by
hand) a recursive procedure which enumerates the set. For example, the
set of objects in a tree can be specified via a predicate something like:


            All X such that Path(Root, X)


      where Path(X, Y) =
            Y is a child of X
            OR
                  there exists a Z, which is a child of X
                  AND Path(Z, Y)


(the actual syntax for this specification within the system is, of course,
quite different from the above, but I hope the example is clear).


This set can be very easily generated simply by doing a depth first
traversal of the tree.


What I am looking for are hints or help on a ``mechanical'' process for
taking membership predicates and ``compiling'' them in to (imperative)
procedures which will generate the set in question.
--
Terry Coatta (coatta@cs.ubc.ca)
Dept. of Computer Science, UBC, Vancouver BC, Canada
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.