lair of the dustbunny

Compilation and Compression

2010-07-10T22:40:00.000-07:00

Quick, which is bigger in general: source code or the resulting compiled executable?

Try to answer that before reading on. If you are being nit picky consider source code that has no comments and minimal whitespace. And consider *any* sort of language compilation process: python to bytecode, c to machine code, etc.

Recently while reading "What is Thought?" by Eric Baum (a great mix of AI, computational theory, cognitive science, evolutionary theory) he stated matter-of-factly that when you compile a program it gets bigger. He was using this in analogy with how DNA is (relatively) concise but the things it builds (e.g. all the connections in the human brain) are much, much bigger (in the Shannon information sense).

That seemed completely wrong to me. Humans are inefficient and verbose. Machines are efficient and concise. Surely some optimizing compiler (or even just a regular compiler) will show my code to be a joke and transform it into a small jewel-like essence that I wasn't capable of at my high level of abstraction.

And so I started looking at examples. .py to .pyc files. c to binaries. .hs to binaries. And wouldn't you know it, more often then not the resulting "compiled" entity was larger.

I was surprised that my intuition was so far off on this. I asked around with my co-workers and more often than not they had the same faulty intuition as me. So at least I'm not alone. But it's strange that my intuition was so far off on this.

Now I think my intuition is properly adjusted and here's how I think about it now.

Humans aren't inefficient and verbose. Quite the opposite. Saying something like:

print "hello world"

as a simple python program is a very terse way of making *lots* of low level details happen. In fact all programming languages (no matter how high or low you think of them) are very abstract (ie concise) compared to what is really going on. Even assembler is a massive collection of shortcuts and abstractions compared to the actual physics going on.

So no matter what language you are working in you are essentially working with shortcuts that need to actually be fleshed out into more precise and verbosely specific instructions.

What's really funny is that from reading "What Is Thought" I actually see a deep relationship between compilation and compression that I had never considered before. A little Information Theory is a dangerous thing...

Programming Language Gymnasium

2010-07-08T21:28:00.000-07:00

A list of sites/books/etc for practicing to be a programming language polyglot:

Books:
- Programming Challenges (Skienna)
- Data Structures and Algorithm Analysis in C (Weiss)
- SICP
Problem Sets
- 99 problems prolog, haskell, python, lisp, oz, scala, ocaml, perl 6
- Project Euler
- Coding Kata, javascript specific
- SPOJ
- FaceBook puzzles
- Python Challenge
- C puzzles
Contests
- Ruby Quiz
- Perl Quiz of the Week (offline/defunct?)
- Programming Praxis
- Prolog Programming Contests
- Valladolid Problem Server
- TopCoder
Comparisons
- Rosetta Code
- PLEAC

Links to check out:

My Plan for Programming Language World Domination

2010-07-03T15:49:00.001-07:00

I've recently been playing around with prolog (of all things). This happened after reading in "Coders at Work" that Erlang was originally written in prolog. This blew my mind. My impression from a few weeks of prolog usage in a programming languages course and another few weeks in an AI course that it was a *cute* idea but not really anything like a general purpose language. I guess this just emphasizes the point that you don't really know enough to have a valid opinion after such a short exposure. FWIW, I've been pleasantly surprised at the feel of declarative programming.

This sort of reactivated a crazy idea I had in my youth. Back in high school I had this notion of being a polyglot. At one point I had a different language for each day of the week (French on Mondays, German on Tuesdays, etc.). Needless to say this overwhelmed me and I never really mastered any of them (though I retained an interest in linguistics).

But I still love this idea of learning lots of languages. But now it occurs to me that I *can* do this with programming languages. The main flaw (besides the audacity) of my original goal was that I didn't have access to any native speakers with which to really practice my language skills. But with programming languages you can always practice to your hearts content.

So here is my plan. I will rotate through my list of "keeper" languages as I run through my usual diet of "99 problems", "euler problems", ACM contest problems and other puzzlers I come across. After I confirm that I can comfortably solve relatively interesting (though smallish) problems in my current list of "keeper" languages I'll start work on getting another language up to speed to add to my Bat utility belt.

Part of my interest in such a plan is that I just love learning to think in new ways. OK, that's a lie. Sometimes it's interesting. Sometimes it is maddening. But in either case it feels important and useful like going for long runs and eating right. I don't love exercise, but sometimes it feels good and I'm more worried about what will happen if I *don't* do it than discomfort/nuisance of actually doing it.

My other concern is related to the fact that I quite luckily have been able to program primarily in python for the last 9 years. This has been fun, but I worry that I could be missing out on other cool emerging technologies and that while python is a decent way to express your thoughts, it is not perfect and I shouldn't stop exercising different ways to bend computers to my will.

So here is my initial list of languages that I presume that I can currently solve programming puzzles in: python, prolog and haskell. Haskell is my language of the year and prolog has been quickly ramping up again. After I verify that these guys are reliably at my fingertips the next few languages will likely be from this short list:

oz: Gives me an excuse to read CTM and it feels like and important laboratory for programming ideas
c: I feel guilty that I've lost my fluency in this. I want to get comfortable with thinking at that level again.
java: this is a lingua franca that I should be comfortable with (though I think it has the least to teach me). I used to be paid to do this, but I don't miss it.
a lisp (commonlisp/scheme/clojure/emacslisp): Do I need a reason? OK, probably scheme so that I can go through SICP all the way and be able to wield the ninja star of continuations with confidence.
smalltalk: Is there a more direct road to OO mastery? I've spent some time before but probably didn't give it enough of a chance. Also being different is sort of the point of this exercise.

There are many more that seem worth cultivating, but I don't dare write them down for fear of overwhelming myself too early on.

Any way, here we go again.

One Language a Year: Haskell - update 2

2010-02-26T22:15:00.001-08:00

