On Tue, 09 Dec 2003 15:36:59 -0800, Richard wrote:

>At 07:56 AM 12/9/2003 -0800, Jonathan Kirwan wrote:
>>...
>>The implementation details are actually quite simple.  The body
>>of any for() loop is compiled as a nested function.  Yield calls
>>this nested body, via a pointer provided as an "extra
parameter"
>>to the iterator function.  When the iterator completes (returns)
>>then the local iterator context is popped and the original call
>>to the iterator returns and execution then proceeds.  No extra
>>stacks.  Just straight forward stuff.
>>...
>
>How a MSP430 list keeps getting off track to language war, asm vs. C, ANSI 
>C quirks, language extension etc. are beyond me :-)

What's life without such?

>but as a compiler vendor, I'm interested in
seeing what extra values I can
>provide to the users. This may be one of them.

A nice differentiating advantage.  But I admit I'm biased.

>Minor quibble is that C compilers don't know
how to handler "nested 
>functions" because there aren't any such thing in C. So depending
on the 
>internal compiler architecture, it may or may not be a big deal.

I can't pretend to fully apprehend the issues.  However, I have
hacked iterators into C before, using added assembly for things
like the yield() function I used.  The model is something like:

  L:    <for body statement>
  L+1:  return to yield()
  L+2:  unwind iterator frame and return

Where,
  L is the target of an iterator function call parameter
  L+1 is the target of a continue in <for body statement>
  L+2 is the target of a break in <for body statement>

A return in <for body statement> simply performs the usual
function return, as that process naturally unwinds the stack.

Also, the yield code needs to save it's own frame pointer and
restore the saved frame pointer located in the iterator's call
frame, so that <for body statement> is called with the frame
pointer set correctly for its context.  However, the stack still
holds all the local context for the iterator, but the <for body
statement> doesn't need to know about that.  When the body
completes a cycle, it just returns to the yield code (whose
address was placed on the stack when the yield code called to
label L.)  The yield code then restores its own frame pointer
and the execution continues in the iterator.

If the <for body statement> performs a continue statement, the
code simply jumps to L+1.  If the <for body statement> performs
a break statement, the code jumps to L+2 where the iterator's
frame is unwound, executing a return to the original call to the
iterator.  Of course, on return from that original call,
execution continues after the for loop.

I didn't need recursive descent for my hacked version, though.
The problem which pushes more for nested functions, I think, is
that iterators may need to support recursive descent.  But an
iterator function is called with specialized parameters so it
cannot properly just call itself.  Which is why I illustrated
the pidgin C code version with a nested function in the iterator
in order to support the recursive descent.

So I think it depends some on how general a path one decides to
take.  After some consideration of the details, you may find a
way to do it without major efforts.  One certain issue is to
watch out for register assignments by the compiler for the
enclosing function and that body of code for the for loop, since
it's going to be called by the iterator's yield.

It's hard for me to say whether or not generalized "nested
function" support is required.  It's probably desirable, but
perhaps not strictly required.

>As a further aside, one of my first jobs as a
compiler job is to maintain a 
>Pascal to C translator. It was interesting to see how it handles nested 
>functions in Pascal.

I'd probably be interested in seeing that, too.

Anyway, one more thing just to push the idea out a little more.
Iterators are a light weight way of solving some kinds of
producer/consumer problems, but without using separate threads
or processes.  Only the one stack is required.

Let's say I decide to implement an "iterator" behavior, but
entirely within valid C.  So, to achieve this, perhaps
ungracefully but with standard C, I decide to pass a function
pointer to the iterator, as this protype suggests:

  void iteratePrimes (int min, int max, void (*f) (int));

Somewhere in the body of iteratePrimes(), it is ready to start
passing all of the indicated primes it has produced for the
given range to some "consumer" function.  In this case, that's
(*f)().  Fine.  So it does so.

But let's say that I want to just count the primes in that
range.  I don't want to print them or save them somewhere.  Just
count them.  So how do I achieve some kind of persistent state
for the function that iteratePrimes() will call, so that the
count can be updated?  Well, I need to pass that state to
iteratePrimes() so that it can pass it to the function it calls
so that the state can be updated.  A mouthful, but there it is.
So we change the interface to:

  void iteratePrimes (int min, int max,
                      void (*f) (int, void*), void *s);

Now, we can initialize our state before calling iteratePrimes()
and then allow our passed function to repeatedly update it with
each prime.  It can count!  Okay.  Solved that one.

