home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1425 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.8 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!cs.utexas.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: coatta@cs.ubc.ca (Terry Coatta)
  3. Newsgroups: comp.compilers
  4. Subject: Set Generators
  5. Keywords: question, theory
  6. Message-ID: <92-08-125@comp.compilers>
  7. Date: 20 Aug 92 18:32:36 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: coatta@cs.ubc.ca (Terry Coatta)
  10. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  11. Lines: 31
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. In a system that I am working on, sets of objects are often specified via
  15. membership predicates.  In order to generate the sets involved the
  16. membership predicate is essentially evaluated for all objects in the
  17. system, and when it evaluates to true, the object is added to the set
  18. being generated.  For many of the predicates I can, however, generate (by
  19. hand) a recursive procedure which enumerates the set.  For example, the
  20. set of objects in a tree can be specified via a predicate something like:
  21.  
  22.       All X such that Path(Root, X)
  23.  
  24.    where Path(X, Y) =
  25.       Y is a child of X 
  26.       OR
  27.          there exists a Z, which is a child of X 
  28.          AND Path(Z, Y)
  29.  
  30. (the actual syntax for this specification within the system is, of course,
  31. quite different from the above, but I hope the example is clear).
  32.  
  33. This set can be very easily generated simply by doing a depth first
  34. traversal of the tree.
  35.  
  36. What I am looking for are hints or help on a ``mechanical'' process for
  37. taking membership predicates and ``compiling'' them in to (imperative)
  38. procedures which will generate the set in question.
  39. --
  40. Terry Coatta (coatta@cs.ubc.ca)
  41. Dept. of Computer Science, UBC, Vancouver BC, Canada
  42. -- 
  43. Send compilers articles to compilers@iecc.cambridge.ma.us or
  44. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  45.