Purely stack-based generators

[Norbert Nemec]

Walter Bright wrote:
> Norbert Nemec wrote:
>> Walter Bright wrote:
>>> The trouble with a generator using the caller's stack is that then 
>>> the generator cannot recursively call itself (such as if it was 
>>> walking a tree). In order to work properly in the general case, a 
>>> generator has to allocate all its local variables on the heap.
>>
>> Which concept of generators do you refer to? The stack-based 
>> generators that I suggested do in fact work recursively. A generator 
>> can obtain its values from other generators or even recursively from 
>> itself without needing heap space anywhere.
> 
> How can it do that, and yet allow the calling function also call other 
> functions?

When a generator is called for the first time, it shifts the ESP to make 
room for its own local variables. When it yields, the ESP remains where 
it is, so the generator's local data is protected. At any time, the ESP 
can be used as usual for regular function calls.

Whenever a loop is entered, it needs some additional space on the stack 
for all the local data of contained generators. This stack space is 
finite, simply defined by the sum of the local data of each contained 
generator. The loop's stack space is released when the loop is 
terminated. Any loops nested inside the outer loop, perhaps inside 
generators, will reserve additional stack space, but none of these stack 
spaces can survive the lifetime of an outer loop, so whenever a loop 
exits, all the stack spaces if inner loops can be freed as well.

I will try to work out an example in assembly code, but I have not used 
assembly in years, so it will take some time.