Skip to main content

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:

#!/usr/local/bin/io

/*
* 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 := "findprimes_modcount.io"

/*
* 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(
FIRST_PRIME := 2
DEFAULT_OPT_TRIES := 2

/*
* 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,
optTries := DEFAULT_OPT_TRIES
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:
Io:
findprimes_modcount.io
timed 0m23.274s
meaningful lines of code 45

findprimes_simple.io
timed 0m5.868s
meaningful lines of code 28

Python:
findprimes_modcount.py
timed 0m3.891s
meaningful lines of code 45

findprimes_simple.py
timed 0m1.313s
meaningful lines of code 28

Perl:
findprimes_modcount.pl
timed 0m6.590s
meaningful lines of code 42

findprimes_simple.pl
timed 0m1.016s
meaningful lines of code 31

C:
findprimes_modcount.c
timed 0m0.655s
meaningful lines of code 73

findprimes_simple.c
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 ;)

Comments

Brandon L. Golm said…
For most values of 42, 42 is less than 45. So, of course, your Perl code is fewer lines. That's good for the following reasons: (1) it's ugly, and ugly is good. and (2) only Perl programmers will be able to read it, thus nobody new will try to learn Perl (if they do, they will be flamed on CLPM), (3) perl6 (not Perl 6) will never exist, but if it does you can bet it will be ugly (??::), (4) bye.

Popular posts from this blog

Ubuntu 20.04 on a 2015 15" MacBook Pro

I decided to give Ubuntu 20.04 a try on my 2015 15" MacBook Pro. I didn't actually install it; I just live booted from a USB thumb drive which was enough to try out everything I wanted. In summary, it's not perfect, and issues with my camera would prevent me from switching, but given the right hardware, I think it's a really viable option. The first thing I wanted to try was what would happen if I plugged in a non-HiDPI screen given that my laptop has a HiDPI screen. Without sub-pixel scaling, whatever scale rate I picked for one screen would apply to the other. However, once I turned on sub-pixel scaling, I was able to pick different scale rates for the internal and external displays. That looked ok. I tried plugging in and unplugging multiple times, and it didn't crash. I doubt it'd work with my Thunderbolt display at work, but it worked fine for my HDMI displays at home. I even plugged it into my TV, and it stuck to the 100% scaling I picked for the othe

ERNOS: Erlang Networked Operating System

I've been reading Dreaming in Code lately, and I really like it. If you're not a dreamer, you may safely skip the rest of this post ;) In Chapter 10, "Engineers and Artists", Alan Kay, John Backus, and Jaron Lanier really got me thinking. I've also been thinking a lot about Minix 3 , Erlang , and the original Lisp machine . The ideas are beginning to synthesize into something cohesive--more than just the sum of their parts. Now, I'm sure that many of these ideas have already been envisioned within Tunes.org , LLVM , Microsoft's Singularity project, or in some other place that I haven't managed to discover or fully read, but I'm going to blog them anyway. Rather than wax philosophical, let me just dump out some ideas: Start with Minix 3. It's a new microkernel, and it's meant for real use, unlike the original Minix. "This new OS is extremely small, with the part that runs in kernel mode under 4000 lines of executable code.&quo

Haskell or Erlang?

I've coded in both Erlang and Haskell. Erlang is practical, efficient, and useful. It's got a wonderful niche in the distributed world, and it has some real success stories such as CouchDB and jabber.org. Haskell is elegant and beautiful. It's been successful in various programming language competitions. I have some experience in both, but I'm thinking it's time to really commit to learning one of them on a professional level. They both have good books out now, and it's probably time I read one of those books cover to cover. My question is which? Back in 2000, Perl had established a real niche for systems administration, CGI, and text processing. The syntax wasn't exactly beautiful (unless you're into that sort of thing), but it was popular and mature. Python hadn't really become popular, nor did it really have a strong niche (at least as far as I could see). I went with Python because of its elegance, but since then, I've coded both p