Sleep

[pmb]

Presented in opposite order.

---

So, perhaps you were wondering if it was possible to write something like Perl::Memoize in python. The answer, of course is yes. There's lots of versions, from the simple yet appealing

def fib(n):
    if n == 0:
        return 0
    elif n== 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

def memo(f):
    answers = {}
    def g(n):
        if n not in answers:
            answers[n] = f(n)
        return answers[n]
    return g

fib = memo(fib)

To the more-complicated, to the CRAZY. You see, now that python has closures, memoization of closures becomes a possibility. So what you do is break them up, carefully poke innards which you are not supposed to know about, and put them all back together. http://soy.dyndns.org/~peter/projects/fun/random/memoize.py

---

It became clear around 10 pm last night that there was no way for goteam to get to PDX in time for her flight on public transit. So we called up theshytiger and asked to borrow her car. Then we arose at 4:3-, drove to PDX airport (120 miles), I dropped Tracy off, I had breakfast with a surprised nedthealpaca and chocolatesmudge, and then drove back (120 miles). Then I went out to lunch with a faculty candidate. Then I worked on the python crap, then I went to other meetings.

I have been tired beyond belief but not wanting to sleep for ~5 hours now. I have had lots of rambling conversations with people on the phone or in person. I think I will now finally go to well deserved sleep.

Comments

[bellwethr.livejournal.com]

So, I get your fibonacci example, and I scratched my head a few times looking at your more complex example, but think I understand a little of what's going on.

As long as the function in question is purely functional, this technique can be applied, correct? Is it possible to detect when a function suffers from side-effects and ignore the request for memoization?

[pmb.livejournal.com]

I think I can reduce "are there any illegal side effects?" to the halting problem...

[bellwethr.livejournal.com]

Hmm... maybe--although couldn't you build a database of memoizable functions, and if your function calls a non-memoizable function then it's non-memoizable? (I'm thinking of more practical techniques, not theoretical.)

[pmb.livejournal.com]

Right - that wouldn't be so bad, except that python has lots of ways of mucking with the namespace of things that seem like they should be already defined.

Those techniques are also pretty standard Python idioms, so defense against them would need to be pretty robust. The fact that names often aren't resolved until execution of that line, combined with the "sometimes a closure, sometimes a global" crap that I had to deal with could make it very difficult.

[goteam.livejournal.com]

Thank you, thank you, thank you again for the last-minute drive of doom. I miss you and love you and will now continue helping my brother move out of his dorm room instead of inflicting any more mush.

[jesserud.livejournal.com]

Why does redefining fib at the bottom change the meaning of the recursive fib calls? I'm surprised that static scoping doesn't disallow that in Python or JavaScript.

[pmb.livejournal.com]

Name resolution (mostly) doesn't happen until you try and execute a particular line - that is why the func_globals case suffices for the easy case.

For everything dealing with the makefib(), fib() is defined in a nested scope, which means that it carries a closure around with itself. I do surgery on that closure to redefine fib().