Path: utzoo!mnetor!uunet!mcvax!ukc!cam-cl!scc
From: scc@cl.cam.ac.uk (Stephen Crawley)
Newsgroups: comp.lang.misc
Subject: Iterators (was Re: From Modula to Oberon)
Message-ID: <1147@jenny.cl.cam.ac.uk>
Date: 18 Mar 88 19:36:35 GMT
References: <2827@enea.se> <1557@pasteur.Berkeley.Edu> <3764@bloom-beacon.MIT.EDU> <22162@bbn.COM> <1139@PT.CS.CMU.EDU>
Sender: scc@cl.cam.ac.uk
Reply-To: scc@cl.cam.ac.uk (Stephen Crawley)
Organization: U of Cambridge Comp Lab, UK
Lines: 76
Keywords: CLU iterators closures genericity
Summary: You CAN simulate iterators ... but it is not nice

In article <1139@PT.CS.CMU.EDU> edw@IUS1.CS.CMU.EDU (Eddie Wyatt) writes:
In an earlier article, someone else writes:

>> [... Clu iterators are coroutines]

No they are not.  Most of the things that you can do with coroutines you
can't do with iterators.

>But do you need coroutines to implimented generlized iteration.  
>I think not.  

Spot on.  You CAN implement iterators with coroutines, but in practice
they are implemented more cheaply by turning the loop body into a procedure
like thing that is passed to the iterator as a hidden parameter.  More
details on the implementation of CLU iterators can be found in

  DGS Note 124 "VAX CLU Implementation Notes"  by Sharon E. Perl 29/11/84
  Laboratory for Computer Science, Massachusetts Institute of Technology

> [...]
>Example:
>
>	void iterate_inorder(root,func)
>	    TREE *root;
>	    void (*func)();
>	    {
>	    if (root != NULLPTR(TREE))
>		{
>	    	iterate_inorder(root->left,func);
>	    	func(root->val);
>	    	iterate_inorder(root->right,func);
>		}
>	    }
>
>    I do see one problem though, which is dealing with variable
>    referenced  inside the loop.  They would have to become
>    global.  Comments as to why this method might not work in general?

Apart from being a disgusting hack ... making your "local" variables into
globals will only work if the pseudo-iterator is NEVER called recursively.

To get it to work recursively, there are two approaches.

1)  Declare the relevant local variables as a structure, and pass a
    pointer to the struct as an extra parameter to the iter procedure
    and hence to the "loop body" procedure.  This involves casting /
    loopholing of the pointer, or a generic type parameter in a high 
    level programming language.

2)  Declare the loop body procedure in the same (non-global) scope as
    the local variables for the loop.  The loop locals are then available
    to the loop body procedure as non-locals.  This assumes that your
    language allows this ... C, BCPL, Pascal, Modula-*, Ada etc don't, 
    but Algol-68 and Mesa do, as do any languages which support proper
    procedure closures.


Here's an example of 2)

  ...
  P:  proc (...) =
    x, y: FooType
    loopbody: proc (elem: ElemType) = {
      ...
      x := list_elem.foo
      list_elem.foo := y
      ...
      }
    
    (* body of P *)
    ...
    iterate_over(list, loopbody)
    ...
    }

-- Steve