April 2, 2008

Functional ActionScript – Part III

In Part I of Functional ActionScript I gave a short introduction to functional programming in ActionScript. Then, Part II discussed some functional APIs that ActionScript provides and gave an example for each one of them. This last part — Part III — of my series will be a little bit different. This time I would like to take the opportunity to share a small but fascinating example with you that will hopefully serve as an inspiration to look at functional programming more closely.

Functional vs. Imperative

Without going into much depth, I'd like to quickly discuss the main conceptual difference between functional and imperative programming as it applies to the example in this article. In the course Formal Methods & Functional Programming we were taught that often times functional vs. imperative is actually about what vs. how

Programming in an imperative way (i.e., in ActionScript, C, Eiffel, etc.) means that we're telling the machine each step it has to take to get to the result. In that case, it's all about how to do it to get there. On the other hand, if we program in a functional way, it's more about the what to do rather than how to do it to get to the result. Please keep this in the back of your head as you continue reading.

Haskell

In summer 2007, just before finishing my first year as undergraduate at ETH, an assistant gave us a sneak peek at the courses in the second year of the Computer Science curriculum. I remember, when we looked at the course Formal Methods & Functional Programming he showed us the following example. I also remember that I was quite impressed.

Example: QuickSort

Here we go: QuickSort in Haskell… 
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
…compared to QuickSort in C. 
void qsort(int a[], int lo, int hi) {
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p))
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    t = a[l];
    a[l] = a[hi];
    a[hi] = t;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

Walk-Trough

Let’s look at these three lines that reveal us quite a bit about Haskell:

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

Line 1: This is the type declaration for the function qsort. Haskell has a very sophisticated type system that goes beyond what we can observe here but this is interesting nonetheless.

First, since qsort a sorting algorithm it takes a list of something (where a is that something and the square brackets denote that it is a list of something) and again returns a list of that something. Compare this to ActionScript, for example. There you have to define explicit types such Number, String, etc. (if you want to take advantage of the static type checking) and therefore hypothetically have to write a separate sorting algorithm for each one of them, e.g. one that takes a list of Number and one that takes a list of String. Unlike ActionScript 3 (where it’s optional), Haskell is statically typed. To avoid the mess of having to write a sorting routine for every type, Haskell takes advantage of parametric polymorphism. All you need to tell Haskell, is that this something called a has a total order, meaning you can compare two instances of a and determine which one is greater than the other. This is done with the constraint: Ord a =>

Line 2: Here we merely say that if qsort gets an empty list it will return an empty list. This elegant notion of handling different inputs by listing the cases specifically takes advantage of Haskell’s pattern matching capabilities.

Line 3: This is the line where all the magic happens. This is such a great example for the expressiveness of functional programming that I hope I can convey its meaning as clearly as possible.

First, qsort is called with a non-empty list (since the empty list case is covered in line 2) that is defined as x:xs. This notation basically means that the list is split into x, the first element of the list, called head, and xs, the rest of the list, called tail. Second, we select the head of the list x as pivot. Then we recursively call qsort with a new list that looks like this:

[y | y <- xs, y < x]

Read it as follows: Take all y, where y is an element of xs (the tail or the rest of the list) and y is smaller (mathematically: less than) than the pivot x.

Just look at this as QuickSort’s partitioning. The code above actually could be rewritten like this:

(filter (< x) xs)

I prefer the former variant which is basically syntactic sugar and takes advantage of Haskell’s list comprehension feature. Coming to think of it, my preference is probably influenced by my ETH background where we were indoctrinated with set theory. Chuckle.

This was the hard part actually, as the rest works pretty much the same. We concatenate this left-hand side sub-list with the pivot…

… ++ [x] ++ …

…and then all the preceding with the right-hand side sub-list that is the sorted list of all elements that are greater or equal the pivot x:

qsort [y | y <- xs, y >= x]

…and we're done.

Discussion

If you compare the functional Haskell and the imperative C version of QuickSort you can hopefully see what I was trying to bring across regarding to the concept of what vs. how. Besides this, I can't think of anything to discuss at this point… well, maybe except for questions like What about performance? (which I hope to cover some time in the future) or Is this even a real QuickSort? (…if you ask C. A. R. Hoare the answer is probably «No.»)

It is important to note that this series (I dare not to say life) is not about programming language X vs. programming language Y. It's about learning different concepts or rather different ways of thinking and apply the best of them in our daily endeavours as programmers. At this point I'd like to thank my buddy Boris (who's busy working on his Google Reader App for the iPhone as I am writing this) for the great discussions about software engineering & programming languages that sometimes keep us both awake until 3am. This exchange pushes me to think outside the box every day. Thanks. And yes, Boris, I will hopefully pick up Python sometime…

One More Thing…

What would this part of the series on Functional ActionScript be, if it wasn’t even related to ActionScript and I didn’t have the opportunity to show off a little bit?

Example: Functional QuickSort in ActionScript

Here we go: 
function quickSort( list : Array ) : Array
{
  // non-recursive branch
  if( list.length == 0 )
  {
    // return the empty array if we can't split it more
    return []
  }
  else
  {
    // choose first element as pivot
    var pivot : Number = list[ 0 ]

    // slice of the pivot and keep them as rest
    var rest : Array = list.slice( 1 )

    return(
      // sort all numbers…
      quickSort(
        // …that are less or equal than pivot…
        rest.filter(
                wrap( lessOrEqualThan( pivot ) )
              )
           )
           // …concatenate them with the pivot…
           .concat(
                [ pivot ]
              )
           // …and concatenate all of the previous…
           .concat(
      // …with all sorted numbers…
      quickSort(
        // …that are greater than pivot.
        rest.filter(
                  wrap( greaterThan( pivot ) )
                )
           )
          )
      )
  }
}

function lessOrEqualThan( value : Number ) : Function
{
  return(
         function( x : Number ) : Boolean
         {
           return x <= value
         }
      )
}

function greaterThan( value : Number ) : Function
{
  return(
         function( x : Number ) : Boolean
         {
           return x > value
         }
      )
}
For the definition of wrap check out Functional ActionScript – Part II.

The example above (and the fact that I wrote it in a few minutes) made me realize for the first time the potential of ActionScript which allows us to write programs in a functional way. The QuickSort code in ActionScript is pretty much the equivalent of the Haskell code at the beginning. You can walk through it with the Haskell Walk-Trough and the comments will hopefully help you in case you get stuck.

But does this actually work? Let's see what happens when we take an unsorted list and run quickSort on it:

var unsortedList : Array = [ 23, 15, 16, 42, 8, 4 ]

quickSort( unsortedList )

//? 4,8,15,16,23,42

Tada! Works like a charm. Enjoy.

Source

View Source | Download Source (ZIP, 3KB)

Epilogue

Like I said at the beginning, this was the last part of my series on Functional ActionScript. I hope you enjoyed reading it and learned something new here and there. I definitely did. If would like to learn more about functional programming, I suggest you to check out Haskell or look at some of the links I put together in Further Reading. As I will learn more about all of this myself, I hope I will come back to this really fascinating topic sometime in the future. Stay tuned.

Further Reading

References