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.

Merge sort in Scala and Processing (2/3)

(Part 1 2 3)

For my merge sort demonstration, I wanted a factory object producing snapshots of progressive sorting in an array of integers. It would essentially be a (partial) function with the signature
(Array[Int]) ⇒ RepeatingIterator[Int].

The argument to the factory is an array of integers that represents the initial state, before sorting.

The class RepeatingIterator is derived from Iterator. It repeats infinitely by yielding the first item after the last, and so on.

  object SortStates {
    def apply (init: Array[Int]) = {
       Create stages 

       Define conversion function 

      new RepeatingIterator(Seq(init) ++
        (stages map convFn))
    }
  }

Create stages

The states of partial to complete ordering are mapped from an instance of Stages (which is a structure that will be described in part 3; suffice to say that it provides a method def map (f: List[Int] ⇒ Array[Int])).

      val size   = init.size
      val stages = new Stages(size)

Define conversion function

The function passed to map is an object whose apply method takes two arguments: a copy of the initial state, and one of the stages mapped over.

      val convFn = StateFunc(init take size) _

The StateFunc object

This object is a function (Array[Int])(List[Int]) ⇒ Array[Int] that takes as its first argument the previous state of the values. The second argument is a list that describes one stage in the merging process. After building a state with buildState, it is written back to the data parameter and finally returned.

object StateFunc {
   Define merge method 

   Define splitMerge method 

   Define buildState method 

  def apply (data: Array[Int])(stage: List[Int]) = {
    val state =
      buildState(data, stage).flatten.toArray

    for (i ← 0 until data.size)
      data(i) = state(i)

    state
  }
}

Define buildState method

The buildState method builds a new state by merging the sorted lists of the previous state. One merge operation is done for each element of the stage data structure. During each merge operation, the following constants are defined:

n

the length of the resulting sublist

s

the total length of the sublists that are already merged

r

a list of n values past the s first values of data

If the sublist length (n) is 1, it is already sorted and r is simply added to the result. Otherwise, r is passed to the method splitMerge.

  private def buildState (data: Array[Int], stage: List[Int]) = {
    for {
      i ← 0 until stage.size
      n = stage(i)
      s = (stage take i sum)
      r = (data drop s take n).toList
    } yield if (n == 1) r else splitMerge(r)
  }

Define splitMerge method

The splitMerge method splits its parameter (which has n values) into two sublists with n / 2 and n - n / 2 values, respectively. The subroutine merge is then applied to the two lists.

  private def splitMerge (r: List[Int]) = {
    val n   = r.size
    val n_2 = n / 2
    val xs1 = r take n_2
    val xs2 = r drop n_2 take (n - n_2)
    merge(xs1, xs2)
  }

Define merge method

The merge method is the same as in the mergeSort function in part 1.

  private def merge (a: List[Int], b: List[Int]): List[Int] =
    (a, b) match {
      case (_, Nil) ⇒ a
      case (Nil, _) ⇒ b
      case (ah :: at, bh :: _) if (ah <= bh) ⇒
        ah :: merge(at, b)
      case (_, bh :: bt) ⇒ bh :: merge(a, bt)
    }

And that's it for SortStates and StateFunc. In the final part I will show Stages and RepeatingIterator.