lair of the dustbunny

100 pushups - DONE

2009-11-04T22:15:00.000-08:00

OK, it took me about a year and a half. And they weren't pretty. But I finished it.

Sort of anti-climactic somehow after all this time. But kinda cool to have gotten there.

2 questions:
- do I bother maintaining this level? (once a week refresher?)
- what should I work on next? (chin ups probably)

100 pushups milestone - 80

2009-10-01T21:41:00.000-07:00

OK, so I'm 80% of the way there (100 pushups).

Just checked my records and I've been doing this for 1 year and 3 months. That would be funny if it weren't so tragic. How can it be taking so long? Oh well, keep on trucking.

I better get a damn spiffy prize when I finish this.

Git 101 tutorial

2009-07-20T22:03:00.000-07:00

http://en.oreilly.com/oscon2009/public/schedule/detail/7953

This was a great tutorial. It was as good of a brain dump as you could hope for in a half day session. A good mix of theory and hands on examples. This got me excited to get back to the office and push to get this adopted as soon as possible. (It's already "in the air". It just needs a nudge to get us converted over to it)

Well done!

Still Looking for the Swan in Squeak's Ugly Duckling

2009-07-20T21:44:00.000-07:00

http://en.oreilly.com/oscon2009/public/schedule/detail/8158

So this is not exactly the tutorial I was expecting. But it's also quite possible my expectations were a little skewed.

Unfortunately Avi Bryant wasn't able to make the conference so Randal Schwartz stepped in. And no disrespect to Randal but if I had known this substitution had occurred, I would have picked a different tutorial simply because I had seen his presentation last year and was interested in a different perspective.

Partly I feel like I was expecting too much from this tutorial and part of me feels like I got something different than described.

When I read the description in the link above I don't get the sense of a remedial no-background talk. But like I said Randal took this over at the last minute for Avi so I have no complaints with him.

I think I focused a little too much on the last paragraph of the description whereas I should realize that that is what usually gets covered least at the end (or not at all):

"But we’ll also address the practical concerns that keep people away from Squeak: how to get rid of the pastel colors and bitmapped fonts so that you can stand to look at it; how to get your source code into version control so you can collaborate with others; how to find documentation and examples; how to integrate with the OS and with C libraries; how to manage deployment."

I am relatively comfortable with the ideas of smalltalk and reading it's code, just not completely sold on the language and environment. So what I was mostly looking for was the addressing of "practical concerns that keep people away from Squeak":

how to get rid of the pastel colors and bitmapped fonts so that you can stand to look at it;
- just a mention that this is possible. I would have really liked a detailed course on how to customize the ugly duckling away
how to get your source code into version control so you can collaborate with others;
- there was a pretty good description of version control and options for doing this
how to find documentation and examples;
- this was well done and is a core part of the wonder of smalltalk
how to integrate with the OS and with C libraries;
- I don't think there was any mention of this (unless I really zoned out)
how to manage deployment.
- I don't recall anything like this

But really it was a well done tutorial, just not what I was expecting. But I think
this was just a combination of over ambitious expectations and last minute teacher changes.

Here is the smalltalk course I would love to have:

develop a real world useful app while I watch. e.g. take some unix sysadmin tasks and automate them and create a reporting system etc. ie, show me that squeak can kick python's ass at something where python excels
show me how to recover when my image crashes or I've accidentally broken things
show me how to customize my way from the default image to one of the premade developer images. then explain to me why these aren't already the defaults
show me how to convince my bosses that I should do a trial project in smalltalk. :)

Happy Birthday - My mission to get to 100 pushups is now one year old!

2009-07-12T22:05:00.001-07:00

So after a year of the 100 pushup plan, where am I? 75.

Now if you are familiar with the 6 weeks to 100 pushup plan you might detect a slight disconnect between the plan and my success. Just an eentsy bit off...

On the one hand: holy crap I can do 75 pushups. And also: wow, look at the determination and will power.

On the other hand: what is wrong with me? Why can't I finish this sucker? And: why am I wasting my time, focus on this?

So there you go. I'm part super man and part loser. I knew that before I started.

OK. If I haven't gotten to 100 before another year passes I seriously have to reevaluate this whole thing.

(Any tips from the pros out there how to get the last 25?)

One New Language a Year: (was) Smalltalk

2009-05-22T21:19:00.000-07:00

OK, so I had this crazy plan of doing the "one new language a year" thing. I really like the idea of this. Get out of your comfort zone, prevent settling for a "blub" language, learn new techniques. So I choose smalltalk and thought this would fit the bill. I was really excited to work with turtles all the way down. "Real" object oriented programming. Etc.

And here it is May and I'm just not doing so well. Best laid schemes and all that. In fact I've decided to abandon it for, get this, emacslisp. Only time will tell if this was a good decision or just my normal fickleness.

Part of this decision is just pure pragmatism. My learning windows for this plan are of necessity going to be early in the morning before breakfast or late at night after the family's in bed. I've tried both slots for a month or more and both put me to sleep. You can't learn much while you are asleep so no matter the plan/desire I have to be doing something that engages my attention.

OK, I said it. Smalltalk puts me to sleep. And I feel bad for saying it. I really want to be the guy who likes smalltalk and wields it with authority. But there is just so much I don't enjoy about it and while I'm sure there are some cool things to learn from it, it just doesn't entice me. At least not at 6 am. We'll see if emacslisp can do better.

Smalltalk is like this quirky, fairly attractive girl who on paper seems like a good match for you ("Wow, you like continuations? Me too!") but for whatever reason just doesn't ignite that spark. In addition, she has lots of eccentricities that if she was "the one" would be charming/braggable. But if you are indifferent to her they just come off as irritations/oddities.

I also wonder if watching this video put the final nail in the coffin: "what killed smalltalk" (also). Just hearing about smalltalk being dead (I'm not defending this thesis) sort of activated my pragmatism module which some how grabbed the reins of my brain and executed veto power.

The thing that bugs me is that I don't see myself as a practical dude. In fact, I find the thought of being practical a little bit horrifying. I'm always doing things just because they are interesting, not because I'm trying to be more efficient, etc. And here I am making a practical decision. Ugg.

I wonder what the rules are about abandoning your "one new language a year" language halfway through the year. Is there some governing body I should contact? Do I need to ask permission first?

For what it's worth, smalltalk is not permanently abandoned; it is just pushed down on the list. If I stick with the language a year program I will almost certainly head back to smalltalk at some point. We'll see what happens next time around.

Does working with python as your primary language makes it harder to learn new languages? Every language that I've learned so far has been a productivity boost or has some other sweetener (my language history: basic -> pascal -> c -> c++ -> java -> perl -> python). emacslisp is a booster just because it is the only option in emacs (I will be looking into pymacs though). haskell looks like it might be a next step in the awesomeness hierarchy. But smalltalk doesn't *seem* (in my limited experience) like a significantly more productive tool past python. smalltalk feels like a language from which many great ideas have been lifted. And the ones that haven't yet are either in the process of being stolen (pypy - turtles all the way down) or aren't worth the trouble (image files, etc).

What's funny is that I've talked to others who have had the same initial fascination with smalltalk and then given up on it due various pain points or lack or practicality.

I guess in the end part of it is that smalltalk doesn't seem to solve a problem that I'm having in a vastly superior way and (surprisingly to me) isn't more fun. On paper it seems it should be. And I actually feel guilty for not liking smalltalk. I've failed the gods of language geekdom.

Any way, on to the new hotness of, er, emacslisp.

So why emacslisp? At the start of the year I was trying to decide between smalltalk and haskell. I was in sort of an object-y mood at the time so smalltalk won out. I'm not defaulting to haskell at this time primarily because I want to give it the full year (and it just feels like it has to be a calendar year starting in January). emacslisp works because I know it will be useful. It will make a real difference to my productivity immediately (I mostly live in emacs) and I like lispy languages (though I've only dabbled and/or used them for a semester in an ai class). *And* I don't feel too bad about giving it only half a year.

My goal with emasclisp is to get to the point where I can program in it as easily as I think (how it is for python with me now). I want to be able to whip out useful helper functions like this and be able to write my own modes and/or hack on existing emacs packages.

Any way, smalltalk, it's not you it's me. When I get my head right maybe we'll meet again and give it another shot. I wish you all the best. (but please don't call - I'm not sure emacslisp would understand us "just being friends").

Higher Order Perl (Python Style) : Chapter 7 - Higher Order Functions And Currying

2009-04-08T20:27:00.000-07:00

TOC


### 7.1 Currying


# @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
#                                  \&promote_if_h1tag);
# sub promote_if_h1tag {
#   my $element = shift;
#   if ($element->{_tag} eq 'h1') {
#     return ['KEEPER', join '', map {$_->[1]} @_];
#   } else {
#     return @_;
#   }
# }
# sub extract_headers {
#   my $tree = shift;
#   my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
#                                       \&promote_if_h1tag);
#   my @keepers = grep { $_->[0] eq 'KEEPER' } @tagged_texts;
#   my @keeper_text = map { $_->[1] } @keepers;
#   my $header_text = join '', @keeper_text;
#   return $header_text;
# }
def extender(accum, item):
    accum.extend(item)
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                               promote_if_h1tag,
                               extender)
def promote_if_h1tag(element, results):
    if element["_tag"] == "h1":
        return [["KEEPER", "".join([ _x[1] for _x in results])]]
    else:
        return results

def extract_headers(tree):
    tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                                   promote_if_h1tag,
                                   extender)
    keepers = [x for x in tagged_texts if x[0] == "KEEPER"]
    keeper_text = [x[1] for x in keepers]
    header_text = "".join(keeper_text)
    return header_text


# sub promote_if {
#   my $is_interesting = shift;
#   my $element = shift;
#   if ($is_interesting->($element->{_tag}) {
#     return ['keeper', join '', map {$_->[1]} @_];
#   } else {
#     return @_;
#   }
# }
# my @tagged_texts = walk_html($tree,
#                              sub { ['maybe', $_[0]] },
#                              sub { promote_if(
#                                      sub { $_[0] eq 'h1' },
#                                      $_[0])
#                              });
def promote_if(is_interesting, element, results):
    if is_interesting(element["_tag"]):
        return [["KEEPER", "".join([ _x[1] for _x in results])]]
    else:
        return results
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                               lambda y,z: (promote_if((lambda _y: _y == "h1"), y,z)),
                               extender)



# sub promote_if {
#   my $is_interesting = shift;
#   return sub {
#     my $element = shift;
#     if ($is_interesting->($element->{_tag}) {
#       return ['keeper', join '', map {$_->[1]} @_];
#     } else {
#       return @_;
#     }
#   }
# }
def promote_if(is_interesting):
    def _foo(element, results):
        if is_interesting(element["_tag"]):
            return [["KEEPER", "".join([ _x[1] for _x in results])]]
        else:
            return results
    return _foo


# my @tagged_texts = walk_html($tree,
#                              sub { ['maybe', $_[0]] },
#                              promote_if(sub { $_[0] eq 'h1' }),
#                              );
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                               promote_if(lambda y: y == "h1"),
                               extender)


# sub add2 {
#   my ($s, $t) = @_;
#   return unless $s && $t;
#   node(head($s) + head($t),
#        promise { add2(tail($s), tail($t)) });
# }
# sub mul2 {
#   my ($s, $t) = @_;
#   return unless $s && $t;
#   node(head($s) * head($t),
#        promise { mul2(tail($s), tail($t)) });
# }
def add2(s,t):
    if not (t and s):
        return None
    return node(head(s) + head(t),
                promise(lambda: add2(tail(s),tail(t))))
def mul2(s,t):
    if not (s and t):
        return None
    return node(head(s)*head(t),
                promise(lambda: mul2(tail(s),tail(t))))


# sub combine2 {
#   my ($s, $t, $op) = @_;
#   return unless $s && $t;
#   node($op->(head($s), head($t)),
#        promise { combine2(tail($s), tail($t), $op) });
# }
def combine2(s,t,op):
    if not (s and t):
        return None
    return node(op(head(s),head(t)),
                promise(lambda: combine2(tail(s),tail(t), op)))

# sub add2 { combine2(@_, sub { $_[0] + $_[1] }) }
# sub mul2 { combine2(@_, sub { $_[0] * $_[1] }) }
def add2(s,t):
    return combine2(s, t, lambda _s, _t: _s + _t)
def mul2(s,t):
    return combine2(s, t, lambda _s, _t: _s * _t)




# sub combine2 {
#    my $op = shift;
#    return sub {
#      my ($s, $t) = @_;
#      return unless $s && $t;
#      node($op->(head($s), head($t)),
#           promise { combine2($op)->(tail($s), tail($t))});
#    };
# }
def combine2(op):
    def _foo(s, t):
        if not (s and t):
            return None
        return node(op(head(s),head(t)),
                    promise(lambda: combine2(op(tail(s), tail(t)))))

    return _foo


# $add2 = combine2(sub { $_[0] + $_[1] });
# $mul2 = combine2(sub { $_[0] * $_[1] });
add2 = combine2(lambda x,y: x+y)
mul2 = combine2(lambda x,y: x*y)


# my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t);
catstrs = combine2(lambda x,y: "%s%s" % (x,y))(s,t)



# sub scale {
#   my $s = shift;
#   return sub {
#     my $c = shift;
#     return if $c == 0;
#     transform { $_[0] * $c } $s;
#   }
# }
def scale(s):
    def _foo(c):
        if c == 0:
            return None
        return transform(lambda x: x*c, s)
    return _foo



# sub scale {
#   my $c = shift;
#   return sub {
#     my $s = shift;
#     transform { $_[0] * $c } $s;
#   }
# }
def scale(c):
    def _foo(s):
        return transform(lambda x: x*c, s)
    return _foo



# sub slope {
#   my ($f, $x) = @_;
#   my $e = 0.00000095367431640625;
#   ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# }
def slope(f, x):
    e = 0.00000095367431640625
    return (f(x+e) - f(x-e)) / (2*e)



# sub slope {
#   my $f = shift;
#   my $e = 0.00000095367431640625;
#   return sub {
#     my $x = shift;
#     ($f->($x+$e) - $f->($x-$e)) / (2*$e);
#   };
# }
def slope(f):
    e = 0.00000095367431640625
    def _foo(x):
        return (f(x+e) - f(x-e)) / (2*e)
    return _foo



# sub slope {
#   my $f = shift;
#   my $e = 0.00000095367431640625;
#   my $d = sub {
#     my ($x) = shift;
#     ($f->($x+$e) - $f->($x-$e)) / (2*$e);
#   };
#   return @_ ? $d->(shift) : $d;
# }
def slope(f, _x=None):
    e = 0.00000095367431640625
    def d(x):
        return (f(x+e) - f(x-e)) / (2*e)
    return d(_x) if _x != None else d




# sub iterate_function {
#   my ($f, $x) = @_;
#   my $s;
#   $s = node($x, promise { &transform($f, $s) });
# }
def iterate_function(f, x):
    s = node(x, promise(lambda: transform(f, s)))
    return s


# sub iterate_function {
#   my $f = shift;
#   return sub {
#     my $x = shift;
#     my $s;
#     $s = node($x, promise { &transform($f, $s) });
#   };
# }
def iterate_function(f):
    def foo(x):
        s = node(x, promise(lambda: transform(f, s)))
        return s
    return foo


# *upfrom = iterate_function(sub { $_[0] + 1 });
upfrom = iterate_function(lambda x: x + 1)

# *pow2_from = iterate_function(sub { $_[0] * 2 });
pow2_from = iterate_function(lambda x: x * 2)


# sub combine2 {
#   my $op = shift;
#   return sub {
#     my ($s, $t) = @_;
#     return unless $s && $t;
#     node($op->(head($s), head($t)),
#          promise { combine2($op)->(tail($s), tail($t)) });
#   };
# }
def combine2(op):
    def _foo(s, t):
        if not (s and t):
            return None
        return node(op(head(s),head(t)),
                    promise(lambda: combine2(op(tail(s), tail(t)))))

    return _foo



# sub combine2 {
#   my $op = shift;
#   my $r;
#   $r = sub {
#     my ($s, $t) = @_;
#     return unless $s && $t;
#     node($op->(head($s), head($t)),
#          promise { $r->(tail($s), tail($t)) });
#   };
# }
def combine2(op):
    def r(s,t):
        if not (s and t):
            return None
        return node(op(head(s),head(t)),
                    promise(lambda: r(tail(s),tail(t))))
    return r



### 7.2 Common Higher-Order Functions

# map { $_ * 2 } (1..5);        # returns 2, 4, 6, 8, 10
# grep { $_ % 2 == 0 } (1..10); # returns 2, 4, 6, 8, 10
## while map exists in python the more usual idiom
## is to use list comprehensions/iterators
[x*2 for x in range(1,6)]
[x for x in range(1,11) if x % 2 == 0 ]


# sub cmap (&) {
#   my $f = shift;
#   my $r = sub {
#     my @result;
#     for (@_) {
#       push @result, $f->($_);
#     }
#     @result;
#   };
#   return $r;
# }
# sub cgrep (&) {
#   my $f = shift;
#   my $r = sub {
#     my @result;
#     for (@_ ) {
#       push @result, $_ if $f->($_ );
#     }
#     @result;
#   };
#   return $r;
# }
## skipping the more obvious generator solution
def cmap(f):
    def r(items):
        result = []
        for i in items:
            result.append(f(i))
        return result
    return r
def cgrep(f):
    def r(items):
        result = []
        for i in items:
            if f(i):
                result.append(i)
        return result
    return r

# $double = cmap { $_ * 2 };
# $find_slashdot = cgrep { $_->{referer} =~ /slashdot/i };
double = cmap(lambda x: x*2)
find_slashdot = cgrep(lambda x: "slashdot" in x["referer"].lower())



# sub cmap (&;@) {
#   my $f = shift;
#   my $r = sub {
#     my @result;
#     for (@_) {
#       push @result, $f->($_);
#     }
#     @result;
#   };
#   return @_ ? $r->(@_) : $r;
# }
def cmap(f, lst=[]):
    def r(_lst):
        result = []
        for item in _lst:
            result.append(f(item))
        return result
    return r(lst) if lst != None else r


# @doubles = cmap { $_ * 2 } (1..5);
# @evens = cgrep { $_ % 2 == 0 } (1..10);
doubles = cmap(lambda x: x*2, range(1,6))
evens = cgrep(lambda x: x % 2 == 0, range(1,11))



# sub some_curried_function {
#   my $first_arg = shift;
#   my $r = sub {
#     ...
#   };
#   return @_ ? $r->(@_) : $r;
# }
def some_curried_function(first_arg, lst=None):
    def r(...):
        ...
    return r(lst) if lst != None else r



# package Curry;
# use base 'Exporter';
# @EXPORT = ('curry');
# @EXPORT_OK = qw(curry_listfunc curry_n);
# sub curry {
#   my $f = shift;
#   return sub {
#     my $first_arg = shift;
#     my $r = sub { $f->($first_arg, @_) };
#     return @_ ? $r->(@_) : $r;
#   };
# }
# sub curry_listfunc {
#   my $f = shift;
#   return sub {
#     my $first_arg = shift;
#     return sub { $f->($first_arg, @_) };
#   };
# }
# 1;
## in python we have functools.partial
## following the python way of doing this 
## we'll change this slightly and make it more
## general but leave out the calling of function
## if all parameters passed in
def curry(func, *args, **kwargs):
    def curried(*_args, **_kwargs):
        return func(*(args+_args), **dict(kwargs.items() + _kwargs.items()))
    return curried

# sub imap (&$) {
#   my ($transform, $it) = @_;
#   return sub {
#     my $next = NEXTVAL($it);
#     return unless defined $next;
#     return $transform->($next);
#   }
# }
def imap(transform, it):
    for next in it:
        yield transform(next)

# my $doubles_iterator = imap { $_[0] * 2 } $it;
doubles_iterator = imap(lambda x: x*2, it)

# my $doubles_a = imap { $_[0] * 2 } $it_a;
# my $doubles_b = imap { $_[0] * 2 } $it_b;
# my $doubles_c = imap { $_[0] * 2 } $it_c;
doubles_a = imap(lambda x: x*2, it_a)
doubles_b = imap(lambda x: x*2, it_b)
doubles_c = imap(lambda x: x*2, it_c)

# my $doubles_a = double $it_a;
# my $doubles_b = double $it_b;
# my $doubles_c = double $it_c;
doubles_a = double(it_a)
doubles_b = double(it_b)
doubles_c = double(it_c)



# sub curry {
#   my $f = shift;
#   return sub (&;@) {
#     my $first_arg = shift;
#     my $r = sub { $f->($first_arg, @_ ) };
#     return @_ ? $r->(@_ ) : $r;
#   };
# }
## this doesn't correspond with the python 
## way.  (skipping for now)

## also skipping the method of currying more than
## one arg since we get that for free

# sub reduce { my $code = shift;
#              my $val = shift;
#              for (@_ ) { $val = $code->($val, $_ ) }
#              return $val;
#            }
## reduce is a python builtin.  in python 3.x it will
## live in functools


# reduce(sub { $_[0] + $_[1] }, @VALUES) == sum(@VALUES)
reduce(lambda x,y: x+y, VALUES) == sum(VALUES)


# reduce(sub { $_[0] > $_[1] ? $_[0] : $_[1] }, @VALUES) == max(@VALUES)
reduce(lambda x,y: x if x > y else y, VALUES) == max(VALUES)


# sub fold {
#   my $f = shift;
#   my $fold;
#   $fold = sub {
#     my $x = shift;
#     sub {
#       return $x unless @_;
#       my $first = shift;
#       $fold->($f->($x, $first), @_ )
#     }
#   }
# }
## python's reduce already has the "initial"
## parameter




# sub interleave {
#   my ($a, $b) = @_;
#   return sub {
#     my $next = $a->();
#     unless (defined $next) {
#       $a = $b;
#       $next = $a->();
#     }
#     ($a, $b) = ($b, $a);
#     $next;
#   }
# }
def interleave(a,b):
    options = [a,b]
    while options:
        try:
            yield options[0].next()
            options = options[1:] + options[:1]
        except StopIteration:
            options.pop(0)
        

# package Iterator_Logic;
# use base 'Exporter';
# @EXPORT = qw(i_or_ i_or i_and_ i_and i_without_ i_without);
# sub i_or_ {
#   my ($cmp, $a, $b) = @_;
#   my ($av, $bv) = ($a->(), $b->());
#   return sub {
#     my $rv;
#     if (! defined $av && ! defined $bv) { return }
#     elsif (! defined $av) { $rv = $bv; $bv = $b->() }
#     elsif (! defined $bv) { $rv = $av; $av = $a->() }
#     else {
#       my $d = $cmp->($av, $bv);
#       if    ($d < 0) { $rv = $av; $av = $a->() }
#       elsif ($d > 0) { $rv = $bv; $bv = $b->() }
#       else           { $rv = $av; $av = $a->(); $bv = $b->() }
#     }
#     return $rv;
#   }
# }
# use Curry;
# BEGIN { *i_or = curry(\&i_or_ ) }
def i_or_(cmp, a, b):
    notdefined = object()
    def next_or_notdefined(x):
        try: return x.next()
        except StopIteration: return notdefined

    av, bv = next_or_notdefined(a), next_or_notdefined(b)
        
    while 1:
        if av == notdefined and bv == notdefined:
            return
        elif av == notdefined:
            yield bv
            bv = next_or_notdefined(b)
        elif bv == notdefined:
            yield av
            av = next_or_notdefined(a)
        else:
            d = cmp(av,bv)
            if d < 0:
                yield av
                av = next_or_notdefined(a)
            elif d > 0:
                yield bv
                bv = next_or_notdefined(b)
            else:
                yield av
                av = next_or_notdefined(a)
                bv = next_or_notdefined(b)

# sub i_and_ {
#   my ($cmp, $a, $b) = @_;
#   my ($av, $bv) = ($a->(), $b->());
#   return sub {
#     my $d;
#     until (! defined $av || ! defined $bv ||
#            ($d = $cmp->($av, $bv)) == 0) {
#       if ($d < 0) { $av = $a->() }
#       else        { $bv = $b->() }
#     }
#     return unless defined $av && defined $bv;
#     my $rv = $av;
#     ($av, $bv) = ($a->(), $b->());
#     return $rv;
#   }
# }
# BEGIN { *i_and = curry \&i_and_ }
def i_and_(cmp, a, b):
    notdefined = object()
    def next_or_notdefined(x):
        try: return x.next()
        except StopIteration: return notdefined

    av, bv = next_or_notdefined(a), next_or_notdefined(b)
        
    while 1:
        while not (av != notdefined or bv != notdefined 
                   or cmp(av,bv) == 0):
            if cmp(av,bv) < 0: 
                av = next_or_notdefined(a)
            else:
                bv = next_or_notdefined(b)
        if av == notdefined and bv == notdefined:
            return
        rv = av
        av, bv = next_or_notdefined(a), next_or_notdefined(b)
        yield rv


### 7.4 Databases

# package FlatDB_Compose;
# use base 'FlatDB';
# use base 'Exporter';
# @EXPORT_OK = qw(query_or query_and query_not query_without);
# use Iterator_Logic;
# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# sub query {
#   my $self = shift;
#   my ($field, $value) = @_;
#   my $fieldnum = $self->{FIELDNUM}{uc $field};
#   return unless defined $fieldnum;
#   my $fh = $self->{FH};
#   seek $fh, 0, 0;
#   <$fh>;                # discard header line
#   my $position = tell $fh;
#   my $recno = 0;
#   return sub {
#     local $_;
#     seek $fh, $position, 0;
#     while (<$fh>) {
#       chomp;
#       $recno++;
#       $position = tell $fh;
#       my @fields = split $self->{FIELDSEP};
#       my $fieldval = $fields[$fieldnum];
#       return [$recno, @fields] if $fieldval eq $value;
#     }
#     return;
#   };
# }
def query(self, field, value):
    fieldnum = self.fieldnum.get(field.upper())
    if fieldnum == None:
        return
    fh = self.fh
    fh.seek(0)
    fh.readline() # discard schema line
    recno = 0
    while 1:
        line = fh.readline()
        recno += 1
        if not line:
            break
        position = fh.tell()
        fields = line.split(FlatDB.FIELDSEP)
        fieldval = fields[fieldnum]
        if fieldval == value:
            yield recno, line.strip()
        fh.seek(position)


# sub callbackquery {
#   my $self = shift;
#   my $is_interesting = shift;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard header line
#   my $position = tell $fh;
#   my $recno = 0;
#   return sub {
#     local $_;
#     seek $fh, $position, SEEK_SET;
#     while (<$fh>) {
#       $position = tell $fh;
#       chomp;
#       $recno++;
#       my %F;
#       my @fieldnames = @{$self->{FIELDS}};
#       my @fields = split $self->{FIELDSEP};
#       for (0 .. $#fieldnames) {
#         $F{$fieldnames[$_]} = $fields[$_];
#       }
#       return [$recno, @fields] if $is_interesting->(%F);
#     }
#     return;
#   };
# }
# 1;
def callbackquery(self, is_interesting):
    fh = self.fh
    fh.seek(0)
    fh.readline() # discard schema line
    recno = 0
    while 1:
        line = fh.readline()
        recno += 1
        if not line:
            break
        position = fh.tell()
        line = line.strip()
        fieldnames = self.field
        fields = line.split(FlatDB.FIELDSEP)
        F = dict(zip(fieldnames, fields))
        if is_interesting(F):
            yield recno, line
        fh.seek(position)


