March 29, 2008

Functional ActionScript – Part I

One of the things I love about studying Computer Science is all the different languages & concepts I am being exposed to. When I started this blog, one of my goals was to present these concepts to people who maybe haven’t yet come across them. In the following series of posts, I will give you a sneak peek into one of these concepts, called Functional Programming and how it can make your life as ActionScript programmer easier.

The inspiration for this series comes from two sources, namely…

  1. An old blog post by Ruben Swieringa
  2. The course Formal Methods & Functional Programming

Retrospective

Back in time, Ruben wrote a utility function that… …lets you increase/decrease/multiply/divide
all values of an Array all at once.

This idea behind it shows a great deal of understanding from Ruben. I assume that he recognized he was writing the same code over and over again (a violation of the DRY principle.) Namely, code to apply a certain operation to the elements of an Array. So he did the right thing and extracted this code into a separate class and released it under the name ArrayTool.

Feel free to take look at Ruben’s code. Later, I will show you how to take his good idea, take it even one step further and how all of this relates to Functional Programming.

Functions Are Your Friends

This semester, I am taking a course called Formal Methods & Functional Programming. As part of the course we are learning a programming language called Haskell. Haskell belongs to the family of functional programming languages. Besides the fact that it has no assignments in the traditional sense and everything revolves around lists and functions, there’s even more to find out in this very enlightening introduction to Haskell.

Now I will show you what concepts we can take from Haskell (or any other functional programming language for that matter) and apply them in ActionScript. Strange enough, many people are not aware that ActionScript allows us to program in a functionial way to a certain extent. We can do that because functions are first-class citizens in ActionScript and you will see what this means at the end of this article.

Step 1

Alright, let us begin with a small example which is probably familiar to most of us…

Example: Operations on an Array

Code Example 1

Something like this… 
  var list : Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

  for( var i : int = 0; i < list.length; i++ )
  {
      list[ i ] = list[ i ] * 2
  }

  // list = [ 2,4,6,8,10,12,14,16,18 ]
…I'd say, is the classical way to double all elements of an Array… 
  for( i = 0; i < list.length; i++ )
  {
      list[ i ] = list[ i ] * 3
  }

  // list = [ 3,6,9,12,15,18,21,24,27 ]
…and that is the classical way to triple all elements of an Array.

Code Example 2

Taking the functional approach, the above would look more like this… 
var list : Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

list = list.map(
   function( x : int, index : int, array : Array ) : int
   {
      return x * 2
   }
  )

  // list = [ 2,4,6,8,10,12,14,16,18 ]
…or this… 
list = list.map( triple )

function triple( x : int, index : int, array : Array ) : int
{
  return x * 3
}
  // list = [ 3,6,9,12,15,18,21,24,27 ]

Step 1: Discussion

Let us compare these two ways of doing things: First, what has stayed the same in both examples? The operation we apply to an element of the Array is defined in almost the same way in both approaches:

  • Code Example 1, line 5 vs. Code Example 2, line 6
  • Code Example 1, line 11 vs. Code Example 2, line 15

However, what did we gain by the functional approach? Well, we got rid of the loop that looked exactly the same in the first example (line 3 & 9) — great! But what's more important, I believe, is the greater expressiveness of the functional code. For instance, take the following code snippet:

list.map( triple )

You can read it out loud and actually understand what it's doing. This is a very powerful side-effect (no pun intended) of programming in a functional way. I couldn’t say it better than the following quote which appears at the beginning of Structure and Interpretation of Computer Programs… Programs should be written for people to read,
and only incidentally for machines to execute.

 

Friend Number One: Map

With this example, I've just introduced you to our first friend from Functional Programming: map. The function Array.map is the functional abstraction of the concept of a loop over an Array that modifies its elements. Give map a function and it will apply it to all the elements of an Array. In the next part of this series I will introduce you to even more friends by presenting a more systematic overview of ActionScripts functional APIs.

Step 2

Alright, now we have abstracted the notion of applying an operation to all the elements of an Array with the map function. At the beginning, I told you that I will show you how we could take the idea behind Ruben's ArrayTool and take it to the next step. Well, this was the first step but the example above is still missing one thing which is a way to define the value we want the operation to work with.

Let's take a look at that next.

Higher-Order Goodness

For instance, we would like to make the function triple from Code Example 2 more generic by allowing it to take any value as multiplier (and by changing its name to multiplyBy on the way there.)

Our first realization will be that we cannot add another argument to multiplyBy, e.g. like this…

function multiplyBy( x : int, index : int,
                 array : Array, multiplicator : Number ) : int
{
    return x * multiplicator
}

…because Array.map only takes functions as argument that have the following form:

function callback( item : *, index : int, array : Array) : void;

The bad news is that, if we try nevertheless, Flash will complain…

ArgumentError: Error #1063: Argument count mismatch on Examples/$construct/multiplyBy(). Expected 4, got 3.
    at Array$/_map()
    at Array/http://adobe.com/AS3/2006/builtin::map()
    at …]

…the good news is that there is a very elegant way (or in some sense, another friend) to solve our problem called Higher-Order Functions. Wikipedia says…

Higher-Order Functions

In mathematics and computer science, higher-order functions or functionals are functions which do at least one of the following:

  • take one or more functions as an input
  • output a function

I suggest we have a look at the code first and discuss it afterwards…

Code Example 3

The following example shows a way to make our code from Step 1 even more generic… 
var list : Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

list = list.map( multiplyBy( 2 ) )
// list = [ 2,4,6,8,10,12,14,16,18 ]

list = list.map( multiplyBy( 3 ) )
// list = [ 3,6,9,12,15,18,21,24,27 ]

function multiplyBy( value : Number ) : Function
{
    return function( x : int, index : int,
                      array : Array ) : Number
    {
         return x * value
    }
}

Step 2: Discussion

What happened here? First, multiplyBy now only takes one argument, the value by which we want to multiply our elements (line 9). This is nice but not all that special. In my opinion, where it really get's interesting is the return type of multiplyBy. It's indeed a function and thus makes multiplyBy a higher-order function according to the second part of Wikipedia's definition. If you look at it closely, you will see that multiplyBy now creates exactly the type of function in regards of arguments and return type that Array.map requires. Besides, on the way there, we used an elegant way to define the multiplier value from the outside by using it within the body of the returned function which we want to use for our operations.

The example above embodies the very idea I wanted to bring across in this first part on Functional ActionScript, namely the idea that we can use functions just like any other type and go beyond that by creating functions that return functions themselves (or take functions as arguments). By doing this we can write code that much better expresses its intent, and therefore is easier to understand and ultimately easier to maintain.

In the next part of this series you will see more mechanisms like map that are available to you within ActionScript, as well as some examples on how Functional Programming can make your life easier. Stay tuned.

Epilogue

If you look at Code Example 3, this is exactly what I meant by… Functions are first-class citizens in ActionScript. It's true. ActionScript allows you to create functions, store them in a variable or pass them around like any other type such as Number or Array. Additionally, you can apply these functions in other places. I don't know if you've realized it but event listeners in ActionScript 3 are functions that are passed around and executed with their own context. Such functions are called closures just as the function returned by multiplyBy is a closure with the argument value as its sole free variable. Furthermore we can create functions that take functions as arguments and return functions themselves. I think this is really cool. And in fact, this is basically what Functional Programming is all about and the reason why it's called that way. Functional programming languages use functions as their main tool for building abstractions. If you learn more about it, you will see how powerful and how mind-boggling this concept can be at times. Enjoy.

Further Reading