But now let's say that we may need to abort the process of
counting.  Let's say that if our count saturates, we want to
abort the counting with that saturated value.  Now, we need some
way to abort the iterating process.  That means we need to let
the iterator function know "when to quit."  Ah, a status return
value, as in:

  void iteratePrimes (int min, int max,
                      int (*f) (int, void*), void *s);

Now, our iterator can proceed and, if the function it calls to
process each value passes back a "stop" status value then it can
simply abort the process and return.

Of course, none of this solves having access to other
information which the parent function may have.

The result of this is that for each kind of "body" code which
may be needed to consume objects from an iterator, there needs
to be a separate function.  Iterators are wonderful tools, if
and when you can just write a new body to use the resulting
objects in unique ways.  But in the above cases, you have to
write a bevy of consumer functions which are at "arm's length"
from the place where the consumption is really intended.  This
reduces the readability and maintainability of the code.  And it
adds plenty of work.  Practice informs me that this *IS* the
real point of having iterator support in the language.

It's "solvable" in C.  I'm not suggesting that there
aren't some
work-arounds, as C is quite capable.  But the readability and
maintenence of such code does suffer some.

Jon

At 12:06 AM 12/10/2003 +0000, Paul Curtis wrote:
>Richard,
>
> > Minor quibble is that C compilers don't know how to handler
"nested
> > functions" because there aren't any such thing in C. So
> > depending on the
> > internal compiler architecture, it may or may not be a big deal.
>
>I believe the GNU compiler implements nested functions, doesn't it?
>That was one of the things required by GNAT as Ada has nested functions.

Yes, I didn't mean ALL C compilers :-)

> > As a further aside, one of my first jobs as a
compiler job is
> > to maintain a
> > Pascal to C translator. It was interesting to see how it
> > handles nested
> > functions in Pascal.
>
>The only problem is up-level addressing, which can be implemented by a
>static link or by a Dijkstra display--both have plus and minus points,
>especially when tasking/coroutines are in use or efficiency is at a
>premium.  If you don't use up-level addressing in your nested
procedure,
>there is absolutely no problem in code generation whatsoever as you
>don't need to pass the static link nor maintain the display.

Exactly. Ah, the joy and memory of PTC...

// richard (This email is for mailing lists. To reach me directly, please 
use richard@rich...) 

Richard,

> Minor quibble is that C compilers don't know
how to handler "nested 
> functions" because there aren't any such thing in C. So 
> depending on the 
> internal compiler architecture, it may or may not be a big deal.

I believe the GNU compiler implements nested functions, doesn't it?
That was one of the things required by GNAT as Ada has nested functions.

> As a further aside, one of my first jobs as a
compiler job is 
> to maintain a 
> Pascal to C translator. It was interesting to see how it 
> handles nested 
> functions in Pascal.

The only problem is up-level addressing, which can be implemented by a
static link or by a Dijkstra display--both have plus and minus points,
especially when tasking/coroutines are in use or efficiency is at a
premium.  If you don't use up-level addressing in your nested procedure,
there is absolutely no problem in code generation whatsoever as you
don't need to pass the static link nor maintain the display.

--
Paul Curtis, Rowley Associates Ltd http://www.rowley.co.uk
CrossWorks for MSP430 and ARM processors 

At 07:56 AM 12/9/2003 -0800, Jonathan Kirwan wrote:
>...
>The implementation details are actually quite simple.  The body
>of any for() loop is compiled as a nested function.  Yield calls
>this nested body, via a pointer provided as an "extra parameter"
>to the iterator function.  When the iterator completes (returns)
>then the local iterator context is popped and the original call
>to the iterator returns and execution then proceeds.  No extra
>stacks.  Just straight forward stuff.
>...

How a MSP430 list keeps getting off track to language war, asm vs. C, ANSI 
C quirks, language extension etc. are beyond me :-) but as a compiler 
vendor, I'm interested in seeing what extra values I can provide to the 
users. This may be one of them.

Minor quibble is that C compilers don't know how to handler "nested 
functions" because there aren't any such thing in C. So depending on
the 
internal compiler architecture, it may or may not be a big deal.

As a further aside, one of my first jobs as a compiler job is to maintain a 
Pascal to C translator. It was interesting to see how it handles nested 
functions in Pascal.


// richard (This email is for mailing lists. To reach me directly, please 
use richard@rich...) 

On Tue, 9 Dec 2003 10:06:33 +0100 (MET), Anders wrote:

>Jonathan Kirwan <jkirwan@jkir...> writes:
>
>> This isn't the same as iterator coroutines.  And they do not need
OS
>> support.  I guess I should have provided examples [of iterator style
>> coroutines], along with what the stack frame looks like during
>> execution.
>
>Please do, as most of us are not familiar with coroutines.
>
>    -- Anders

