?

Log in

No account? Create an account
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: jes5199
2009-01-18 12:35 am (UTC)
1) I am astounded that any scheme fails to have "reduce" or "filter". Those always near the top the list of "useful things we learned from LISP"

2) A programming language that discourages writing sub-functions is dangerous

3) Why doesn't ruby have generators? I guess we would write them inside out- pass your prime-eating code as a block:
def factor(n)
  factors = []
  my_sieve.each do |d|
    break if n < d
    if n % d == 0
      factors.push(d)
      n /= d
      retry
    end
  end
  return factors
end

and the sieve (from your google page, bug included:)
def sieve
  i = 2
  loop do
    yield i
    n = i + 1
    (2...i).each do |k|
      if n % k == 0
        n = n + 1
      end
    end
    i = n
  end
end
(Reply) (Thread)
[User Picture]From: jes5199
2009-01-18 12:47 am (UTC)
the bug seems to be
if n % k == 0
  n = n + 1


n + 1 is never tested for factors in 2..k

I've got a fixed version for ruby, but it's not pretty:
def sieve
  i = 2
  loop do
    yield i
    n = i + 1

    catch(:next) do
      loop do
        catch(:retry) do
          (2...i).each do |k|
            if n % k == 0
              n = n + 1
              throw :retry
            end
          end
          throw :next
        end
      end
    end

    i = n
  end
end
(Reply) (Parent) (Thread)
[User Picture]From: conform
2009-01-18 02:00 am (UTC)
here's the version i had last night after i fixed the bug and started incrementing by twos:

def sieve():
	i = 2
	n = 3
	yield i
	while True:
		for k in range (3, n):
			if n % k == 0:
				break		
		else:
			i = n
			yield i
		n += 2
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-01-18 01:39 am (UTC)
python generators in ruby, implementing using the terrifying callcc magic. http://pastie.org/363584
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-02-17 03:44 pm (UTC)
I am astounded that any scheme fails to have "reduce" or "filter". Those always near the top the list of "useful things we learned from LISP"

For what it's worth, Chez has fold-left and fold-right. And I'm not sure any actual Scheme doesn't have filter, despite it not being in the (old version of the) spec.
(Reply) (Parent) (Thread)