On Sunday, 9 March 2014 at 10:30:37 UTC, bearophile wrote:
> w0rp:
>
>>> 3. Give up on maximum performance (fiber-based coroutine range)
>>
>> I think that's what I would go for.
>
> Yet there's no need for that. You can have your pie and eat it too, with a small cost. D can rewrite code that contains a yield in an efficient finite state machine (this is what ShedSkin compiler for Python does, and perhaps the C# compiler does the same).

How does this handle recursive generators, e.g. like you would see with a depth-first tree traversal? The "state" in this case is a call stack. How is the memory allocated for the stack?

On Sunday, 9 March 2014 at 11:00:13 UTC, Peter Alexander wrote:
> On Sunday, 9 March 2014 at 10:30:37 UTC, bearophile wrote:
>> w0rp:
>>
>>>> 3. Give up on maximum performance (fiber-based coroutine range)
>>>
>>> I think that's what I would go for.
>>
>> Yet there's no need for that. You can have your pie and eat it too, with a small cost. D can rewrite code that contains a yield in an efficient finite state machine (this is what ShedSkin compiler for Python does, and perhaps the C# compiler does the same).
>
> How does this handle recursive generators, e.g. like you would see with a depth-first tree traversal? The "state" in this case is a call stack. How is the memory allocated for the stack?

The generators mentioned are stack-less. You'd need to maintain the stack yourself.

On Sunday, 9 March 2014 at 11:17:14 UTC, Tobias Pankrath wrote:
> On Sunday, 9 March 2014 at 11:00:13 UTC, Peter Alexander wrote:
>> On Sunday, 9 March 2014 at 10:30:37 UTC, bearophile wrote:
>>> w0rp:
>>>
>>>>> 3. Give up on maximum performance (fiber-based coroutine range)
>>>>
>>>> I think that's what I would go for.
>>>
>>> Yet there's no need for that. You can have your pie and eat it too, with a small cost. D can rewrite code that contains a yield in an efficient finite state machine (this is what ShedSkin compiler for Python does, and perhaps the C# compiler does the same).
>>
>> How does this handle recursive generators, e.g. like you would see with a depth-first tree traversal? The "state" in this case is a call stack. How is the memory allocated for the stack?
>
> The generators mentioned are stack-less. You'd need to maintain the stack yourself.

That's unfortunate. I find that non-recursive generators are pretty easy to write as ranges anyway :-/

Peter Alexander:

> How does this handle recursive generators, e.g. like you would see with a depth-first tree traversal? The "state" in this case is a call stack. How is the memory allocated for the stack?

A Python 2.x test program:


class Node:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

def in_order(node):
    if node is not None:
        for n in in_order(node.left):
            yield n
        yield node.data
        for n in in_order(node.right):
            yield n

def main():
    tree = Node(1,
                Node(2,
                     Node(4,
                          Node(7, None, None),
                          None),
                     Node(5, None, None)),
                Node(3,
                     Node(6,
                          Node(8, None, None),
                          Node(9, None, None)),
                     None))

    for n in in_order(tree):
        print n,
    print

main()


It prints:

7 4 2 5 1 8 6 9 3


ShedSkin translates it to some C++ code, here I show only the in_order function:



class __gen_in_order : public __iter<__ss_int> {
public:
    Node *node;
    __iter<__ss_int> *__0, *__1, *__4, *__5;
    __ss_int __2, __6, n;
    __iter<__ss_int>::for_in_loop __3, __7;

    int __last_yield;

    __gen_in_order(Node *node) {
        this->node = node;
        __last_yield = -1;
    }

    __ss_int __get_next() {
        switch(__last_yield) {
            case 0: goto __after_yield_0;
            case 1: goto __after_yield_1;
            case 2: goto __after_yield_2;
            default: break;
        }
        if ((node!=NULL)) {

            FOR_IN(n,in_order(node->left),0,2,3)
                __last_yield = 0;
                __result = n;
                return __result;
                __after_yield_0:;
            END_FOR

            __last_yield = 1;
            __result = node->data;
            return __result;
            __after_yield_1:;

            FOR_IN(n,in_order(node->right),4,6,7)
                __last_yield = 2;
                __result = n;
                return __result;
                __after_yield_2:;
            END_FOR

        }
        __stop_iteration = true;
    }

};

__iter<__ss_int> *in_order(Node *node) {
    return new __gen_in_order(node);
}



Where FOR_IN is a macro to some foreach-like code:

#define FOR_IN(e, iter, temp, i, t) \
    __ ## temp = iter; \
    __ ## i = -1; \
    __ ## t = __ ## temp->for_in_init(); \
    while(__ ## temp->for_in_has_next(__ ## t)) \
    { \
        __ ## i ++; \
        e = __ ## temp->for_in_next(__ ## t);


Note this is not efficient, because it could generate O(n^2) code, but this is not fault of ShedSkin, as the original Python code has the same problem.

They have recently (in Python 3.3) added to Python the syntax "yield from" that will allow to remove that performance problem (currently I think the performance is not improved):

http://legacy.python.org/dev/peps/pep-0380/

Look especially at the section regarding optimization:

http://legacy.python.org/dev/peps/pep-0380/#optimisations

With this improvement the in_order function becomes:

def in_order(node):
    if node is not None:
        yield from in_order(node.left)
        yield node.data
        yield from in_order(node.right)


The F# language has the same optimization, the two differnet kinds of yield are "yield" and "yield!":

http://theburningmonk.com/2011/09/fsharp-yield-vs-yield/

http://stackoverflow.com/questions/3500488/f-yield-operator-implementation-and-possible-c-sharp-equivalents

Bye,
bearophile

On Saturday, 8 March 2014 at 09:25:38 UTC, Timon Gehr wrote:
> This does not do the same thing. It computes the first row even if it is never requested. std.algorithm.filter suffers from the same problem. This is part of the reason why I think the separation of front and popFront is suboptimal design.

Please have a look at this pull request:
https://github.com/D-Programming-Language/phobos/pull/1987