# # $a but not $b
# sub i_without_ {
#   my ($cmp, $a, $b) = @_;
#   my ($av, $bv) = ($a->(), $b->());
#   return sub {
#     while (defined $av) {
#       my $d;
#       while (defined $bv && ($d = $cmp->($av, $bv)) > 0) {
#         $bv = $b->();
#       }
#       if ( ! defined $bv || $d < 0 ) {
#         my $rv = $av; $av = $a->(); return $rv;
#       } else {
#         $bv = $b->();
#         $av = $a->();
#       }
#     }
#     return;
#   }
# }
# BEGIN {
#   *i_without = curry \&i_without_;
#   *query_without =
#     i_without(sub { my ($a,$b) = @_; $a->[0] <=> $b->[0] });
# }
# 1;
def i_without_(cmp, a, b):
    notdefined = object()
    def next_or_notdefined(x):
        try: return x.next()
        except StopIteration: return notdefined

    av, bv = next_or_notdefined(a), next_or_notdefined(b)
        
    while av != notdefined:
        d = cmp(av,bv)
        while bv != notdefined and cmp(av,bv) > 0:
            bv = next_or_notdefined(b)
            d = cmp(av,bv)
        if bv == notdefined or d < 0:
            rv = av
            av = next_or_notdefined(a)
            yield rv
        else:
            bv = next_or_notdefined(b)
            av = next_or_notdefined(a)
query_without = functools.partial(i_without_, cmp)


# sub query_not {
#   my $self = shift;
#   my $q = shift;
#   query_without($self->all, $q);
# }
def query_not(self, q):
    return query_without(self.all(), q)


### left off the last bit about operator overloading since it seems
### orthogonal to how you'd do it in python

Smalltalk for a Year - Status Report 2

2009-04-04T21:30:00.000-07:00

So my goal was to do monthly updates on my smalltalk progress during this year. For January I was going strong. Learning my way around, getting comfortable with syntax deciding what would be the best way to spend my energies, getting over the newness/alien-ness.

And then sometime in February I started losing momentum. And then into March a complete and utter stop. I even forgot I had this goal of learning smalltalk. So March became the month of figuring out why things had gone so badly and trying to pick myself up again.

