Doing Eratosthenes Justice

Yesterday I showed how to use some closures and macros to implement (very inefficient) lazy lists in Lisp. One of my examples produced an infinite list of prime numbers.

BlueStorm quite correctly pointed out that it was O(n^2), while the classic sieve of Eratosthenes is O(n log n). Always up for a challenge, I went ahead wrote a proper sieve.

(def merge_ (xs ys)
  (with (x (car_ xs) y (car_ ys))
    (if (< x y) (cons_ x (merge_ (cdr_ xs) ys))
        (> x y) (cons_ y (merge_ xs (cdr_ ys)))
        (cons_ x (merge_ (cdr_ xs) (cdr_ ys))))))

(def diff_ (xs ys)
  (with (x (car_ xs) y (car_ ys))
    (if (< x y) (cons_ x (diff_ (cdr_ xs) ys))
        (> x y) (diff_ xs (cdr_ ys))
        (diff_ (cdr_ xs) (cdr_ ys)))))

(def merge-multiples (li)
  (with (xs (car_ li) rest (cdr_ li))
    (cons_ (car_ xs)
           (merge_ (cdr_ xs) (merge-multiples rest)))))

(def multiples (p) (map_ [* _ p] (count-from p)))

(= primes 
  (cons_ 2 (cons_ 3 (cons_ 5 (diff_ (count-from 7) non-primes)))))

(= non-primes (merge-multiples (map_ multiples primes)))

A typical optimization is to ignore multiples of 2, as follows.

(def count-from-by (n by) (cons_ n (count-from-by (+ n by) by)))

(def multiples (p) (map_ [* _ p] (count-from-by p 2)))

(= primes
  (cons_ 2 (cons_ 3 (cons_ 5 (diff_ (count-from-by 7 2) non-primes)))))

(= non-primes (merge-multiples (map_ multiples (cdr_ primes))))

Lazy Lists in Arc

No time for inflammatory ranting today. We're going to define lazy lists in Arc. (See also CL version.)

The idea of adding lazy lists to Lisp dates back to TR44:
CONS should not Evaluate its Arguments (Daniel P. Friedman, 1976). Guy Steele discusses TR44 and other cool ideas in this talk.

In order to delay evaluation, the lazy cons will suspend its arguments in closures. These closures will be executed on first access, and the results stored.

(mac wrap (a) `(fn () ,a))
(def force (f) (wrap (f)))
(mac cons_ (a b) `(cons (wrap ,a) (wrap ,b)))
(def car_ (li) ((zap force (car li))))
(def cdr_ (li) ((zap force (cdr li))))

Presto, we're done! Those are all the primitive we need. Now we'll just define some typical list utilities to using our new car_, cdr_, and cons_.

(def filter (p li)
  (if (no li) li
      (p (car_ li)) (cons_ (car_ li) (filter p (cdr_ li)))
      (filter p (cdr_ li))))

(def map_ (f li)
  (if (no li) li
      (cons_ (f (car_ li)) (map_ f (cdr_ li)))))

(def take (n li) 
  (if (<= n 0) nil
      (cons (car_ li) (take (- n 1) (cdr_ li)))))

With those, we can start playing with infinite lists. For starters, the natural numbers.

(def count-from (n) (cons_ n (count-from (+ n 1))))

(= naturals (count-from 1))

(take 5 (filter odd naturals))   ; => (1 3 5 7 9)
(take 5 (map_ [* _ 3] naturals)) ; => (3 6 9 12 15)

Now, the primes:

(def sieve (li)
  (let p (car_ li)
    (cons_ p (sieve (filter [> (mod _ p) 0] (cdr_ li))))))

(= primes (sieve (count-from 2)))

Holy 4-line prime number sieve, Batman!

(take 10 primes)  ; => (2 3 5 7 11 13 17 19 23 29)

Here is the equivalent in Haskell (see also HaskellWiki.)

primes = sieve [2..] where
    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)

