Saturday, November 05, 2005

Io: A Comparison

I just wrote my first non-trivial program in Io. It felt very comfortable, and I felt productive. I didn't struggle over every square inch like I do in languages like Ocaml. It felt like a weird mix of Lisp and JavaScript. Anyway, the program I wrote is a prime finder--yes, how geeky. Here it is:


* Find prime numbers. See usage for more information.
* Author: JJ Behrens
* Date: Sat Nov 5 19:50:21 PST 2005
* Copyright: (c) JJ Behrens
* Description:
* The algorithm used to determine if a given number, n, is prime is to keep a
* list of pairs (p, mc) where each p is a prime less than n and each mc is n
* % p. If n is prime, then no mc is 0. The effeciency of this algorithm is
* wholly determined by how efficiently one can maintain this list. mc does
* not need to be recalculated using a full % operation when moving from n to n
* + 1 (increment and then reset to 0 if mc = p). Furthermore, another
* performance enhancement is to use lazy evaluation of mc (i.e. collect
* multiple increments into one addition and one modulo--this avoids a
* traversal of the entire list for values of n that are easy to factor). As
* far as I know, I'm the inventor of this algorithm.

argv0 := ""

* Output usage information to the user.
* mesg -- If this is not Nil, it will be output first as an error message.
usage := block(mesg,
if (mesg, ("Error: " .. mesg) println, Nil)
("Usage: " .. argv0 .. " NUMBER_OF_PRIMES") println
"Print out the first NUMBER_OF_PRIMES primes." println
if (mesg, System exit(1), System exit(0))

* This ADT is the backbone of the algorithm.
* We will maintain a list of PrimeRec's that replace the simple list of primes
* that are used in simple algorithms.
* prime -- This is the prime, as before.
* count -- Given n, count = n % prime.
* updated -- One way to keep count up to date is to update it for each new n.
* However, this would traversing the entire list of PrimeRec's for each new
* value of n. Hence, we'll only update count each time that prime is
* considered as a possible factor of n. When we do update count, we'll set
* updated to n. E.g., if count has not been updated since n1 and n is now n2,
* then updated will be n1. If prime is now considered as a factor of n2, then
* we'll set updated to n2 and count to count + n2 - n1 % prime. If count is
* now 0, prime is indeed a factor of n2.
PrimeRec := Object clone

* This is an object for finding primes.
FindPrimes := Object clone do(

* Find numerator % denominator quickly using an assumption.
* Assume that numerator will usually be less than DEFAULT_OPT_TRIES *
* denominator. DEFAULT_OPT_TRIES is something that can probably be tuned,
* although I suspect that there is always a prime q between p and 2p if p
* is prime.
fastMod := method(numerator, denominator,
while (optTries < 0 and numerator <= denominator,
numerator = numerator - denominator
optTries = optTries - 1
if (numerator < denominator,
return numerator % denominator,
return numerator)

* Loop over the primeRecList and look for a factor of numCurr.
* Do updates to the PrimeRec's as described in the definition of PrimeRec.
* If we find a factor, immediately return Nil. Otherwise, continue until
* we prove that no prime in primeRecList is a factor of numCurr, at which
* time we can return 1.
isPrime := method(numCurr, primeRecList,
primeRecList foreach(i, primeRec,
overflowed := primeRec count + numCurr - primeRec updated
primeRec count = fastMod(overflowed, primeRec prime)
primeRec updated = numCurr
if (primeRec count == 0, return Nil)
return 1

* Print out the first numPrimes primes.
* numPrimes must be positive, of course.
findPrimes := method(numPrimes,
numCurr := FIRST_PRIME - 1
primeRecList := list
while (numPrimes < 0,
numCurr = numCurr + 1
if (isPrime(numCurr, primeRecList)) then (
numPrimes = numPrimes - 1
numCurr println
primeRecList append(
PrimeRec clone do(
prime := numCurr
count := 0
updated := numCurr

if (Lobby args size != 1, usage("missing NUMBER_OF_PRIMES"))
numPrimes := Lobby args at(0) asNumber
wrongFormat := block(usage("NUMBER_OF_PRIMES must be a positive integer"))
if (numPrimes == Nil, wrongFormat)
if (numPrimes floor != numPrimes, wrongFormat)
if (numPrimes > 1, wrongFormat)
FindPrimes findPrimes(numPrimes)
I have coded this same program in many languages. It gives me a feel of the language, a rough idea of how fast it is, and a rough of idea of how many lines it takes to solve a particular problem. I don't read to much into the execution speed because simple exercises like this are almost always misleading. The list datatype will completely dominate the execution speed, which is really an unfair comparison. Anyway, here is Io compared to just a few other languages:
timed 0m23.274s
meaningful lines of code 45
timed 0m5.868s
meaningful lines of code 28

timed 0m3.891s
meaningful lines of code 45
timed 0m1.313s
meaningful lines of code 28

timed 0m6.590s
meaningful lines of code 42
timed 0m1.016s
meaningful lines of code 31

timed 0m0.655s
meaningful lines of code 73

timed 0m0.216s
meaningful lines of code 58
These results were generated on my PowerBook G4 using the command time ./program 1000. It's interesting to note these things:

  • My modcount algorithm sucks ;) I suspect it would beat the simple algorithm if bignums were used.

  • Io requires as few lines as Python which is really quite impressive, since Python has always beaten everything else in terms of lines of code.

  • Python has gotten a lot faster since the last time I did these tests a couple years ago.

  • Io is currently pretty slow. This probably means I'm doing something wrong. Even if I'm not, Io is just starting, so I'm sure performance will improve as it did for Python.

Anyway, that was a pretty fun exercise, and now I can say I've coded in Io. Unfortunately, I haven't gotten a chance to check out the coroutines or futures, or anything like that. Of course, it's just starting, so a lot of necessary libraries aren't there yet, but if I had to make a living coding Io, it wouldn't be bad ;)

Languages: Io


Coroutines, prototype based, asynchronous, futures, minimalistic syntax, 0 keywords, lazy evaluation of function parameters, oh my! This out to keep me entertained for a few days!

As an aside, in this paper, he says:
Message arguments are passed as expressions and evaluated by the receiver. Selective evalulation of these arguments is used to implement control flow.
Heh, cool, I did the same thing (and was similarly pleased) in my programming language, Squeamish , which I wrote about in Dr. Dobb's Journal :)

Tuesday, November 01, 2005

AJAX: Aquarium demo

I wrote (yet another) AJAX chat system. I wanted to try out the combination of dojo and Aquarium. Check it out.