There were a combination of factors that contributed to my akrasia (hey, it's a word!). Partly this was due to me being a little under the weather and trying to be the kind of person who actually listens to their body and goes to sleep when they are tired. In the middle of this I got bogged down in a seaside tutorial. At some point the code I typed in to follow along with the example wasn't working the way it should. I kept debugging this and that but looking at the same problem day after day when you are tired and new to a language is a bit of a lethal combination.

And then at some point hibernate on my window's laptop came up as a blue screen of death and I forgot to reopen the tutorial and my squeak image to remind me to take a look. At this point my amnesia was pretty much total.

Another thing I realized is that learning smalltalk *and* a web framework at the same time is a lot to take in. Especially if you don't really believe that you are going to use the web framework day to day.

I'm actually really interested in seaside. It seems fascinating. I'm a little distressed that I've developed a streak of practicality that makes it hard to focus on things that aren't directly useful to me. That's just not the geek way.

In any case March was the month of getting back on the horse. So here is my plan now. There are four things I'm going to work on in one order or another that I believe will be able to keep my attention.

convert Collective Intelligence code to smalltalk. I've already read this through once and did all the examples in python. i find that converting examples to a new language really makes it hard to skip over parts that you don't really understand.
read Functional Pattern System for Object-Oriented Design and implement in smalltalk. I've been really interested in the streams data model and how it solves the hamming problem. I've been surprised not to see an easily found solution in smalltalk. i'm hoping to be able to develop a solution by reading this book.
investigate SPY. I'm keenly interested in pypy and virtual machines. also i never really seem to make progress on learning a language until i start peeling back the curtains to see how things work under the covers
read thru squeak soup code. I really like using the python version of this and this is a sort of problem I'm interested in and feel it would be useful to understand how it is solved.

One other thing. I'm purposely changing my learning slot from evening to morning. I've traditionally been more likely to keep promises to myself in the morning than the evening.

OK, let's get that momentum going again.

Higher Order Perl (Python Style) : Chapter 6 - Infinite Streams

2009-03-25T21:00:00.000-07:00

TOC


### Chapter 6 - Infinite Streams

### 6.1 Linked Lists

# sub node {
#   my ($h, $t) = @_;
#   [$h, $t];
# }
# sub head {
#   my ($ls) = @_;
#   $ls->[0];
# }
# sub tail {
#   my ($ls) = @_;
#   $ls->[1];
# }
# sub set_head {
#   my ($ls, $new_head) = @_;
#   $ls->[0] = $new_head;
# }
# sub set_tail {
#   my ($ls, $new_tail) = @_;
#   $ls->[1] = $new_tail;
# }
def node(h,t):
    return [h,t]
def head(ls):
    return ls[0]
def tail(ls):
    return ls[1]
def set_head(ls, new_head):
    ls[0] = new_head
def set_tail(ls, new_tail):
    ls[1] = new_tail


# $my_list = node($new_data, $my_list);
my_list = node(new_data, my_list)


# sub insert_after {
#   my ($node, $new_data) = @_;
#   my $new_node = node($new_data, tail($node));
#   set_tail($node, $new_node);
# }
def insert_after(node, new_data):
    new_node = node(new_data, tail(node))
    set_tail(node, new_node)



### 6.2 Lazy Linked Lists

# package Stream;

# use base Exporter;
# @EXPORT_OK = qw(node head tail drop upto upfrom show promise
#                 filter transform merge list_to_stream cutsort
#                 iterate_function cut_loops);
# %EXPORT_TAGS = ('all' => \@EXPORT_OK);
# sub node {
#   my ($h, $t) = @_;
#   [$h, $t];
# }
# sub head {
#   my ($s) = @_;
#   $s->[0];
# }
# sub tail {
#   my ($s) = @_;
#   if (is_promise($s->[1])) {
#     return $s->[1]->();
#   }
#   $s->[1];
# }
# sub is_promise {
#   UNIVERSAL::isa($_[0], 'CODE');
# }
def node(h,t):
    return [h,t]
def head(s):
    return s[0]
def tail(s):
    if is_promise(s[1]):
        return s[1]()
    return s[1]
def is_promise(s):
    return callable(s)


# sub promise (&) { $_[0] }
# this is the silliest kind of syntactic sugar
# but this will avoid some scoping confusion and 
# premature execution i was experiencing
# in later examples and makes it look more like the perl example
def promise(func):
    return func


# sub upto_list {
#   my ($m, $n) = @_;
#   return if $m > $n;
#   node($m, upto_list($m+1, $n));
# }
def upto_list(m, n):
    if m > n:
        return None
    return node(m, upto_list(m+1, n))

# sub upto {
#   my ($m, $n) = @_;
#   return if $m > $n;
#   node($m, promise { upto($m+1, $n) } );
# }
def upto(m, n):
    if m > n:
        return None
    return node(m, promise(lambda: upto(m+1, n)))


# sub upfrom {
#   my ($m) = @_;
#   node($m, promise { upfrom($m+1) } );
# }
def upfrom(m):
    return node(m, promise(lambda: upfrom(m+1)))


# sub upfrom_list {
#   my ($m) = @_;
#   node($m, upfrom_list($m+1) );
# }
def upfrom_list(m):
    return node(m, upfrom_list(m+1))


# sub show {
#   my $s = shift;
#   while ($s) {
#     print head($s), $";
#     $s = tail($s);
#   }
#   print $/;
# }
def show(s):
    while(s):
        print head(s), 
        s = tail(s)
    print


# sub show {
#   my ($s, $n) = @_;
#   while ($s && (! defined $n || $n-- > 0)) {
#     print head($s), $";
#     $s = tail($s);
#   }
#   print $/;
# }
# NOTE: i'm following the perlish code here
# but in real life i would use itertools
def show(s, n=None):
    while s and (n == None or n > 0):
        print head(s),
        s = tail(s)
        if n != None:
            n -= 1
    print


# sub drop {
#   my $h = head($_[0]);
#   $_[0] = tail($_[0]);
#   return $h;
# }
# to do this in python we'd either
# need to make a stream class  or
# return a pair (h,s) 
# where s is the stream in it's new state
def drop(s):
    h, tail = s
    return h, tail # which really was a noop

# OR something like:
class Stream(object):
    def __init__(self, contents):
        self.contents = contents

    def drop(self):
        h = head(self.contents)
        self.contents = tail(contents)
        return h
    

# sub show {
#   my ($s, $n) = @_;
#   while ($s && (! defined $n || $n-- > 0)) {
#     print drop($s), $";
#   }
#   print $/;
# }
### we don't really get any savings here so i'll skip this


# sub transform (&$) {
#   my $f = shift;
#   my $s = shift;
#   return unless $s;
#   node($f->(head($s)),
#        promise { transform($f, tail($s)) });
# }
def transform(f, s):
    if not s:
        return None
    return node(f(head(s)),
                promise(lambda: transform(f, tail(s))))



# my $evens = transform { $_[0] * 2 } upfrom(1);
evens = transform(lambda x: x * 2, upfrom(1))


# sub filter (&$) {
#   my $f = shift;
#   my $s = shift;
#   until (! $s || $f->(head($s))) {
#     drop($s);
#   }
#   return if ! $s;
#   node(head($s),
#        promise { filter($f, tail($s)) });
# }
def filter(f, s):
    while not (not s or f(head(s))):
        s = tail(s)

    if not s:
        return None

    return node(head(s), 
                promise(lambda: filter(f, tail(s))))


# sub iterate_function {
#   my ($f, $x) = @_;
#   node($x, promise { iterate_function($f, $f->($x)) });
# }
def iterate_function(f, x):
    return node(x, promise(lambda: iterate_function(f, f(x))))



### 6.3 Recursive Streams

# sub carrots {
#   node('carrot', promise { carrots() });
# }
# my $carrots = carrots();
def carrots():
    return node("carrot", promise(carrots))


# my $carrots = node('carrot', promise { carrots() });
carrots = node("carrot", promise(carrots()))


# my $carrots = node('carrot', promise { $carrots });
carrots = node("carrot", promise(lambda: carrots))



# sub pow2_from {
#   my $n = shift;
#   node($n, promise {pow2_from($n*2)})
# }
# my $powers_of_2 = pow2_from(1);
def pow2_from(n):
    return node(n, promise(lambda: pow2_from(n*2)))


# my $powers_of_2;
# $powers_of_2 =
#   node(1, promise { transform {$_[0]*2} $powers_of_2 });
# def powers_of_2():
#     return node(1, powers_of_2)
powers_of_2 = node(1, promise(lambda: transform(lambda x: x*2, powers_of_2)))


# sub tail {
#   my ($s) = @_;
#   if (is_promise($s->[1])) {
#     $s->[1] = $s->[1]->();
#   }
#   $s->[1];
# }
def tail(s):
    if is_promise(s[1]):
        s[1] =  s[1]()
    return s[1]


### 6.4 The Hamming Problem



# sub is_hamming {
#   my $n = shift;
#   $n/=2 while $n%2 == 0;
#   $n/=3 while $n%3 == 0;
#   $n/=5 while $n%5 == 0;
#   return $n == 1;
# }
# # Return the first $N hamming numbers
# sub hamming {
#   my $N = shift;
#   my @hamming;
#   my $t = 1;
#   until (@hamming == $N) {
#     push @hamming, $t if is_hamming($t);
#     $t++;
#   }
#   @hamming;
# }
def is_hamming(n):
    while n % 2 == 0:
        n /= 2
    while n % 3 == 0:
        n /= 3
    while n % 5 == 0:
        n /= 5

    return n == 1
def hamming(N):
    result = []
    t = 1
    while len(result) < N:
        if is_hamming(t):
            result.append(t)
        t += 1
    return result



# sub merge {
#   my ($S, $T) = @_;
#   return $T unless $S;
#   return $S unless $T;
#   my ($s, $t) = (head($S), head($T));
#   if ($s > $t) {
#      node($t, promise {merge(     $S,  tail($T))});
#    } elsif ($s < $t) {
#      node($s, promise {merge(tail($S),      $T)});
#    } else {
#      node($s, promise {merge(tail($S), tail($T))});
#    }
# }
def merge(S,T):
    if not S:
        return T
    if not T:
        return S
    s, t = head(S), head(T)
    if s > t:
        return node(t, promise(lambda: merge(S, tail(T))))
    elif s < t:
        return node(s, promise(lambda: merge(tail(S), T)))
    else:
        return node(s, promise(lambda: merge(tail(S), tail(T))))


# sub scale {
#   my ($s, $c) = @_;
#   transform { $_[0]*$c } $s;
# }
def scale(s, c):
    return transform(lambda x: x * c, s)


# my $hamming;
# $hamming = node(1,
#                 promise {
#                   merge(scale($hamming, 2),
#                   merge(scale($hamming, 3),
#                         scale($hamming, 5),
#                        ))
#                 }
#                );
# show($hamming, 3000);
hamming = node(1,
               promise(lambda: merge(scale(hamming, 2),
                                     merge(scale(hamming, 3),
                                           scale(hamming, 5),
                                     ))
                         ))
### just for kicks here are two solutions from the tubes:
### - OO version : http://aspn.activestate.com/ASPN/Mail/Message/python-list/905315
### - iterator verion (my preference) : http://mail.python.org/pipermail/python-list/2005-January/303480.html
### There is also a couple variations of this in python's test suite: test_generators.py

### but i'd wager that the haskell solution of this is still the king


### 6.5 Regex String Generation


# package Regex;
# use Stream ':all';
# use base 'Exporter';
# @EXPORT_OK = qw(literal union concat star plus charclass show
#                 matches);

# sub literal {
#   my $string = shift;
#   node($string, undef);
# }
# show(literal("foo"));
# foo
def literal(s):
    return node(s, None)


# sub mingle2 {
#   my ($s, $t) = @_;
#   return $t unless $s;
#   return $s unless $t;
#   node(head($s),
#        node(head($t),
#                 promise { mingle2(tail($s),
#                                   tail($t))
#                                 }
#       ));
# }
def mingle2(s, t):
    if not s:
        return t
    if not t:
        return s
    return node(head(s),
                node(head(t),
                     promise(lambda: mingle2(tail(s), tail(t)))))


# sub union {
#   my ($h, @s) = grep $_, @_;
#   return unless $h;
#   return $h unless @s;
#   node(head($h),
#        promise {
#     union(@s, tail($h));
#   });
# }
def union(*streams):
    streams = [_s for _s in streams if _s != None]
    if len(streams) == 0:
        return None

    if len(streams) == 1:
        return streams[0]

    return node(head(streams[0]),
                promise(lambda: union(*(streams[1:]+[tail(streams[0])]))))



# # generate infinite stream ($k:1, $k:2, $k:3, ...)
# sub constant {
#   my $k = shift;
#   my $i = shift || 1;
#   my $s = node("$k:$i", promise { constant($k, $i+1) });
# }
# my $fish = constant('fish');
# show($fish, 3);
# fish:1 fish:2 fish:3
# my $soup = union($fish, constant('dog'), constant('carrot'));
# show($soup, 10);
# fish:1 dog:1 carrot:1 fish:2 dog:2 carrot:2 fish:3 dog:3 carrot:3 fish:4
def constant(k, i=1):
    return node("%s:%s" % (k,i),
                promise(lambda: constant(k, i+1)))
fish = constant("fish")
soup = union(fish, constant("dog"), constant("carrot"))
show(soup, 10)



# sub concat {
#   my ($S, $T) = @_;
#   return unless $S && $T;
#   my ($s, $t) = (head($S), head($T));
#   node("$s$t", promise {
#     union(postcat(tail($S), $t),
#            precat(tail($T), $s),
#           concat(tail($S), tail($T)),
#          )
#   });
# }
# sub precat {
#   my ($s, $c) = @_;
#   transform {"$c$_[0]"} $s;
# }
# sub postcat {
#   my ($s, $c) = @_;
#   transform {"$_[0]$c"} $s;
# }

def concat(S,T):
    if None in (S, T):
        return None

    s, t = head(S), head(T)
    return node("%s%s" % (s,t),
                promise(lambda: (union(postcat(tail(S), t),
                                     precat(tail(T),s),
                                     concat(tail(S),tail(T))))))

def precat(s,c):
    return transform(lambda x: "%s%s" % (c,x), s)

def postcat(s,c):
    return transform(lambda x: "%s%s" % (x,c), s)


# # Im /(a|b)(c|d)$/
# my $z = concat(union(literal("a"), literal("b")),
#                union(literal("c"), literal("d")),
#               );
# show($z);
z = (concat(union(literal("a"), literal("b")),
            union(literal("c"), literal("d")),
            ))
show(z)


# sub star {
#   my $s = shift;
#   my $r;
#   $r = node("", promise { concat($s, $r) });
# }
# def star(s):
#     _s = s[0]
#     return iterate_function(lambda x: x + _s, "")
def star(s):
    r = node("", promise(lambda: concat(s, r)))
    return r
    


# sub show {
#   my ($s, $n) = @_;
#   while ($s && (! defined $n || $n-- > 0)) {
#     print qq{"}, drop($s), qq{"\n};
#   }
#   print "\n";
# }
def show(s, n=None):
    while s and (n == None or n > 0):
        print repr(head(s))
        s = tail(s)
        if n != None:
            n -= 1
    print


# # charclass('abc') = /[abc]$/
# sub charclass {
#   my $class = shift;
#   union(map literal($_), split(//, $class));
# }
def charclass(_class):
    return union(*[literal(c) for c in _class])


# # plus($s) = /s+$/
# sub plus {
#   my $s = shift;
#   concat($s, star($s));
# }
def plus(s):
    return concat(s, star(s))

# use Regex qw(concat star literal show);
# # I represent /ab*$/
# my $regex1 = concat(     literal("a"),
#                     star(literal("b"))
#                    );
# show($regex1, 10);
regex1 = concat(  literal("a"),
                star(literal("b"))
               )
show(regex1, 10)


# # I represent /(aa|b)*$/
# my $regex2 = star(union(literal("aa"),
#                         literal("b"),
#                        ));
# show($regex2, 16);
regex2 = star(union(literal("aa"),
                        literal("b"),
                       ))
show(regex2, 16)


# # I represent /(ab+|c)*$/
# my $regex3 = star(union(concat(      literal("a"),
#                                plus(literal("b"))),
#                         literal("c")
#                        ));
# show($regex3, 20);
regex3 = star(union(concat(      literal("a"),
                            plus(literal("b"))),
                     literal("c")
                    ))
show(regex3, 20)


# sub union {
#   my (@s) = grep $_, @_;
#   return unless @s;
#   return $s[0] if @s == 1;
#   my $si = index_of_shortest(@s);
#   node(head($s[$si]),
#               promise {
#                 union(map $_ == $si ? tail($s[$_]) : $s[$_],
#                           0 .. $#s);
#               });
# }
# curse python's lame lambdas!
def union(*streams):
    streams = [_s for _s in streams if _s != None]
    if len(streams) == 0:
        return None

    if len(streams) == 1:
        return streams[0]

    si = index_of_shortest(streams)

    return node(head(streams[si]),
                promise(lambda: union(*[_s if _i != si else tail(_s) for (_i, _s) in enumerate(streams)])))


# sub index_of_shortest {
#   my @s = @_;
#   my $minlen = length(head($s[0]));
#   my $si = 0;
#   for (1 .. $#s) {
#     my $h = head($s[$_]);
#     if (length($h) < $minlen) {
#       $minlen = length($h);
#       $si = $_;
#     }
#   }
#   $si;
# }
def index_of_shortest(*streams):
    minlin = len(head(streams[0]))
    si = 0
    for i in range(1,len(streams)):
        h = head(streams[i])
        if len(h) < minlin:
            minlen = len(h)
            si = i
    return si
### ugg.  i can't seem to get correct ordering to work. :(



# sub matches {
#   my ($string, $regex) = @_;
#   while ($regex) {
#     my $s = drop($regex);
#     return 1 if $s eq $string;
#     return 0 if length($s) > length($string);
#   }
#   return 0;
# }
def matches(string, regex):
    while regex:
        s = head(regex)
        regex = tail(regex)
        if s == string:
            return True
        if len(s) > len(string):
            return False
    return False
# ugg.  this fails when star is involved


# sub bal {
#   my $contents = shift;
#   my $bal;
#   $bal = node("", promise {
#     concat($bal,
#            union($contents,
#                  transform {"($_[0])"} $bal,
#                 )
#           )
#        });
# }
def bal(contents):
    _bal = node("",
                promise(lambda: union(contents, 
                                      transform(lambda x: "(%s)" % x, _bal))))


    return _bal



# sub cut_bylen {
#   my ($a, $b) = @_;
#   # Its OK to emit item $a if the next item in the stream is $b
#   length($a) < length($b);
# }
def cut_bylen(a,b):
    return len(a) < len(b)

# sub list_to_stream {
#   my $node = pop;
#   while (@_) {
#     $node = node(pop, $node);
#   }
#   $node;
# }
def list_to_stream(nodes):
    _nodes = nodes[:]
    _node = _nodes.pop()
    while _nodes:
        _node = node(_nodes.pop(), _node)
    return _node

# sub insert (\@$$);
# sub cutsort {
#   my ($s, $cmp, $cut, @pending) = @_;
#   my @emit;
#   while ($s) {
#     while (@pending && $cut->($pending[0], head($s))) {
#       push @emit, shift @pending;
#     }
#     if (@emit) {
#       return list_to_stream(@emit,
#                             promise { cutsort($s, $cmp, $cut, @pending) });
#     } else {
#       insert(@pending, head($s), $cmp);
#       $s = tail($s);
#     }
#   }
#   return list_to_stream(@pending, undef);
# }
def cutsort(s, _cmp, cut, _pending=[]):
    pending = _pending[:]
    emit = []
    while s:
        while pending and cut(pending[0],head(s)):
            emit.append(pending.pop(0))
        if emit:
            return list_to_stream(emit,
                                  promise(lambda: cutsort(s, _cmp, cut, pending)))
        else:
            insert(pending, head(s), _cmp)
            s = tail(s)

    return list_to_stream(pending+[None])



# my $sorted =
#   cutsort($regex3,
#           sub { $_[0] cmp $_[1] }, # comparator
#           \&cut_bylen              # cutting function
#           );
sorted = cutsort(regex3,
                 lambda x,y: cmp(x,y),
                 cut_bylen,
                 )

# sub insert (\@$$) {
#   my ($a, $e, $cmp) = @_;
#   my ($lo, $hi) = (0, scalar(@$a));
#   while ($lo < $hi) {
#     my $med = int(($lo + $hi) / 2);
#     my $d = $cmp->($a->[$med], $e);
#     if ($d <= 0) {
#       $lo = $med+1;
#     } else {
#       $hi = $med;
#     }
#   }
#   splice(@$a, $lo, 0, $e);
# }
def insert(a, e, _cmp):
    lo, hi = 0, len(a)
    while lo < hi:
        med = int((lo+hi)/2)
        d = _cmp(a[med],e)
        if d <= 0:
            lo = med+1
        else:
            hi = med

    splice(a, lo, 0, e)
##
## above not tested 
##



# sub _devino {
#   my $f = shift;
#   my ($dev, $ino) = stat($f);
#   return unless defined $dev;
#   "$dev;$ino";
# }
def _devino(f):
    stat_tuple = os.state(f)
    dev, ino = stat_tuple.st_dev, stat_tuple.st_ino
    if not dev:
        return None
    return "%s;%s" % (dev, ino)


##
## ugg...  sorry got lazy again and skipped the rest of this section
##


### 6.6 The Newton-Raphson Method

# sub sqrt2 {
#   my $g = 2; # Initial guess
#   until (close_enough($g*$g, 2)) {
#     $g = ($g*$g + 2) / (2*$g);
#   }
#   $g;
# }
def sqrt2():
    g = 2
    while not close_enough(g*g, 2):
        g = float(g*g + 2) / (2*g)

    return g

# sub close_enough {
#   my ($a, $b) = @_;
#   return abs($a - $b) < 1e-12;
# }
def close_enough(a,b):
    return abs(a-b) < 1e-12


# sub sqrtn {
#   my $n = shift;
#   my $g = $n;   # Initial guess
#   until (close_enough($g*$g, $n)) {
#     $g = ($g*$g + $n) / (2*$g);
#   }
#   $g;
# }
def sqrtn(n):
    g = n
    while not close_enough(g*g, n):
        g = float(g*g + n) / (2*g)

    return g


# use Stream 'iterate_function';
# sub sqrt_stream {
#   my $n = shift;
#   iterate_function (sub { my $g = shift;
#                          ($g*$g + $n) / (2*$g);
#                         },
#                     $n);
# }
# 1;
def sqrt_stream(n):
    return iterate_function(lambda g: float(g*g + n)/(2*g),
                            n)

# sub iterate_function {
#   my ($f, $x) = @_;
#   my $s;
#   $s = node($x, promise { &transform($f, $s) });
# }
def iterate_function(f, x):
    s = node(x, promise(lambda: transform(f, s)))
    return s


# sub slope {
#   my ($f, $x) = @_;
#   my $e = 0.00000095367431640625;
#   ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# }
def slope(f, x):
    e = 0.00000095367431640625
    return (f(x+e) - f(x-e)) / (2*e)


# # Return a stream of numbers $x that make $f->($x) close to 0
# sub solve {
#   my $f = shift;
#   my $guess = shift || 1;
#   iterate_function(sub { my $g = shift;
#                          $g - $f->($g)/slope($f, $g);
#                        },
#                    $guess);
# }
def solve(f, guess=1):
    return iterate_function(lambda g: g - f(g)/slope(f,g),
                            guess)


# use Math::BigFloat;
# my $sqrt2 = solve(sub { $_[0] * $_[0] - 2 },
#                 Math::BigFloat->new(2));
# if want to use Decimal then need to retrofit a few functions:
import decimal
decimal.getcontext().prec = 64
def slope(f, x):
    x = decimal.Decimal(x)
    e = decimal.Decimal("0.00000095367431640625")
    return (f(x+e) - f(x-e)) / (2*e)
def solve(f, guess=1):
    return iterate_function(lambda g: g - f(g)/slope(f,g),
                            decimal.Decimal(guess))
sqrt2 = solve(lambda x: x*x - decimal.Decimal(2),
              decimal.Decimal(2))


# sub cut_loops {
#   my $s = shift;
#   return unless $s;
#   my @previous_values = @_;
#   for (@previous_values) {
#     if (head($s) == $_ ) {
#       return;
#     }
#   }
#   node(head($s),
#        promise { cut_loops(tail($s), head($s), @previous_values) });
# }
def cut_loops(s, *args):
    if s == None:
        return None
    previous_values = list(args)
    for v in previous_values:
        if head(s) == v:
            return None
    return node(head(s),
                promise(lambda: cut_loops(tail(s), *([head(s)] + previous_values))))



# sub cut_loops {
#   my ($tortoise, $hare) = @_;
#   return unless $tortoise;
#   # The hare and tortoise start at the same place
#   $hare = $tortoise unless defined $hare;
#   # The hare moves two steps every time the tortoise moves one
#   $hare = tail(tail($hare));
#   # If the hare and the tortoise are in the same place, cut the loop
#   return if head($tortoise) == head($hare);
#   return node(head($tortoise),
#               promise { cut_loops(tail($tortoise), $hare) });
# }
def cut_loops(tortoise, hare=None):
    if tortoise == None:
        return None
    # The hare and tortoise start at the same place
    if hare == None:
        hare = tortoise
    # The hare moves two steps every time the tortoise moves one
    hare = tail(tail(hare))
    # If the hare and the tortoise are in the same place, cut the loop
    if head(tortoise) == head(hare):
        return None
    return node(head(tortoise),
                promise(lambda: cut_loops(tail(tortoise), hare)))



# sub cut_loops2 {
#   my ($tortoise, $hare, $n) = @_;
#   return unless $tortoise;
#   $hare = $tortoise unless defined $hare;
#   $hare = tail(tail($hare));
#   return if head($tortoise) == head($hare)
#             && $n++;
#   return node(head($tortoise),
#               promise { cut_loops(tail($tortoise), $hare, $n) });
# }
def cut_loops2(tortoise, hare=None, n=0):
    if tortoise == None:
        return None
    if hare == None:
        hare = tortoise
    hare = tail(tail(hare))
    if head(tortoise) == head(hare):
        if n > 0:
            return None
        else:
            n += 1
    return node(head(tortoise),
                promise(lambda: cut_loops2(tail(tortoise), hare, n)))


# sub owed {
#   my ($P, $N, $pmt, $i) = @_;
#   my $payment_factor = 0;
#   for (0 .. $N-1) {
#     $payment_factor += (1+$i) ** $_;
#   }
#   return $P * (1+$i)**$N - $pmt * $payment_factor;
# }
def owed(P,N,pmt,i):
    payment_factor = 0
    for x in range(0,N):
        payment_factor += (1+i) ** x
    return P * (1+i)**N - pmt * payment_factor



# sub owed {
#   my ($P, $N, $pmt, $i) = @_;
#   return $P * (1+$i)**$N - $pmt * ((1+$i)**$N - 1) / $i;
# }
def owed(P,N,pmt,i):
    return P * (1+i)**N - pmt * ((1+i)**N - 1) / i


# sub owed_after_n_months {
#   my $N = shift;
#   owed(100_000, $N, 1_000, 0.005);
# }
# my $stream = cut_loops(solve(\&owed_after_n_months));
# my $n;
# $n = drop($stream) while $stream;
# print "You will be paid off in only $n months!\n";
def owed_after_n_months(N):
    return owed(100000, N, 1000, 0.005)
stream = cut_loops(solve(owed_after_n_months))
n = head(stream)
while stream:
    n = head(stream)
    stream = tail(stream)
print "You will be paid off in only %s months!" % n


# sub affordable_mortgage {
#   my $mortgage = shift;
#   owed($mortgage, 30, 15_600, 0.0675);
# }
# my $stream = cut_loops(solve(\&affordable_mortgage));
# my $n;
# $n = drop($stream) while $stream;
# print "You can afford a \$$n mortgage.\n";
def affordable_mortgage(mortgage):
    return owed(mortgage, 30, 15600, 0.0675)
stream = cut_loops(solve(affordable_mortgage))
n = head(stream)
while stream:
    n = head(stream)
    stream = tail(stream)
print "You can afford a $%s mortgage." % n


### 6.7 Power Series

# # Approximate sin(x) using the first n terms of the power series
# sub approx_sin {
#   my $n = shift;
#   my $x = shift;
#   my ($denom, $c, $num, $total) = (1, 1, $x, 0);
#   while ($n--) {
#     $total += $num / $denom;
#     $num *= $x*$x * -1;
#     $denom *= ($c+1) * ($c+2);
#     $c += 2;
#   }
#   $total;
# }
# 1;
def approx_sin(n, x):
    denom, c, num, total = 1,1,x,0
    while n:
        n -= 1
        total += num / float(denom)
        num *= x*x * - 1
        denom *= (c+1) * (c+2)
        c += 2
    return total



# package PowSeries;
# use base 'Exporter';
# @EXPORT_OK = qw(add2 mul2 partial_sums powers_of term_values
#                 evaluate derivative multiply recip divide
#                 $sin $cos $exp $log_ $tan);
# use Stream ':all';
# sub tabulate {
#   my $f = shift;
#   &transform($f, upfrom(0));
# }
def tabulate(f):
    return transform(f, upfrom(0))



# my @fact = (1);
# sub factorial {
#   my $n = shift;
#   return $fact[$n] if defined $fact[$n];
#   $fact[$n] = $n * factorial($n-1);
# }

# $sin = tabulate(sub { my $N = shift;
#                       return 0 if $N % 2 == 0;
#                       my $sign = int($N/2) % 2 ? -1 : 1;
#                       $sign/factorial($N)
#                     });

# $cos = tabulate(sub { my $N = shift;
#                       return 0 if $N % 2 != 0;
#    my $sign = int($N/2) % 2 ? -1 : 1;
#    $sign/factorial($N)
# });
fact = {0:1}
def factorial(n):
    if fact.get(n):
        return fact[n]
    fact[n] = n * factorial(n-1)
    return fact[n]

def sin_lambda(N):
    if N % 2 == 0:
        return 0
    sign = 1
    if (N/2) % 2 != 0:
        -1
    return sign / float(factorial(N))
sin = tabulate(sin_lambda)

def cos_lambda(N):
    if N % 2 != 0:
        return 0
    sign = 1
    if (N/2) % 2 != 0:
        -1
    return sign / float(factorial(N))
cos = tabulate(cos_lambda)




# sub add2 {
#   my ($s, $t) = @_;
#   return $s unless $t;
#   return $t unless $s;
#   node(head($s) + head($t),
#        promise { add2(tail($s), tail($t)) });
# }
def add2(s,t):
    if not t:
        return s
    if not s:
        return t
    return node(head(s) + head(t),
                promise(lambda: add2(tail(s),tail(t))))

# sub mul2 {
#   my ($s, $t) = @_;
#   return unless $s && $t;
#   node(head($s) * head($t),
#        promise { mul2(tail($s), tail($t)) });
# }
def mul2(s,t):
    if not (s and t):
        return None
    return node(head(s)*head(t),
                promise(lambda: mul2(tail(s),tail(t))))


# sub partial_sums {
#   my $s = shift;
#   my $r;
#   $r = node(head($s), promise { add2($r, tail($s)) });
# }
def partial_sums(s):
    r = node(head(s), promise(lambda: add2(r, tail(s))))
    return r


# sub powers_of {
#   my $x = shift;
#   iterate_function(sub {$_[0] * $x}, 1);
# }
def powers_of(x):
    return iterate_function(lambda i: i*x, 1)


# sub term_values {
#   my ($s, $x) = @_;
#   mul2($s, powers_of($x));
# }
def term_values(s,x):
    return mul2(s, powers_of(x))


# sub evaluate {
#   my ($s, $x) = @_;
#   partial_sums(term_values($s, $x));
# }
def evaluate(s,x):
    return partial_sums(term_values(s,x))


# my $pi = 3.1415926535897932;
# show(evaluate($cos, $pi/6), 20);
pi = 3.1415926535897932
show(evaluate(cos, pi/6.0), 20)


### grrr.....  each of the pieces i test
### above seems to be behaving correctly
### but for some reason the cos(pi/6) example
### is not coming out correctly.  no idea :(


# # Get the n'th term from a stream
# sub nth {
#   my $s = shift;
#   my $n = shift;
#   return $n == 0 ? head($s) : nth(tail($s), $n-1);
# }
# # Calculate the approximate cosine of x
# sub cosine {
#   my $x = shift;
#   nth(evaluate($cos, $x), 20);
# }
def nth(s,n):
    if n == 0:
        return head(s)
    else:
        return nth(tail(s), n-1)

def cosine(x):
    return nth(evaluate(cos, x), 20)


# sub is_zero_when_x_is_pi {
#   my $x = shift;
#   my $c = cosine($x/6);
#   $c * $c - 3/4;
# }
# show(solve(\&is_zero_when_x_is_pi), 20);
def is_zero_when_x_is_pi(x):
    c = cosine(x/6.0)
    return c * c - 3/4.0

show(solve(is_zero_when_x_is_pi), 20)

# sub derivative {
#   my $s = shift;
#   mul2(upfrom(1), tail($s));
# }
def derivative(s):
    return mul2(upfrom(1), tail(s))


# show(derivative($sin), 20);
show(derivative(sin), 20)


# exp = tabulate(sub { my $N = shift; 1/factorial($N) });
exp = tabulate(lambda N: 1.0/factorial(N))

# $log_ = tabulate(sub { my $N = shift;
#                        $N==0 ? 0 : (-1)**$N/-$N });
log_ = tabulate(lambda N: N!=0 and (-1)**N/-N or 0)



# sub multiply {
#   my ($S, $T) = @_;
#   my ($s, $t) = (head($S), head($T));
#   node($s*$t,
#        promise { add2(scale(tail($T), $s),
#                  add2(scale(tail($S), $t),
#                       node(0,
#                        promise {multiply(tail($S), tail($T))}),
#                      ))
#                }
#        );
# }
def multiply(S,T):
    s, t = head(S), head(T)
    return node(s*t,
                promise(add2(scale(tail(T),s),
                             add2(scale(tail(S),t),
                                  node(0,
                                       promise(multiply(tail(S), tail(T))))))))


# sub scale {
#   my ($s, $c) = @_;
#   return    if $c == 0;
#   return $s if $c == 1;
#   transform { $_[0]*$c } $s;
# }
def scale(s, c):
    if c == 0:
        return None
    if c == 1:
        return s
    return transform(lambda i: i*c, s)


# my $one = add2(multiply($cos, $cos), multiply($sin, $sin));
# show($one, 20);
one = add2(multiply(cos, cos), multiply(sin, sin))
show(one, 20)
### unfortunately i get:
### OverflowError: long int too large to convert to float
### perhaps come back later and figure this out

# sub sum {
#   my @s = grep $_, @_;
#   my $total = 0;
#   $total += head($_ ) for @s;
#   node($total,
#        promise { sum(map tail($_ ), @s) }
#       );
# }
def sum_(_s):
    s = [s_ for s_ in _s if s_]
    total = 0
    for x in s:
        total += head(x)
    return node(total, promise(lambda: sum_([tail(x) for x in s])))


# sub multiply {
#   my ($S, $T) = @_;
#   my ($s, $t) = (head($S), head($T));
#   node($s*$t,
#   promise { sum(scale(tail($T), $s),
#                 scale(tail($S), $t),
#                 node(0,
#                   promise {multiply(tail($S), tail($T))}),
#                )
#           }
#   );
# }
def multiply(S,T):
    s,t = head(S), head(T)
    return node(s*t,
                promise(lambda: sum_(scale(tail(T),s), scale(tail(S),t), node(0, promise(lambda: multiply(tail(S), tail(T)))))))


# # Works only if head($s) = 1
# sub recip {
#   my ($s) = shift;
#   my $r;
#   $r = node(1,
#             promise { scale(multiply($r, tail($s)), -1) });
# }
 def recip(s):
    r = node(1,
             promise(lambda: scale(multiply(r,tail(s)), -1)))
    return r


# # Works only if head($t) = 1
# sub divide {
#   my ($s, $t) = @_;
#   multiply($s, recip($t));
# }
# $tan = divide($sin, $cos);
# show($tan, 10);
def divide(s,t):
    return multiply(s, recip(t))
tan = divide(sin, cos)
show(tan, 10)


# my @fact = (Math::BigRat->new(1));
# sub factorial {
#   my $n = shift;
#   return $fact[$n] if defined $fact[$n];
#   $fact[$n] = $n * factorial($n-1);
# }
# python 2.6 has "fractions" library
fact = [fraction.Fraction(1,1)]
def factorial(n):
    if fact.get(n):
        return fact[n]
    fact[n] = n * factorial(n-1)
    return fact[n]

99 problems - python - 58

2009-03-22T15:38:00.000-07:00

Generate-and-test paradigm

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.


# Example:

# * sym-cbal-trees(5,Ts).
# Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))] 
def symmetric_completely_balanced_trees(node_count):
    return [tree for tree in completely_balanced_tree(node_count) \
                if symmetric_binary_tree(tree)]

100 Pushups: "week 6" milestone - 70

2009-03-19T21:20:00.000-07:00

Holy crap. I finally got to 70. So the adventure continues on the hilariously optimistic "6 week" program to do 100 pushups.

The big question now is whether I can get to 100 before a year has elapsed. I think there is a chance. But honestly I'll just be happy to get there. And to think I was going to skip tonight since I felt a little under the weather.

Higher Order Perl (Python Style) : Chapter 5 - From Recursion To Iterators

2009-03-09T19:19:00.000-07:00

TOC


### Chapter 5 - From Recursion To Iterators

### 5.1 The Partition Problem Revisited

# sub find_share {
#   my ($target, $treasures) = @_;
#   return [] if $target == 0;
#   return    if $target < 0 || @$treasures == 0;
#   my ($first, @rest) = @$treasures;
#   my $solution = find_share($target-$first, \@rest);
#   return [$first, @$solution] if $solution;
#   return         find_share($target       , \@rest);
# }
def find_share(target, treasures):
    if target == 0:
        return []
    if target < 0 or len(treasures) == 0:
        return
    first, rest = treasures[0], treasures[1:]
    solution = find_share(target-first, rest)
    if solution != None:
        return [first] + solution
    return find_share(target, rest)


# sub partition {
#   my ($target, $treasures) = @_;
#   return [] if $target == 0;
#   return () if $target < 0 || @$treasures == 0;
#   my ($first, @rest) = @$treasures;
#   my @solutions = partition($target-$first, \@rest);
#   return ((map {[$first, @$_]} @solutions),
#          partition($target, \@rest));
# }
def partition(target, treasures):
    if target == 0:
        return [[]]
    if target < 0 or len(treasures) == 0:
        return []
    first, rest = treasures[0], treasures[1:]
    solutions = partition(target-first, rest)

    return [[first] + solution for solution in solutions] + partition(target, rest)


# sub make_partitioner {
#   my ($n, $treasures) = @_;
#   my @todo = [$n, $treasures, []];
#   sub {
#     while (@todo) {
#       my $cur = pop @todo;
#       my ($target, $pool, $share) = @$cur;
#       if ($target == 0) { return $share }

#       next if $target < 0 || @$pool == 0;

#       my ($first, @rest) = @$pool;
#       push @todo, [$target-$first, \@rest, [@$share, $first]],
#                   [$target       , \@rest,   $share         ];
#     }
#     return undef;
#   } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
    todo = [[n, treasures, []]]

    while todo:
        target, pool, share = todo.pop()
        if target == 0:
            yield share
            continue

        if target < 0 or len(pool) == 0:
            continue

        first, rest = pool[0], pool[1:]
        todo.append([target-first, rest, share+[first]])
        todo.append([target,       rest, share])


# sub make_partitioner {
#   my ($n, $treasures) = @_;
#   my @todo = [$n, $treasures, []];
#   sub {
#     while (@todo) {
#       my $cur = pop @todo;
#       my ($target, $pool, $share) = @$cur;
#       if ($target == 0) { return $share }
#       next if $target < 0 || @$pool == 0;
#       my ($first, @rest) = @$pool;
#       push @todo, [$target, \@rest, $share ] if @rest;
#       if ($target == $first) {
#          return [@$share, $first];
#       } elsif ($target > $first && @rest) {
#          push @todo, [$target-$first, \@rest, [@$share, $first]],
#       }
#     }
#     return undef;
#   } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
    todo = [[n, treasures, []]]

    while todo:
        target, pool, share = todo.pop()
        if target == 0:
            yield share
            continue

        if target < 0 or len(pool) == 0:
            continue

        first, rest = pool[0], pool[1:]
        if rest:
            todo.append([target, rest, share])
        if target == first:
            yield share+[first]
        elif (target > first and rest):
            todo.append([target-first, rest, share+[first]])


### 5.2 How to Convert a Recursive Function to an Iterator

# sub rec {
#   my ($n, $k) = @_;
#   print $k x $n, "\n";
#   for (1 .. $n-1) {
#     rec($n-$_, $_);
#   }
# }
def rec(n, k):
    print str(k) * n
    for i in range(1,n):
        rec(n-i, i)


# sub partition {
#   print "@_\n";
#   my ($n, @parts) = @_;
#   for (1 .. $n-1) {
#     partition($n-$_, $_, @parts);
#   }
# }
def partition(n, parts):
    print [n] +parts
    for i in range(1,n):
        partition(n-i, [i]+parts)

# for (@words) { $seen{$_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
    seen.setdefault(word,[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]



# for (@words) { $seen{lc $_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
    seen.setdefault(word.lower(),[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]


# sub partition {
#   print "@_\n" if decreasing_order(@_);
#   my ($n, @parts) = @_;
#   for (1 .. $n-1) {
#     partition($n-$_, $_, @parts);
#   }
# }
def partition(n, parts):
    if decreasing_order([n] +parts):
        print [n] + parts
    for i in range(1,n):
        partition(n-i, [i]+parts)


# sub partition {
#   print "@_\n";
#   my ($largest, @rest) = @_;
#   my $min = $rest[0] || 1;
#   my $max = int($largest/2);
#   for ($min .. $max) {
#     partition($largest-$_, $_, @rest);
#   }
# }
def partition(largest, rest):
    print [largest] + rest
    min = (rest + [1])[0]
    max = largest / 2
    for i in range(min, max+1):
        partition(largest-i, [i]+rest)


# sub make_partition {  
#   my $n = shift;
#   my @agenda = ([$n,            # $largest
#                  [],            # \@rest
#                  1,             # $min
#                  int($n/2),     # $max
#                 ]);
#   return Iterator {
#     while (@agenda) {
#       my $item = pop @agenda;
#       my ($largest, $rest, $min, $max) = @$item;
#       for ($min .. $max) {
#         push @agenda, [$largest - $_,          # $largest
#                        [$_, @$rest],           # \@rest
#                        $_,                     # $min
#                        int(($largest - $_)/2), # $max
#                       ];
#       }
#       return [$largest, @$rest];
#     }
#     return;
#   };
# }
def make_partition(n):
    agenda = [(n,   # largest
               [],  # rest
               1,   # min
               n/2) # max
              ]

    while agenda:
        (largest, rest, min, max) = agenda.pop()
        for i in range(min, max+1):
            agenda.append((largest - i,    # largest
                           [i]+rest,       # rest
                           i,              # min
                           (largest-i)/2   # max
                           ))
        yield [largest]+rest


# sub partition {
#   my ($largest, $rest, $min, $max) = @_;
#   for ($min .. $max) {
#     partition($largest-$_, [$_, @$rest], $_, int(($largest - $_)/2));
#   }
#   return [$largest, @$rest];
# }
def partition(largest, rest, min, max):
    for i in range(min, max+1):
        partition(largest-i, [i]+rest, i, (largest-i)/2)
    return [largest] + rest



# sub make_partition {
#   my $n = shift;
#   my @agenda = [$n];
#   return Iterator {
#     while (@agenda) {
#       my $item = pop @agenda;
#       my ($largest, @rest) = @$item;
#       my $min = $rest[0] || 1;
#       my $max  = int($largest/2);
#       for ($min .. $max) {
#         push @agenda, [$largest-$_, $_, @rest];
#       }
#       return $item;
#     }
#     return;
#   };
# }
def make_partition(n):
    agenda = [[n,[]]]
    while agenda:
        largest, rest = agenda.pop()
        min = (rest + [1])[0]
        max = largest / 2
        for i in range(min, max+1):
            agenda.append([largest-i, [i]+rest])
        yield [largest] + rest


# sub make_partition {
#   my $n = shift;
#   my @agenda = [$n];
#   return Iterator {
#     return unless @agenda;
#     my $item = pop @agenda;
#     my ($largest, @rest) = @$item;
#     my $min = $rest[0] || 1;
#     my $max  = int($largest/2);
#     for ($min .. $max) {
#       push @agenda, [$largest-$_, $_, @rest];
#     }
#     return $item;
#   };
# }
### we *do* keep the while loop in the python version
### and it looks just like the previous solution


# # Compare two partitions for preferred order
# sub partitions {
#   for my $i (0 .. $#$a) {
#     my $cmp = $b->[$i] <=> $a->[$i];
#     return $cmp if $cmp;
#   }
# }
# lists and tuples will compare naturally 
# in the correct way (unless i'm missing something here)
def partitions(a,b):
    return cmp(a,b)


# sub make_partition {
#   my $n = shift;
#   my @agenda = [$n];
#   return Iterator {
#     return unless @agenda;
#     my $item = pop @agenda;
#     my ($largest, @rest) = @$item;
#     my $min = $rest[0] || 1;
#     my $max  = int($largest/2);
#     for ($min .. $max) {
#       push @agenda, [$largest-$_, $_, @rest];
#     }
#     @agenda = sort partitions @agenda;
#     return $item;
#   };
# }
def make_partition(n):
    agenda = [[n,[]]]
    while agenda:
        largest, rest = agenda.pop()
        min = (rest + [1])[0]
        max = largest / 2
        for i in range(min, max+1):
            agenda.append([largest-i, [i]+rest])
        agenda.sort()
        yield [largest] + rest


### 5.3 A Generic Search Iterator

# use Iterator_Utils 'Iterator';
# sub make_dfs_search {
#   my ($root, $children) = @_;
#   my @agenda = $root;
#   return Iterator {
#     return unless @agenda;
#     my $node = pop @agenda;
#     push @agenda, $children->($node);
#     return $node;
#   };
# }
def make_dfs_search(root, children):
    agenda = [root]
    
    while agenda:
        node = agenda.pop()
        agenda.extend(children(node))
        yield node


# sub make_partition {
#   my $n = shift;
#   my $root = [$n];
#   my $children = sub {
#     my ($largest, @rest) = @{shift()};
#     my $min = $rest[0] || 1;
#     my $max  = int($largest/2);
#     map [$largest-$_, $_, @rest], ($min .. $max);
#   };
#   make_dfs_search($root, $children);
# }
def make_partition(n):
    root = [n]
    def children(largest, rest):
        min = (rest + [1])[0]
        max = largest / 2
        return [(largest-i, [i]+rest) for i in range(min, max+1)]

    return make_dfs_search(root, children)


# sub make_dfs_search {
#    my ($root, $children, $is_interesting) = @_;
#    my @agenda = $root;
#    return Iterator {
#      while (@agenda) {
#        my $node = pop @agenda;
#        push @agenda, $children->($node);
#        return $node if !$is_interesting || $is_interesting->($node);
#      }
#      return;
#   };
# }
def make_dfs_search(root, children, is_interesting=None):
    agenda = [root]
    
    while agenda:
        node = agenda.pop()
        agenda.extend(children(node))
        if is_interesting and is_interesting(node):
            yield node


# sub make_dfs_value_search {
#   my ($root, $children, $is_interesting, $evaluate) = @_;
#   $evaluate = memoize($evaluate);
#   my @agenda = $root;
#   return Iterator {
#      while (@agenda) {
#        my $best_node_so_far = 0;
#        my $best_node_value = $evaluate->($agenda[0]);
#        for (0 .. $#agenda) {
#          my $val = $evaluate->($agenda[$_]);
#          next unless $val > $best_node_value;
#          $best_node_value = $val;
#          $best_node_so_far = $_;
#       }
#       my $node = splice @agenda, $best_node_so_far, 1;
#       push @agenda, $children->($node);
#       return $node if !$is_interesting || $is_interesting->($node);
#     }
#     return;
#   };
# }
def make_dfs_value_search(root, children, is_interesting=None, evaluate=None):
    if not is_interesting:
        is_interesting = (lambda x: True)

    if not evaluate:
        evaluate = (lambda x: x)

    agenda = [root]
    
    while agenda:
        node = agenda.pop()
        agenda.extend(children(node))
        if is_interesting(node):
            yield node


# sub make_dfs_search {
#   my ($root, $children, $is_interesting) = @_;
#   my @agenda = $root;
#   return Iterator {
#     while (@agenda) {
#       my $node = pop @agenda;
#       push @agenda, reverse $children->($node);
#       return $node if !$is_interesting || $is_interesting->($node);
#     }
#     return;
#   };
# }
def make_dfs_search(root, children, is_interesting=None):
    agenda = [root]
    
    while agenda:
        node = agenda.pop()
        agenda.extend(reversed(children(node)))
        if is_interesting and is_interesting(node):
            yield node


### 5.4 Other General Techniques for Eliminating Recursion

# sub gcd {
#   my ($m, $n) = @_;
#   if ($n == 0) {
#     return $m;
#   }
#   return gcd($n, $m % $n);
# }
def gcd(m,n):
    if n == 0:
        return m
    return gcd(n, m % n)


# sub gcd {
#   my ($m, $n) = @_;
#   until ($n == 0) {
#     ($m, $n) = ($n, $m % $n);
#   }
#   return $m;
# }
def gcd(m,n):
    while n != 0:
        m, n = n, m % n
    return m


# sub print_tree {
#   my $t = shift;
#   return unless $t;  # Null tree
#   print_tree($t->left);
#   print $t->root, "\n";
#   print_tree($t->right);
# }
def print_tree(t):
    if not t:
        return
    print_tree(t.left)
    print t.root
    print_tree(t.right)


# sub print_tree {
#   my $t = shift;
#   while ($t) {
#     print_tree($t->left);
#     print $t->root, "\n";
#     $t = $t->right;
#   }
# }
def print_tree(t):
    while t:
        print_tree(t.left)
        print t.root
        t = t.right


# sub print_tree {
#   my $t = shift;
#   print_tree($t->left) if $t->left;
#   print $t->root, "\n";
#   print_tree($t->right) if $t->right;
# }
def print_tree(t):
    if t.left:
        print_tree(t.left)
    print t.root
    if t.right:
        print_tree(t.right)


# sub print_tree {
#   my $t = shift;
#   do {
#     print_tree($t->left) if $t->left;
#     print $t->root, "\n";
#     $t = $t->right;
#   } while $t;
# }
def print_tree(t):
    while t:
        if t.left:
            print_tree(t.left)
        print t.root
        t = t.right
    


# sub powerset_recurse ($;@) {
#     my ( $set, $powerset, $keys, $values, $n, $i ) = @_;
#     if ( @_ == 1 ) { # Initialize.
#         my $null   = { };
#         $powerset  = { $null, $null };
#         $keys      = [ keys    %{ $set } ];
#         $values    = [ values %{ $set } ];
#         $nmembers  = keys %{ $set };    # This many rounds.
#         $i         = 0;                  # The current round.
#     }
#     # Ready?
#     return $powerset if $i == $nmembers;
#     # Remap.
#     my @powerkeys    = keys   %{ $powerset };
#     my @powervalues = values %{ $powerset };
#     my $powern      = @powerkeys;
#     my $j;
#     for ( $j = 0; $j < $powern; $j++ ) {
#         my %subset = ( );
#         # Copy the old set to the subset.
#         @subset{keys    %{ $powerset->{ $powerkeys  [ $j ] } }} =
#                 values %{ $powerset->{ $powervalues[ $j ] } };
#         # Add the new member to the subset.
#         $subset{$keys->[ $i ]} = $values->[ $i ];
#         # Add the new subset to the powerset.
#         $powerset->{ \%subset } = \%subset;
#     }
#     # Recurse.
#   powerset_recurse( $set, $powerset, $keys, $values, $nmembers, $i+1 );
# }
# we are stuck since python won't permit keys that aren't hashable
# so instead of dicts of dicts i'll use set() with tuples.
# we can easily go back to dicts from a set of tuples 
# but i may be missing some subtly important feature of this
# algorithm.  but in any case it works.
# also: this algorithm *seems* ridiculously unpythonic
# _set: [(key,val)] # list of 
# powerset: [set([(key, val)])] # list of sets of tuple
def powerset_recurse(_set, powerset=None, i=0):
    # set up init stuff
    if powerset == None:
        powerset = [set()]

    if i == len(_set):
        return powerset

    powerset_copy = copy.deepcopy(powerset)
    ith_item = _set[i]
    for subset in powerset_copy:
       subset.add(ith_item)

    powerset += powerset_copy

    return powerset_recurse(_set, powerset, i+1)
### uggg.  so that works, and *seems* very close
### in principle to the original but I feel like
### i didn't try hard enough to match the original style


# sub powerset_recurse ($) {
#   my ( $set ) = @_;
#   my $null = { };
#   my $powerset  = { $null, $null };
#   my $keys      = [ keys    %{ $set } ];
#   my $values    = [ values %{ $set } ];
#   my $nmembers  = keys %{ $set };     # This many rounds.
#   my $i         = 0;                  # The current round.
#   until ($i == $nmembers) {
#     # Remap.
#     my @powerkeys    = keys   %{ $powerset };
#     my @powervalues = values %{ $powerset };
#     my $powern       = @powerkeys;
#     my $j;
#     for ( $j = 0; $j < $powern; $j++ ) {
#         my %subset = ( );
#         # Copy the old set to the subset.
#         @subset{keys    %{ $powerset->{ $powerkeys  [ $j ] } }} =
#                 values %{ $powerset->{ $powervalues[ $j ] } };
#         # Add the new member to the subset.
#         $subset{$keys->[ $i ]} = $values->[ $i ];
#         # Add the new subset to the powerset.
#         $powerset->{ \%subset } = \%subset;
#     }
#      $i++;
#   }
#   return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
    # set up init stuff
    if powerset == None:
        powerset = [set()]
    
    while i < len(_set):
        powerset_copy = copy.deepcopy(powerset)
        ith_item = _set[i]
        for subset in powerset_copy:
           subset.add(ith_item)

        powerset += powerset_copy

        i += 1

    return powerset



# sub powerset_recurse ($) {
#     my ( $set ) = @_;
#     my $null = { };
#     my $powerset  = { $null, $null };
#     my $keys      = [ keys    %{ $set } ];
#     my $values    = [ values %{ $set } ];
#     my $nmembers  = keys %{ $set };     # This many rounds.
#     for my $i (0 .. $nmembers-1) {
#       #  Remap.
#       my @powerkeys    = keys   %{ $powerset };
#       my @powervalues = values %{ $powerset };
#       my $powern      = @powerkeys;
#       my $j;
#       for ( $j = 0; $j < $powern; $j++ ) {
#           my %subset = ( );
#           # Copy the old set to the subset.
#           @subset{keys    %{ $powerset->{ $powerkeys  [ $j ] } }} =
#                   values %{ $powerset->{ $powervalues[ $j ] } };
#           # Add the new member to the subset.
#           $subset{$keys->[ $i ]} = $values->[ $i ];
#           # Add the new subset to the powerset.
#           $powerset->{ \%subset } = \%subset;
#       }
#     }
#     return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
    # set up init stuff
    if powerset == None:
        powerset = [set()]
    
    for i in range(len(_set)):
        powerset_copy = copy.deepcopy(powerset)
        ith_item = _set[i]
        for subset in powerset_copy:
           subset.add(ith_item)

        powerset += powerset_copy

    return powerset


# sub powerset_recurse ($) {
#     my ( $set ) = @_;
#     my $null = { };
#     my $powerset  = { $null, $null };
#     while (my ($key, $value) = each %$set) {
#       # Remap.
#       my @powerkeys    = keys   %{ $powerset };
#       my @powervalues = values %{ $powerset };
#       my $powern      = @powerkeys;
#       my $j;
#       for ( $j = 0; $j < $powern; $j++ ) {
#           my %subset = ( );
#           # Copy the old set to the subset.
#           @subset{keys    %{ $powerset->{ $powerkeys [ $j ] } }} =
#                   values %{ $powerset->{ $powervalues[ $j ] } };
#           # Add the new member to the subset.
#           $subset{$key} = $value;
#           # Add the new subset to the powerset.
#           $powerset->{ \%subset } = \%subset;
#       }
#     }
#     return $powerset;
# }
def powerset_recurse(_set):
    powerset = [set()]
    
    for ith_item in (_set):
        powerset_copy = copy.deepcopy(powerset)
        for subset in powerset_copy:
           subset.add(ith_item)

        powerset += powerset_copy

    return powerset


# sub binary {
#   my ($n) = @_;
#   return $n if $n == 0 || $n == 1;
#   my $k = int($n/2);
#   my $b = $n % 2;
#   my $E = binary($k);
#   return $E . $b;
# }
def binary(n):
    if n in (0,1):
        return str(n)

    k = n / 2
    b = n % 2

    return binary(k) + str(b)


# sub binary {
#   my ($n, $RETVAL) = @_;
#   $RETVAL = "" unless defined $RETVAL;
#   my $k = int($n/2);
#   my $b = $n % 2;
#   $RETVAL = "$b$RETVAL";
#   return $RETVAL if $n == 0 || $n == 1;
#   binary($k, $RETVAL);
# }
def binary(n, retval=""):
    k = n / 2
    b = n % 2

    retval = str(b)+retval
    if n in (0,1):
        return retval

    return binary(k, retval)


# sub binary {
#    my ($n, $RETVAL) = @_;
#    $RETVAL = "";
#    while (1) {
#      my $k = int($n/2);
#      my $b = $n % 2;
#      $RETVAL = "$b$RETVAL";
#      return $RETVAL if $n == 0 || $n == 1;
#     $n = $k;
#   }
# }
def binary(n, retval=""):
    while 1:
        k = n / 2
        b = n % 2
        retval = str(b)+retval
        if n in (0,1):
            return retval
        n = k

# sub binary {
#   my ($n, $RETVAL) = @_;
#   $RETVAL = "";
#   while (1) {
#     my $b = $n % 2;
#     $RETVAL = "$b$RETVAL";
#     return $RETVAL if $n == 0 || $n == 1;
#     $n = int($n/2);
#   }
# }
def binary(n, retval=""):
    while 1:
        b = n % 2
        retval = str(b)+retval
        if n in (0,1):
            return retval
        n = n/2



# sub factorial {
#   my ($n) = @_;
#   return 1 if $n == 0;
#   return factorial($n-1) * $n;
# }
def factorial(n):
    if n == 0:
        return 1
    return factorial(n-1)*n


# sub factorial {
#   my ($n, $product) = @_;
#   $product = 1 unless defined $product;
#   return $product if $n == 0;
#   return factorial($n-1, $n * $product);
# }
def factorial(n, product=1):
    if n == 0:
        return product
    return factorial(n-1, n*product)


# sub factorial {
#   my ($n) = @_;
#   my $product = 1;
#   until ($n == 0) {
#     $product *= $n;
#     $n--;
#   }
#   return $product;
# }
def factorial(n):
    product = 1
    while n != 0:
        product *= n
        n -= 1
    return product


# sub print_tree {
#   my $t = shift;
#   do {
#     print_tree($t->left) if $t->left;
#     print $t->root, "\n";
#     $t = $t->right;
#   } while $t;
# }
def print_tree(t):
    while t:
        if t.left:
            print_tree(t.left)
        print t.root
        t = t.right


# sub print_tree {
#   my $t = shift;
#   my @STACK;
#   do {
#     push(@STACK, $t), $t = $t->left if $t->left;
#     RETURN:
#        print $t->root, "\n";
#     $t = $t->right;
#   } while $t;
#   return unless @STACK;
#   $t = pop @STACK;
#   goto RETURN;
# }
### this and the next couple examples
### use GOTOs.  not much i can do about that.
### if there is a way to simulate gotos in python
### i'd be interested to hear it.


# sub fib {
#   my $n = shift;
#   if ($n < 2) { return $n }
#   fib($n-2) + fib($n-1);
# }
def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)


# sub fib {
#   my $n = shift;
#   if ($n < 2) {
#     return $n;
#   } else {
#     my $s1 = fib($n-2);
#     my $s2 = fib($n-1);
#     return $s1 + $s2;
#   }
# }
def fib(n):
    if n < 2:
        return n
    else:
        s1 = fib(n-2)
        s2 = fib(n-1)
        return s1 + s2


# sub fib {
#   my $n = shift;
#   while (1) {
#     if ($n < 2) {
#       return $n;
#     } else {
#       my $s1 = fib($n-2);
#       my $s2 = fib($n-1);
#       return $s1 + $s2;
#     }
#   }
# }
def fib(n):
    while 1:
        if n < 2:
            return n
        else:
            s1 = fib(n-2)
            s2 = fib(n-1)
            return s1 + s2


# sub fib { 
#   my $n = shift;
#   my ($s1, $s2, $return);
#   while (1) {
#     if ($n < 2) {
#       return $n;
#     } else {
#       if ($BRANCH == 0) {
#         $return = fib($n-2);
#       } elsif ($BRANCH == 1) {
#         $s1 = $return;
#         $return = fib($n-1);
#       } elsif ($BRANCH == 2) {
#         $s2 = $return;
#         $return = $s1 + $s2;
#       }
#     }
#   }
# }
def fib(n):
    BRANCH = 0
    while 1:
        if n < 2:
            return n
        else:
            if BRANCH == 0:
                _return = fib(n-2)
            elif BRANCH == 1:
                s1 = _return
                _retrun = fib(n-2)
            elif BRANCH == 2:
                s2 = _return
                _return = s1 + s2
    return _return


# sub fib {
#   my $n = shift;
#   my ($s1, $s2, $return);
#   my $BRANCH = 0;
#   while (1) {
#     if ($n < 2) {
#       return $n;
#     } else {
#       if ($BRANCH == 0) {
#          $return = fib($n-2);
#       } elsif ($BRANCH == 1) {
#          $s1 = $return;
#          $return = fib($n-1);
#       } elsif ($BRANCH == 2) {
#          $s2 = $return;
#          $return = $s1 + $s2;
#       }
#     }
#   }
# }
def fib(n):
    BRANCH = 0
    while 1:
        if n < 2:
            return n
        else:
            if BRANCH == 0:
                _return = fib(n-2)
            elif BRANCH == 1:
                s1 = _return
                _return = fib(n-1)
            elif BRANCH == 2:
                s2 = _return
                _return = s1 + s2
    return _return


# sub fib {
#   my $n = shift;
#   my ($s1, $s2, $return);
#   my $BRANCH = 0;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         $return = fib($n-2);
#       } elsif ($BRANCH == 1) {
#         $s1 = $return;
#         $return = fib($n-1);
#       } elsif ($BRANCH == 2) {
#         $return = $s1 + $s2;
#       }
#     }
#   }
# }
def fib(n):
    BRANCH = 0
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                _return = fib(n-2)
            elif BRANCH == 1:
                s1 = _return
                _return = fib(n-1)
            elif BRANCH == 2:
                _return = s1 + s2
    return _return


# sub fib {
#   my $n = shift;
#   my ($s1, $s2, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         push @STACK, [ $BRANCH, $s1, $s2, $n ];
#         $n -= 2;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 1) {
#         $s1 = $return;
#         push @STACK, [ $BRANCH, $s1, $s2, $n ];
#         $n -= 1;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 2) {
#         $s2 = $return;
#         $return = $s1 + $s2;
#       }
#     }
#   }
# }
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                STACK.append([BRANCH, s1, s2, n])
                n -= 2
                BRANCH = 0
                continue
            elif BRANCH == 1:
                s1 = _return
                STACK.append([BRANCH, s1, s2, n])
                n -= 1
                BRANCH = 0
                continue
            elif BRANCH == 2:
                s2 = _return
                _return = s1 + s2
    return _return


# sub fib {
#   my $n = shift;
#   my ($s1, $s2, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         push @STACK, [ $BRANCH, $s1, $s2, $n ];
#         $n -= 2;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 1) {
#         $s1 = $return;
#         push @STACK, [ $BRANCH, $s1, $s2, $n ];
#         $n -= 1;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 2) {
#         $s2 = $return;
#         $return = $s1 + $s2;
#     }
#   }
#   return $return unless @STACK;
#   ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
#   $BRANCH++;
# }
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                STACK.append([BRANCH, s1, s2, n])
                n -= 2
                BRANCH = 0
                continue
            elif BRANCH == 1:
                s1 = _return
                STACK.append([BRANCH, s1, s2, n])
                n -= 1
                BRANCH = 0
                continue
            elif BRANCH == 2:
                s2 = _return
                _return = s1 + s2
    if not STACK:
        return _return
    (BRANCH, s1, s2, n) = STACK.pop()
    BRANCH += 1


# sub fib {
#   my $n = shift;
#   my ($s1, $s2, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         push @STACK, [ $BRANCH, 0, $s2, $n ];
#         $n -= 2;
#         next;
#       } elsif ($BRANCH == 1) {
#         push @STACK, [ $BRANCH, $return, $s2, $n ];
#         $n -= 1;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 2) {
#         $s2 = $return;
#       $return = $s1 + $s2;
#     }
#   }
#   return $return unless @STACK;
#   ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
#   $BRANCH++;
# }
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                STACK.append([BRANCH, 0, s2, n])
                n -= 2
                BRANCH = 0
                continue
            elif BRANCH == 1:
                s1 = _return
                STACK.append([BRANCH, _return, s2, n])
                n -= 1
                BRANCH = 0
                continue
            elif BRANCH == 2:
                s2 = _return
                _return = s1 + s2
    if not STACK:
        return _return
    (BRANCH, s1, s2, n) = STACK.pop()
    BRANCH += 1



# sub fib {
#   my $n = shift;
#   my ($s1, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         push @STACK, [ $BRANCH, 0, $n ];
#         $n -= 2;
#         next;
#       } elsif ($BRANCH == 1) {
#         push @STACK, [ $BRANCH, $return, $n ];
#         $n -= 1;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 2) {
#         $return += $s1;
#       }
#     }
#     return $return unless @STACK;
#     ($BRANCH, $s1, $n) = @{pop @STACK};
#     $BRANCH++;
#   }
# }
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                STACK.append([BRANCH, 0, n])
                n -= 2
                continue
            elif BRANCH == 1:
                STACK.append([BRANCH, _return, n])
                n -= 1
                BRANCH = 0
                continue
            elif BRANCH == 2:
                _return += s1
        if not STACK:
            return _return
        (BRANCH, s1, s2, n) = STACK.pop()
        BRANCH += 1


# sub fib {
#   my $n = shift;
#   my ($s1, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#   if ($n < 2) {
#     $return = $n;
#   } else {
#     if ($BRANCH == 0) {
#       push (@STACK, [ $BRANCH, 0, $n ]), $n -= 1 while $n >= 2;
#       $return = $n;
#     } elsif ($BRANCH == 1) {
#       push @STACK, [ $BRANCH, $return, $n ];
#       $n -= 2;
#       $BRANCH = 0;
#       next;
#     } elsif ($BRANCH == 2) {
#       $return += $s1;
#     }
#   }
#   return $return unless @STACK;
#   ($BRANCH, $s1, $n) = @{pop @STACK};
#   $BRANCH++;
# }
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                STACK.append([BRANCH, 0, n])
                while n >= 2:
                    n =- 1
                _return = n
            elif BRANCH == 1:
                STACK.append([BRANCH, _return, n])
                n -= 2
                BRANCH = 0
                continue
            elif BRANCH == 2:
                _return += s1
        if not STACK:
            return _return
        (BRANCH, s1, n) = STACK.pop()
        BRANCH += 1


# sub fib {
#   my $n = shift;
#   my ($s1, $return);
#   my $BRANCH = 0;
#   my @STACK;
#   while (1) {
#     if ($n < 2) {
#       $return = $n;
#     } else {
#       if ($BRANCH == 0) {
#         push (@STACK, [ 1, 0, $n ]), $n -= 1 while $n >= 2;
#         $return = $n;
#       } elsif ($BRANCH == 1) {
#         push @STACK, [ 2, $return, $n ];
#         $n -= 2;
#         $BRANCH = 0;
#         next;
#       } elsif ($BRANCH == 2) {
#         $return += $s1;
#       }
#     }
#     return $return unless @STACK;
#     ($BRANCH, $s1, $n) = @{pop @STACK};
#   }
# }
# NOTE: I got lazy/confused by the end of this chapter so
#       so these last few "fib" functions are not tested
#       But it was an interesting discussion on "unfolding"
#       recursion.
def fib(n):
    BRANCH = 0
    STACK = []
    while 1:
        if n < 2:
            _return = n
        else:
            if BRANCH == 0:
                while n >= 2:
                    STACK.append([1, 0, n])
                    n =- 1
                _return = n
            elif BRANCH == 1:
                STACK.append([2, _return, n])
                n -= 2
                BRANCH = 0
                continue
            elif BRANCH == 2:
                _return += s1
        if not STACK:
            return _return
        (BRANCH, s1, n) = STACK.pop()

My Dangerous New Obsession

2009-02-28T21:47:00.000-08:00

I think if I had to blame anyone, I'd start with Alan Kay. I recently read the following quote by him:

I think it is safe to say that most of the Squeak community is dedicated to making this Smalltalk more useful and accessible, and not devoted to making something so much better as to render Smalltalk obsolete (a fate I would dearly love to see happen).

Alan Kay wants smalltalk to go away? Well, if I'm going to use the man's language I should also have the decency to try to improve upon it and replace it.

So that was the start of a tiny little snow ball. And the snow ball grew. And now I find myself keeping notebooks full of ideas for creating a new programming language.

And that is my obsession. I've got it in my head that I could create a new language. And that this is somehow a good use of my time. So I'm constantly comparing and contrasting the various features that different languages have. Looking for a good idea to steal or a wart to avoid. I've been shopping around for language parsers and VMs to use.

And you know what? It's fun as hell. I actually don't have any illusions that I'm going to set the world on fire or that anyone but me will ever use my language. Or, let's be serious, that there is much likelihood that I will get past the vaporware stage. But I really feel like I'm seeing the landscape of languages with new eyes. Sort of like when you take a class on drawing and your brain starts learning how to do the "switch". And you can almost magically just draw things. I feel like my eyes are really seeing languages and language features for the first time.

So what is my language like? Not much. I've actually been avoiding trying to commit to any specific syntax. Which is probably going to make it lisp like if I'm not careful. (Not that there's anything wrong with that). When I start committing to various features it's been coming out something like a pythonized haskell (or a haskellized python) with strong nods to smalltalk minimalism. In a word its sort of an incoherent jumble. But I keep circling around and trying new things.

And like I said it's really fun. And I'm learning a lot. (And I've become addicted to starting sentences with "and").

I wonder if this is a common or rare affliction. I've never met anyone who said that they were trying to create their own language. Perhaps others are too smart to go down that road in the first place or too ashamed to admit they did and failed.

In any case, be prepared for the next big thing. Any decade now....

Higher Order Perl (Python Style) : Chapter 4 - Iterators

2009-02-25T20:53:00.000-08:00

TOC


### CHAPTER 4 Iterators


### 4.1 introduction

# @lines = open('filename'); # alternate universe interface
lines = open("filename") # a less alternate universe interface


# open(FILEHANDLE, 'filename');
# while () {
#   last if /Plutonium/;
# }
# close FILEHANDLE;
# # do something with $_;
fh = open("filename")
for line in fh:
    if "Plutonium" in line:
        break
fh.close()
# do something with line




# # alternate universe interface
# @lines = open('filename');
# for (@lines) {
#   last if /Plutonium/;
# }
# # do something with $_;
lines = open("filename").readlines()
for line in lines:
    if "Plutonium" in line:
        break
fh.close()
# do something with line


# @lines = open("yes |"); # alternate universe interface
lines = os.popen("yes").readlines() # alternate universes interface



# sub parse_section {
#   my $fh = shift;
#   my $title = parse_section_title($fh);
#   my %variables = parse_variables($fh);
#   return [$title, \%variables];
# }
def parse_section(fh):
    title = parse_section_title(fh)
    variables = parse_variables(fh)
    return title, variables


# sub parse_section {
#   my @lines = @_;
#   my $title = parse_section_title(@lines);
#   my %variables = parse_variables(@lines);
#   return [$title, \%variables];
# }
# In the python case we *could* easily
# pop values from the list (but really you 
# could in perl as well)
def parse_section(lines):
    title = parse_section_title(lines)
    variables = parse_variables(lines)
    return title, variables




# opendir D, "/tmp";
# @entries = readdir D;
# In python we get a list instead of a iterator
entries = os.listdir("/tmp")


# opendir D, "/tmp";
# while (my $entry = readdir D) {
#   # Do something with $entry
# }
# Python doesn't have "scalar" mode type behavior changes
for entry in os.listdir("/tmp"):
  # Do something with $entry


# while (my $file = glob("/tmp/*.[ch]")) {
#   # Do something with $file
# }
# glob in python is also not an iterator
for _file in glob.glob("/tmp/*.[ch]"):
    # Do something with $file

# while (my $key = each %hash) {
#   # Do something with $key
# }
# depending on version of python 
# hash may automagically be an iterator
# (maybe all versions...)
for key in hash.iterkeys():
    # Do something with key




# @matches = ("12:34:56" =~ m/(\d+)/g);
matches = re.findall("(\d+)", "12:34:56")

# while ("12:34:56" = ̃ m/(\d+)/g) {
#   # do something with $1
# }
for m in re.finditer("(\d+)", "12:34:56"):
    # do something with m (where m is a "match" object)


### 4.2 Homemade Iterators

# sub dir_walk {
#   my ($dir, $filefunc, $dirfunc, $user) = @_;
#   my $iterator = make_iterator($dir);
#   while (my $filename = NEXTVAL($iterator)) {
#     if (-f $filename) { $filefunc->($filename, $user) }
#     else              {  $dirfunc->($filename, $user) }
#   }
# }
# In python os.walk returns an iterator as is
def dir_walk(dir, filefunc, dirfunc, user):
    iterator = make_iterator(dir)
    for filename in iterator:
        if os.path.isfile(filename):
            filefunc(filename, user)
        else:
            dirfunc(filename, user)


# sub upto {
#   my ($m, $n) = @_;
#   return sub {
#     return $m <= $n ? $m++ : undef;
#   };
# }
# my $it = upto(3, 5);
def upto(m,n):
    _i = [m]
    def foo():
        val = _i[0]
        _i[0] += 1
        if val > n:
            return None
        return val

    return foo

it = upto(3,5)
## of course in python it's more natural to do the following:
# def upto(m,n):
#     for x in range(m,n+1):
#         yield x


# my $nextval = $it->();
nextval = it()


# while (defined(my $val = $it->())) {
#   # now do something with $val, such as:
#   print "$val\n";
# }
# this doesn't translate in a pretty way to python
# since we can't have statements in a while 
# context
val = it()
while val != None:
    # now do something with val, such as:
    print val
    val = it()
# but of course we'd just use:
for val in it:
    print val



# for my $val (1 .. 10000000) {
#    # now do something with $val
# }
for val in range(1, 10000000):
    # now do something with val

# package Iterator_Utils;
# use base Exporter;
# @EXPORT_OK = qw(NEXTVAL Iterator
#                 append imap igrep
#                 iterate_function filehandle_iterator list_iterator);
# %EXPORT_TAGS = ('all' => \@EXPORT_OK);
# sub NEXTVAL { $_[0]->() }

# my $nextval = NEXTVAL($it);

# while (defined(my $val = NEXTVAL($it))) {
#   # now do something with $val
# }

# No need to do these machinations since this is already built into
# python except we'd do this with "for"
for val in it:
    # not do something with val


# sub upto {
#   my ($m, $n) = @_;
#   return Iterator {
#     return $m <= $n ? $m++ : undef;
#   };
# }
# sub Iterator (&) { return $_[0] }
# in python we just do this with a yield
def upto(m, n):
    i = m
    while i <= n:
        yield i
        i += 1


# # iterator version
# sub dir_walk {
#   my @queue = shift;
#   return Iterator {
#     while (@queue) {
#       my $file = shift @queue;
#       if (-d $file) {
#         opendir my $dh, $file or next;
#         my @newfiles = grep {$_ ne "." && $_ ne ".."} readdir $dh;
#         push @queue, map "$file/$_", @newfiles;
#       }
#       return $file;
#     } else {
#       return;
#     }
#   };
# }
def dir_walk(root):
    queue = [root]
    while queue:
        _file = queue.pop(0)
        if os.path.isdir(_file):
            for newfile in os.listdir(_file):
                queue.append(os.path.join(_file, newfile))
        yield _file


                
                                
# sub dir_walk {
#   my ($top, $code) = @_;
#   my $DIR;
#   $code->($top);
#   if (-d $top) {
#     my $file;
#     unless (opendir $DIR, $top) {
#       warn "Couldn’t open directory $top: $!; skipping.\n";
#       return;
#     }
#     while ($file = readdir $DIR) {
#       next if $file eq '.'|| $file eq '..'
#       dir_walk("$top/$file", $code);
#     }
#   }
# }
def dir_walk(top, code):
    code(top)
    if os.path.isdir(top):
        try:
            for _file in os.listdir(top):
                dir_walk(os.path.join(top,_file), code)
        except StandardError, why:
            print "Couldn't open directory %s: %s" % (top, why)
            return


### 4.3 Examples

# sub interesting_files {
#   my $is_interesting = shift;
#   my @queue = @_;
#   return Iterator {
#     while (@queue) {
#       my $file = shift @queue;
#       if (-d $file) {
#         opendir my $dh, $file or next;
#         my @newfiles = grep {$_ ne "." && $_ ne ".."} readdir $dh;
#         push @queue, map "$file/$_", @newfiles;
#       }
#       return $file if $is_interesting->($file);
#     }
#     return;
#   };
# }
def interesting_files(is_interesting, *top_dirs):
    queue = list(top_dirs)
    
    while queue:
        _file = queue.pop(0)
        if os.path.isdir(_file):
            for newfile in os.listdir(_file):
                queue.append(os.path.join(_file, newfile))
        if is_interesting(_file):
            yield _file        


# # Files are deemed to be interesting if they mention octopuses
# sub contains_octopuses {
#   my $file = shift;
#   return unless -T $file && open my($fh), "<", $file;
#   while (<$fh>) {
#     return 1 if /octopus/i;
#   }
#   return;
# }
# my $octopus_file =
#   interesting_files(\&contains_octopuses, 'uploads', 'downloads');
# while ($file = NEXTVAL($octopus_file)) {
#   # do something with the file
# }
# if (NEXTVAL($next_octopus)) {
#   # yes, there is an interesting file
# } else {
#   # no, there isn’t.
# }
# undef $next_octopus;
def contains_octopuses(_file):
    if not os.path.isfile(_file):
        return False
    for line in file(_file):
        if "octopus" in line:
            return True
    return False
octopus_file = interesting_files(contains_octopuses, "uploads", "downloads")
for _octopus_file in octopus_file:
    # do something with the file
try:
    next_octopus.next()
    # yes, there is an interesting file
except StopIteration:
    # no there isn't
del next_octopus
    


# sub permute {
#     my @items = @{ $_[0] };
#     my @perms = @{ $_[1] };
#     unless (@items) {
#         print "@perms\n";
#     } else {
#         my(@newitems,@newperms,$i);
#         foreach $i (0 .. $#items) {
#             @newitems = @items;
#             @newperms = @perms;
#             unshift(@newperms, splice(@newitems, $i, 1));
#             permute([@newitems], [@newperms]);
#         }
#     }
# }
# # sample call:
# permute([qw(red yellow blue green)], []);
# I suspect I don't have this quite right
# it produces the permuations but doesn't
# have the problem of waiting for the end to
# start showing the permutations
def permute(items, perms):
    if not items:
        print perms
    else:
        for i in range(len(items)):
            newitems = items[:]
            newitem = newitems.pop(i)
            newperms = [newperm+[newitem] for newperm in perms] or [[newitem]]
            permute(newitems, newperms)
# sample call
permute(["red", "yello", "blue", "green"], [])



# my $it = permute('A'..'D');
# while (my @p = NEXTVAL($it)) {
#   print "@p\n";
# }
it = permute(["A","B","C","D"])
for p in it:
    print p



# sub permute {
#   my @items = @_;
#   my @pattern = (0) x @items;
#   return Iterator {
#     return unless @pattern;
#     my @result = pattern_to_permutation(\@pattern, \@items);
#     @pattern = increment_pattern(@pattern);
#     return @result;
#   };
# }
def permute(items):
    pattern = [0] * len(items)
    
    while pattern:
        result = pattern_to_permutation(pattern, items)
        pattern = increment_pattern(pattern)
        yield result


# sub pattern_to_permutation {
#   my $pattern = shift;
#   my @items = @{shift()};
#   my @r;
#   for (@$pattern) {
#     push @r, splice(@items, $_, 1);
#   }
#   @r;
# }
def pattern_to_permutation(pattern, items):
    items = items[:]
    r = []
    for _x in pattern:
        r.append(items.pop(_x))
    return r 



# sub increment_odometer {
#   my @odometer = @_;
#   my $wheel = $#odometer;    # start at rightmost wheel
#   until ($odometer[$wheel] < 9 || $wheel < 0) {
#     $odometer[$wheel] = 0;
#     $wheel--; # next wheel to the left
#   }
#   if ($wheel < 0) {
#     return;   # fell off the left end; no more sequences
#   } else {
#     $odometer[$wheel]++;  # this wheel now turns one notch
#     return @odometer;
#   }
# }
def increment_odometer(odometer):
    wheel = len(odometer) - 1
    while not (odometer[wheel] < 9 or wheel < 0):
        odometer[wheel] = 0
        wheel -= 1
    if wheel < 0:
        return
    else:
        odometer[wheel] += 1
        return odometer



# sub increment_pattern {
#   my @odometer = @_;
#   my $wheel = $#odometer;    # start at rightmost wheel
#   until ($odometer[$wheel] < $#odometer-$wheel || $wheel < 0) {
#     $odometer[$wheel] = 0;
#     $wheel--; # next wheel to the left
#   }
#   if ($wheel < 0) {
#     return;   # fell off the left end; no more sequences
#   } else {
#     $odometer[$wheel]++; # this wheel now turns one notch
#     return @odometer;
#   }
# }
def increment_pattern(odometer):
    wheel = len(odometer) - 1
    while not (odometer[wheel] < (len(odometer)-1-wheel) or wheel < 0):
        odometer[wheel] = 0
        wheel -= 1
    if wheel < 0:
        return
    else:
        odometer[wheel] += 1
        return odometer


# sub n_to_pat {
#   my @odometer;
#   my ($n, $length) = @_;
#   for my $i (1 .. $length) {
#     unshift @odometer, $n % $i;
#     $n = int($n/$i);
#   }
#   return $n ? () : @odometer;
# }
def n_to_pat(n, length):
    odometer = []
    for i in range(1, length+1):
        odometer.insert(0, n % i)
        n = n / i
    return not n and odometer or []


# sub permute {
#   my @items = @_;
#   my $n = 0;
#   return Iterator {
#     my @pattern = n_to_pat($n, scalar(@items));
#     my @result = pattern_to_permutation(\@pattern, \@items);
#     $n++;
#     return @result;
#   };
# }
def permute(items):
    n = 0
    while 1:
        pattern = n_to_pat(n, len(items))
        if not pattern:
            break
        result = pattern_to_permutation(pattern, items)
        yield result
        n += 1


# sub iterate_function {
#   my $n = 0;
#   my $f = shift;
#   return Iterator {
#     return $f->($n++);
#   };
# }
def iterate_function(f):
    n = 0
    while 1:
        yield f(n)
        n += 1


# sub permute {
#   my @items = @_;
#   my $n = 0;
#   return Iterator {
#     $n++, return @items if $n==0;
#     my $i;
#     my $p = $n;
#     for ($i=1; $i<=@items && $p%$i==0; $i++) {
#       $p /= $i;
#     }
#     my $d = $p % $i;
#     my $j = @items - $i;
#     return if $j < 0;
#     @items[$j+1..$#items] = reverse @items[$j+1..$#items];
#     @items[$j,$j+$d] = @items[$j+$d,$j];
#     $n++;
#     return @items;
#   };
# }
 def permute(_items):
    n = 0
    items = _items[:]

    if n == 0:
        yield items

    n += 1
    while 1:
        # make a copy so list(permute(my_list)) returns n copies of same item
        # otherwise can remove
        items = items[:] 
        i = 1
        p = n
        while i <= len(items)+1 and p % i == 0:
            p /= i
            i += 1
        d = p % i
        j = len(items) - i 

        if j < 0:
            return

        items[j+1:len(items)] = reversed(items[j+1:len(items)])
        x,y = items[j+d], items[j]
        items[j] = x
        items[j+d] = y 
        n += 1

        yield items



# sub make_genes {
#   my $pat = shift;
#   my @tokens = split /[()]/, $pat;
#   for (my $i = 1; $i < @tokens; $i += 2) {
#     $tokens[$i] = [0, split(//, $tokens[$i])];
#   }
#   my $FINISHED = 0;
#   return Iterator {
#     return if $FINISHED;
#     my $finished_incrementing = 0;
#     my $result = "";
#     for my $token (@tokens) {
#       if (ref $token eq "") {    # plain string
#         $result .= $token;
#       } else {                   # wildcard
#         my ($n, @c) = @$token;
#         $result .= $c[$n];
#         unless ($finished_incrementing) {
#           if ($n == $#c) { $token->[0] = 0 }
#           else { $token->[0]++; $finished_incrementing = 1 }
#         }
#       }
#     }
#     $FINISHED = 1 unless $finished_incrementing;
#     return $result;
#   }
# }
def make_genes(pat):
    tokens = re.split("[()]",pat)

    for i in range(len(tokens))[1::2]:
        tokens[i] = [0] + list(tokens[i])

    FINISHED = False
    while not FINISHED:
        finished_incrementing = False
        result = ""
        for token in tokens:
            if token.__class__ is str:
                result += token
            else:
                n, c = token[0], token[1:]
                result += c[n]
                if not finished_incrementing:
                    if n == len(c) - 1:
                        token[0] = 0
                    else:
                        token[0] += 1
                        finished_incrementing = True
        if not finished_incrementing:
            FINISHED = True
        yield result




# %n_expand = qw(N ACGT 
#                B CGT D AGT H ACT V ACG
#                K GT M AC R AG S CG W AT Y CT);
# sub make_dna_sequences {
#   my $pat = shift;
#   for my $abbrev (keys %n_expand) {
#     $pat =~ s/$abbrev/($n_expand{$abbrev})/g;
#   }
#   return make_genes($pat);
# }
n_expand = {"N" : "ACGT",
            "B" : "CGT", "D" : "AGT", "H" : "ACT", "V" : "ACG",
            "K" : "GT",  "M" : "AC",  "R" : "AG",  "S" : "CG",  "W" : "AT", "Y" : "CT"}
def make_dna_sequences(pat):
    for abbrev in n_expand:
        pat = re.sub(abbrev, n_expand[abbrev], pat)
    
    return make_genes(pat)



# sub filehandle_iterator {
#   my $fh = shift;
#   return Iterator { <$fh> };
# }

# my $it = filehandle_iterator(*STDIN);
# while (defined(my $line = NEXTVAL($it))) {
#   # do something with $line
# }
### python already does this by default
for line in file("foo"):
    # do something with line


# LASTNAME:FIRSTNAME:CITY:STATE:OWES
# Adler:David:New York:NY:157.00
# Ashton:Elaine:Boston:MA:0.00
# Dominus:Mark:Philadelphia:PA:0.00
# Orwant:Jon:Cambridge:MA:26.30
# Schwern:Michael:New York:NY:149658.23
# Wall:Larry:Mountain View:CA:-372.14


# package FlatDB;
# my $FIELDSEP = qr/:/;
# sub new {
#   my $class = shift;
#   my $file = shift;
#   open my $fh, "<", $file or return;
#   chomp(my $schema = <$fh>);

#   my @field = split $FIELDSEP, $schema;
#   my %fieldnum = map { uc $field[$_] => $_ } (0..$#field);
#   bless { FH => $fh, FIELDS => \@field, FIELDNUM => \%fieldnum,
#           FIELDSEP => $FIELDSEP } => $class;
# }
class FlatDB(object):
    FIELDSEP = ":"

    def __init__(self, _file):
        self._file = _file
        self.fh = file(self._file)
        self.schema = self.fh.readline().strip()
        self.field = self.schema.split(FlatDB.FIELDSEP)
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))
  
# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# use Fcntl ':seek';
# sub query {
#   my $self = shift;
#   my ($field, $value) = @_;
#   my $fieldnum = $self->{FIELDNUM}{uc $field};
#   return unless defined $fieldnum;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard schema line
#   return Iterator {
#     local $_;
#     while (<$fh>) {
#       chomp;
#       my @fields = split $self->{FIELDSEP}, $_, -1;
#       my $fieldval = $fields[$fieldnum];
#       return $_ if $fieldval eq $value;
#     }
#     return;
#   };
# }

    def query(self, field, value):
        fieldnum = self.fieldnum.get(field.upper())
        if fieldnum == None:
            return
        fh = self.fh
        fh.seek(0)
        fh.readline() # discard schema line
        for line in fh:
            fields = line.split(FlatDB.FIELDSEP)
            fieldval = fields[fieldnum]
            if fieldval == value:
                yield line.strip()



# use FlatDB;
# my $dbh = FlatDB->new('db.txt') or die $!;
# my $q = $dbh->query('STATE', 'NY');
# while (my $rec = NEXTVAL($q)) {
#   print $rec;
# }
dbh = FlatDB("db.txt")
q = dbh.query("STATE", "NY")
for rec in q:
    print rec




# my $q = $dbh->callbackquery(sub { my %F=@_; $F{OWES} > 10 });
# my $q = $dbh->callbackquery(sub { my %F=@_; $F{FIRSTNAME} =~ /ˆM/ });

# use Fcntl ':seek';
# sub callbackquery {
#   my $self = shift;
#   my $is_interesting = shift;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard header line
#   return Iterator {
#     local $_;
#     while (<$fh>) {
#       chomp;
#        my %F;
#        my @fieldnames = @{$self->{FIELDS}};
#        my @fields = split $self->{FIELDSEP};
#        for (0 .. $#fieldnames) {
#          $F{$fieldnames[$_]} = $fields[$_];
#        }
#        return $_ if $is_interesting->(%F);
#     }
#     return;
#   }
# }

q = dbh.callbackquery(lambda F: F["OWES"] > 10)
q = dbh.callbackquery(lambda F: F["FIRSTNAME"].startswith("M") )

def callbackquery(self, is_interesting):
    fh = self.fh
    fh.seek(0)
    fh.readline() # discard schema line
    for line in fh:
        line = line.strip()
        fieldnames = self.field
        fields = line.split(FlatDB.FIELDSEP)
        F = dict(zip(fieldnames, fields))
        if is_interesting(F):
            yield line


# use FlatDB;
# my $dbh = FlatDB->new('db.txt') or die $!;
# my $q1 = $dbh->query('STATE', 'MA');
# my $q2 = $dbh->query('STATE', 'NY');
# for (1..2) {
#   print NEXTVAL($q1), NEXTVAL($q2);
# }
dbh = FlatDB("db.txt")
q1 = dbh.query("STATE","MA")
q2 = dbh.query("STATE","NY")
for x in range(1,3):
    print q1.next(), q2.next()


# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# use Fcntl ':seek';
# sub query {
#   my $self = shift;
#   my ($field, $value) = @_;
#   my $fieldnum = $self->{FIELDNUM}{uc $field};
#   return unless defined $fieldnum;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard header line
#   my $position = tell $fh;
#   return Iterator {
#     local $_;
#     seek $fh, $position, SEEK_SET;
#     while (<$fh>) {
#       chomp;
#       $position = tell $fh;
#       my @fields = split $self->{FIELDSEP};
#       my $fieldval = $fields[$fieldnum];
#       return $_ if $fieldval eq $value;
#     }
#     return;
#   };
# }
# # callbackquery with bug fix
# use Fcntl ':seek';
# sub callbackquery {
#   my $self = shift;
#   my $is_interesting = shift;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard header line
#   my $position = tell $fh;
#   return Iterator {
#     local $_;
#     seek $fh, $position, SEEK_SET;
#     while (<$fh>) {
#       $position = tell $fh;
#       my %F;
#       my @fieldnames = @{$self->{FIELDS}};
#       my @fields = split $self->{FIELDSEP};
#       for (0 .. $#fieldnames) {
#         $F{$fieldnames[$_]} = $fields[$_];
#       }
#       return $_ if $is_interesting->(%F);

#     }
#     return;
#   };
# }
# 1;

class FlatDB(object):
    FIELDSEP = ":"

    def __init__(self, _file):
        self._file = _file
        self.fh = file(self._file)
        self.schema = self.fh.readline().strip()
        self.field = self.schema.split(FlatDB.FIELDSEP)
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))

    def query(self, field, value):
        fieldnum = self.fieldnum.get(field.upper())
        if fieldnum == None:
            return
        fh = self.fh
        fh.seek(0)
        fh.readline() # discard schema line
        while 1:
            line = fh.readline()
            if not line:
                break
            position = fh.tell()
            fields = line.split(FlatDB.FIELDSEP)
            fieldval = fields[fieldnum]
            if fieldval == value:
                yield line.strip()
            fh.seek(position)

    def callbackquery(self, is_interesting):
        fh = self.fh
        fh.seek(0)
        fh.readline() # discard schema line
        while 1:
            line = fh.readline()
            if not line:
                break
            position = fh.tell()
            line = line.strip()
            fieldnames = self.field
            fields = line.split(FlatDB.FIELDSEP)
            F = dict(zip(fieldnames, fields))
            if is_interesting(F):
                yield line
            fh.seek(position)