P.S. A multi-arg version of map_. I did the single argument version above because it is easier to follow.

(def map_ (f . lists)
  (if (some no lists) nil
      (cons_ (apply f (map car_ lists))
             (apply map_ f (map cdr_ lists)))))

P.P.S. Bonus: Fibonacci sequence.

(= fibs (cons_ 1 (cons_ 1 (map_ + fibs (cdr_ fibs)))))

Is Java the new COBOL? No.

I'll bash Java as much as the next guy, but when people start to throw around the 'C' word, that's where I draw the line. Being compared to COBOL is kind of like being compared to Hitler. As Dijkstra said in 1975:

The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offence.

Would anyone say the same about Java with a strait face?

The Perils of Java Schools offers some of the harshest criticism of Java to receive widespread attention. What's the chief complaint? Java is too easy! I'm serious. Joel actually asserts that Java is not difficult enough for a college curriculum. He argues that C++, with its pointer-juggling headaches, is much better at weeding out lesser minds.

This is such a bizarre thing to say that I hardly know where to start.

First off, I went to MST (formerly UMR) where our CS department uses C++ and we're damn proud of it. Therefore, it is with a heavy heart that I admit the following: Yes, Java is easier, but that's not a bug, it's a feature! Making programming easier is a Good Thing.

Second, there actually exist C++ programmers who don't understand recursion. Sad but true. It's even possible (albeit rare) to make it through my school's pointer minefield without being able to recurs your way out of a wet paper bag. Joel is just plain wrong to assume that there is a single "part of the brain" whose purpose is to grok pointers and recursion. Pointers and recursion are not the same. At all.

I'll grant that someone who only knows Java is unlikely to understand pointers, but how bad is that really? Pointers don't help you think in higher levels of abstraction. They exist for the sole purpose of getting in your way. Other respectable languages without pointers include: Lisp, Python, Haskell, Ocaml, and Scala.

Recursion is a completely different matter. Java and C++ both support recursion equally well (or equally poorly). If you don't understand recursion, you don't really understand functions/methods. Period.

Let's assume for the moment that I'm done picking on Joel Spolsky. His real point is that schools should not water down their curriculum, and I absolutely agree. Self-respecting CS departments should fight to keep data structures, operating systems, language design, and graph theory. They should also continue to require calculus. This all has nothing to do with our petty programming language feuds. Despite what we C++ elitists would have you believe, C++ is not an academic language. It is a vocational one. Universities teach C++ because employers want that skill, not because they think it builds character.

Still, in all of his anti-Java rhetoric, Joel never (AFAIK) compared Java to COBOL. That would be hitting below the belt.

What makes me rush to Java's defense all of the sudden? Mostly it's because I'm at home sick with a cold... but here is an equally good reason.

IDENTIFICATION DIVISION.
PROGRAM-ID. HELLO-WORLD.
PROCEDURE DIVISION.
MAIN.
   DISPLAY 'Hello World'.
   STOP RUN.

I can not and will not compare Java to that. Let's look at another example, just to drive it home.

x = y * 2;       // C, C++, Java
$x = $y * 2;     #  Perl
X = Y * 2        !  Fortran
(set! x (* y 2)) ;  Scheme
(= x (* y 2))    ;  Arc

These are all fairly reasonable ways to multiply y by 2 and store the result in x. How does it look in COBOL?

MULTIPLY 2 BY Y GIVING X.

I can't even look at that without cringing. COBOL was a horrifically misguided attempt to blend pseudo-code with pseudo-English. Being a "business-oriented language", COBOL had syntax designed to appeal to the managers of 1960. Java was an effort to simplify and enhance C++, designed to appeal to the programmers of 1995.

So remember: Java just kinda sucks. COBOL really really really really sucks. If COBOL were an ice cream flavor, it would be pralines and arsenic. If COBOL were the only programming language I could use, I would leave the field.

Nicknames for Noam Chomsky

