Tony Morris

Not your usual Haskell weenie.

Kojo with Staging

Lalit Pant has released a new version of Kojo. It features Staging, a new 2D graphics/animation module by yours truly. :)

The announcement and download link is here.

Brushing off some cobwebs...

Oh, I'm still around somewhere, but things have been a bit hectic lately. On the plus side, I've gotten involved with the Kojo project. On the not so plus side, I've had (and have) some pretty horrible personal issues to deal with.

Eventually, there will be more here.

Wonktional programming

Daedalus and his son Icarus were imprisoned by King Minos, and made themselves wings out of wax and feathers to escape. Before they took off from the island, Daedalus warned his son not to fly too close to the sun. The sensation of flying made Icarus forget the warning and he soared higher and higher. Eventually the wax melted and he fell into the sea.

A programmer can escape the prison of procedural programming using functional programming, but going for the purest form of FP isn't really a sustainable goal. Most likely, these wonktional programmers will melt their wings by straying too close to the realm of mathematics and plunge to their deaths.

(A response to this.)

The Literate Programming Wiki

I've made a couple of contributions at the LiteratePrograms Wiki. Literate programming has never really caught on, but I personally like it as a way to document a program. I usually don't develop programs as literate source because I tend to rewrite a completely a few times to try different approaches, and I suspect this is true for many programmers, especially hobby programmers. However, the wiki reunited me with the Inform programming language, and it seems that it is currently being developed in literate form. I will look into this.

Unsung

Most of us In The Business can name a lot of men and their accomplishments: Vint Cerf ("The father of the Internet"), John Backus (FORTRAN, BNF), Donald Knuth (WEB, TeX, TAOCP), Bill Gates (um, yeah).

But, can you name the person who invented the compiler? Do you know who developed the Apollo flight software? Who designed the trashcan icon and the Windows Solitaire deck? Can you name any of the six first programmers on the ENIAC?

If you can't, it could be because they belong to a certain group that tends to be overlooked. You can find some of them on this list, though.

Established 1993

Yes, really. Not on the web, of course, but I was blogging (sort of) about programming and coding on FidoNet back then (the "point" comes from the FidoNet addressing terminology). I maintained a website about C/C++ from ca. 1996, and revived the name Point Pelewin for a personal web site in 1998.

                   __
                  /  \
                 /|oo \
                (_|  /_)
                 _`@/_ \    _
                |     | \   \\
                | (*) |  \   )) 
   ______       |__U__| /  \//
  / FIDO \       _//|| _\   /
 (________)     (_/(_|(____/

Merge sort in Scala and Processing (3/3)

(Part 1 2 3)

Odds and Ends

In the first two parts, I demonstrated visualization of the process of merge sorting an array of integers. In this part I will describe the two steps left undescribed: how to create a collection of stages and how to create a repeating iterator. I will also present a shuffling function that can be used to create the initial state.

The Stages class

The Stages class provides a map method which is used by the SortStates class to create a collection of states. The function that creates one of the states needs to 1) see the state array (which contains the previous state) and 2) be told how to rearrange it into the next state. The actual function passed to map is curried with the state array, so the only thing map needs to prepare is the collection of stages of rearrangement information.

class Stages (n: Int) {
   Define generate method 

  def map (f: List[Int] => Array[Int]) =
    generate() map f
}

Define generate method

The generate method creates the stages recursively, bottoming out when the parameter i exceeds n.

  private def generate (i: Int = 2): List[List[Int]] = {
     Define split subroutine 

    if (n <= i) {
       Base case 
    } else {
       Preceding cases 
    }
  }

Base case

In the base case, the state array (whose length is stored in the n field) is in a partially sorted state where two sublists of roughly equal length are individually sorted (e.g. Array(1, 3, 5, 0, 2, 4)) and are to be merged into a completely sorted array. The conversion function, of class StateFunc (described in part 2), will be able perform this operation if given a list containing the total length of the sublists, i.e. List(n).

      List(n) :: Nil

Preceding cases

In each of the cases preceding the base case, the state array consists of k pairs of sorted sublists that are to be merged into k sorted sublists (which will be merged in the next stage, and so on). Thus, in the general case C_x the stage information is a list of 2 × k integers where the sum of each pair is equal to the corresponding integer in the stage information of the following case C_x+1.

      val tail = generate(2 * i)
      split(tail.head) :: tail

Define split subroutine

The split subroutine uses h to create a list of integers whose size is twice that of h and where every element e ∈ h is mapped to two elements, the first being e/2 and the second being e-e/2.

    def split (h: List[Int]) =
      h flatMap { e => List(e/2, e-e/2) }

The RepeatingIterator class

The RepeatingIterator class trivially encapsulates a sequence and overrides the next method to reset the internal iterator every time it is exhausted. The hasNext method accordingly always returns true.

class RepeatingIterator[A] (xs: Seq[A]) extends Iterator[A] {
  private var iter = xs.iterator
  override def hasNext = true
  override def next () = {
    if (!iter.hasNext) iter = xs.iterator
    iter.next
  }
}

Shuffling the values

In the example, I passed an array of values in reverse order to SortStates. Alternatively, the array can be shuffled like this:

object Shuffle {
  private val rand = new scala.util.Random

  def apply[A] (xs: Array[A]) = {
    for (n <- 0 until xs.size) {
      val k = n + rand.nextInt(xs.size-n)
      val v = xs(k)
      xs(k) = xs(n)
      xs(n) = v
    }
    xs take xs.size
  }
}

And that's merge sort.