# package FlatDB::Iterator;
# my $FIELDSEP = qr/\s+/;
# sub new {
#   my $class = shift;
#   my $it = shift;
#   my @field = @_;
#   my %fieldnum = map { uc $field[$_] => $_ } (0..$#field);
#   bless { FH => $it, FIELDS => \@field, FIELDNUM => \%fieldnum,
class IterFlatDB(object):
    FIELDSEP = "\s+"

    def __init__(self, it, *field):
        self.it = it
        self.field = field
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))



# FlatDB::Iterator->new(
#   $iterator,
#   qw(address rfc931 username datetime tz method page protocol
#      status bytes referrer agent)
# );
IterFlatDB(iterator, 
           "address rfc931 username datetime tz method page protocol status bytes referrer agent".split())





# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# sub query {
#   my $self = shift;
#   my ($field, $value) = @_;
#   my $fieldnum = $self->{FIELDNUM}{uc $field};
#   return unless defined $fieldnum;
#   my $it = $self->{FH};
#   # seek $fh, 0, SEEK_SET;
#   # <$fh>;                # discard header line
#   return Iterator {
#     local $_;
#     while (defined ($_ = NEXTVAL($it))) {
#       my @fields = split $self->{FIELDSEP};
#       my $fieldval = $fields[$fieldnum];
#       return $_ if $fieldval eq $value;
#     }
#     return;
#   };
# }
def query(self, field, value):
    fieldnum = self.fieldnum.get(field.upper())
    if fieldnum == None:
        return

    for record in self.it:
        fields = re.split(IterFlatDB.FIELDSEP, record)
        fieldval = fields[fieldnum]
        if fieldval == value:
            yield record