Broadly speaking, coroutines are found in a lot of places.  They
are nothing more than as little as two different processes,
threads, or fibers which alternate execution streams by
returning from one to where the other one left off.  Operating
system processes qualify for this broad meaning, which I suppose
is why coroutines are often associated with operating systems.
Switching "tasks" via Intel's TSS is also another example of a
coroutine method.

There's a narrower use of the term, though.  It's often applied
to cases where two threads of execution are "highly interactive"
and where very fast exchanging of control is needed.  This is
more the context in which I meant, earlier.

On the MSP430, the CALL instruction is:

    CALL dst           ; dst --> tmp     [moves dst to tmp]
                       ;  PC --> -(SP)   [always pushes PC]
                       ; tmp --> PC      [transfers control]

Assuming that the address of the routine to return to is already
on the stack (notice, we are not talking about two stacks here),
then I believe that one simple form of coroutine can be
implemented in a single instruction on the MSP430:

    CALL @SP+          ; (sp)+ --> tmp   [pops stack to tmp]
                       ;    PC --> -(SP) [pushes current PC]
                       ;   tmp --> PC    [transfers control]

Notice that this instruction is used exactly the same in both
execution streams to alternate control between them.  The stack
retains the alternating location to return to the other thread.

This is one of the simplest forms of coroutine and it is very
close to the one I was talking about with iterator coroutines.
Very light weight, one shared stack, two contexts.

(I haven't verified this with testing, but it should work
correctly from my reading of CALL.)

Switching now to a "pidgin C" example, in order to point out
what a coroutine iterator *might* look like:

 typedef struct mynode_s {
    int type;
    struct mynode_s *left, *right;
 } mynode_t;

 iterator (mynode_t *) eachleaf (mynode_t *n) {
       void walk (mynode_t *n) {
          if (n == 0)
             return;
          if (n->left == 0 && n->right == 0)
             yield n;
          eachleaf (n->left);
          eachleaf (n->right);
          return;
       }
       walk (n);
    return;
 }

This might well be used in this context:

 ...
       for (leaf in eachleaf (tree))
          printleaf (leaf);
 ...

If I change the tree structure... say to add a third "middle"
node pointer... I can bury this detail in eachleaf() and it
automatically affects the iteration of any loop anywhere in the
code.  This aids "information hiding," too.

In C, traversing the tree will generally require exposing the
tree data structure in any for loop sequencing through the nodes
of the tree.  Also, the mechanism for walking a tree either
requires some "state" to be carried around explicitly in static
or heap variables or else the hard-coded logic of various places
where the same walking procedure is used needs to be changed.
Yes, you can put that logic into #define macros.  Yes, you can
use explicit heap or statics.  But with iterators, the
sequencing techniques and visibility of the tree can be
restricted to the tree module alone.  The for() loop only needs
to invoke an appropriate iterator and doesn't need to worry
about the representation.

So the above iterator style remains preferable to me. If the
iterator is in a separately compiled module, I can change the
method, even change the very tree structure itself, and I can
contain those changes to that module.  Other modules do not need
recompilation, since the iterator is simply linked in. With
macros, I need to recompile everything using them.  And with
explicit heap or static state being carried around by the
callers (so that more calls to a supporting function can
'remember' where they last were at), we have additional overhead
for each iteration since the call to the next() function must
re-initialize itself from that state in order to continue. Also,
any changes in the methodology and the amount of required state
may also require the callers to be recompiled.  Or else, if the
call to first() allocates the heap space then an explicit call
to some ending routine may be needed to free it back up.

This also can be helpful in the case where the iteration
algorithm is complex, too, and not just involving recursive
descent.  For example, in iterating through a set of primes. Or,
in the case of a C compiler (for example) where one needs to
sequence through the objects that overlap a given object, x, in
memory.  Simulating this last iteration with macros does work,
but a large amount of code is reproduced each time the macro is
invoked and, every time it's changed, every module using it must
be recompiled, as well.

Iterators may also allow improved type checking since both
parameters AND yielded results are declared.

The implementation details are actually quite simple.  The body
of any for() loop is compiled as a nested function.  Yield calls
this nested body, via a pointer provided as an "extra parameter"
to the iterator function.  When the iterator completes (returns)
then the local iterator context is popped and the original call
to the iterator returns and execution then proceeds.  No extra
stacks.  Just straight forward stuff.

The downside regarding performance is that each loop iteration
is now a function call and any variables in the body's parent
accessed from the body cannot now reside in CPU registers (they
must be spilled to local stack, I suppose, if they are.)

