home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / pop / 63 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  4.4 KB
  1. From: sfk@otter.hpl.hp.com (Steve Knight)
  2. Date: Wed, 18 Nov 1992 12:29:21 GMT
  3. Subject: Re: A little Pop history
  4. Message-ID: <116670012@otter.hpl.hp.com>
  5. Organization: Hewlett-Packard Laboratories, Bristol, UK.
  6. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!sdd.hp.com!hpscit.sc.hp.com!scd.hp.com!hpscdm!hplextra!otter.hpl.hp.com!otter!sfk
  7. Newsgroups: comp.lang.pop
  8. References: <Bxpqvt.Lq@deshaw.com>
  9. Lines: 118
  10.  
  11. Nice to hear from Jonathan again.  So as a greeting I'll stick the boot
  12. in on his implementation of recursivemember :-)
  13.  
  14. Jonathan implements recursivemember like this:
  15. >     define recursivemember(item, list);
  16. >     var item, list, element;
  17. >         if list = [] then
  18. >             return(false)
  19. >         endif;
  20. >         for el in list do
  21. >             if el = item then
  22. >                 return(true)
  23. >             elseif islist(el) and recursivemember(item, el) then
  24. >                 return(true);
  25. >             endif
  26. >         endfor;
  27. >         return(false);
  28. >     enddefine;
  29.  
  30. I still don't much like this as a solution.  For example, you can never
  31. find [] in a tree -- but you can find all other lists.  We need to take
  32. a systematic view of the meaning of lists representing tress.  We can 
  33. either adopt the view that the trees are built up from "dotted pairs", to 
  34. borrow Lisp-speak, or that the lists simply represent linear 
  35. collections.
  36.  
  37. The first view leads to this solution.  But look how horribly [] gets
  38. treated again.
  39.  
  40. define recmem( x, tree );
  41.     x = tree or
  42.     tree.islist and not( tree.null ) and
  43.     ( recmem( x, tree.hd) or recmem( x, tree.tl ) )
  44. enddefine;
  45.  
  46. Ikk.  The more typical Pop-style solution is to treat the lists as being
  47. linear collections rather than binary trees.  This gives us the following
  48. solution
  49.  
  50. define recmem( x, tree ); 
  51.  
  52.     define recmemlist( x, list );
  53.         not( list.null ) and
  54.         ( recmem( x, list.hd ) or recmemlist( x, list.tl )
  55.     enddefine;
  56.             
  57.     x = tree or tree.islist and recmemlist( x, tree )
  58. enddefine;
  59.  
  60. This is obviously an inefficient solution -- it chews up stack space
  61. like there is no tomorrow, because no implementation of Pop does
  62. tail-call optimisation.  So you need to modify the solution like this
  63.  
  64. define recmem( x, tree );
  65.  
  66.     define recmemlist( x, list );
  67.         not( list.null ) and
  68.         ( recmem( x, list.hd ) or chain( x, list.tl, recmemlist ) )
  69.     enddefine;
  70.  
  71.     x = tree or tree.islist and chain( x, tree, recmemlist )
  72. enddefine;
  73.  
  74. The call to "chain" forces the currently active procedure to exit and
  75. invoke the procedure on top of the stack.  In other words this is a manual
  76. implementation of tail-call optimisation. 
  77.  
  78. As an alternative, you might choose to expand the recursion into a
  79. loop.  But that's a detail and there would be only a minor 
  80. performance gain.  And you would use up more stack space.  So take
  81. your pick.  Here's the above routine converted to use a loop.
  82.  
  83. define recmem( x, tree );
  84.     x = tree or
  85.     tree.islist and
  86.     lblock                               ;;; begin new lexical block.
  87.         lvars result = false;            ;;; tree might be null.
  88.         until tree.null do
  89.             ;;; Nice Pop idiom.  "dest" returns head and tail of a 
  90.             ;;; non-empty list.  So E.dest -> E is an expression that
  91.             ;;; steps E down the list and leaves the head on the stack.
  92.             recmem( x, tree.dest -> tree ) -> result;    
  93.             quitif( result );            ;;; shortcut when we find true.
  94.         enduntil;
  95.         result                           ;;; push the result.
  96.     endlblock
  97. enddefine;
  98.  
  99. Since this version was created from the recursive version, it retains all
  100. the behaviour we want.  In particular, it treats [] as a legitimate search
  101. target and doesn't make it a special case.  One criticism, however, would 
  102. be that the algorithm doesn't immediately generalise to a representation 
  103. of trees as vectors (1D arrays).  
  104.  
  105. To remedy that, we can introduce the appropriate for loop:
  106.  
  107. define recmem( x, tree );
  108.     x = tree or
  109.     x.isvector and
  110.     lblock
  111.         lvars result = false;
  112.         for i in_vector tree do
  113.             ;;; Another cute idiom.  ->> is an assignment that duplicates
  114.             ;;; the value on the stack before the assignment.
  115.             quitif( recmem( x, t ) ->> result )
  116.         endfor;
  117.         result
  118.     endlblock
  119. enddefine;
  120.  
  121. This version can be trivially modified to cope with any data type
  122. that provides a loop or iteration procedure.  It has no special treatment
  123. for any element.  It is efficient in both space and time, although not 
  124. quite optimal in either.  And a mere 11 lines of non-commented code.
  125.  
  126. Yow!
  127.  
  128. Steve
  129.