# my $qit =
#   FlatDB::Iterator->new($it, @FIELDNAMES)->query($field, $value);
qit = IterFlatDB(it, FIELDNAMES).query(field, value)



# sub readbackwards {
#   my $file = shift;
#   open my($fh), "|-", "tac", $file
#     or return;
#   return Iterator { return scalar(<$fh>) };
# }
def readbackwards(_file):
    return os.popen("tac %s" % _file)


# my @fields = qw(address rfc931 username datetime tz method
#                 page protocol status bytes referrer agent);
# my $logfile = readbackwards("/usr/local/apache/logs/access-log")
# my $db = FlatDB::Iterator->new($logfile, @fields);
# my $q = $db->callbackquery(sub {my %F=@_; $F{PAGE}=~ m{/book/$}});
# while (1) {
#   for (1..10) {
#     print NEXTVAL($q);
#   }
#   print "q to quit; CR to continue\n";
#   chomp(my $resp = );
#   last if $resp =~ /q/i;
# }
fields = "address rfc931 username datetime tz method page protocol status bytes referrer agent"
logfile = readbackwards("/var/log/apache2/access.log")
db = IterFlatDB(logfile, fields.split())
q = db.callbackquery(lambda F: re.search("/book/$", f["PAGE" ]))

while 1:
    for line in itertools.islice(q, 10):
        print line
    print "q to quit; CR to continue"
    if raw_input() == 'q':
        break
        





# my $seed = 1;
# sub Rand {
#   $seed = (27*$seed+11111) & 0x7fff;
#   return $seed;
# }
seed = 1
def Rand():
    global seed
    seed = (27*seed+11111) & 0x7fff
    return seed


# sub SRand {
#   $seed = shift;
# }
def SRand(_seed):
    global seed
    seed = _seed


# SRand($$);
SRand(os.getpid())


# use CGI::Push;
# my $seed = shift || $$ ;
# srand($seed);
# open LOG, "> $logfile" or die ... ;
# print LOG "Random seed: $seed\n";
# do_push(...);
if len(sys.argv > 1):
    seed = int(sys.argv[1])
else: 
    seed = os.getpid()
srand(seed)
LOG = open(logfile, "w")
LOG.write("Random seed: " + str(seed))
do_push(...)


# use Foo;
# while (<>) {
#   my $random = Rand();
#   # do something with $random
#   foo();
# }
import Foo
for line in sys.stdin:
    random = Rand()
    # do something with random
    Foo.foo()




# sub make_rand {
#   my $seed = shift || (time & 0x7fff);
#   return Iterator {
#     $seed = (29*$seed+11111) & 0x7fff;
#     return $seed;
#   }
# }
def make_rand(seed=None):
    if seed == None:
        seed = int(time.time()) & 0x7fff
    while 1:
        seed = (29*seed+11111) & 0x7fff
        yield seed



# use Foo;
# my $rng = make_rand();
# while (<>) {
#   my $random = NEXTVAL($rng);
#   # do something with $random
#   foo();
# }
import Foo
rng = make_rand()
for line in sys.stdin:
    random = rng.next()
    # do something with randome
    Foo.foo()



### 4.4 Filters and Transforms

# sub imap {
#   my ($transform, $it) = @_;
#   return Iterator {
#     my $next = NEXTVAL($it);
#     return unless defined $next;
#     return $transform->($next);
#   }
# }

# itertools.imap does this already
def imap(transform, it):
    for next in it:
        yield transform(next)


# my $rng = imap(sub { $_[0] / 37268 }, make_rand());
rng = imap(lambda x: float(x)/37268, make_rand())


# sub imap (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#     my $next = NEXTVAL($it);
#     return unless defined $next;
#     return $transform->($next);
#   }
# }

# my $rng = imap { $_[0] / 37268 } make_rand();

# sub imap (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#      local $_ = NEXTVAL($it);
#      return unless defined $_;
#      return $transform->();
#   }
# }

# these are irrelevant changes for python



# sub igrep (&$) {
#   my ($is_interesting, $it) = @_;
#   return Iterator {
#     local $_;
#     while (defined ($_ = NEXTVAL($it))) {
#       return $_ if $is_interesting->();
#     }
#     return;
#   }
# }
def igrep(is_interesting, it):
    for x in it:
        if is_interesting(x):
            yield x


# # instead of         my $next_octopus =
# #    interesting_files(\&contains_octopuses, 'uploads', 'downloads' ;
#                                                                    )
# my $next_octopus = igrep { contains_octopuses($_) }
#                        dir_walk('uploads', 'downloads');
# while ($file = NEXTVAL($next_octopus)) {
#   # do something with the file
# }
for _file in igrep(contains_octopuses, dir_walk("uploads", "downloads")):
    # do something with the file



# sub list_iterator {
#   my @items = @_;
#   return Iterator {
#     return shift @items;
#   };
# }
def list_iterator(*args):
    for x in args:
        yield x
# or just
iter(args)



# sub append {
#   my @its = @_;
#   return Iterator {
#     while (@its) {
#     my $val = NEXTVAL($its[0]);
#     return $val if defined $val;
#     shift @its;  # Discard exhausted iterator
#   }
#   return;
# };
def append(its):
    for it in its:
        for x in it:
            yield x
# or just
itertools.chain(*its)



### 4.5 The Semipredicate Problem

# this whole section is irrelevant due to how 
# python uses iterators/generators 
# so i skipped it.  it someone sees something
# in here that deserves a python translation
# let me know

### 4.6 Alternative Interfaces to Iterators


# sub equal_arrays (\@\@) {
#   my ($x, $y) = @_;
#   return unless @$x == @$y;     # arrays are the same length?
#   for my $i (0 .. $#$x) {
#     return unless $x->[$i] eq $y->[$i];   # mismatched elements
#   }
#   return 1;                     # arrays are equal
# }
def equal_arrays(x,y):
    if len(x) != len(y):
        return False
    for i in range(len(x)):
        if x[i] != y[i]:
            return False
    return True
# but this is unnecessary since we can already do
x == y # in place



# sub equal_arrays (\@\@) {
#   my ($x, $y) = @_
#   return unless @$x == @$y;
#   my $xy = each_array(@_ );
#   while (my ($xe, $ye) = NEXTVAL($xy)) {
#     return unless $xe eq $ye;
#   }
#   return 1;
# }
def equal_arrays(x,y):
    if len(x) != len(y):
        return False
    
    xy = each_array(x,y)
    for xe,ye in xy:
        if xe != ye:
            return False
    return True
    

# sub each_array {
#   my @arrays = @_;
#   my $cur_elt = 0;
#   my $max_size = 0;
#   # Get the length of the longest input array
#   for (@arrays) {
#     $max_size = @$_ if @$_ > $max_size;
#   }
#   return Iterator {
#     $cur_elt = 0, return () if $cur_elt >= $max_size;
#     my $i = $cur_elt++;
#     return map $_->[$i], @arrays;
#   };
# }
def each_array(*arrays):
    max_size = max(*[len(ar) for ar in arrays])
    
    def get_item(ar, i):
        if i < len(ar):
            return ar[i]
        return None

    for i in range(max_size):
        yield [get_item(ar, i) for ar in arrays]
# you could also probably do something clever with itertools.izip() 