[NOTE: If you have something better to be doing, you might want to move along. This is not one of my useful or insightful posts.]

This is part of an ongoing battle between myself and my linguistic superior, Hannah.

• Choam Nomsky
• Chommers in Charge
• Chomalicious
• Noam-ero Uno
• The Roaming Noam
• Chomfoolery
• Chernoambyl
• Chomp Suey
• Hong-Chom Phooey
• Long-Chom Silver's
• International House of Chomcakes
• GNU Gnoam 2.20
• Chomskeroony
• ThelNoamious Monk
• Everlasting Chomstopper
• The Blue-Collar Lingustics Tour featuring Jeff Foxchomsky and Chomsky the Cable Guy
• ENoamuel Chomstein
• Rikki-Tikki-Chomsky
• Chomery Clinton
• Barrack OChoma
• Chom Edwards
• Chom McCain
• Mitt Chomney
• Chom Knuth
• Necronoamicon
• H.P. Chomscraft
• The Call of Cthulhomsky
• Noamus Opperandi
• Chubby Chomsker
  
• Fats Chomino
• The Human Genoam Project
• Istanbul (Not ChomstantiNoample)
• Chompernicus

Current score: Ray 32, Hannah 45

Hannah: As a wise man once said: "It is not enough to succeed, one's friends must also fail."
Ray: Who said that? Chomfucious?

P.S. I can see now that this will be a battle of truly astronoamical proportions!

The Functional Programming Apologist

There do exist legitimate criticisms of functional programming (FP) concepts, just as there are reasonable criticisms of imperative style, procedural style, prolog-esk logic/constraint programming, and even our precious object-orientation. Still, as you might expect, the vast majority of the tomatoes hurled in the general direction of the FP community are totally absurd. Here are a couple actual comments from various blogs. I am not giving the sources for obvious reasons, but you could probably find them in Google.

Imperative languages represent the straight line from point A to point B. They reflect the true nature of the beast. If you had to slay a dragon, would you try to convince another dragon to fight for you, or would you grab a damn weapon?

Yes, as a matter of fact, I WOULD get another dragon to fight for me. It's called abstraction! This is why we have programming languages in the first place, even though machine code "reflects the true nature of the beast". Does your CPU know what object orientation is? Unless you do all your structure and flow control using GOTO, you are NOT reflecting the true nature of your beloved beast. Sorry to break the news.

Here's another real gem. I see this sort of thing all the time.

Closures in today's world are a "language geek" feature. Unless done extremely carefully and in a way that supports the various skill levels of developers, they end up being unusable and unsupportable by anything less than computer language savants. In their inherent obscurity and complexity, "language geek" style closures are about as anti-Java as you can get.

First off thanks for calling me a geek, I really didn't get enough of that growing up interested in computers. Imagine a time when Java didn't have generics. In other words, imagine Java 1 through 4. Java 5 generics evolved from the type classes in Haskell — a fringe fancy-pants FP academic language if there ever was one. Some people (possibly the same ones) were saying:

Generics in today's world are a "language geek" feature. Unless done extremely carefully and in a way that supports the various skill levels of developers, they end up being unusable and unsupportable by anything less than computer language savants. In their inherent obscurity and complexity, "language geek" style generics are about as anti-Java as you can get.

I think I've made my point.

But wait! Maybe I've been wrong all these years! Maybe generics and even anonymous inner classes are perfect additions to Java, but closures would be stepping way over the line. After all, they are an FP concept and Java is OO. That's like the Hatfields and the McCoys and the two would never mix. Could that really be the case?

Let's see what James Gosling, the inventer of Java, said about it just yesterday:

There has been a lot of chatter about the closures proposal penned by Neal Gafter. And, in particular, whether or not I support it. I absolutely do. Java feels alive, not stuck in some chisel marks on stone tablets. Closures were left out of Java initially more because of time pressures than anything else. Closures, as a concept, are tried and true - well past the days of being PhD topics.

And don't even ask me what Guy Steele would say about it!