Sleep

May. 12th, 2004 10:56 pm
pmb: (Default)
[personal profile] 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 [livejournal.com profile] goteam to get to PDX in time for her flight on public transit. So we called up [livejournal.com profile] 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 [livejournal.com profile] nedthealpaca and [livejournal.com profile] 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.

Date: 2004-05-12 11:25 pm (UTC)
From: [identity profile] 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?

Date: 2004-05-13 02:25 pm (UTC)
From: [identity profile] pmb.livejournal.com
I think I can reduce "are there any illegal side effects?" to the halting problem...

Date: 2004-05-13 03:14 pm (UTC)
From: [identity profile] 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.)

Date: 2004-05-13 04:52 pm (UTC)
From: [identity profile] 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.

Date: 2004-05-13 02:38 pm (UTC)
From: [identity profile] 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.

Date: 2004-05-14 12:36 am (UTC)
From: [identity profile] 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.

Date: 2004-05-14 10:30 am (UTC)
From: [identity profile] 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().

Profile

pmb: (Default)
pmb

October 2009

S M T W T F S
    1 23
45678910
11121314151617
18192021222324
25262728293031

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2025 11:54 pm
Powered by Dreamwidth Studios