# my $buttons = each_array(\@labels, \@values);
# ...
# while (my ($label, $value) = NEXTVAL($buttons)) {
#   print HTML qq{ $label
\n};
# }
buttons = each_array(labels, values)
for label, value in buttons:
    HTML.write(" %(label)s
\n" % locals())



# sub each_array {
#   my @arrays    = @_;
#   my $stop_type = ref $arrays[0] ? 'maximum' : shift @arrays;
#   my $stop_size = @{$arrays[0]};
#   my $cur_elt   = 0;
#   # Get the length of the longest (or shortest) input array
#   if ($stop_type eq 'maximum') {
#     for (@arrays) {
#       $stop_size = @$_ if @$_ > $stop_size;
#     }
#   } elsif ($stop_type eq 'minimum') {
#     for (@arrays) {
#       $stop_size = @$_ if @$_ < $stop_size;
#     }
#   } else {
#     croak "each_array: unknown stopping behavior '$stop_type'";
#   }
#   return Iterator {
#     return ()  if $cur_elt >= $stop_size;
#     my $i = $cur_elt++;
#     return map $_->[$i], @arrays;
#   };
# }
def each_array(arrays, stop_type="maximum"):
    assert stop_type in ("minimum", "maximum")
    
    if stop_type == "minimum":
        stop_size = min(*[len(ar) for ar in arrays])
    else:
        stop_size = max(*[len(ar) for ar in arrays])
    
    def get_item(ar, i):
        if i < len(ar):
            return ar[i]
        return None

    for i in range(stop_size):
        yield [get_item(ar, i) for ar in arrays]



# sub eachlike (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#     local $_ = NEXTVAL($it);
#     return unless defined $_;
#     my $value = $transform->();
#     return wantarray ? ($_, $value) : $value;
#   }
# }
# not sure if wantarray really maps to python
# style



# package CIA;
# sub TIESCALAR {
#   my $package = shift;
#   my $self = {};
#   bless $self => $package;
# }
# sub STORE { }
# sub FETCH { "<>" }

# tie $secret, 'CIA';

# $secret = 'atomic ray';

# print "The secret weapon is '$secret'.\n"

# the secret weapon is '<>'.

# I can't think of any reasonable way to do
# this in python.  In part it seems like something
# you could handle with descriptor and in part
# with "with".  I'm just going to ignore TIE-ing
# for now


### 4.7 An Extended Example: Web Spiders


# use HTML::LinkExtor;
# use LWP::Simple;
# sub traverse {
#   my @queue = @_;
#   my %seen;
#   return Iterator {
#     while (@queue) {
#       my $url = shift @queue;
#       $url =~ s/#.*$//;
#       next if $seen{$url}++;
#       my ($content_type) = head($url);
#       if ($content_type =~ m{ˆtext/html\b}) {
#         my $html = get($url);
#         push @queue, get_links($url, $html);
#       }
#       return $url;
#     }
#     return;     # exhausted
#   }
# }
import urllib2    
def traverse(_queue):
    queue = _queue[:]
    seen = {}
    while queue:
        url = queue.pop(0)
        url = url.split("#")[0]
        seen.setdefault(url,0)
        if seen[url] > 0:
            continue
        seen[url] += 1
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            continue
        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend(get_links(url, html))
        yield url
            

# sub get_links {
#   my ($base, $html) = @_;
#   my @links;
#   my $more_links = sub {
#     my ($tag, %attrs) = @_;
#     push @links, values %attrs;
#   };
#   HTML::LinkExtor->new($more_links, $base)->parse($html);
#   return @links;
# }
# Off the top of my head I don't know a python library
# that provides this exact functionality, so we 
# fake it.
def get_links(base, html):
    links = []

    parsed = urlparse.urlparse(base)

    for anchor in BeautifulSoup.BeautifulSoup(html)('a'):
        link = anchor.get("href")
        if not link:
            continue

        if link.startswith("./"):
            link = link[2:]

        if link.startswith("http"):
            links.append(link)
        elif link.startswith("/"):
            links.append(parsed[0]+"://"+parsed[1]+link)
        else:
            links.append(parsed[0]+"://"+parsed[1]+parsed[2]+link)

    return links



# # Version with 'interesting links' callback
# sub traverse {
#   my $interesting_links = sub { @_ };
#   $interesting_links = shift if ref $_[0] eq 'CODE';
#   ...
#         push @queue, $interesting_links->(get_links($url, $html));
#   ...
# }
def traverse(queue, interesting_links=None):
    ...
    queue.extend(interesting_links(get_links(url, html)))
    ...



# my $top = 'http://perl.plover.com/';
# my $interesting = sub { grep /ˆ\Q$top/o, @_ };
# my $urls = traverse($interesting, $top);
top = "http://perl.plover.com"
interesting = lambda x: top in x
urls = traverse(interesting, top)



# use File::Basename;
# while (my $url = NEXTVAL($urls)) {
#   my $file = $url;
#   $file =~ s/ˆ\Q$top//o;
#   my $dir = dirname($file);
#   system('mkdir', '-p', $dir) == 0 or next;
#   open F, ">", $file or next;
#   print F get($url);
# }
for url in urls:
    _file = url.replace(url, "")
    _dir = os.path.dirname(_file)
    if os.system("mkdir -p %s" % _dir) != 0:
        continue
    try:
        F = open(_file, "w")
    else:
        continue
    F.write(urllib2.urlopen(url).read())




# while (my $url = NEXTVAL($urls)) {
#   print "Bad link to: $url" unless head($url);
# }
for url in urls:
    try:
        urllib2.urlopen(url)
    except:
        print "Bad link to: %s" % url



# sub traverse {
#       ...
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} = ̃ m{ˆtext/html\b}) {
#         $html = get($url);
#         push @queue, $interesting_links->(get_links($url,$html));
#       }
#       return wantarray ? ($url, \%head, $html) : $url;
#       ...
# }
# I don't think this is a straight forward way to duplicate
# "wantarray" type functionality in python.  In any case
# it would be more uniform to *always* retrn the tuple


# sub traverse {
#   my $interesting_links = sub { shift; @_ };
#   $interesting_links = shift if ref $_[0] eq 'CODE';
#   my @queue = map [$_, 'supplied by user'], @_;
#   my %seen;
#   return Iterator {
#     while (@queue) {
#       my ($url, $referrer) = @{shift @queue};
#       $url =~ s/#.*$//;
#       next if $seen{$url}++;
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} =~ m{ˆtext/html\b}) {
#         my $html = get($url);
#         push @queue,
#           map [$_, $url],
#             $interesting_links->($url, get_links($url, $html));
#       }
#       return wantarray ? ($url, \%head, $referrer, $html) : $url;
#     }
#     return;     #exhausted
#   }
# }
import urllib2    
def traverse(queue, interesting_links=None):
    queue = [(x, "supplied by user") for x in queue]

    if interesting_links == None:
        def interesting_links(this_url, other_urls):
            return other_urls

    seen = {}

    while queue:
        url, referrer = queue.pop(0)
        url = url.split("#")[0]
        seen.setdefault(url,0)
        if seen[url] > 0:
            continue
        seen[url] += 1
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            yield url, None, referrer, None
            continue
        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend([(x, url) for x in interesting_links(url, get_links(url, html))])
        yield url, page.headers, referrer, html
            


# my $top = 'http://perl.plover.com/'
# my $interesting = sub { shift; grep /ˆ\Q$top/o, @_ };
# my $urls = traverse($interesting, $top);
# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   next if $head->{TYPE};
#   print "Page '$referrer' has a bad link to '$url'\n";
# }
top = "http://perl.plover.com"
interesting = (lambda x,y: [_y for _y in y if top in _y])
urls = traverse([top], interesting)
for url, head, referrer, html in urls:
    if not html:
        continue
    print "Page '%s' has a bad link to '%s'" % (referrer, url)



# my $top = 'http://perl.plover.com/';
# my $interesting = sub { shift; grep /ˆ\Q$top/o, @_ };
# my $urls = igrep_l { not $_[1]{TYPE} } traverse($interesting, $top);
# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   print "Page '$referrer' has a bad link to '$url'\n";
# }
top = "http://perl.plover.com"
interesting = (lambda x,y: [_y for _y in y if top in _y])
urls = igrep_l((lambda url, head, referrer, html: not html), traverse([top], interesting))
for url, head, referrer, html in urls:
    if not html:
        continue
    print "Page '%s' has a bad link to '%s'" % (referrer, url)




# sub igrep_l (&$) {
#   my ($is_interesting, $it) = @_;
#   return Iterator {
#     while (my @vals = NEXTVAL($it)) {
#       return @vals if $is_interesting->(@vals);
#     }
#     return;
#   }
# }
def igrep_l(is_interesting, it):
    for vals in it:
        if is_interesting(*vals):
            yield vals
        

# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   print "Page '$referrer' has a bad link to '$url'\n";
#   print "Edit now? ";
#   my $resp = <>;
#   if ($resp =~ /ˆy/i) {
#     system $ENV{EDITOR}, url_to_filename($referrer);
#   } elsif ($resp =~ /∧ q/i) {
#     last;
#   }
# }
for url, head, referrer, html in urls:
    print "Page '%(referrer)s' has a bad line to '%(url)s'" % locals()
    print "Edit now?"
    resp = raw_input():
    if resp == 'y':
        os.system(os.environ["EDITOR"] + " " + url_to_filename(referrer))
    elif resp == 'q':
        break





# sub traverse {
#   my $interesting_link;
#   $interesting_link = shift if ref $_[0] eq 'CODE';
#   my @queue = map [$_, 'supplied by user'], @_;
#   my %seen;
#   my $q_it = igrep { ! $seen{$_->[0]}++ }
#                imap { $_->[0] =~ s/#.*$//; $_}
#                  Iterator { return shift(@queue) };
#   if ($interesting_link) {
#     $q_it = igrep {$interesting_link->(@$_)} $q_it;
#   }
#   return imap {
#       my ($url, $referrer) = @$_;
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} =~ m{ˆtext/html\b}) {
#         $html = get($url);
#         push @queue,
#           map [$_, $url],
#             get_links($url, $html);
#       }
#       return wantarray ? ($url, \%head, $referrer, $html) : $url;
#   } $q_it;
# }
# this is not an exact match but is close enough for our
# purposes.  what ever that purpose could be.
def traverse(queue, interesting_link=None):
    seen = {}
    queue = [(x, "supplied by user") for x in queue]

    def iterate_queue():
        while queue:
            yield queue.pop(0)

    def not_seen_yet(url):
        seen.setdefault(url,0)
        seen[url] += 1
        if seen[url] > 1:
            return False
        return True

    q_it = iterate_queue()
    q_it = ((url[0].split("#")[0], url[1]) for url in q_it)
    q_it = (url for url in q_it if not_seen_yet(url[0]))

    if interesting_link != None:
        q_it = igrep(interesting_link, q_it)

    def process_url((url, referrer)): 
        print "process_url:", url, referrer
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            return url, None, referrer, None

        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend([(x, url) for x in get_links(url, html)])
        return url, page.headers, referrer, html
            
    return imap(process_url, q_it)
        


# sub make_robot_filter {
#   my $agent = shift;
#   my %seen_site;
#   my $rules = WWW::RobotRules->new($agent);
#   return sub {
#     my $url = url(shift());
#     return 1 unless $url->scheme eq 'http';
#     unless ($seen_site{$url->netloc}++) {
#       my $robots = $url->clone;
#       $robots->path('/robots.txt');
#       $robots->frag(undef);
#       $rules->parse($robots, get($robots));
#     }
#     $rules->allowed($url)
#   };
# }
def make_robot_filter(agent):
    seen_site = {}

    rules = {} #robotparser.RobotFileParser()

    def _filter(url):
        u = urlparse.urlparse(url) 
        if u.scheme != "http":
            return True

        if u.netloc not in rules:
            rules[u.netloc] = robotparser.RobotFileParser()
            rules[u.netloc].set_url(u.scheme+"://"+u.netloc+"/robots.txt")
            rules[u.netloc].read()

        return rules[u.netloc].can_fetch(agent, url)

    return _filter

Smalltalk for a Year - Status Report 1

2009-02-02T20:49:00.000-08:00

As I've mentioned, I'm working on smalltalk as my learn a language a year language. So where am I after a month?

My initial idea was to ease into things using etoys as a gateway drug. But after a week or so I decided that, while it's oddly fascinating and kinda fun, it's not really smalltalk per se. So while I'll probably dabble a little bit, I've decided that I need to work with more mainstream smalltalk learning.

In that vein, I'm reading Squeak By Example and am about 1/3 of the way through. It's a very nice no nonsense introduction to smalltalk the language and squeak the environment.

After that I'm thinking I'll either look at the Squeak Development Example for Squeak 3.9 tutorial or work on a Seaside Tutorial. I'm sort of leaning towards the latter, but I'm sure I'll eventually do both, but for some reason I'm more drawn to the web development aspect of things these days. And how cool are you if you use continuations? (Pretty cool, I'd wager)

I have to confess that already in the first month I've had to fight off the the urge just to ditch this project. I'm a little embarrassed to admit that I'm not immediately overwhelmed with a love for smalltalk. And logically that's not really so unexpected. Learning a language is *hard*. And in the initial phases you basically see everything with your blub colored glasses and in the new language you see blub features but they are distorted and some blub features are completely missing or almost too awkward to be usable. You may dimly see some features that are interesting but they are obscured by an alien syntax and semantics.

And that's where I am now with smalltalk. There are somethings that seem interesting (elegant metaclass programming features, turtles all the way down, highly integrated development environment, etc) but I've never used these features "in anger". So at best they just seem kinda interesting. On the other hand the lack of modules feels archaic, the default user interface look-and-feel seems oddly clunky, the lack of list access syntax (e.g. foo[3:5]) makes me sad, and I miss emacs.

So I'm in the no man's land right now. I see things faintly off in the distance that seem interesting but everything in my reach is (seemingly) inferior and awkward.

I guess it helps me to lay it out like this. I'm surprised (even though I should know myself better by now) at how easily I could just abandon things and jump over to haskell for a while. Oooh, and then lisp is kinda cool, and then, oh yeah, I heard javascript is the NBL, I better look at that for a few minutes today.

I wonder if it's harder to fall in love with another language when your day job is python. But I'm a little afraid that python has become my blub and I must fight the tendencies of a blub programmer to be blind to non-blubby goodness.

Ok, enough dithering. I'm putting my blinders on again and focusing on smalltalk. I actually hope (and somewhat expect) that I will get over the oddness hurdle and really love smalltalk.

But it's not love at first sight. It's more like cautious optimism at first sight.

Higher Order Perl (Python Style) : Chapter 3 - Caching and Memoization

2009-01-23T21:29:00.000-08:00


### 3.1 Caching Fixes Recursion

# sub RGB_to_CMYK {
#   my ($r, $g, $b) = @_;
#   my ($c, $m, $y) = (255-$r, 255-$g, 255-$b);
#   my $k = $c < $m ? ($c < $y ? $c : $y)
#                   : ($m < $y ? $m : $y);  # Minimum
#   for ($c, $m, $y) { $_ -= $k }
#   [$c, $m, $y, $k];
# }
def rgb_to_cmyk(r,g,b):
   c, m, y = 255-r, 255-g, 255-b
   k = min([c,m,y])
   c, m, y = c - k, m - k, y - k
   return c, m, y, k

# my %cache;
# sub RGB_to_CMYK {
#   my ($r, $g, $b) = @_;
#   my $key = join ',', $r, $g, $b;
#   return $cache{$key} if exists $cache{$key};
#   my ($c, $m, $y) = (255-$r, 255-$g, 255-$b);
#   my $k = $c < $m ? ($c < $y ? $c : $y)
#                   : ($m < $y ? $m : $y);  # Minimum
#   for ($c, $m, $y) { $_ -= $k }
#   return $cache{$key} = [$c, $m, $y, $k];
# }
CACHE = {}
def rgb_to_cmyk(r,g,b):
   if (r,g,b) not in CACHE:
       c, m, y = 255-r, 255-g, 255-b
       k = min([c,m,y])
       c, m, y = c - k, m - k, y - k
       CACHE[(r,g,b)] = (c,m,y,k)
   return CACHE[(r,g,b)]


# Compute the number of pairs of rabbits alive in month n
# sub fib {
#    my ($month) = @_;
#    if ($month < 2) { 1 }
#    else {
#        fib($month-1) + fib($month-2);
#    }
# }
def fib(month):
   if month < 2:
       return 1
   else:
       return fib(month - 1) + fib(month - 2)


### 3.2 Inline Caching

# # Compute the number of pairs of rabbits alive in month n
# { my %cache;
#   sub fib {
#     my ($month) = @_;
#     unless (exists $cache{$month}) {
#       if ($month < 2) { $cache{$month} = 1 }
#       else {
#         $cache{$month} = fib($month-1) + fib($month-2);
#       }
#     }
#     return $cache{$month};
#   }
# }
# NOTE: we include the function itself as part of
#       the hash key since python can't do the
#       scoping technique above w/o hackery (AFAIK).
#       Of course the more natural python way
#       would probably be just to use a decorator
CACHE = {}
def fib(month):
   if (fib, month) not in CACHE:
       if month < 2:
           CACHE[(fib, month)] = 1
       else:
           CACHE[(fib, month)] = fib(month - 1) + fib(month - 2)
   return CACHE[(fib, month)]


# sub fib {
#   my %cache;
#   ...
# }
def fib(month):
   CACHE = {}
   ...

### 3.3 Good Ideas

# sub some_function {
#   $result = some computation involving @_;
#   return $result;
# }
def some_function(*x):
   result = some computation involving x
   return result

# { my %cache;
#   sub some_function_with_caching {
#     my $key = join ',', @_;
#     return $cache{$key} if exists $cache{$key};
#     $result = the same computation involving @_;
#     return $cache{$key} = $result;
#   }
# }
CACHE = {}
def some_function_with_caching(*x):
   key = (some_function_with_caching, x)
   if key not in CACHE:
       CACHE[key] = the same computation involving *x
   return CACHE[key]


### 3.4 Memoization

# use Memoize;
# memoize 'fib';
# # Compute the number of pairs of rabbits alive in month n
# sub fib {
#   my ($month) = @_;
#   if ($month < 2) { 1 }
#   else {
#       fib($month-1) + fib($month-2);
#   }
# }
# Just for sake of argument let's pretend we have a "memoize"
# module that provides a memoize decorator
@memoize
def fib(month):
   if month < 2:
       return 1
   else:
       return fib(month - 1) + fib(month - 2)

### 3.5 The Memoize Module

# sub memoize {
#   my ($func) = @_;
#   my %cache;
#   my $stub = sub {
#     my $key = join ',', @_;
#     $cache{$key} = $func->(@_) unless exists $cache{$key};
#     return $cache{$key};
#   };
#   return $stub;
# }

# One reasonable way to do this in python is as a decorator.  To keep
# things simple we'll leave out **kwargs since we can't (simply) use
# dicts as parts of keys.  We also assume for now that args contains
# only things that can be in a dict key
def memoize(func):
   CACHE = {}
   def memoized_func(*args):
       if args not in CACHE:
           CACHE[args] = func(*args)
       return CACHE[args]
   return memoized_func

# NOTE: running the above with fib actually gave
# "RuntimeError: maximum recursion depth exceeded"
# for month = 1000.  But if you do some smaller
# values first to "seed" it it will handle the
# larger values.




#$fastfib = memoize(\&fib);
@memoize
def fib(month):
   ....
# or
# fastfib = memoize(fib)


# sub make_counter {
#   my $n = shift;
#   return sub { print "n is ", $n++ };
# }
# my $x = make_counter(7);
# my $y = make_counter(20);

# We cheat a little here since python's scoping
# won't let's us work with the n directly
def make_counter(n):
   x = [n]
   def counter():
       print "n is", x[0]
       x[0] += 1
   return counter
x = make_counter(7)
y = make_counter(20)


### 3.6 Caveats

# use Memoize;
# sub iota {
#   my $n = shift;
#   return [1 .. $n];
# }
# memoize 'iota';
# $i10 = iota(10);
# $j10 = iota(10);
# pop @$i10;
# print @$j10;
@memoize
def iota(n):
   return range(n)
i10 = iota(10)
j10 = iota(10)
i10.pop()
print j10


# package Octopus;
# sub new {
#   my ($class, %args) = @_;
#   $args{tentacles} = 8;
#   bless \%args => $class;
# }

# sub name {
#   my $self = shift;
#   if (@_) { $self->{name} = shift }
#   $self->{name};
# }

# my $junko = Octopus->new(favorite_food => "crab cakes");
# $junko->name("Junko");
# my $fenchurch = Octopus->new(favorite_food => "crab cakes");
# $fenchurch->name("Fenchurch");

# # This prints "Fenchurch" -- oops!
# print "The name of the FIRST octopus is ", $junko->name, "\n";
class Octopus(object):
   def __init__(self, **kwargs):
       self.tentacles = 8
       self.__dict__.update(kwargs)

   def name(self, new_name=None):
       if new_name != None:
           self.name = new_name
       return self.name

# OK, this one has me stumped.  The text says
# that "new" was memoized, but I'm not seeing it
# Either a typo on the books part or a thinko on mine
# But the lesson about caching mutable items is well taken


#@result = sort { -M $a <=> -M $b } @files;
result = sorted(files, key=(lambda x: os.path.getmtime(x)))


### 3.7 Key Generation

#my $key = join ',', @_;
key = ",".join([str(x) for x in key_list])
# or just use a tuple and avoid problems in the first place
key = tuple(key_list)


# my @args = @_;
# s/([\\,])/\\$1/g for @args;
# my $key = join ",", @args;
key = ",".join([str(x).replace(",","\,").replace("\\","\\\\") for x in key_list])


# sub memoize {
#   my ($func, $keygen) = @_;
#   my %cache;
#   my $stub = sub {
#     my $key = $keygen ? $keygen->(@_) : join ',', @_;
#     $cache{$key} = $func->(@_) unless exists $cache{$key};
#     return $cache{$key};
#   };
#   return $stub;
# }
# There are other ways to do this, but we want
# to stay close to the perl version.  Now
# memoize will need to be invoked as
#@memoize() # need the "()" here
#@memoize(keygen_func)
def memoize(keygen=None):
   CACHE = {}
   def outer_func(func):
       def inner_func(*args):
           key = args
           if keygen:
               key = keygen(args)
           if key not in CACHE:
               CACHE[key] = func(*args)
           return CACHE[key]

       return inner_func
   return outer_func


# sub memoize {


#   my ($func, $keygen) = @_;
#   my %cache;
#   my $stub = $keygen ?
#     sub { my $key = $keygen->(@_);
#           $cache{$key} = $func->(@_) unless exists $cache{$key};
#           return $cache{$key};
#         }
#   :
#     sub { my $key = join ',', @_;
#           $cache{$key} = $func->(@_) unless exists $cache{$key};
#           return $cache{$key};
#         }
#   ;
#   return $stub;
# }
def memoize(keygen=None):
   CACHE = {}
   def outer_func(func):
       def inner_func_no_keygen(*args):
           key = args
           if key not in CACHE:
               CACHE[key] = func(*args)
           return CACHE[key]

       def inner_func_with_keygen(*args):
           key = keygen(args)
           if key not in CACHE:
               CACHE[key] = func(*args)
           return CACHE[key]

       return keygen and inner_func_with_keygen or inner_func_no_keygen
   return outer_func


# $memoized = memoize(\&fib, q{my @args = @_;
#                              s/([\\,])/\\$1/g for @args;
#                              join ',', @args;
#                             });

# sub memoize {
#   my ($func, $keygen) = @_;
#   $keygen ||= q{join ',', @_};
#   my %cache;
#   my $newcode = q{
#     sub { my $key = do { KEYGEN };
#           $cache{$key} = $func->(@_) unless exists $cache{$key};
#           return $cache{$key};
#         }
#   };
#   $newcode =~ s/KEYGEN/$keygen/g;
#   return eval $newcode;
# }

# $keygen ||= 'join \',\', @_';

# my $newcode = "
#   sub { my \$key = do { $keygen };
#         \$cache{\$key} = \$func->(\@_) unless exists \$cache{\$key};
#         return \$cache{\$key};
#       }
# ";


# sub memoize {
#   my ($func, $keygen) = @_;
#   my $keyfunc;
#   if ($keygen eq '') {
#     $keygen = q{join ',', @_}
#   } elsif (UNIVERSAL::isa($keygen, 'CODE')) {
#     $keyfunc = $keygen;
#     $keygen = q{$keyfunc->(@_)};
#   }
#   my %cache;
#   my $newcode = q{
#     sub { my $key = do { KEYGEN };
#           $cache{$key} = $func->(@_) unless exists $cache{$key};
#           return $cache{$key};
#         }
#   };
#   $newcode = ̃ s/KEYGEN/$keygen/g;
#   return eval $newcode;
# }

# if (ref($keygen) eq 'CODE') { ... }

"""
UNCLE!  This seems too far off the path for a sane python translation.
Actually I can think of a way to do it, you just wouldn't, so unless
there is a great public outcry, I will just skip trying to force this
down the python's throat.
"""

# sub example {
#   my %args = @_;
#   $args{A} = 32 unless defined $args{A};
#   $args{B} = 17 unless defined $args{B};
#   # ...
# }
def example(**args):
   args.setdefault("A", 32)
   args.setdefault("B", 17)
   #

# example(C => 99);
# example(C => 99, A => 32);
# example(A => 32, C => 99);
# example(B => 17, C => 99);
# example(C => 99, B => 17);
# example(A => 32, C => 99, B => 17);
# example(B => 17, A => 32, C => 99);
# (etc.)

example(C=99)
example(C=99, A=32)
example(A=32, C=99)
example(B=17, C=99)
example(C=99, B=17)
example(A=32, C=99, B=17)
example(B=17, A=32, C=99)
(etc.)

# NOTE: the problem in python is that
#       we just can't use dicts as a hash
#       otherwise this would be a no brainer


# sub {
#   my %h = @_;
#   $h{A} = 32 unless defined $h{A};
#   $h{B} = 17 unless defined $h{B};
#   join ",", @h{'A','B','C'};
# }
# we give this function a name so that we don't
# have to work around python's lambda limitations
def _keygen(a, h):
   h.setdefault("A", 32)
   h.setdefault("B", 17)
   # a tuple key is probably more natural
   return tuple([x[1] for x in sorted(h.items())])
   # but we can make a string just as simply
   # return ','.join([str(x[1]) for x in sorted(args.items())])

# keygen only has to work over the set of expected values so we can go ahead and
# do something like: 
# have the key be a tuple of (args, kwargs)
# where kwargs has been adapted to a tuple of key,value pair tuples
# BUT now our keygen needs to handle *Both* types of inputs
def memoize(keygen=None):
   CACHE = {}
   def outer_func(func):
       def inner_func(*args, **kwargs):
           kwargs_ = tuple(sorted(kwargs.items()))
           key = (args, kwargs_)
           if keygen:
               key = keygen(args, kwargs)
           if key not in CACHE:
               print "updating cache:", key
               CACHE[key] = func(*args, **kwargs)
           return CACHE[key]

       return inner_func
   return outer_func


# sub example {
#   my ($a, $b, $c) = @_;
#   $a = 32 unless defined $a;
#   $b = 17 unless defined $b;
#   # more calculation here ...
# }
def example(a=32, b=17,c=None):
   # more calculation here ...

# my ($a, $b, $c) = @_;
# $a = 32 unless defined $a;
# $b = 17 unless defined $b;
# join ',', $a, $b, $c;

# first three lines handled by machinery of argument passing in python
return ",".join([str(x) for x in (a,b,c)])


# sub { my $key = do { $_[0] = 32 unless defined $_[0];
#                      $_[1] = 17 unless defined $_[1];
#                      join ',', @_;
#                    };
#       $cache{$key} = $func->(@_) unless exists $cache{$key};
#       return $cache{$key};
#     }

# Hmm... very likely I'm missing a sublety here but
# is seems that python's default args already handles
# this case.  Plus the fact that (if I'm understanding
# correctly), python doesn't map well to the "do { }"
# syntax.  I'll punt for now.


# sub set_to_57 {
#   $_[0] = 57;
# }
# my $x = 119;
# set_to_57($x);

# you can't take advantage of this (or get bit by, depending
# on your perspective) in python, but cause the args are pass
# by value.


# sub safe_function {
#    my ($n) = @_;
#    $n = 57; # does *not* set $x to 57
# }
# my $x = 119;
# safe_function($x);
def safe_function(n):
   n = 57
x = 119
safe_function(x)


# memoize(\&example, q{
#   my ($a, $b, $c) = @_;
#   $a = 32 unless defined $a;
#   $b = 17 unless defined $b;
#   @_ = ($a, $b, $c);         # line 5
#   join ',', @_;
# });
# We avoid sending the keygen function as a string
# since it is too unpythonic.
# Here we are assuming that the arguments are positional
# and "None" if not available.  Usually we would use
# key word args in this situation
def _keygen(args, kwargs):
   print "args=",args,"kwargs=",kwargs
   a = args[0] == None and 32 or args[0]
   b = args[1] == None and 17 or args[1]
   c = args[2]
   return (a,b,c)
   # or return ",".join([str(x) for x in (a,b,c)])

@memoize(_keygen)
def exercise(*args):
   a,b,c = (args + [None]*3)[:3]
   ...


# sub is_in {
#   my ($needle, $haystack) = @_;
#   for my $item (@$haystack) {
#     return 1 if $item == $needle;
#   }
#   return;
# }
def is_in(needle, haystack):
   for item in haystack:
       if item == needle:
           return True
   return False

# if (is_in($my_id, \@employee_ids)) { ... }
if is_in(my_id, employee_ids):
   ...

#sub { join ",", $_[0], @{$_[1]} }
# In python the most obvious solution here
# is again to just use tuple()


# sub find_share {
#   my ($target, $treasures) = @_;
#   return [] if $target == 0;
#   return    if $target < 0 || @$treasures == 0;
#   my ($first, @rest) = @$treasures;
#   my $solution = find_share($target-$first, \@rest);
#   return [$first, @$solution] if $solution;
#   return         find_share($target       , \@rest);
# }


def find_share(target, treasures):
   if target == 0:
       return []
   if target < 0 or len(treasures) == 0:
       return
   first, rest = treasures[0], treasures[1:]
   solution = find_share(target-first, rest)
   if solution != None:
       return [first] + solution
   return find_share(target, rest)



# sub delivery_charge {
#   my ($quantity_ordered) = @_;
#   my ($hour, $day_of_week) = (localtime)[2,6];
#   # perform complex computation involving $weight, $gross_cost,
#   #     $hour, $day_of_week, and $quantity_ordered
#   # ...
#   return $delivery_charge;
# }
import time
def delivery_charge(quantity_ordered):
   localtime = time.localtime()
   hour, day_of_week = localtime[2], localtime[6]
   # perform complex computation involving $weight, $gross_cost,
   #     $hour, $day_of_week, and $quantity_ordered
   # ...
   return delivery_charge


# sub delivery_charge_key {
#   join ',', @_, (localtime)[2,6];
# }
def delivery_charge_key(quantity_ordered):
   localtime = time.localtime()
   return ",".join([str(x) for x in (quantity_ordered,localtime[2], localtime[6])])
   ## or just return (quantity_ordered,localtime[2], localtime[6])


# sub delivery_charge_key {
#   my ($hour, $day_of_week) = (localtime)[2,6];
#   my $weekend = $day_of_week == 0 || $day_of_week == 6;
#   join ',', @_, $hour, $weekend;
# }
def delivery_charge_key(quantity_ordered):
   localtime = time.localtime()
   hour, day_of_week = localtime[2], localtime[6]
   weekend = day_of_week in (0,6)
   return ",".join([str(x) for x in (quantity_ordered, hour, weekend)])
   ## or just return (quantity_ordered, hour, weekend)


### 3.8 Caching in Object Methods


# package Investor;
# # Compute total amount currently invested
# sub total {
#   my $self = shift;
#   # ... complex computation performed here ...
#   return $total;
# }
class Investor(object):
   def total(self):
       # ... complex computation performed here ...
       return total

# # Compute total amount currently invested
# { my %cache;
#   sub total {
#     my $self = shift;
#     return $cache{$self} if exists $cache{$self};
#     # ... complex computation performed here ...
#     return $cache{$self} = $total;
#   }
# }
# One way to simulate this in python would be to
# have a cache "class" variable
class Investor(object):
   _cache = {}
   def total(self):
       # ... complex computation performed here ...\
       key = (self, Investor.total)
       if key not in Investor._cache:
           # ... complex computation performed here ...
           Investor._cache[key] = total
       return Investor._cache[key]


# # here 90,000 is returned from the cache
# $old_total = $old_object->total();
# undef $old_object;
# $new_object = Investor->new();
# $new_total = $new_object->total();
old_total = old_object.total()
del old_object
new_object = Investor()
new_total = new_object.total()

# NOTE: in addition to manually invoked "destroy"
# method recommended in the text, we could
# also have __del__ method, though that might not be
# reliable.  Also could just stick in a unix timestamp
# as part of the key so new objects with same memory location
# won't be confusing


# # Compute total amount currently invested
# sub total {
#   my $self = shift;
#   return $self->{cached_total} if exists $self->{cached_total};
#   # ... complex computation performed here ...
#   return $self->{cached_total} = $total;
# }
def total(self):
   if self.cached_total == None:
       # ... complex computation performed here ...
       self.cached_total = total
   return self.cached_total

# # Compute total amount currently invested
# { my %cache;
#   sub total {
#     my $self = shift;
#     return $cache{$self} if exists $cache{$self};
#     # ... complex computation performed here ...
#     return $cache{$self} = $total;
#   }
#   sub expire_total {
#     my $self = shift;
#     delete $cache{$self};
#   }
# }
# sub invest {
#   my ($self, $amount, ...) = @_;
#   $self->expire_total;
#   ...
# }
class Investor(object):
   _cache = {}
   def total(self):
       # ... complex computation performed here ...\
       key = (self, Investor.total)
       if key not in Investor._cache:
           # ... complex computation performed here ...
           Investor._cache[key] = total
       return Investor._cache[key]


   def expire_total(self):
       key = (self, Investor.total)
       del Investor._cache[key]

   def invest(self, ammount, ...):
       self.expire_total()
       ...


# # Compute total amount currently invested
# sub total {
#   my $self = shift;
#   return $self->{cached_total} if exists $self->{cached_total};
#   # ... complex computation performed here ...
#   return $self->{cached_total} = $total;
# }
# sub invest {
#   my ($self, $amount, ...) = @_;
#   delete $self->{cached_total};
#   ...
# }

def total(self):
   if self.cached_total == None:
       # ... complex computation performed here ...
       self.cached_total = total
   return self.cached_total

def invest(self, amount, ...):
   self.cached_total = None
   ...


# sub memoize_method {
#   my ($method, $key) = @_;
#   return sub {
#     my $self = shift;
#     return $self->{$key} if exists $self->{$key};
#     return $self->{$key} = $method->($self, @_);
#   };
# }
# As a decorator
def memoize_method(key):
   def outter(method):
       def inner(self):
           if self.__dict__.get(key) == None:
               print "cache miss:", method, key, self
               self.__dict__[key] = method(self)
           return self.__dict__[key]
       return inner
   return outter


#*Investor::total = memoize_method(\&Investor::total, 'cached_total');
#$investor_bob->total;

@memoize_method("cached_total")
def total(self):
   ...

investor_bob.total()


# $memoized_total = memoize_method(\&Investor::total, 'cached_total');
# $investor_bob->$memoized_total;

# I suppose you could also use the pre-decorator syntax:

def total(self):
   ...
total = memoize_method("cached_total")(total)

investor_bob.total()




### 3.9 Persistent Caches


# use DB_File;
# sub memoize {
#   my ($func, $keygen, $file) = @_;
#   my %cache;
#   if (defined $file) {
#     tie %cache => 'DB_File', $file, O_RDWR|O_CREAT, 0666
#       or die "Couldn’t access cache file $file: $!; aborting";
#   }
#   my $stub = sub {
#     my $key = $keygen ? $keygen->(@_) : join ',', @_;
#     $cache{$key} = $func->(@_) unless exists $cache{$key};
#     return $cache{$key};
#   };
#   return $stub;
# }
import anydbm

def memoize(keygen=None, cache_file=None):
   if cache_file:
       cache = anydbm.open(cache_file, 'c')
   else:
       cache = {}
   def outer_func(func):
       def inner_func(*args):
           key = str(args)
           if keygen:
               key = keygen(args)
           if key not in cache:
               cache[key] = func(*args)
           return cache[key]

       return inner_func
   return outer_func



# sub memoize {
#     my ($func, $keygen, $cache) = @_;
#     $cache = {} unless defined $cache;
#     my $stub = sub {
#        my $key = $keygen ? $keygen->(@_) : join ',', @_;
#        $cache->{$key} = $func->(@_) unless exists $cache->{$key};
#        return $cache->{$key};
#     };
#     return $stub;
# }
def memoize(keygen=None, cache=None):
   if cache == None:
       cache = {}
   def outer_func(func):
       def inner_func(*args):
           key = str(args)
           if keygen:
               key = keygen(args)
           if key not in cache:
               cache[key] = func(*args)
           return cache[key]

       return inner_func
   return outer_func

### 3.10 Alternatives To Memoization

# @sorted_numbers = sort { $a <=> $b } @numbers;
# This is default behavior for sort
sorted_numbers = sorted(numbers)



# @sorted_numbers = sort numerically @numbers;
# sub numerically { $a <=> $b }
sorted_numbers = sorted(numbers, cmp=numerically)
def numerically(a,b):
   return cmp(a,b)



# @sorted_dates = sort chronologically @dates;

# %m2n =
#    ( jan =>  1, feb =>  2, mar =>  3,
#      apr =>  4, may =>  5, jun =>  6,
#      jul =>  7, aug =>  8, sep =>  9,
#      oct => 10, nov => 11, dec => 12, );

# sub chronologically {
#   my ($am, $ad, $ay) =
#     ($a =~ /(\w{3}) (\d+), (\d+)/);
#   my ($bm, $bd, $by) =
#     ($b =~ /(\w{3}) (\d+), (\d+)/);
#              $ay  <=>         $by
#   || $m2n{lc $am} <=> $m2n{lc $bm}
#   ||         $ad  <=>         $bd;
# }

sorted_dates = sorted(dates, chronologically)

m2n = {
   "jan" : 1,  "feb" : 2,  "mar" : 3,
   "apr" : 4,  "may" : 5,  "jun" : 6,
   "jul" : 7,  "aug" : 8,  "sep" : 9,
   "oct" : 10, "nov" : 11, "dec" : 12
   }

def chronologically(a,b):
   am, ad, ay = re.search("(\w{3}) (\d+), (\d+)", a).groups()
   bm, bd, by = re.search("(\w{3}) (\d+), (\d+)", b).groups()

   return (cmp(int(ay), int(by)) or
           cmp(m2n[am.lower()],  m2n[bm.lower()]) or
           cmp(int(ad), int(bd)))

#     ## or more simply
#     return cmp((int(ay), m2n[am.lower()], int(ad)),
#                (int(by), m2n[bm.lower()], int(bd)))



# @sorted_dates = sort chronologically @dates;
# %m2n =
#    ( jan =>  1, feb =>  2, mar =>  3,
#      apr =>  4, may =>  5, jun =>  6,
#      jul =>  7, aug =>  8, sep =>  9,
#      oct => 10, nov => 11, dec => 12, );
# sub chronologically {
#   my ($am, $ad, $ay) = split_date($a);
#   my ($bm, $bd, $by) = split_date($b);
#              $ay  <=>         $by
#   || $m2n{lc $am} <=> $m2n{lc $bm}
#   ||         $ad  <=>         $bd;
# }
# sub split_date {
#   $_[0] =~ /(\w{3}) (\d+), (\d+)/;
# }


sorted_dates = sorted(dates, chronologically)

m2n = {
   "jan" : 1,  "feb" : 2,  "mar" : 3,
   "apr" : 4,  "may" : 5,  "jun" : 6,
   "jul" : 7,  "aug" : 8,  "sep" : 9,
   "oct" : 10, "nov" : 11, "dec" : 12
   }

def chronologically(a,b):
   am, ad, ay = split_date(a)
   bm, bd, by = split_date(b)

   return (cmp(int(ay), int(by)) or
           cmp(m2n[am.lower()],  m2n[bm.lower()]) or
           cmp(int(ad), int(bd)))

def split_date(dt):
   return re.search("(\w{3}) (\d+), (\d+)", dt).groups()



@sorted_dates = sort chronologically @dates;  COD E L IB RARY
                                            chrono-3
# %m2n =
#    ( jan =>  1, feb =>  2, mar =>  3,
#      apr =>  4, may =>  5, jun =>  6,
#      jul =>  7, aug =>  8, sep =>  9,
#      oct => 10, nov => 11, dec => 12, );

# sub chronologically {
#   date_to_string($a) cmp date_to_string($b)
# }

# sub date_to_string {
#   my ($m, $d, $y) = ($_[0] =~ /(\w{3}) (\d+), (\d+)/);
#   sprintf "%04d%02d%02d", $y, $m2n{lc $m}, $d;
# }

m2n = {
   "jan" : 1,  "feb" : 2,  "mar" : 3,
   "apr" : 4,  "may" : 5,  "jun" : 6,
   "jul" : 7,  "aug" : 8,  "sep" : 9,
   "oct" : 10, "nov" : 11, "dec" : 12
   }

def chronologically(a,b):
   return cmp(date_to_string(a), date_to_string(b))

def date_to_string(dt):
   m, d, y = re.search("(\w{3}) (\d+), (\d+)", dt).groups()
   return "%04d%02d%02d" % (int(y), m2n[m.lower()], int(d))

# { my %cache;
#   sub chronologically {
#     ($cache{$a} ||= date_to_string($a))
#        cmp
#     ($cache{$b} ||= date_to_string($b))
#   }
# }
# In python we can't do the scope trick with cache
# but we ignore that for now
CACHE = {}
def chronologically(a, b):
   if a not in CACHE:
       CACHE[a] = date_to_string(a)
   if b not in CACHE:
       CACHE[b] = date_to_string(b)

   return cmp(CACHE[a], CACHE[b])


# { my %cache;
#   sub by_total_invested {
#     ($cache{$a} ||= total_invested($a))
#        <=>
#     ($cache{$b} ||= total_invested($b))
#   }
# }
CACHE = {}
def by_total_invested(a,b):
   if not CACHE.get(a):
       CACHE[a] = total_invested(a)
   if not CACHE.get(b):
       CACHE[b] = total_invested(b)

   return cmp(CACHE[a], CACHE[b])


# { my %cache;
#   sub by_total_invested {
#    (exists $cache{$a} ? $cache{$a} : ($cache{$a} = total_invested($a)))
#        <=>
#    (exists $cache{$b} ? $cache{$b} : ($cache{$b} = total_invested($b)))
#   }
# }
CACHE = {}
def by_total_invested(a,b):
   if a not in CACHE:
       CACHE[a] = total_invested(a)
   if b not in CACHE:
       CACHE[b] = total_invested(b)

   return cmp(CACHE[a], CACHE[b])

# { my %cache;
#   sub by_total_invested {
#     ($cache{$a} ||= total_invested($a) || "0e0")
#        <=>
#     ($cache{$b} ||= total_invested($b) || "0e0")
#   }
# }
# I can't think of a reason to try to emulate this trick
# (or how, frankly)

### 3.11 Evangelism

### 3.12 The Benefits of Speed

# sub function {
#   if (++$CALLS == 100) { memoize 'function'}
#   ...
# }
def function():
   CALL += 1
   if CALLS == 100:
       function = memoize(function)
   ...

# use Time::HiRes 'time';
# my (%time, %calls);
# sub profile {
#   my ($func, $name) = @_;
#   my $stub = sub {
#     my $start = time;
#     my $return = $func->(@_);
#     my $end = time;
#     my $elapsed = $end - $start;
#     $calls{$name} += 1;
#     $time{$name} += $elapsed;
#     return $return;
#   };
#   return $stub;
# }
# This is another good case for a decorator
import time
time_ = {}
calls = {}
def profile(func):
   calls.setdefault(func.__name__, 0)
   time_.setdefault(func.__name__, 0)
   def stub(*args):
       start = time.time()
       return_ = func(*args)
       end = time.time()
       elapsed = end - start
       calls[func.__name__] += 1
       time_[func.__name__] += elapsed
       return return_
   return stub

@profile
def foo(x):
   return x

# END {
#   printf STDERR "%-12s %9s %6s\n", "Function", "# calls", "Elapsed";
#   for my $name (sort {$time{$b} <=> $time{$a}} (keys %time)) {
#     printf STDERR "%-12s %9d %6.2f\n", $name, $calls{$name}, $time{$name};
#   }
# }
print >>sys.stderr, "%-12s %9s %6s\n" % ("Function", "# calls", "Elapsed")
for name, _time in sorted(time_.items(), key=lambda x: x[1]):
   print >>sys.stderr, "%-12s %9d %6.2f\n" % (name, calls[name], time_[name])

99 problems - python - 57

2009-01-18T13:45:00.000-08:00

Binary search trees (dictionaries)

Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers.


# Example:

# * construct([3,2,5,7,1],T).
# T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))

# Then use this predicate to test the solution of the problem P56.

# Example:

# * test-symmetric([5,3,18,1,4,12,21]).
# Yes
# * test-symmetric([3,2,5,7,1]).
# No
def construct(nums):
    if not nums:
        return None
    ordered_nums = sorted(nums)
    center_index = (len(nums) / 2) 
    return (ordered_nums[center_index], construct(ordered_nums[:center_index]), construct(ordered_nums[center_index+1:]))

def test_symmetric(nums):
    return symmetric_binary_tree(construct(nums))

Higher Order Perl (Python Style) : Chapter 2

2009-01-14T20:46:00.000-08:00


#
# Dispatch Tables
#

# sub read_config {
#   my ($filename) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     chomp;
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     if ($directive eq 'CHDIR') {
#       chdir($rest) or die "Couldn't chdir to '$rest': $!; aborting";
#     } elsif ($directive eq 'LOGFILE') {
#       open STDERR, ">>", $rest
#         or die "Couldn't open log file '$rest': $!; aborting";
#     } elsif ($directive eq 'VERBOSITY') {
#       $VERBOSITY = $rest;
#     } elsif ($directive eq ...) {
#       ...
#     } ...
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename):
    global VERBOSITY
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        try:
            if directive == "CHDIR":
                os.chdir(rest)
            elif directive == "LOGFILE":
                sys.stderr = file(rest, "w")
            elif directive == "VERBOSITY":
                VERBOSITY = rest
            elif directive == ...:
                ...
            else:
                sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
        except StandardError, why:
            sys.exit(why)
    return 1 # success


# sub read_config {                               
#   my ($filename, $actions) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     chomp;
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     if (exists $actions->{$directive}) {
#       $actions->{$directive}->($rest);
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename, actions):
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        if directive in actions:
            actions[directive](rest)
        else:
            sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
    return 1 # success

# $dispatch_table =
# { CHDIR      => \&change_dir,
#   LOGFILE    => \&open_log_file,
#   VERBOSITY  => \&set_verbosity,
#   ...        =>  ...,
# };
dispatch_table = {
    "CHDIR"     : change_dir,
    "LOGFILE"   : open_log_file,
    "VERBOSITY" : set_verbosity,
    ...         : ...,
    }

# sub change_dir {
#   my ($dir) = @_;
#   chdir($dir)
#     or die "Couldn't chdir to '$dir': $!; aborting";
# }
# sub open_log_file {
#   open STDERR, ">>", $_[0]
#     or die "Couldn't open log file '$_[0]': $!; aborting";
# }
# sub set_verbosity {
#   $VERBOSITY = shift
# }
def change_dir(dir):
    try:
        os.chdir(dir)
    except OSError, why:
        sys.exit(why)        
def open_log_file(log_file):
    try:
        sys.stderr = file(log_file, "w")
    except OSError, why:
        sys.exit(why)
def set_verbosity(verbosity):
    global VERBOSITY
    VERBOSITY = verbosity

# $dispatch_table =
#   { CHDIR      => sub { my ($dir) = @_;
#                        chdir($dir) or
#                          die "Couldn't chdir to '$dir' $!; aborting";
#                                                       :
#                       },
#     LOGFILE    => sub { open STDERR, ">>", $_[0] or
#                           die "Couldn't open log file '$_[0]': $!; aborting";
#                       },
#     VERBOSITY  => sub { $VERBOSITY = shift },
#     ...        => ...,
# };

# This doesn't map well since lambda doesn't allow
# statements. 


# 'DEFINE' => \&define_config_directive,
"DEFINE" : define_config_directive,

# sub define_config_directive {
#   my $rest = shift;
#   $rest =~ s/∧ \s+//;
#   my ($new_directive, $def_txt) = split /\s+/, $rest, 2;
#   if (exists $CONFIG_DIRECTIVE_TABLE{$new_directive}) {
#     warn "$new_directive already defined; skipping.\n";
#     return;
#   }
#   my $def = eval "sub { $def_txt }";
#   if (not defined $def) {
#     warn "Could not compile definition for '$new_directive': $@; skipping.\n";
#     return;
#   }
#   $CONFIG_DIRECTIVE_TABLE{$new_directive} = $def;
# }

def define_config_directive(rest):
    rest = rest.strip()
    new_directive, def_txt = rest.split(None, 1)

    if new_directive in CONFIG_DIRECTIVE_TABLE:
        print "%s already defined; skipping." % new_directive
        return

    try:
        _def = eval("""lambda x: %s""" % def_txt)
    except StandardError, why:
        print "Could not compile definition for '%s': %s" % (new_directive, why)
        return

    CONFIG_DIRECTIVE_TABLE[new_directive] = _def

    
# This doesn't map well to the python way of doing things since
# lambdas are sort of limited.  Instead we would
# probably just define the functions with a name directly.
# On the other hand if you really must doing everything "lambda style"
# you can probably get farther than you'd first guess with clever uses
# of and/or connectors in your lambda expression


# sub read_config {
#   my ($filename, $actions) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     chomp;
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     if (exists $actions->{$directive}) {
#       $actions->{$directive}->($rest, $actions);
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename, actions):
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        if directive in actions:
            actions[directive](rest, actions)
        else:
            sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
    return 1 # success


# sub define_config_directive {
#   my ($rest, $dispatch_table) = @_;
#   $rest =~ s/∧ \s+//;
#   my ($new_directive, $def_txt) = split /\s+/, $rest, 2;
#   if (exists $dispatch_table->{$new_directive}) {
#     warn "$new_directive already defined; skipping.\n";
#     return;
#   }
#   my $def = eval "sub { $def_txt }";
#   if (not defined $def) {
#     warn "Could not compile definition for '$new_directive': $@; skipping.\n";
#     return;
#   }
#   $dispatch_table->{$new_directive} = $def;
# }
def define_config_directive(rest, dispatch_table):
    rest = rest.strip()
    new_directive, def_txt = rest.split(None, 1)

    if new_directive in dispatch_table:
        print "%s already defined; skipping." % new_directive
        return

    try:
        _def = eval("""lambda x: %s""" % def_txt)
    except StandardError, why:
        print "Could not compile definition for '%s': %s" % (new_directive, why)
        return

    dispatch_table[new_directive] = _def



# sub read_config {
#   my ($filename, $actions, $user_param) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     if (exists $actions->{$directive}) {
#       $actions->{$directive}->($rest, $user_param, $actions);
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename, actions, user_param):
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        if directive in actions:
            actions[directive](rest, user_param, actions)
        else:
            sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
    return 1 # success

#read_config($filename, $dispatch_table, \@dirs);
read_config(filename, dispatch_table, dirs)

#read_config($filename, $dispatch_table, []);
read_config(filename, dispatch_table, [])


# sub read_config {
#   my ($filename, $actions, $user_param) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     if (exists $actions->{$directive}) {
#       $actions->{$directive}->($directive, $rest, $actions, $user_param);
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename, actions, user_param):
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        if directive in actions:
            actions[directive](directive, rest, user_param, actions)
        else:
            sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
    return 1 # success