Not much to report, except that I am still trucking along through Real World Haskell (currently chapter 7). This is much better than last year (the year of smalltalk) where I was already having lots of trouble with motivation by this point.

I've been thinking alot about what the chances are that haskell will become one of my daily use power tools like python is. Or what the chances are that haskell will "take off" like a python.

I've already (mostly) gotten over one of my haskell phobias: dealing with "do" blocks. When I only had a passing understanding, I always got confused with "<-" and "lets" and "return"s in do blocks (and nested do blocks) and the rules seemed rather arbitrary, etc. Of course I'm no expert now, but at least I don't look at them as magical things. They have a precise use and logic and now I (mostly) get them.

A couple things from python I miss in haskell: list access syntax (e.g. x[2:]), default args/kwargs, etc. Both of these haven't really hurt me yet but just the thought that I don't have them available makes me sad.

How to Run

2010-02-01T20:26:00.003-08:00

I came across this site a few weeks ago and it has really rehabilitated my capacity for running. I'm not a big time runner but I try to run at least once a week and once a month I like to go at least 5 miles. The problem is that my knees haven't been very happy about this project for quite some time. In fact this summer I was trying to ramp up for a half marathon and by the time I got to 8 mile training sessions my knees (one in particular) really laid down the law. Basically they said stop that. I would end up taking ibuprofen and doing hot/cold treatments for a few days. This did not seem like a very wise course to continue and so I backed off.

So I've been trying the idea of barefoot running for the last month or so and the change is striking. I'm not actually going "barefoot". There is about a foot of snow in my front yard currently, but the running style is still the same. The idea is essentially to run on the front pads of your foot rather than landing on your heel. Rather than sending a shock straight from your heel to you knees and hips, you absorb most of it in the front of your foot.

I did my 5 mile route today and instead of finishing in agony and limping into my house I feel like I could easily go and do it again tomorrow.

It definitely takes concentration and practice to run this way and it doesn't feel completely natural quite yet, but at this point I don't think I could go back to "normal" running again. The main difference currently is that my calves get much more of a workout and I can still feel that and the front pads of my feet are just a little tender. They are absorbing a little more impact so I'm not surprised. It's not the feeling of my foot being abused just the tenderness you feel as you are developing tougher skin.

My wife has also adapted this style. She has suffered from plantar fasciitis for quite a while and she has noticed a huge reduction in foot pain.

So the question is, how is this just now getting around? I sure wish I knew about this 20 years ago. I could have saved my body a lot of wear and tear (possibly removing the need for my knee surgery of 6 years ago). Has this been known forever and I was just oblivious? I'd honestly never heard of the idea but now it seems sort of obvious.]

You can't help but wonder how many other easy fixes for modern problems there are out there.

One Language a Year: Haskell - update 1

2010-02-01T20:04:00.000-08:00

So one month in and so far Haskell is treating me much better than Smalltalk did a year ago. What is better? Well to start with my main learning period is a 20 to 30 minute window each morning before work. For whatever reason Smalltalk put me directly to sleep and I would often literally find my forehead mashed into my keyboard. I haven't had that problem at all yet with Haskell. One thing is for sure, if you want to learn a new programming language, you have to be awake.

What is the difference? For one it may just be that I like functional rather than object oriented thinking better. I'm fairly comfortable with object design ideas, but things like design patterns more often than not seem like bandaids over language problems rather than powerful solution cookie cutters. Also I admit that I generally expect object based solution to be over engineered. There is such a thing as beautiful OO solutions, but they seem to be the exception in my experience.

But probably the number one success factor for me is the fantastic book: Real World Haskell. 4 chapters in and I find the pacing quite nice. And there is no shying away from mundane things like reading and writing files and reading command line arguments. I swear I have a Haskell book that doesn't do any discussion of IO until chapter 17. I get that IO is about monads and monads are serious mind benders, but you still need to crank out a "Hello World" program early on. RWH gets that and many other things right.

One of my main rules for making sure I understand everything as I'm going along is to retype in *all* code from scratch as I come across it and to do so without directly copying it. In other words I have to understand it enough to retype it in directly from memory. This is probably something I should always have done, but cutting and pasting is just so easy and there is so little time....

In any case, the year of Haskell is doing quite nicely so far.

Is anything new/unique to Python?

2010-01-17T15:31:00.000-08:00

Looking at haskell I see some of my friends from python. Significant whitespace, list comprehensions, interators (sort of like laziness), tuples. And then it struck me that all of these features in python are derivative. Not that that is a bad thing. But I was surprised that I couldn't think of anything definitively new/unique to python. (Obviously the way these things are combined/balanced is unique)

Hey, internets, did python invent any language features/syntax?

The only thing that I can come up with is maybe the __blah__ (unders before and after) style of exposing syntax overriding.

One New Language a Year: Haskell

2010-01-04T22:25:00.000-08:00

Another year starts and so I try again to do the "Language a Year" thing. Last year it was a close decision between smalltalk and haskell. I went with smalltalk and for various reason it didn't really grab me and I ended up abandoning my efforts and switching to emacslisp.

So hopefully I've learned a little bit about the focus and dedication it takes to work on a new language and I'm ready to try this thing again.

First of all you need a goal or you won't know if you've succeeded (or failed). My goal is to essentially have a new python at my command. Another general purpose language that I can use as easily as I think for any sort of programming itch I happen to have. I originally learned python because I was looking for a new language that was different from what I was using at work. In 2000 or so I was mostly a Java and perl programmer. Python seemed interesting and different so I dove in. Relatively soon after that it became my full time work language and I sort of lost the idea of having a second language that I used in my free time.

So here I am again looking for a "fun" language. I've actually done occasional reading on haskell topics/blogs and have gone through a few short tutorials, but it's hardly a language I would say I'm at all comfortable in. In fact, unlike most languages that I have some familiarity in, random haskell code more often than not seems to have some scary new function/datatype/etc that I can't even start to grok from context.

