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:


* 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 ;)


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

Drawing Sierpinski's Triangle in Minecraft Using Python

In his keynote at PyCon, Eben Upton, the Executive Director of the Rasberry Pi Foundation, mentioned that not only has Minecraft been ported to the Rasberry Pi, but you can even control it with Python . Since four of my kids are avid Minecraft fans, I figured this might be a good time to teach them to program using Python. So I started yesterday with the goal of programming something cool for Minecraft and then showing it off at the San Francisco Python Meetup in the evening. The first problem that I faced was that I didn't have a Rasberry Pi. You can't hack Minecraft by just installing the Minecraft client. Speaking of which, I didn't have the Minecraft client installed either ;) My kids always play it on their Nexus 7s. I found an open source Minecraft server called Bukkit that "provides the means to extend the popular Minecraft multiplayer server." Then I found a plugin called RaspberryJuice that implements a subset of the Minecraft Pi modding API for B

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

Creating Windows 10 Boot Media for a Lenovo Thinkpad T410 Using Only a Mac and a Linux Machine

TL;DR: Giovanni and I struggled trying to get Windows 10 installed on the Lenovo Thinkpad T410. We struggled a lot trying to create the installation media because we only had a Mac and a Linux machine to work with. Everytime we tried to boot the USB thumb drive, it just showed us a blinking cursor. At the end, we finally realized that Windows 10 wasn't supported on this laptop :-/ I've heard that it took Thomas Edison 100 tries to figure out the right material to use as a lightbulb filament. Well, I'm no Thomas Edison, but I thought it might be noteworthy to document our attempts at getting it to boot off a USB thumb drive: Download the ISO. Attempt 1: Use Etcher. Etcher says it doesn't work for Windows. Attempt 2: Use Boot Camp Assistant. It doesn't have that feature anymore. Attempt 3: Use Disk Utility on a Mac. Erase a USB thumb drive: Format: ExFAT Scheme: GUID Partition Map Mount the ISO. Copy everything from