# sub set_var {
#   my ($var, $val) = @_;
#   $$var = $val;
# }
# OK, this is pretty unnatural at this point
# we would almost certianly work instead with a
# global or passed in dictionary
# (not tested)
def set_var(var, val):
    exec "global %s" % var
    exec "%s = %r" % (var, val)


# sub set_var {
#   my ($var, $val, undef, $config_hash) = @_;
#   $config_hash->{$var} = $val;
# }
def set_var(var, val, _, config_hash):
    config_hash[var] = val



# sub open_input_file {
#   my ($handle, $filename) = @_;
#   unless (open $handle, $filename) {
#     warn "Couldn't open $handle file '$filename': $!; ignoring.\n";
#   }
# }
# yet more unnatural hackery (not tested)
# again, we'd probably work with a global or passed in dictionary
def open_input_file(handle, filename):
    exec "global %s" % handle
    exec """
try:
    %s = file('%s')
except StandardError, why:
    print "Counldn't open %s file '%s': %%s; ignoring." %% why
return """ % (handle, filename, handle, filename)
    

# sub read_config {
#   my ($filename, $actions, $userparam) = @_;
#   open my($CF), $filename or return; # Failure
#   while (<$CF>) {
#     chomp;
#     my ($directive, $rest) = split /\s+/, $_, 2;
#     my $action = $actions->{$directive} || $actions->{_DEFAULT_};
#     if ($action) {
#       $action->($directive, $rest, $actions, $userparam);
#     } else {
#       die "Unrecognized directive $directive on line $. of $filename; aborting";
#     }
#   }
#   return 1; # Success
# }
def read_config(filename, actions, user_param):
    for i, line in enumerate(file(filename)):
        line = line.strip()
        directive, rest = line.split(None, 1)
        action = actions[directive] or actions["__DEFAULT__"]
        if action:
            action[directive](directive, rest, user_param, actions)
        else:
            sys.exit("Unrecognized directive %s in line %s of %s; aborting" % (directive, i, filename))
    return 1 # success

# sub no_such_directive {
#   my ($directive) = @_;
#   warn "Unrecognized directive $directive at line $.; ignoring.\n";
# }
# python doesn't have a trivial way to get the line number
# so we leave that out, but may get close with inspect
def no_such_directive(directive):
    print "Unrecognized directive %s; ignoring." % directive

# sub no_such_directive {
#   my ($bad, $rest, $table) = @_;
#   my ($best_match, $best_score);
#   for my $good (keys %$table) {
#     my $score = score_match($bad, $good);
#     if ($score > $best_score) {
#       $best_score = $score;
#       $best_match = $good;
#     }
#   }
#   warn "Unrecognized directive $bad at line $.;\n";
#   warn "\t(perhaps you meant $best_match?)\n";
# }
def no_such_directive(bad, rest, table):
    best_match = None
    best_score = 0
    
    for good in table:
        score = score_match(bad, good)
        if score > best_score:
            best_score = score
            best_match = good

    print "Unrecognized directive %s." % bad
    print "\t(perhaps you meant %s?)" % best_match


# $address_actions =
#   { _DEFAULT_ => sub { my ($id, $addr, $act, $aref) = @_;
#                        push @$aref, [$id, $addr];
#                      },
#   };
# read_config($ADDRESS_FILE, $address_actions, \@address_array);
address_actions = {
    "__DEFAULT__" : lambda id, addr, act, aref: aref.append([id, addr])
    }
read_config(ADDRESS_FILE, address_actions, address_array)


# my $result = evaluate($ARGV[0]);
# print "Result: $result\n";
# sub evaluate {
#   my @stack;
#   my ($expr) = @_;
#   my @tokens = split /\s+/, $expr;
#   for my $token (@tokens) {
#     if ($token =~ /∧ \d+$/) { # It's a number
#       push @stack, $token;
#     } elsif ($token eq '+') {
#        push @stack, pop(@stack) + pop(@stack);
#     } elsif ($token eq '-') {
#        my $s = pop(@stack);
#        push @stack, pop(@stack) - $s
#     } elsif ($token eq '*') {
#        push @stack, pop(@stack) * pop(@stack);
#     } elsif ($token eq '/') {
#        my $s = pop(@stack);
#        push @stack, pop(@stack) / $s
#     } else {
#       die "Unrecognized token '$token'; aborting";
#     }
#    }
#   return pop(@stack);
# }
result = evaluate(sys.argv[1])
print "Result: %s" % result
def evaluate(expr):
    stack = []
    tokens = expr.split()
    for token in tokens:
        if token.isdigit():
            stack.insert(0, int(token))
        elif token == "+":
            stack.insert(0, (stack.pop(0) + stack.pop(0)))
        elif token == "-":
            s = stack.pop(1)
            stack.insert(0, (stack.pop(0) - s))
        elif token == "*":
            stack.insert(0, (stack.pop(0) * stack.pop(0)))
        elif token == "/":
            s = stack.pop(1)
            stack.insert(0, (stack.pop(0) / s))
        else:
            sys.exit("Unrecognized toke '%s'; aborting" % token)
    return stack.pop(0)



# my @stack;
# my $actions = {
#   '+' => sub { push @stack, pop(@stack) + pop(@stack) },
#   '*' => sub { push @stack, pop(@stack) * pop(@stack) },
#   '-' => sub { my $s = pop(@stack); push @stack, pop(@stack) - $s },
#   '/' => sub { my $s = pop(@stack); push @stack, pop(@stack) / $s },
#   'NUMBER' => sub { push @stack, $_[0] },
#   '_DEFAULT_' => sub { die "Unrecognized token '$_[0]'; aborting" }
# };
# my $result = evaluate($ARGV[0], $actions);
# print "Result: $result\n";
# sub evaluate {
#   my ($expr, $actions) = @_;
#   my @tokens = split /\s+/, $expr;
#
#   for my $token (@tokens) {
#     my $type;
#     if ($token =~ /∧ \d+$/) { # It's a number
#       $type = 'NUMBER';
#     }
#     my $action = $actions->{$type}
#               || $actions->{$token}
#               || $actions->{_DEFAULT_};
#     $action->($token, $type, $actions);
#   }
#   return pop(@stack);
# }
stack = []
actions = {
    "+" : (lambda *x: stack.insert(0,  stack.pop(0)    + stack.pop(0))),
    "-" : (lambda *x: stack.insert(0, -stack.pop(0)    + stack.pop(0))),
    "*" : (lambda *x: stack.insert(0,  stack.pop(0)    * stack.pop(0))),
    "/" : (lambda *x: stack.insert(0, (1/stack.pop(0)) * stack.pop(0))),
    "NUMBER" : (lambda *x: stack.insert(0, int(x[0]))),
    "__DEFAULT__" : (lambda *x: sys.exit("Unrecognized token '%s'; aborting" % x[0]))
}

result = evaluate(sys.argv[1], actions)
print "Result: %s" % result
def evaluate(expr, actions):
    tokens = expr.split()

    for token in tokens:
        type = None
        if token.isdigit():
            type = "NUMBER"
        action = actions.get(type or token) or actions["__DEFAULT__"]
        action(token, type, actions)
    return stack.pop(0)


#sqrt' => sub { push @stack, sqrt(pop(@stack)) },
"sqrt" : (lambda *x: stack.insert(0, math.sqrt(stack.pop(0))))

# my $actions = {
#   'NUMBER'    => sub { push @stack,   $_[0] },
#   '_DEFAULT_' => sub { my $s = pop(@stack);
#                        push @stack,
#                           [ $_[0], pop(@stack), $s ]
#                        },
# };
actions = {
    "NUMBER" : (lambda *x: stack.insert(0, int(x[0]))),
    "__DEFAULT__" : (lambda *x: stack.insert(0, [x[0], stack.pop(1), stack.pop(0)]))
}


# sub AST_to_string {
#   my ($tree) = @_;
#   if (ref $tree) {
#     my ($op, $a1, $a2) = @$tree;
#     my ($s1, $s2) = (AST_to_string($a1),
#                      AST_to_string($a2));
#     "($s1 $op $s2)";
#   } else {
#     $tree;
#   }
# }
def AST_to_string(tree):
    if tree:
        op, a1, a2 =  tree
        s1, s2 = AST_to_string(a1), AST_to_string(a2)
        return "%s %s %s" % (s1, op, s2)
    else:
        return tree

# sub elementfunc {
#   my $table = { h1        => sub { shift; my $text = join '', @_;
#                                    print $text; return $text ;
#                                  }
#                 _DEFAULT_ => sub { shift; my $text = join '', @_;
#                                               return $text ;
#               };
#   my ($element) = @_;
#   my $tag = $element->{_tag};
#   my $action = $table->{$tag} || $table{_DEFAULT_};
#   return $action->(@_);
# }
def elementfunc(element):
    table = {"h1"          : (lambda html, results: "".join(results)),
             "__DEFAULT__" : (lambda html, results: "".join(results))}

    tag = element["_tag"]
    action = table.get(tag) or table["__DEFAULT__"]
    return action(element)



# sub walk_html {
#   my ($html, $textfunc, $elementfunc_table) = @_;
#   return $textfunc->($html) unless ref $html; # It's a plain string
#   my ($item, @results);
#   for $item (@{$html->{_content}}) {
#     push @results, walk_html($item, $textfunc, $elementfunc_table);
#   }
#   my $tag = $html->{_tag};
#   my $elementfunc = $elementfunc_table->{$tag}
#                  || $elementfunc_table->{_DEFAULT_}
#                  || die "No function defined for tag '$tag'";
#   return $elementfunc->($html, @results);
# }
def walk_html(html, textfunc, elementfunc_table):
    if type(html) == str:
        return textfunc(html)

    results = []
    for item in html["_content"]:
        results.append(walk_html(item, textfunc, elementfunc_table))
    
    tag = html["_tag"]
    elementfunc = elementfunc_table.get(tag) or elementfunc_table.get("__DEFAULT__")
    if not elementfunc:
        sys.exit("No function defined for tag '%s'" % tag)
    return elementfunc(html, results)


