?

Log in

No account? Create an account
I also sampled everything in the medicine cabinet for comparison. - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

I also sampled everything in the medicine cabinet for comparison. [Jan. 16th, 2009|09:14 pm]
Lindsey Kuper
[Tags|]

The new semester began this past Monday. Between classes, homework, AI-ing, and choir rehearsal, it really seems to be cutting into my blogging-breathlessly-about-Python time.

A couple weeks ago, Tony idealisms suggested that one way to whip my Python into shape might be to do some Project Euler problems, so I decided to try a few. When I sat down to start doing them, I wasn't feeling particularly confident. But when I read the first problem, "Find the sum of all the multiples of 3 or 5 that are below 1000", I astonished myself by barely even having to think about it:

print sum(filter(lambda x : x % 3 = 0 or x % 5 = 0, range(1, 1000))

One line. 20 seconds to write.1 And it worked!

I decided to double-check the answer by solving the same problem in Scheme. Oughta be a snap to port this one trivial line of code ov -- oh, wait, in Scheme I don't have range. And I don't have sum. And, oops, I always forget that % is spelled "R-E-M-A-I-N-D-E-R", and hmm, filter doesn't seem to be in the R5RS, although, oh, good, Chez Scheme has it, and I could use reduce instead of sum, except Chez doesn't have reduce -- although both filter and reduce are in SRFI-1, so I can use them in PLT by sticking a (require srfi/1) at the top of my file, which I am guaranteed to misspell as "sfri" the first time, but you can't use require in Chez, and, and, and, and.

Let me be clear: I love Scheme. It is my favorite programming language. But it's a batteries-not-included sort of programming language. In Scheme you get to make your own batteries. Here's what I wrote:

(define problem-1
  (lambda (n)
    (letrec ((kernel (lambda (x acc)
                       (cond [(= x 0) (display acc) (newline)]
                             [(or (= (remainder x 3) 0)
                                  (= (remainder x 5) 0))
                              (kernel (- x 1) (+ acc x))]
                             [else (kernel (- x 1) acc)]))))
      (kernel (- n 1) 0))))

(problem-1 1000)

So it's a single, monolithic procedure that does the summing, filtering, and ranging all at once. Well, what's wrong with that? It's probably more efficient! To me, though, the more interesting point is that as a moderately experienced Schemer, doing it that way actually felt more right than implementing each of the helpers which would have enabled me to write something like (sum (filter (lambda ...) (range 1 1000)))). I'm not sure how I should feel about that. I would have guessed that a lack of libraries would slow me down as a programmer, but I wouldn't have thought that it would have such a pronounced effect on my actual coding style. But it does. If something I want isn't immediately available, my subconscious knee-jerk reaction isn't to implement it myself -- it's to think, "Oh, then I must not be supposed to use it!" and to look for a workaround.

I moved on to Euler problem 2: "Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million." I had it in Python in about five minutes. Then I went to check my answer by doing it in Scheme. And it dawned on me that I didn't want to.

You guys, a Fibonacci problem. In Scheme. That I didn't want to do. I actually called Alex oniugnip to tell him I was having a crisis of faith. I am entirely serious. That's what I did.

After talking to Alex, though, since I was on a roll and didn't want to think about my crisis of faith, I moved on to Euler 3. "What is the largest prime factor of the number 600851475143?" Now we're talkin'! Hey, I bet I can use one of those crazy generator things! Better find out what that's all about, huh?

Then I hit a brick wall. I stared and stared at Guido's example of a generator in the Python tutorial, but it didn't seem apropos -- it seemed like, well, like the sort of thing that I could do just as easily without a generator, anyway. More to the point, though, I couldn't figure out how to generate an infinite stream! And I'm not just talking about the primes -- I'm saying I couldn't figure out how to do any infinite stream.

I went and got my SICP off the shelf and flipped it open to section 3.5.2. Oh, yes. A stream of the integers. A stream of the integers not divisible by 7. A stream of the Fibonacci numbers. And -- yes! -- a beautiful sieve of Eratosthenes! And, you know, it's SICP, so it's a hardened little pearl of a program, wrapped around a grain of sand they introduced back 20 or 50 or 100 pages ago, and moreover, you've been able to do this kind of thing in Scheme since before Python was ever thought of, because Scheme can be anything you want it to be!2

But I called Alex back, and Alex put Mark on, and I said, "How do I generate the integers?" and Mark explained, and I did like he said, and wait, what? It just goes back to where it left off when you call next()? Nah, too easy. But -- but -- it worked! And then I did it for the not-divisible-by-sevens, and for the Fibonacci numbers, and I'm just not believing it and I'm not believing it and no way. No. Way. This is cheating. It's cheating it's cheating it's cheating it's cheating it's cheating it's cheating it's cheating

def sieve():
    i = 2
    while True:
        yield i
        n = i + 1
        for k in range (2, i):
            if n % k == 0:
                n = n + 1
        i = n

"Python is cheating!" I told Will and Dan after class on Tuesday. They laughed.


  1. And fewer to read.
  2. Actually, maybe what I want to say is: The only thing that Scheme can't be is a language that can't be everything.
LinkReply

Comments:
[User Picture]From: pmb
2009-01-17 11:43 am (UTC)

Woo pythoooon!

Also, something that blew my mind about generating primes:
"The Genuine Sieve of Eratosthenes" - http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
(Reply) (Parent) (Thread)
[User Picture]From: stereotype441
2009-01-17 03:13 pm (UTC)

Re: Woo pythoooon!

Whoa.
(Reply) (Parent) (Thread)
[User Picture]From: dlakelan
2009-01-18 06:10 am (UTC)

Re: Woo pythoooon!

I remember programming a seive of eratosthenes at Chases' house in Pascal ca. 1991. Pretty sure with a little help from you we got it to do the first hundred thousand primes in less than 1 second on a 33mhz or so Mac LC

The real sieve is a thing of beauty.
(Reply) (Parent) (Thread)