The metaphor I have in mind as I dive in is that just as a professional builder uses tools that would be confusing and dangerous to a amateur builder there are programming tools/languages/concepts that are a level of effectiveness above the blub that I'm used to. It will take time/energy to master the more powerful tools but once you have, you will be working at a more advanced level.

I'm really curious to see if I can get a new language in my tool belt that is as concise (or more so) than python, faster, less prone to bugs, etc. Haskell seems as likely to provide this as any language as I'm aware of.

My plan is to use "Real World Haskell" as my main resource. By the end of the year I'd like to have gotten comfortable enough that I could use it interchangeably with python for random fun projects at home and even better to create a project and/or get involved in an existing project so that I have a reason to keep my skills fresh (since it ain't too likely to become my work language any time soon).

In any case I'll check back in a month or so and let you know how it's going.

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)

99 problems - python - 55

2008-12-21T09:24:00.000-08:00

Construct completely balanced binary trees

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function cbal-tree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.


# Example:

# * cbal-tree(4,T). 
# T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
# T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
# etc......No
def completely_balanced_trees(node_count):
    if node_count == 0:
        return [None]
    else:
        right_count  = (node_count - 1) / 2
        left_count = (node_count - 1) - right_count
        left_trees = completely_balanced_trees(left_count)
        right_trees = completely_balanced_trees(right_count)

        trees = []
        for left in left_trees:
            for right in right_trees:
                trees.append(("x", left, right))
                if left_count != right_count:
                    trees.append(("x", right, left))

        return trees

OK, I'm using tuples for trees again. So sue me.

Babylon 5: not so cautious, not so optimistic

2008-12-20T21:13:00.000-08:00

So the general rule for our tv watching these days is that we pretty much just watch tv series that are complete and available in their entirety on netflix. It turns out there are only a limited number of these. After a while you start considering things that have been on your "maybe" list for a while. One very big maybe for me has been Babylon 5. It shows up on all of these top 10 best scifi series lists and people rave about it having one of the best multi season story arcs. Ever.

Having heard that the first season is a bit weak and the things really start to get good in season 2 I asked my wife for some patience and and decided to dig in.

And, well, so far it's been worse than I could have imagined. Terrible set designs. Unbelievably bad diaglog. Very long in the tooth special effects. Unimaginitive aliens. Recycled scifi tropes. Wooden acting. And we are only two episodes away from season 2 starting. And I have to admit I'm really intrigued. Is there really any chance that things turn around *so* dramatically?

I'm a total fanboy for Farscape. In my opinion, the first season there was pretty weak (not Babylon 5 weak, but not great). And yet it slowly grew into one of my all time favorite series. And this was a show that had serious problems throughout but had some amazing highs to make up for it. So I do believe that things can turn around for B5 and that I will like it.

But man, this first season has been so extremely painful. I'm afraid my wife will get revenge on me by making me watch Sex in the City. Oh, god, the horror. The horror....

emacs python mode from scratch: stage 18 - imenu

2008-12-20T06:50:00.000-08:00

So first of all, what *is* imenu.

... read, read ....

So it partly seems like a one file only form of etags. But if you do M-x imenu-add-menubar-index it will add an "index" menu to the menu bar with a list of all files for easy access. Being a bit of a mouse-ophobe, I'm not so sure how I'd like that. Also you have to hit rescan whenever you change the contents of the file (or set up imenu-auto-rescan).

Seems like another case of having more than one way to do things. I'll probably stick with etags, but for completeness here is a brief overview of the imenu support functions.

So there is really just one function:

python-imenu-create-index

Go to the beginning of the file. look for "def and "class" references (unless in comments or string) and add them to the list.

Hmm, I wonder if something else more wonderful is going on here. Doesn't really seem like functionality worth supporting.

Perhaps if you had it set up to go off a simple mouse motion as described here.