Before I leave this, it's possible to write something akin to
the above iterator example, with:

 void eachleaf (mynode_t *n, void (*f) (mynode_t*)) {
          if (n == 0)
             return;
          if (n->left == 0 && n->right == 0)
             (*f) (n);
          eachleaf (n->left);
          eachleaf (n->right);
    return;
 }

In this case, the caller passes a function pointer and the
"iterator" repeatedly calls that function with each node it
walks.  Very similar in many ways, but still different.  The
function being passed to eachleaf() in this case does not have
access to the local context of the caller.  This can be very
important because this may mean that "context baggage" also
needs to be passed to the function that eachleaf() calls and
means extending the call interface to include that.  It starts
to get pretty ugly looking after a while.  Supporting nested
functions would solve some of this, I suppose.

Jon

Jonathan Kirwan <jkirwan@jkir...> writes:

> This isn't the same as iterator coroutines. 
And they do not need OS
> support.  I guess I should have provided examples [of iterator style
> coroutines], along with what the stack frame looks like during
> execution.

Please do, as most of us are not familiar with coroutines.

    -- Anders
-- 
Disclaimer: Opinions expressed in this posting are strictly my own and
not necessarily those of my employer.

"budfrog99" <lee_h_theusch@lee_...> writes:

> ... unless you are using the Kick Start, IIRC.

No, that was the assembler list file.

The preprocessor list option is always available.

    -- Anders
-- 
Disclaimer: Opinions expressed in this posting are strictly my own
and not necessarily those of my employer.

On Tue, 09 Dec 2003 14:36:22 +1030, Al wrote:

>Clyde Stubbs wrote:
>> On Tue, Dec 09, 2003 at 01:42:15PM +1030, onestone wrote:
>> 
>>>But it was never designed for embedded systems, and non-standard
things 
>>>have to be done to accomodate these, so why enforce rigidity
elsewhere, 
>>>especially where it interferes wiuth functionality?
>> 
>> 
>> It's a juggling act - a matter of making value judgements about
what
>> is worth implementing and what is not, and also about how to implement
>> things in a way that leaves the lightest footprint.
>> 
>> I have certain opinions about many of these issues, backed up by the
>> experience of many years and many architectures. But they are just
opinions.
>> There are no absolute answers. And all generalizations are false.
>
>Most things in this field boil down to opinion. Obviously what matters 
>most are the features which sell compilers. It isn't a huge market, and

>selling prices are being driven ever lower, hence it must come down to 
>differentiation between the few compiler vendors, who, I assume are 
>driven by customer feedback, rather than personal bias.
>
>Cheers
>
>Al

Hmm.  You just noted the key, Al:  Differentiation.

Jon

Clyde Stubbs wrote:
> On Tue, Dec 09, 2003 at 01:42:15PM +1030,
onestone wrote:
> 
>>But it was never designed for embedded systems, and non-standard things 
>>have to be done to accomodate these, so why enforce rigidity elsewhere, 
>>especially where it interferes wiuth functionality?
> 
> 
> It's a juggling act - a matter of making value judgements about what
> is worth implementing and what is not, and also about how to implement
> things in a way that leaves the lightest footprint.
> 
> I have certain opinions about many of these issues, backed up by the
> experience of many years and many architectures. But they are just
opinions.
> There are no absolute answers. And all generalizations are false.

Most things in this field boil down to opinion. Obviously what matters 
most are the features which sell compilers. It isn't a huge market, and 
selling prices are being driven ever lower, hence it must come down to 
differentiation between the few compiler vendors, who, I assume are 
driven by customer feedback, rather than personal bias.

Cheers

Al

On Tue, Dec 09, 2003 at 01:42:15PM +1030, onestone wrote:
> But it was never designed for embedded systems,
and non-standard things 
> have to be done to accomodate these, so why enforce rigidity elsewhere, 
> especially where it interferes wiuth functionality?

It's a juggling act - a matter of making value judgements about what
is worth implementing and what is not, and also about how to implement
things in a way that leaves the lightest footprint.

I have certain opinions about many of these issues, backed up by the
experience of many years and many architectures. But they are just opinions.
There are no absolute answers. And all generalizations are false.

Clyde

-- 
Clyde Stubbs                     |            HI-TECH Software
Email: clyde@clyd...          |          Phone            Fax
WWW:   http://www.htsoft.com/    | USA: (408) 490 2885  (408) 490 2885
PGP:   finger clyde@clyd...   | AUS: +61 7 3552 7777 +61 7 3552 7778
---
HI-TECH C: compiling the real world.