[Python-Dev] Cool link

[Tim Peters]

[Christian Tismer]
> ...
> What is your message? Do you want me to react?

I had no msg other than to share a cool link I thought people here would
find interesting.  While Greg Wilson, e.g., complained about the C macro
implementation of CLU iterators in his review, that's exactly the kind of
thing that should be *interesting* to Python-Dev'ers:  a long and gentle
explanation of an actual implementation.  I expect that most people here
still have no clear idea how generators (let alone continuations) can be
implemented, or why they'd be useful.

Here's a function to compute the number of distinct unlabelled binary trees
with n nodes (these are the so-called Catalan numbers -- the book didn't
mention that):

cache = {0: 1}
def count(n):
    val = cache.get(n, 0)
    if val:
        return val
    for leftsize in range(n):
        val += count(leftsize) * count(n-1 - leftsize)
    cache[n] = val
    return val

Here's one to generate all the distinct unlabelled binary trees with n
nodes:

def genbin(n):
    if n == 0:
        return [()]
    result = []
    for leftsize in range(n):
        for left in genbin(leftsize):
            for right in genbin(n-1 - leftsize):
                result.append((left, right))
    return result

For even rather small values of n, genbin(n) builds lists of impractical
size.  Trying to build a return-one-at-a-time iterator form of genbin()
today is surprisingly difficult.  In CLU or Icon, you just throw away the
"result = []" and "return result" lines, and replace result.append with
"suspend" (Icon) or "yield" (CLU).

Exactly the same kind of algorithm is needed to generate all ways of
parenthesizing an n-term expression.  I did that in ABC once, in a
successful attempt to prove via exhaustion that
raise-complex-to-integer-power in the presence of signed zeroes is
ill-defined under IEEE-754 arithmetic rules.  While nobody here cares about
that, the 754 committee took it seriously indeed.  For me, I'm still just
trying to get Python to address all the things I found unbearable in ABC
<0.7 wink>.

so-if-there's-a-msg-here-it's-unique-to-me-ly y'rs  - tim