(if (featurep 'xemacs)
     (global-set-key [(shift button3)] 'imenu) ; XEmacs
   (global-set-key [S-mouse-3] 'imenu)) ; GNU Emacs

Also looks like it integrates in with ido to some extent. Maybe there is some goodness from that.

Any way, that's enough on that topic.

emacs python mode from scratch: stage 17 - ffap

2008-12-17T20:20:00.003-08:00

This is a small bit of code, but it's another little gem that I didn't know exists. There is only one function:

python-module-path

This function uses emacs.modpath to determine the module path for use with ffap-alist

What this gets us is support for M-x find-file-at-point.

It's not *quite* as cool as I first anticipated because the file path finder seems to get confused about what is actually a module, but if point is on a module name on an import line then it will pop you directly over to the python lib directory and open the module. If you already have etags set up to do this then you probably won't be *too* amazed, but this is a nice extra way to accomplish the same thing.

emacs python mode from scratch: stage 16 - completion

2008-12-17T20:10:00.000-08:00

This is a collection of functions that uses emacs.py to find a list of likely completions for module.


python-imports
python-find-imports
python-symbol-completions
python-partial-symbol 
python-complete-symbol
python-try-complete

python-imports

A list of python import statements in the buffer
python-find-imports

Populate the above list. search by looking for "^import" or "^from" (skipping those in comments or strings).

Then reverse the list, clean out text properties and change \n to \\n so that output doesn't end up wrong.
python-symbol-completions

Run emacs.complete(symbol, python-imports) and return the list of completions (in another buffer)
python-partial-symbol

Use a regular expression to go backward and thereby find the complete symbol before point. This seems a little odd to me. I seems like it would be easier to just trust the syntax-table that has already been defined for the mode and just do backward-word from the current position (with a save-excursion). As a guess I'd say it's so that it can treat "." as part of the symbol and skip over that to the beginning of a module/class name.
python-complete-symbol

Find the list of completions (using python-symbol-completions) or just scroll the completions window if they've already been found.
python-try-complete

"hippie-expand" version for doing symbol completions. Basically "he-" does all the heavy lifting hereit just needs to be
given the python-symbol-completions and python-partial-symbol functions.

99 problems - python - 54A

2008-12-13T19:27:00.001-08:00

Check whether a given term represents a binary tree

In Prolog or Lisp, one writes a predicate to do this.

Example in Lisp:


* (istree (a (b nil nil) nil))
T
* (istree (a (b nil nil)))
NIL
def is_tree(t):
    if t == None:
        return True
    elif type(t) == tuple and len(t) == 3:
        (val, left, right) = t
        return is_tree(left) and is_tree(right)
    return False

Is using lispy tuple for representing tree cheating?

99 problems - python - 50

2008-12-13T07:31:00.001-08:00

Huffman codes.

We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms. Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S. In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.]. The task shall be performed by the predicate huffman/2 defined as follows:


# stats: [(letter, count)]
# return: [(count, letter OR (left, right)]
def make_tree(stats):
    pool = sorted([(count, letter) for letter, count in stats])

    while len(pool) > 1:
        first = pool.pop(0)
        second = pool.pop(0)

        node = (first[0]+second[0], (first, second))
        pool.append(node)
        pool.sort()

    return pool[0]

def codes_from_tree(node, path, results):
    count, letter_or_trees = node
    letter = left = right = None
    if type(letter_or_trees) == tuple:
        left, right = letter_or_trees
    else:
        letter = letter_or_trees

    if letter:
        results.append((letter, path))
    else:
        codes_from_tree(left, path+"0", results)
        codes_from_tree(right, path+"1", results)

def huffman(stats):
    results = []
    tree = make_tree(stats)
    codes_from_tree(tree, "", results)
    
    #to sort by huffman code value
    #results.sort(key=lambda x: int(x[1], 2))
    results.sort()

    return results

That solution *feels* a little hacky for me, but I can't think of why it bothers me. It might be that the last time I wrote this was in java, and it was a lot more work. Maybe this just seems too easy.

emacs python mode from scratch: stage 15 - info look

2008-12-12T21:24:00.000-08:00

Probably the main lesson of my explorations of the python mode is that there is a lot of functionality available that I had never heard of before. info-look is a good case in point.

python-after-info-look

This function essentially let's you hook into the info system to look for documentation.

As far as I can tell the main use is for calling info-lookup-symbol (C-h S) and having the info page for the python entity show up.

You need to make sure the info flavor of python documentation is installed on your system. (And hopefully it takes you less time than it did me to realize it wasn't).

Not much else to say on this.

emacs python mode from scratch: stage 14 - context sensitive help

2008-12-08T22:52:00.000-08:00

Here are the relevant variables and function in the context-sensitive help section


VARS:
(defconst db-python-dotty-syntax-table
(defvar view-return-to-alist)
(defvar db-python-imports)

FUNCS:
python-describe-symbol
python-send-receive
python-eldoc-function

db-python-dotty-syntax-table

This creates an altered syntax table that treats "." as "symbol constituent". In other words, "." is treated as part of the variable name rather than as an other type of syntax.
view-return-to-alist

Used by python-describe symbol. Consists of a window and help-return-method
db-python-imports

Used below when calling emacs.* helper functions.
python-describe-symbol

C-c C-f is bound to this and will do a python help(module|func|etc) for thing at point. It dumps out the standard python documentation in another temporary buffer. It uses emacs.py to get the help. Somewhat useful, but i usually have a python prompt open already.
python-send-receive

Convenience function for sending a command to the python interpreter and reading the result.
python-eldoc-function

Use emacs's own documentation reader to populate the message line with brief description of function and args. this is something that I had not noticed before and am glad I came across it while perusing the code.
If you have a python session going and you either run M-x eldoc-mode or you set up a hook such as
```
  (add-hook 'python-mode-hook 'turn-on-eldoc-mode)
```
then this will automatically run the eldoc help facility. Not sure how useful it will be day to day (maybe it's just developer eye candy), but I've seen this sort of thing while running in slime or in the haskell mode and now at least I see where it is coming from. Seems like it only really works with core python libraries. Strangely doesn't seem to know about the functions in the actual file you are currently working in.

Only 4 sections left to walk through. I'm actually pretty eager to be done with this, but I definitely want to finish (however shallow my exploration of this mode is).

Brains games that make you cry

2008-12-07T21:34:00.000-08:00

I think almost as long as I've been a programmer I've tried making little games to test my reflexes and challenge my memory and other cognitive faculties. It's just been a given to me that: (a) you can train your brain in a manner similar to lifting weights or jogging and (b) this is a highly desirable goal.

The problem is that I've never really had enough faith in the games that I created that the effort I put into them (both writing and training with them) would be worth it. Doesn't stop me from getting interested in the idea anew every once in a while. And it seems that there is a general growing interest in these types of games, growing research that they work and (best of all) an increasing number of open source games that are created specifically to help you train your brain.

Of these sorts of games and research results it *seems* that the one with the most credibility is the "n-back task" as described in this wired article and as implemented in Brain Workshop.

Besides the research, one of the things that gives this game credibility is that it is really challenging and not very game like. It really does feel like exercise (in the sense of forcing yourself to go to the gym because you know it is good for you, a necessary evil). And honestly the first few passes through are almost laughably hard. You are trying to maintain a memory of positions and letter values being thrown out you and notice if the position or letter value is the same as n turns ago.

And the funny thing is that even after a couple of days of not really spending too much time on it, I'm definitely getting better at it. It's actually a weird feeling. The first few times through is just chaos and then all of a sudden you start moving from a slight guess that, yes, I think they did say "C" 2 turns ago and are now repeating it, to being really confident. But of course as soon as you get good at 2-back, it graduates you to 3-back.

Now the problem is how do I test if I am indeed getting smarter? I'll let you know if my brain seems like it has kicked it up a notch or two.

emacs python mode from scratch: stage 13 - python inferior mode

2008-12-05T20:45:00.001-08:00

My plan was to look at context sensitive help next but it dependeds on a python inferior process so let's get that working next.

Here are the function/variables of relevance:


(defcustom python-python-command "python"
(defcustom python-jython-command "jython"
(defvar python-command python-python-command
(defvar python-buffer nil
(defconst python-compilation-regexp-alist
(defvar inferior-python-mode-map
(defvar inferior-python-mode-syntax-table
(define-derived-mode inferior-python-mode comint-mode "Inferior Python"
(defcustom inferior-python-filter-regexp "\\`\\s-*\\S-?\\S-?\\s-*\\'"
(defun python-input-filter (str)
(defun python-args-to-list (string)
(defvar python-preoutput-result nil
(defvar python-preoutput-leftover nil)
(defvar python-preoutput-skip-next-prompt nil)
(defun python-preoutput-filter (s)
(defun run-python (&optional cmd noshow new)
(defun python-send-command (command)
(defun python-send-region (start end)
(defun python-send-string (string)
(defun python-send-buffer ()
(defun python-send-defun ()
(defun python-switch-to-python (eob-p)
(defun python-send-region-and-go (start end)
(defcustom python-source-modes '(python-mode jython-mode)
(defvar python-prev-dir/file nil
(defun python-load-file (file-name)
(defun python-proc ()
(defun python-set-proc ()

The main mechanism for creating a python inferior process appears to be creating a derived mode based on comint-mode (defined in comint.el). Most of the code then is defining helper functions for making this mode python aware.

So without further ago, here is a brief look at the above functions:

python-python-command
python-jython-command

Variables which allow customization of what command to use for invoking python (jython)
python-command

The actual command (probably one of the above) that will actually be executed by run-python
python-buffer

The python buffer that will be the target of code issued from files in python-mode
python-compilation-regexp-alist

compilation-error-regexp-alist is set to this value. This is set by inferior-python-mode and is used by compile.el. This regular expression basically matches a python exception stacktrace:
```
   Traceback (most recent call last):
     File "foo.py", line 13, in 
       1/0
   ZeroDivisionError: integer division or modulo by zero
```
Honestly I'm a little confused by this since I don't think this regex actually matches the above and I'm not clear what purpose "compile" would need with it.
inferior-python-mode-map

Add a few keys for loading a file and doing pychecker. The key sequence for pychecker seems superfluous here. I never feel like kicking off pychecker while i'm in an interacive session.
inferior-python-mode-syntax-table

Adjust syntax table so that single quotes don't mess up the syntax coloring. "." is the syntax table entry for punctuation-like things.
inferior-python-mode

This is where the python interactive mode is defined. It overrides the default commint-mode. There is a comment here that the "python-mode" type things (keybindings, etc) should be inherited from python mode itself.

The basic customization is to adjust some regular expressions that are used by commint to decide what sort of things get maintained in the history, what the "prompt" looks like (>>>), etc.
inferior-python-filter-regexp

The default is not to save things in the history if they are 3 or less in length. I hadn't noticed this behavior before.

I'm not sure if there is some rhyme or reason why sometimes they use the rx style and sometime they use traditional emacs style regexps (in this case "\\`\\s-*\\S-?\\S-?\\s-*\\'").
python-input-filter

This basically is a wrapper for ignoring inferior-python-filter-regexp
python-args-to-list

This will be used by run-python below to collect args for kicking off a python process. Doesn't work with quoted white space. Don't know emacs lisp well at all but it seems like a complicated way to just tokenize on SPACE and TAB.
python-preoutput-result

Not sure what "_emacs_out" is about, and not sure I care to spend the time tracking this down. (Possibly for emacs.py)
python-preoutput-leftover

related to _emacs_out
python-preoutput-skip-next-prompt

This (as well as previous 2 functions) are used by python-preoutput-filter
python-preoutput-filter

This function appears to clean up the output a bit and prevent spurious >>> ... ... >>> from littering the output. I'm going to punt on this. I'm not especially interested in the logic here but it is interesting passing to see a complex function needed to make the python mode behave in a friendly fashion.
run-python

Start a new python process or use an existing one if available. runs python-command with -i.
python-send-command

A wrapper around python-send-string that is used by python-send-region and python-load-file
python-send-region

Copy a section of code to temporary file and evaluate it. Can't do it directly in the interpreter since empty lines will confuse it
python-send-string

Evaluate a python string in the buffer. This function checks for trailing \n or intermediate \t and throws in an extra \n so that the command is properly terminated in a way that the interpreter is expecting.
python-send-buffer

Wrap python-send-region but use the entire buffer as the region
python-send-defun

Send a region but use beginning-of-defun/end-of-defun to delimit the region
python-switch-to-python

Create a new python process if necessary and switch to it. Giving it an argument makes it go to the end of the buffer
python-send-region-and-go

Combine python-send-region and python-switch-to-python
python-source-modes

A list of mode names so we can automatically tell if the buffer has python code in it
python-prev-dir/file

A cache of the directory and file used by python-load-file so that it has a default value if necessary
python-load-file

Import a python file in its entirety into the python process. Uses emacs.py if the file ends in .py otherwise uses "execfile"
python-proc

Return to or create and move to a python process
python-set-proc

Associate the python-buffer with the current buffer (which is a python process). This is used by things like python-send-region so they know where to send output.

I think unless you understand the details of how comint works (which I don't) it's hard to get a strong feel for how the inferior-python-mode works. As always it's interesting to see all of the crazy details that have to be taken care of to get a simple looking thing like an embedded python interpreter working.

That was a very cursory overview of how the python process inferior mode works (even by my already lax standards). I admit it, I'm getting a little exhausted by this project. But I'm going to keep slogging through and finish doing at least a cursory inspection of every line in python.el.

Another thing that is becoming clear is that, while this process is helping me understand emacs and emacslisp, I have a lot of work to do, and at some point I really need to just sit down and learn emacslisp in a focused way.

Is it possible that I like sushi merely as a means to confound my wife?

2008-12-04T21:39:00.000-08:00

Sometimes I wonder....

Choose Two

2008-12-02T22:48:00.000-08:00

I was cracking wise with my co-workers the other day and later in the day I related the hi-jinx to my wife. I had proffered the following theory on the relative combination of desirable attributes in your mate.

"Gentleman, you've got cute, smart and nice. And you get to choose two."

My attractive, intelligent wife confirms that this is a sound theory.

99 problems - python - 49

2008-11-25T16:06:00.000-08:00

Gray codes.

An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,


n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].

Find out the construction rules and write a predicate with the following specification:


def gray(n):
    if n == 0:
        yield ""
    else:
        base = list(gray_code(n-1))

        for code in base:
            yield "0"+code

        for code in reversed(base):
            yield "1"+code

99 problems - python - 48

2008-11-22T13:17:00.001-08:00

Truth tables for logical expressions (3).

Generalize problem P47 in such a way that the logical expression may contain any number of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List.


Example:
* (table (A,B,C) (A and (B or C) equ A and B or A and C))
true true true true
true true fail true
true fail true true
true fail fail true
fail true true true
fail true fail true
fail fail true true
fail fail fail true

def int_to_bool_tuple(x,size):
    result = []
    while x:
        result.insert(0, (x & 1) == 1)
        x >>= 1
    return ([False]*(size-len(result))) + result
    
def table2(var_count, func):
    for x in range(2**var_count):
        bools = int_to_bool_tuple(x,var_count)
        for b in bools:
            print "%-5s" % b,
        print func(*bools)

As I was exploring ideas for this solution I noticed that python 2.6 has a bin() function which gives a string representation of a number as binary. Need to upgrade to 2.6 I guess. Of course if I'm going to upgrade, might as well wait for 3.0.

99 problems - python - 46

2008-11-22T09:30:00.000-08:00

Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed.

A logical expression in two variables can then be written as in the following example: and(or(A,B),nand(A,B)).

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.


def and_(x,y): return x and y
def or_ (x,y): return x or y
def not_(x): return not x
def nand_(x,y): return not (x and y)
def nor_(x,y): return not (x or y)
def xor_(x,y): return x ^ y
def impl_(x,y):return not x or y
def equ_(x,y): return x == y

def bool_table(func):
    inputs = [(x,y) for x in (True,False) for y in (True,False)]
    for x,y in inputs:
        print "%-5s %-5s %-5s" % (x,y,func(x,y))

Note: I'm just going to skip 47 since it's pretty much a noop based on how python already works, and how I solved this problem. Unless I'm missing something subtle.

100 Pushups: week 6 (8th try)

2008-11-21T21:43:00.000-08:00

It just occurred to me that I've been doing this crazy 100 pushups thing since at least July. I'm still humorously far from my goal, but damn if I'm still making some progress. For instance this week after doing my various reps (150+ pushups in 20+ increments) I was able to get to 53 which is a new record for me.

But nevertheless it is still pretty funny that I've been doing the 6th week of a 6 week program for 8 weeks now. And it *only* took me 6 weeks or so to finish week 5. But I did finish.

The idea of doing 100 pushups seemed sort of comical to me when I started this bad boy, but now it's my mission. I just hope I finish this decade sometime.

Pragmatic Thinking and Learning

2008-11-18T22:37:00.000-08:00

I've just started this book and while I think that I will get lots of interesting things out of it, it has already set off some alarm bells with me. The same alarm bell that goes off when I hear someone quote the "fact" that we only use 10% of out brains (well, maybe that's true for you...).

In any case the author seems to stick pretty close to the Betty (Drawing on the Right Side of the Brain) Edwards L/R distinction which I've grown skeptical of over the years. That was a low buzz no real alarm, just be wary.

But next came a reference to the"Unskilled and Unaware" paper. I've always thought that result sounded pretty reasonable, but today I came across this.

Hopefully the book doesn't continue to be full of too many debunked/sketchy studies.

I actually expect I will like the book and recommend it, but I just wish you could get a clear, unambiguous picture of state of the art learning/creativity techniques with minimal "woo".

99 problems - python - 41

2008-11-16T07:04:00.000-08:00

Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.


# using goldbach as defined previously
def goldbach_list(start,end,threshold=None):
    start = max([start,4])
    for n in range(start,end+1):
        if n % 2 == 0:
            i,j = goldbach(n)
            if threshold == None or i > threshold:
                print "%d = %d + %d" % (n, i, j)

99 problems - python - 40

2008-11-16T06:39:00.000-08:00

Goldbach's conjecture. Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.


# using primes_range from previous problem
def goldbach(n):
    assert n % 2 == 0

    for i in primes_range(2, n):
        for j in primes_range(i, n):
            if i + j == n:
                return (i,j)

99 problems - python - 39

2008-11-15T22:30:00.000-08:00

A list of prime numbers


# using is_prime from earlier problem
def primes_range(start,end):
    return [n for n in range(start, end+1) if is_prime(n)]

99 problems - python - 37

2008-11-15T21:08:00.000-08:00

Calculate Euler's totient function phi(m) (improved). See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:

phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

Note that a ** b stands for the b'th power of a. Note: Actually, the official problems show this as a sum, but it should be a product.


# using prime_factors_mult from earlier
def totient_phi2(n):
    if n == 1:
        return 1

    def product(lst):
        return reduce(lambda x,y: x*y, lst)
    return product([((p-1)*(p**(m-1)))  for (p, m) in prime_factors_mult(n)])

I'm pretty sure that "reduce" will be leaving python 3. We hardly knew ye. I don't understand that removal. Of course I'll just be adding it right the hell back in. And no one can stop me!

99 problems - python - 36

2008-11-15T19:41:00.001-08:00

Determine the prime factors of a given positive integer.

Construct a list containing the prime factors and their multiplicity.

Example:

* (prime-factors-mult 315)
((3 2) (5 1) (7 1))


#using prime_factors from the previous problem
import itertools
def prime_factors_mult(n):
    return [(x, len(list(y))) for x,y in itertools.groupby(prime_factors(n))]

99 problems - python - 35

2008-11-15T15:55:00.000-08:00

Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.


def prime_factors(n):
    factor = 2
    while n > 1:
        if n % factor == 0:
            yield factor
            n = n / factor
        else:
            factor += 1

This ended up being simpler and more beautiful than I was expecting. I think I'm falling in love with python all over again. *snif*

99 problems - python - 34

2008-11-15T14:26:00.000-08:00

Calculate Euler's totient function phi(m). Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.


# using coprime defined previously
def totient_phi(m):
    if m == 1:
        return 1
    return len([r for r in range(1,m) if coprime(r,m)])

emacs python mode from scratch: stage 12 - bicycle repair man

2008-11-15T06:36:00.000-08:00

For this session we'll get bicycle repair man support working.

First let's see if we can get brm working by itself and then see how it integrates into emacs.

To start it I ran:


M-x python-setup-brm

It took a little googling and experimentation to figure out how to use this. But I finally figured out that if you select some text then the menus do their thing.

This is a strange little tool. I guess I'm so used to refactoring with global search and replaces that this seems overly constraining. But perhaps it's just unfamiliar. I suspect that if you got used to it then you could learn to like it, but I'm skeptical. One behavior that was very counter intuitive is that you can't use the normal emacs undo to revert the refactoring change. You have to do it via the menus (or presumably the brm console). In any case let's look at the code that runs brm.

Firstly it does an autoload of pymacs.

I've never really played with this before but you can see that it is loaded correctly and working by doing the following in *scratch*:


(pymacs-eval "2 + 2")
4

The second prep step is to get the bicycle repair man module itself loaded:


(autoload 'brm-init "bikemacs")

Which I'm assuming works since I was able to do a refactoring

python-setup-brm

This code is mostly just busy work to set up of menus.

Strangely this code ends with an (error ... ) embedded in an (error ...).
Not sure what that is about.

Interestingly in the comments the author of python.el expresses doubts that brm is useful.
Note to self, I should also look at ropemacs. Looks like rope has more features and if I recall an earlier experiment correctly does autocomplete of python variables/modules as well.

Any way, onward and upward. Next stop, context sensitive help.

99 problems - python - 33

2008-11-15T06:21:00.000-08:00

Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Using gcd as defined in the previous problem:


def coprime(m,n):
    return gcd(m,n) == 1

99 problems - python - 32

2008-11-12T21:42:00.000-08:00

Determine the greatest common divisor of two positive integer numbers.


def gcd(m,n):
    m,n = sorted([m,n])

    while m != 0:
        m, n = (n % m), m

    return n

Humorously, I resisted using a recursive algorithm. I don't know why, but it just seemed more reasonable to use a straight iterative one. Also I really like how m,n = (n%m), m saves us from having to declare a temporary variable.

emacs python mode from scratch: stage 11 - skeleton

2008-11-12T19:22:00.000-08:00

We are actually getting to the point where this mode would actually be useful for developing with.

Next let's get skeleton support working now.

Here are the new functions I've copied over:


python-use-skeletons
python-skeletons
python-mode-abbrev-table
def-python-skeleton
def-python-skeleton if
define-skeleton python-else
def-python-skeleton while
def-python-skeleton for
def-python-skeleton try/except
define-skeleton python-target
def-python-skeleton try/finally
def-python-skeleton def
def-python-skeleton class
python-default-template "if"
python-expand-template

python-use-skeletons

This controls whether or not skeleton functions are added to the python-mode-abbrev-table
python-skeletons

A list of all the skeletons. apparently used when working on compound statements.
python-mode-abbrev-table

This is where the actual abbrevs are stored
def-python-skeleton

A macro for getting a skeletons "registered" in the abbrev system. First it creates a name for the skeleton of the form: python-insert-foo. Then if adds this name to the pyton-mode-abbrev-table. Finally it calls define-skeleton and creates the skeleton.

Each of the following create the appropriate skeleton by name


def-python-skeleton if
def-python-skeleton while
def-python-skeleton for
def-python-skeleton try/except
def-python-skeleton try/finally
def-python-skeleton def
def-python-skeleton class

define-skeleton python-else

else clause used by if and other else-able statements. One reason I would find it hard to get excited about using this particular skeleton/template system is that it seems sort of ridiculous to be prompted after a for loop or a while loop, etc for an else clause. I can count on 1 hand how many times i've ever used an else clause other than part of an if cascade. It seems like an unnecessary burden to make the user consider this case every time they are writing a for loop.
define-skeleton python-target

Helper used by try/except
python-default-template

Variable that defines what template to use by default in python-expand-template
python-expand-template

This function is for allowing a skeleton to be used directly as a key sequence rather than as an abbrev. Interestingly if defaults to the "if" template but then let's you update what the default is.

I'm not totally sold on the value of skeletons for python. The syntax is already so minimal that the distraction of writing code through the minibuffer doesn't seem like a big win but it's something i'd like to explore in detail sometime and see if it works for me if i give it a chance.

Next let's get bicycle repair man support working.

99 problems - python - 31

2008-11-08T22:36:00.000-08:00

Determine whether a given integer number is prime.


import math
def is_prime(n):
    for test in range(2, int(math.sqrt(n) + 1)):
        if n % test == 0:
            return False

    return True

(no, I'm not skipping problems, the original set skips too)

BTW, below is the prime number generator function in Haskell in case you haven't seen it before. For my money it's about the most beautiful line (or 2) of code I've ever seen. It almost gives me goose bumps when I see it.

It's deceptively simple looking, but the more you look at it the more your mind is guaranteed to be blown as it sinks in how subtly cool this is


primes = sieve [2..]
    where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]

* (guarantee not binding any where)

99 problems - python - 28

2008-11-08T22:29:00.000-08:00

Sorting a list of lists according to length of sublists

a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.

Example:
* (lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))
((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L))

b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency; i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

Example:
* (lfsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))
((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n))

(a) it should be enough to do

sorted(lst_of_lsts, key=lambda x: len(x))

If you want the lists of same length to be alphabetically sorted as well then you could do:

sorted(sorted(lst_of_lsts), key=lambda x: len(x))

(b)


def length_frequency_sort(lst_of_lists):
    freqs = {}

    for lst in lst_of_lists:
        freqs.setdefault(len(lst), 0)
        freqs[len(lst)] += 1

    return sorted(lst_of_lists, key=lambda x: freqs[len(x)])

99 problems - python - 27

2008-11-08T22:10:00.000-08:00

Group the elements of a set into disjoint subsets.

a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.

Example:
* (group3 '(aldo beat carla david evi flip gary hugo ida))
( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) )
... )

b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.

Example:
* (group '(aldo beat carla david evi flip gary hugo ida) '(2 2 5))
( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) )
... )


def combination(lst, size):
    #defined as in previous problem

def grouped_combos(lst, sizes):
    assert len(lst) == sum(sizes)

    if not sizes:
        yield []
    else:
        for combo in combinations(lst, sizes[0]):
            rest = sorted(list(set(lst) - set(combo)))
            for rest_combo in grouped_combos(rest, sizes[1:]):
                yield [combo] + rest_combo

I have a sorted thrown in since using set gave unreliable ordering after the set difference. I really love recursion. It seems like the above would be quite annoying without it.

99 problems - python - 26

2008-11-08T16:49:00.001-08:00

Generate the combinations of K distinct objects chosen from the N elements of a list In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.


def combinations(lst, size):
    if len(lst) < size:
        return
    elif size == 0:
        yield []
    else:
        # keep first
        for combo in combinations(lst[1:], size-1):
            yield [lst[0]] + combo
        # skip first
        for combo in combinations(lst[1:], size):
            yield combo

After I wrote this I remembered that python's test/test_generators.py also had an implementation of this:


>>> def gcomb(x, k):
...     "Generate all combinations of k elements from list x."
...
...     if k > len(x):
...         return
...     if k == 0:
...         yield []
...     else:
...         first, rest = x[0], x[1:]
...         # A combination does or doesn't contain first.
...         # If it does, the remainder is a k-1 comb of rest.
...         for c in gcomb(rest, k-1):
...             c.insert(0, first)
...             yield c
...         # If it doesn't contain first, it's a k comb of rest.
...         for c in gcomb(rest, k):
...             yield c

Which is amazingly similar. I guess in python there really is OBWTDI (one best way to do it).

So anyway I think from here on out the questions will continue to be less and less "trivial".

99 problems - python - 25

2008-11-08T14:07:00.000-08:00

Generate a random permutation of the elements of a list.

Once again python provides us with a solution, so we don't have to code at all.

random.shuffle(lst)

Since this works in place you may want to copy your list first before operating on.

Keep your shirt on, these do get interesting after a while. But it is nice to see how many "problems" are already solved for us.

99 problems - python - 24

2008-11-07T22:36:00.000-08:00

Lotto: Draw N different random numbers from the set 1..M.

No reason to use anything other than random.sample(population, count)

emacs python mode from scratch: stage 10 - pychecker

2008-11-07T22:28:00.000-08:00

My next step is to get pychecker working. Turns out it's not much code. Here are the functions:

python-check-command

the default string to use as the command for running pychecker
python-saved-check-command

a cache of the command above and the name of the file we are
currently working with
python-check

Pretty straightforward but a couple of things to note.

I wasn't aware that the "interactive" command took straight elisp as an argument. I had just assumed you had to use the magic argument strings.

It's a little strange that they use an old school emacs lisp regular expression ("(\\([^,]+\\), line \\([0-9]+\\))") rather than the rx style they seemed to use everywhere else.

A note on pychecker. I find this utility fascinating. For good and bad reasons. It's really quite useful. C-c C-w is reflexively typed after saving a file. And the fact that it is so useful makes it extra confusing that it it seems sort of abandoned (at least last I checked).

As a future project I'd like to look at it (or one of it's cohorts, pylint, pyflakes, etc) and see how it works and perhaps complain less and help more,but it seems strangely abandoned now. I did start to take a look at one point and it seemed very complex so I ran away with my tail between my legs. But fortunately I have a short memory for scary things and I'll likely return to it someday.

Getting pychecker working required less code than I suspected.

Next I'll do skeleton support which if nothing else is a lot more lines of code.

99 problems - python - 23

2008-11-05T21:41:00.000-08:00

Extract a given number of randomly selected elements from a list.


import random
def random_select(lst, n):
    for x in range(n):
        yield random.choice(lst)

Depending on how you interpret the problem you may just want to use random.sample

99 problems - python - 22

2008-11-05T21:36:00.000-08:00

Create a list containing all integers within a given range.

OK, just use range(). Anything else would be silly. Depending on how you interpret this problem you may need to add one to the second parameter.

99 problems - python - 21

2008-11-03T21:53:00.000-08:00

Insert an element at a given position into a list.


def insert_at(x, lst, n):
    return lst[:n-1] + [x] + lst[n-1:]

99 problems - python - 20

2008-11-02T20:59:00.000-08:00

Remove the K'th element from a list.


def remove_at(lst, n):
    return lst[:(n-1)] + lst[n:]

The simplest thing to do would be to just use .pop(), but I assuming that a non-destructive operation would be preferred in this case.