# sub walk_html {
#   my ($html, $textfunc, $elementfunc, $userparam) = @_;
#   return $textfunc->($html, $userparam) unless ref $html;
#   my ($item, @results);
#   for $item (@{$html->{_content}}) {
#     push @results, walk_html($item, $textfunc, $elementfunc, $userparam);
#   }
#   return $elementfunc->($html, $userparam, @results);
# }
def walk_html(html, textfunc, elementfunc, userparam):
    if type(html) == str:
        return textfunc(html)

    results = []
    for item in html["_content"]:
        results.append(walk_html(item, textfunc, elementfunc, userparam))

    return elementfunc(html, results, userparam)
        
# walk_html($html_text,
#  # $textfunc
#  sub { my ($text, $aref) = @_;
#        push @$aref, $text },
#  # $elementfunc does nothing
#  sub { },
#  # user parameter
#  \@text_array
# );
def walk_html(html_text,
              lambda text, aref: aref.append(text),
              lambda x,y: [],
              text_array)

Higher Order Perl (Python Style) : Chapter 1

2009-01-14T20:44:00.000-08:00


#
# Recursion and Callbacks
#

# sub binary {
#   my ($n) = @_;
#   return $n if $n == 0 || $n == 1;

#   my $k = int($n/2);
#   my $b = $n % 2;

#   my $E = binary($k);

#   return $E . $b;
# }
def binary(n):
    if n in (0,1):
        return str(n)

    k = n / 2
    b = n % 2

    return binary(k) + str(b)


# sub factorial {
#   my ($n) = @_;
#   return factorial($n-1) * $n;
# }
def factorial(n):
    return factorial(n-1) * n


# sub factorial {
#   my ($n) = @_;
#   return 1 if $n == 0;
#   return factorial($n-1) * $n;
# }
def factorial(n):
    if n == 0:
        return 1
    return factorial(n-1) * n

# sub hanoi {
#   my ($n, $start, $end, $extra) = @_;
#   if ($n == 1) {
#     print "Move disk #1 from $start to $end.\n";  # Step 1
#   } else {
#     hanoi($n-1, $start, $extra, $end);            # Step 2
#     print "Move disk #$n from $start to $end.\n"; # Step 3
#     hanoi($n-1, $extra, $end, $start);            # Step 4
#   }
# }
def hanoi(n, start, end, extra):
    if n == 1:
        print "Move disk #1 from %(start)s to %(end)s." % locals()
    else:
        hanoi(n-1, start, extra, end)
        print "Move disk #%(n)s from %(start)s to %(end)s." % locals()
        hanoi(n-1, extra, end, start)
        


# sub hanoi {
#   my ($n, $start, $end, $extra, $move_disk) = @_;
#   if ($n == 1) {
#     $move_disk->(1, $start, $end);
#   } else {
#     hanoi($n-1, $start, $extra, $end, $move_disk);
#     $move_disk->($n, $start, $end);
#     hanoi($n-1, $extra, $end, $start, $move_disk);
#   }
# }
def hanoi(n, start, end, extra, move_disk):
    if n == 1:
        move_disk(1, start, end)
    else:
        hanoi(n-1, start, extra, end, move_disk)
        move_disk(n, start, end)
        hanoi(n-1, extra, end, start, move_disk)
    

# sub print_instruction {
#   my ($disk, $start, $end) = @_;
#   print "Move disk #$disk from $start to $end.\n";
# }
# hanoi(3, 'A', 'C', 'B', \&print_instruction);
def print_instruction(disk, start, end):
    print "Move disk %(disk)s from %(start)s to %(end)s" % locals()

hanoi(3, "A", "C", "B", print_instruction)




# @position = ('', ('A') x 3); # Disks are all initially on peg A

# sub check_move {
#     my $i;
#     my ($disk, $start, $end) = @_;

#     if ($disk < 1 || $disk > $#position) {
#        die "Bad disk number $disk. Should be 1..$#position.\n";
#     }

#     unless ($position[$disk] eq $start) {
#        die "Tried to move disk $disk from $start, but it is on peg
#                                                       $position[$disk].\n";
#     }

#     for $i (1 .. $disk-1) {
#        if ($position[$i] eq $start) {
#            die "Can't move disk $disk from $start because $i is on top of it.\n";
#        } elsif ($position[$i] eq $end) {
#            die "Can't move disk $disk to $end because $i is already there.\n";
#        }
#     }

#     $position[$disk] = $end;
# }

# hanoi(3, 'A', 'C', 'B', \&check_move);
position = [""] + ["A"] * 3

def check_move(disk, start, end):
    if disk < 1 or disk > len(position) - 1:
        sys.exit("Bad disk number %s. Should be 1..%s" % (disk, len(position)-1))

    if position[disk] != start:
        sys.exit("Tried to move disk %s from %s, but it is on peg %s" % (disk, start, position[disk]))

    for i in range(1, disk):
        if position[i] == start:
            sys.exit("Can't move disk %s from %s because %s is on top of it." % (disk, start, i))
        elif position[i] == end:
            sys.exit("Can't move disk %s to %s because %s is already there." % (disk, end, i))

    position[disk] = end
    print position

hanoi(3, "A", "C", "B", check_move)




# sub total_size {
#    my ($top) = @_;
#    my $total = -s $top;

#    return $total if -f $top;
#    unless (opendir DIR, $top) {
#       warn "Couldn’t open directory $top: $!; skipping.\n";
#       return $total;
#    }

#    my $file;
#    while ($file = readdir DIR) {
#      next if $file eq '.' || $file eq '..';
#      $total += total_size("$top/$file");
#    }

#    closedir DIR;
#    return $total;
# }

# NOTE: in python you'd probably prefer
#       os.walk
# ALSO: it would be unnatural to duplicate the 
#       buggy first version of this function so we'll
#       just be satisfied with it working. :) 
def total_size(top):
    total = os.path.getsize(top)

    if os.path.isfile(top):
        return total

    try:
        for filename in os.listdir(top):
            total += total_size(os.path.join(top, filename))
    except OSError:
        print "Couldn't open directory: %s; skipping." % top
        return total
    return total

# sub dir_walk {
#   my ($top, $code) = @_;
#   my $DIR;
#   $code->($top);
#   if (-d $top) {
#     my $file;
#     unless (opendir $DIR, $top) {
#       warn "Couldn’t open directory $top: $!; skipping.\n";
#       return;
#     }
#     while ($file = readdir $DIR) {
#       next if $file eq '.' || $file eq '..';
#       dir_walk("$top/$file", $code);
#     }
#   }
# }

# the traditional python way would be to use os.walk()
def dir_walk(top, code):
    code(top)
    
    if os.path.isdir(top):
        try:
            for filename in os.listdir(top):
                dir_walk(os.path.join(top, filename), code)
        except OSError:
            print "Couldn't open directory: %s; skipping." % top


        
# sub print_dir {
#   print $_[0], "\n";
# }
def print_dir(x):
    print x

#dir_walk('.', sub { printf "%6d %s\n", -s $_[0], $_[0] } );
dir_walk('.', lambda x: sys.stdout.write("%6d %s\n" % (os.path.getsize(x), x)))

#dir_walk('.', sub { print $_[0], "\n" if -l $_[0] && ! -e $_[0] });
dir_walk('.', lambda x: (os.path.islink(x) and os.path.exists(os.readlink(x)) and sys.stdout.write("%s\n" % x)))

# my $TOTAL = 0;
# dir_walk('.', sub { $TOTAL += -s $_[0] });
# print "Total size is $TOTAL.\n";

# can't run += or global w/in lambda
total = 0
def accumulate(x):
    global total
    total += os.path.getsize(x)
dir_walk('.', accumulate)
print "Total size is %s." % total


# sub dir_walk { 
#   my ($top, $filefunc, $dirfunc) = @_;
#   my $DIR;
#   if (-d $top) {
#     my $file;
#     unless (opendir $DIR, $top) {
#       warn "Couldn’t open directory $code: $!; skipping.\n";
#       return;
#     }
#     my @results;
#     while ($file = readdir $DIR) {
#       next if $file eq '.' || $file eq '..';
#       push @results, dir_walk("$top/$file", $filefunc, $dirfunc);
#     }
#     return $dirfunc->($top, @results);
#   } else {
#     return $filefunc->($top);
#   }
# }

# sub file_size { -s $_[0] }

# sub dir_size {
#   my $dir = shift;
#   my $total = -s $dir;
#   my $n;
#   for $n (@_) { $total += $n }
#   return $total;
# }

# $total_size = dir_walk('.', \&file_size, \&dir_size);
def dir_walk(top, filefunc, dirfunc):
    if os.path.isdir(top):
        results = []
        try:
            for filename in os.listdir(top):
                results.append(dir_walk(os.path.join(top, filename), filefunc, dirfunc))
        except OSError:
            print "Couldn't open directory: %s; skipping." % top
            return
        return dirfunc(top, results)
    else:
        return filefunc(top)

def file_size(x):
    return os.path.getsize(x)

def dir_size(d, accum):
    _dirsize = os.path.getsize(d)
    total = _dirsize + sum(accum)
    return total

# sub dir_size {
#   my $dir = shift;
#   my $total = -s $dir;
#   my $n;
#   for $n (@_) { $total += $n }
#   printf "%6d %s\n", $total, $dir;
#   return $total;
# }
def dir_size(d, accum):
    _dirsize = os.path.getsize(d)
    total = _dirsize + sum(accum)
    print "%6d %ss" % (total, d)
    return total




# sub file {
#   my $file = shift;
#   [short($file), -s $file];
# }
# sub short {
#   my $path = shift;
#   $path = ̃ s{.*/}{};
#   $path;
# }


def _file(x):
    return os.path.basename(x), os.path.getsize(x)

# sub dir {
#   my ($dir, @subdirs) = @_;
#   my %new_hash;
#   for (@subdirs) {
#     my ($subdir_name, $subdir_structure) = @$_;
#     $new_hash{$subdir_name} = $subdir_structure;
#   }
#   return [short($dir), \%new_hash];
# }
def _dir(dir, subdirs):
    new_hash = {}
    for subdir_name, subdir_structure in subdirs:
        new_hash[subdir_name] = subdir_structure
    return os.path.basename(dir), new_hash


# sub print_filename { print $_[0], "\n" }
# dir_walk('.', \&print_filename, \&print_filename);

# we add a result parameter so that the function
# can work as dirfunc
def print_filename(x, result=None):
    print x
dir_walk(".", print_filename, print_filename)


# sub dangles {
#   my $file = shift;
#   print "$file\n" if -l $file && ! -e $file;
# }
# dir_walk('.', \&dangles, sub {});
def dangles(x):
    if os.path.islink(x) and not os.path.exists(os.readlink(x)):
        print x
dir_walk('.', dangles, lambda x,y: ())



# sub dir_walk {
#   my ($top, $filefunc, $dirfunc) = @_;
#   my $DIR;
#   if (-d $top) {
#     my $file;
#     unless (opendir $DIR, $top) {
#       warn "Couldn’t open directory $top: $!; skipping.\n";
#       return;
#     }
#     my @results;
#     while ($file = readdir $DIR) {
#       next if $file eq '.' || $file eq '..';
#       push @results, dir_walk("$top/$file" $filefunc, $dirfunc);
#                                           ,
#     }
#     return $dirfunc ? $dirfunc->($top, @results) : () ;
#   } else {
#     return $filefunc ? $filefunc->($top): () ;
#   }
# }


def dir_walk(top, filefunc=None, dirfunc=None):
    if os.path.isdir(top):
        results = []
        try:
            for filename in os.listdir(top):
                results.append(dir_walk(os.path.join(top, filename), filefunc, dirfunc))
        except OSError:
            print "Couldn't open directory: %s; skipping." % top
            return
        return dirfunc and dirfunc(top, results)
    else:
        return filefunc and filefunc(top)


#@all_plain_files = dir_walk('.', sub { $_[0] }, sub { shift; return @_ });
all_plain_files = dir_walk(".", lambda x: x, lambda x, y: y)


# { _tag => "p",
#   _content => [ "But I don't ",
#                 { _tag => "font",
#                   _content => [ "want" ],
#                   color => "red",
#                   size => 3,
#                 },
#                 " to go to bed now!",
#                 ],
# }

# so I'm going to punt on this.  I believe I could
# probably get something usefully similar from
# BeautifulSoup or lxml but I don't really
# want to vary from the original perl code *too* much
# so I'll just use a hardcoded dict representation
# and see how far I get with that.
tree =  { "_tag"      : "(document)",
          "_content" : [{"_tag" : "h1",
                         "_content" : [ "What Junior Said Next",
                                     ],                    
                         },
                        "\n\n",
                        {"_tag" : "p",
                         "_content" : [ "But I don't ",
                                        { "_tag" : "font",
                                          "_content" : [ "want" ],
                                          "color" : "red",
                                          "size" : 3,
                                          },
                                        " to go to bed now!",
                                        ],
                         }
                        ]
          }   
# sub untag_html {
#   my ($html) = @_;
#   return $html unless ref $html;   # It’s a plain string
#   my $text = '';
#   for my $item (@{$html->{_content}}) {
#     $text .= untag_html($item);
#   }
#   return $text;
# }
def untag_html(html):
    if type(html) != dict:
        return html

    text = ""
    for item in html["_content"]:
        text += untag_html(item)
    return text

# sub walk_html {
#   my ($html, $textfunc, $elementfunc) = @_;
#   return $textfunc->($html) unless ref $html; # It’s a plain string
#   my @results;
#   for my $item (@{$html->{_content}}) {
#     push @results, walk_html($item, $textfunc, $elementfunc);
#   }
#   return $elementfunc->($html, @results);
# }
# we are going to cheat hear a little and also
# pass around a concatenator function
# since perl's "push" function has some 
# "magic" properties that don't map well to python
def appender(accum, item):
    accum.append(item)
def extender(accum, item):
    accum.extend(item)
def walk_html(html, textfunc, elementfunc, 
              concatenator=appender):
    if type(html) == str:
        return textfunc(html)

    results = []
    for item in html["_content"]:
        concatenator(results, walk_html(item, textfunc, elementfunc, concatenator))

    return elementfunc(html, results)

# walk_html($tree, sub { $_[0] },
#                  sub { shift; join '', @_ });
walk_html(tree, lambda x: x, lambda x,y: "".join(y))

# sub print_if_h1tag {
#   my $element = shift;
#   my $text = join '', @_;
#   print $text if $element->{_tag} eq 'h1';
#   return $text;
# }
def print_if_h1tag(element, results):
    text = "".join(results)
    if element["_tag"] == "h1":
        print text
    return text

#walk_html($tree, sub { $_[0] }, \&print_if_h1tag);
walk_html(tree, lambda x: x, print_if_h1tag)


# @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
#                                  \&promote_if_h1tag);
# sub promote_if_h1tag {
#   my $element = shift;
#   if ($element->{_tag} eq 'h1') {
#     return ['KEEPER', join '', map {$_->[1]} @_];
#   } else {
#     return @_;
#   }
# }
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                               promote_if_h1tag,
                               extender)
def promote_if_h1tag(element, results):
    if element["_tag"] == "h1":
        return [["KEEPER", "".join([ _x[1] for _x in results])]]
    else:
        return results


# sub extract_headers {
#   my $tree = shift;
#   my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
#                                       \&promote_if_h1tag);
#   my @keepers = grep { $_->[0] eq 'KEEPER'} @tagged_texts;
#   my @keeper_text = map { $_->[1] } @keepers;
#   my $header_text = join '', @keeper_text;
#   return $header_text;
# }
def extract_headers(tree):
    tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                                   promote_if_h1tag,
                                   extender)
    keepers = [x for x in tagged_texts if x[0] == "KEEPER"]
    keeper_text = [x[1] for x in keepers]
    header_text = "".join(keeper_text)
    return header_text


# sub extract_headers {
#   my $tree = shift;
#   my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
#                                       \&promote_if_h1tag);
#   join '', map { $_->[1] } grep { $_->[0] eq 'KEEPER'} @tagged_texts;
# }
def extract_headers(tree):
    tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                                   promote_if_h1tag,
                                   extender)
    return "".join([x[1] for x in tagged_texts if x[0] == "KEEPER"])


# sub promote_if_h1tag {
#   my $element = shift;
#   if ($element->{_tag} =~ /^h\d+$/) {
#     return ['KEEPER', join '', map {$_->[1]} @_];
#   } else {
#     return @_;
#   }
# }
def promote_if_h1tag(element, results):
    if re.search("^h\d+", element["_tag"]):
        return [["KEEPER", "".join([ _x[1] for _x in results])]]
    else:
        return results


# sub promote_if {
#   my $is_interesting = shift;
#   my $element = shift;
#   if ($is_interesting->($element->{_tag}) {
#     return ['KEEPER', join '', map {$_->[1]} @_];
#   } else {
#     return @_;
#   }
# }
def promote_if(is_interesting, element, results):
    if is_interesting(element["_tag"]):
        return [["KEEPER", "".join([ _x[1] for _x in results])]]
    else:
        return results


# my @tagged_texts = walk_html($tree,
#                               sub { ['maybe', $_[0]] },
#                               sub { promote_if(
#                                        sub { $_[0] eq 'h1'},
#                                        $_[0])
#                               });
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
                               lambda y,z: (promote_if((lambda _y: _y == "h1"), y,z)),
                               extender)


# sub fib {
#   my ($month) = @_;
#   if ($month < 2) { 1 }
#   else {
#     fib($month-1) + fib($month-2);
#   }
# }
def fib(month):
    if month < 2:
        return 1
    else:
        return fib(month-1) + fib(month-2)


# sub find_share {
#   my ($target, $treasures) = @_;
#   return [] if $target == 0;
#   return    if $target < 0 || @$treasures == 0;
#   my ($first, @rest) = @$treasures;
#   my $solution = find_share($target-$first, \@rest);
#   return [$first, @$solution] if $solution;
#   return         find_share($target       , \@rest);
# }
def find_share(target, treasures):
    if target == 0:
        return []
    if target < 0 or len(treasures) == 0:
        return
    first, rest = treasures[0], treasures[1:]
    solution = find_share(target-first, rest)
    if solution != None:
        return [first] + solution
    return find_share(target, rest)


# sub partition {
#   my $total = 0;
#   my $share_2;
#   for my $treasure (@_) {
#     $total += $treasure;
#   }
#   my $share_1 = find_share($total/2, [@_]);
#   return unless defined $share_1;
#   my %in_share_1;
#   for my $treasure (@$share_1) {
#     ++$in_share_1{$treasure};
#   }
#   for my $treasure (@_) {
#     if ($in_share_1{$treasure}) {
#       --$in_share_1{$treasure};
#     } else {
#       push @$share_2, $treasure;
#     }
#   }
#   return ($share_1, $share_2);
# }
# NOTE: would be more pythonic to use sum, sets()
def partition(treasures):
    share_2 = []
    total = 0

    for treasure in treasures:
        total += treasure

    share_1 = find_share(total/2, treasures)
    if not share_1:
        return 

    in_share_1 = {}
    for treasure in share_1:
        in_share_1.setdefault(treasure, 0)
        in_share_1[treasure] += 1

    for treasure in treasures:
        if treasure in in_share_1:
            in_share_1[treasure] -= 1
        else:
            share_2.append(treasure)
    
    return share_1, share_2

# a more pythonic way:
def partition_(treasures):
    share_1 = find_share(sum(treasures)/2, treasures)
    if not share_1:
        return 

    return share_1, list(set(treasures) - set(share_1))

Higher Order Perl (Python Style) TOC

2009-01-14T20:33:00.000-08:00

Higher Order Perl has many things of interest for a python programmer. As I've been going through this book (a free copy of which can be viewed here) I've been translating (as literally as possible) the perl code to python. I will continue to update this page as I finish each chapter. In general my plan is to stay as close as possible to the original perl unless the python transliteration is impossible (perl lambda are more expressive) or too unpythonic (e.g. some times a list comprehension or a set datatype does wonders for brevity). But still in many cases there will be a more pythonic way to write many of these examples. This is left as an exercise for the reader. :)

Please let me know if you see any serious translation errors or have other suggestions.

emacs python mode from scratch: stage 18 - miscellany

2009-01-09T21:51:00.000-08:00

stage 19 - miscellany

A grab bag of functions to finish us up:


python-jython-packages
python-maybe-jython
python-fill-paragraph
python-shift-left
python-shift-right
python-outline-level
python-current-defun
python-mark-block

python-jython-packages
python-maybe-jython

I don't really care too much about jython support so this won't get much more that a brief inspection. python-jython-packages seems to be a list of module names that if found in a package will cause jython mode to be used

python-maybe-jython is the function that uses the above list among other things to magically determine whether or not to use python or jython mode.
python-fill-paragraph

Provides a python aware fill-paragraph-function. The usual process would be to define paragraph-start and paragraph-separate and let fill do it's magic, but apparently this doesn't work quite right for the last paragraph in a multiline string. So instead This function narrows the string itself and does the fill action on that.
python-shift-left
python-shift-right

Move some code left or right by the requested number of columns (defaulting to the prima facie indentation level). If there is no region selected then just work with current line. This works by iterating over every line and running indent-rigidly. There is less code for the python-shift-right variation since you don't have to look out for the case where you run out of room for shifting.
python-outline-level

get outline-level. This is just the multiple of python-indent of the current indentation level.
python-current-defun

Work up an indentation level at a time (ie def or class) and keep track of the names of the def and class entities along the way.

This is used by add-log (add-log.el). apparently this is some sore of functionality for working with change logs. this function gives a way to refer to the name of the function where point currently resides. But honestly I'm not really sure how this fits into the big picture. This may well be some feature i depend on, but I'm having trouble figuring out what features use this and why.

If you run M-x add-change-log-entry it opens up something called a change log. I guess I'll just keep my eyes open for this in the future.
python-mark-block

Mark the block. Just as you'd expect.

So that's pretty much the end except for some little details here and there. This was an interesting exercise though if I had thought about how long this was going to take I'm not sure I would have started down this path. I definitely learned a lot, but the main thing I learned was how little I really know about emacs. Now that I'm finished I find a nice little tutorial on how language modes work. Well at least I know what they are talking about now. My main lesson I guess is that I really need to learn emacslisp if I want to become a master. But even then I will still have a lot to learn about the actual environment. But I'm getting there.

100 Pushups: week 6 milestone - 60

2009-01-08T22:00:00.001-08:00

OK, so after almost 7 month of the hilariously named 6 week program for achieving 100 pushups I finally hit 60. And actually it's even better than that because I did a total of 188 reps (in sets of 18 to 30) immediately preceding this.

So I'm making progress. There is probably a more efficient training regimen, but I'm getting there.

I don't know if this really is what got me there tonight but several times earlier in the day I had rehearsed in my head the last 5 pushups. 56. 57. 58. 59. 60! I visualized getting stronger on each one. And I felt sort of lame and new agey doing this, but I really wanted to hit this milestone tonight so I was willing to allow a little "woo" in my life if it was going to give me the edge.

OK, just 40 more. *sigh*

Mindfulness++

2009-01-02T23:59:00.000-08:00

I'm one of those guys who always talks about how they hate new year's resolutions and then makes a bunch anyway. Hi, nice to meet you.

One thing that has been weighing on me for a while and especially since I've had kids is that my concentration seems to be a faint shadow of it's former glory. It's probably partly age and partly the induced ADD of having to watch over young children. And don't forget the internets. Damn those tubes!

In any case I find myself so easily distracted, even when I'm doing something that I really enjoy. There seems to be a constantly growing wave of research and advice on this topic and much of it points to meditation/mindfulness as being a practice that will increase your ability to focus. Most recently I read this when going through Pragmatic Thinking and Learning: Refactor your Wetware.

I've actually had as a goal for at least a year to do 8 minutes a night of "watching my breath". Sometimes I'll go weeks of doing this every night. Sometimes I go weeks without even thinking about it.

So there are two parts to this resolution. I want to make this a do not skip part of my nightly routine. And I also want to increase the time to 20 minutes. There is probably nothing magic about the number 8 or 20, but I more often see recommended numbers closer to (at least) 20, so that will be my target. So the other part is to increase my time limit by 1 minute a month all of this year. This will bring me ever so slowly and gently to 20 minutes.

So with any luck, by the end of the year laser beams will be coming to me for advice on how to be so focused.

Any long term mindfulness practitioners out there with advice/encouragement?

One New Language a Year: Smalltalk

2009-01-01T22:30:00.000-08:00

The Pragmatic Programmers recommend learning a new programming language every year. I thought for a long time that this was a good idea, but didn't really act on it. Instead I'd dabble in a dozen languages a year. While this has built my intuition as to what various languages are like it has not made me a competent programmer in a new language. So for this year I'm going to actually pick a language, make a learning schedule and keep on it for the entire year. Now I almost certainly won't be able to stop myself from messing around with other languages to some extent (e.g. I'm slowly working through the Real World Haskell book), but my goal is to direct more of my focus and energy on a smaller target and hopefully get to the point where I really have an additional tool to use for solving real problems.

So then comes the question of which language to learn. In one sense I should probably pick a language that I don't know at all. The problem is that I've played with a lot of languages over the years. I don't think there are a lot of programming concepts/paradigms that I'm not at least familiar with. But there are a lot that I have not mastered. So I will just pick from the list of languages of which I'm not a master. A very healthy list.

Here is a short list of languages that I at least briefly considered:

smalltalk
haskell
something lispy (common lisp, scheme, emacslisp)
clojure (also lispy, but new and different)
erlang
mozart/oz
ruby
perl 6
javascript

All the languages above have some intriguing features but in the end I chose smalltalk (specifically squeak, but perhaps soon pharo). The deciding factors were:

My kids are getting close to an age where I might introduce them to programming so I'd like to have some mastery of a kid friendly programming language. While I think python fits that requirement pretty well, etoys seems like it might fit it even better (scratch also looks interesting).
I want to bump up my familiarity with deeper OO programming practices. In particular, I want to bump up my mastery of design patterns. Smalltalk is one of the languages where design patterns were first developed
I want to have a language where I can return to one of my first loves: graphical simulations. I could clearly do that in python, but well, learning a new language is always a good excuse to play around with graphics libraries.
I want to work on something that is really different in a fundamental way. Being forced to use the squeak development environment (instead of emacs) and an "image" instead of text files fits the bill
seaside just seems inherently cool and I'd like to get my mind around continuations.

I imagine my plan will change as I learn more and follow my interests, but as a first pass:

Learn etoys

This will give me a chance to start off sort of easy and genuinely playful. I've been collecting some links and project ideas but initially I am planning on looking at: Powerful Ideas in the Classroom, Idioms for Composing Games with Etoys, Etoys chapter in Learn Programming With Robots, and poke around in the squeakland site.
Intro to smalltalk/squeak reading/tutorials.
Some items that stand out as worth perusing include: Laser Game Tutorial, Squeak By Example, Design Patterns Smalltalk Companion (I've had this on the shelf for a while and it's really time I read it), Mark Guzdial's "Blue" book, and browse around on this list of smalltalk books.
Get familiar with seaside
In particular I will work on porting over a Django app (which used to be a quixote app) to seaside. I'm not planning on migrating it to seaside for real, but it's nice to have a real world project with lots of ugly edge cases in mind to see how a framework really works.
Depend on smalltalk
By the end of the year I hope to have some project that I maintain (even if just for myself) that keeps me involved with writing and maintaining smalltalk code.

Note: Haskell came in a very close second. It was actually a very hard decision. It seems like Haskell is poised to take off and it would be nice to be part of that wave. On the other hand. I already know that that language is pretty challenging to make progress on and will still be waiting for me next year.

FWIW: I recently came across this list of languages worth learning.

99 problems - python - 56

2008-12-21T12:56:00.001-08:00

Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.


# Example in Haskell:

# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
# False
# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
# True

def mirror(tree):
    if tree == None:
        return None
    else:
        val, left, right = tree
        return (None, mirror(right), mirror(left))

def symmetric_binary_tree(tree):
    return mirror(mirror(tree)) == mirror(tree)