personal experiences and code :)

Friday, September 21, 2007

higher order actionscript

I happened on the every method on the Flex Array class yesterday, and so I took a peek; guess what else I found? Implementations for map, filter, (add reduce). I should not be surprised, but my eyebrows did jump a bit when I saw them. I wonder how many developers are actually using these functions, and writing actionscript code in a more functional way, generally.

In (oop-style) Actionscript 1 [1] code, you typically wrote code like:
var o = function() {};
o.prototype = {
foo : function() {},
baz : function() {}
};

There is nothing special about the o.prototype though, for what we want to discuss, rather the bit after it. This is Actionscript shorthand for creating key/value pairs; so foo and baz are keys, and for their values we are storing two functions (as values). Note that they could have been any valid type, but in this case they are Functions. This is not so much of a big thing, but if you do not actually know it, it is quite a big thing. As Daniel Friedman mentions in the "Education of a Programmer in Languages", "both C and ML pass values around" but their interpretation of a value is quite different. Based on what a value is in the language you write code in, the possibilities, both in terms of what you can actually apply and what solutions you can think of, are quite different.

I don't think developers pay attention to the functional nature of Actionscript enough. In the Flash/Actionscript developer community, it is standard practice to see code like:
button.addEventListener("click", Delegate.create(this, function() { /*do something*/ }));

What the code block above is doing is passing an anonymous function--it could have been some other named function--as a 'listener' that should be executed when a button's onRelease event/callback occurs; this is everyday code. Passing functions as 'listeners', however, is about one of the very few instances, in most of the code I have seen, where I see functions being passed around.

Actionscript is a functional programming language. Among other things this means that it supports functions that can accept and/or return functions as arguments or return values, respectively. When you can store functions as values, you can pass them as arguments, and you can return them from other functions, because they are, afterall, just values. Functions that can accept functions as arguments, and/or return other functions are referred to as higher order functions. Developers should explore the functional nature of Actionscript more. It is quite powerful and allows for some pretty elegant code.

functional, you say? list-at-a-time functions

There are a multitude of times in code, where you want to apply a certain function to a whole list (Array) and return either a new list back, or some computed single value from that list.

For example, we have a list of donuts, and we want to see which ones have chocolate, and then later decide to take chunks of bites out of them:



// some_list has a few donuts, and i want to see which is juicier
var v:Array = [];
for (var i:Number = 0, n:Number = donuts.length; i < n; ++i)
if ((donuts[i] as Donut).hasChocolate())
v.push(donut[i]);

// then some where later in the day, we take a huge bite on those donuts with some function, randomBite(donut):Donut
var u:Array = [];
for (var i:Number = 0, n:Number = v.length; i < n; ++i)
u.push(randomBite(v[i] as Donut));


filter: The first loop is a filtering operation. It returns a list of all the donuts that pass the hasChocolate test.
Per its name, a filter takes an intial list, and applies a certain predicate to the elements, returning only those that satisfy the predicate.

map: A map is a way to apply a function to list (Array), and then return the results as a new list. The second loop is a mapping operation. It applies randomBite to all the list items, and returns a new list based on the value of those operations. If I am the one doing the randomBites, you might end up with a few nulls in your returned list ;)

What are more practical examples? Return all unchecked items on a form; programatically click all buttons that satisfy some condition; passing a function to be used to calculate new positions in tweening (which again, is standard in the community) etc.

Both loops can be re-written as [2]:


function choco(donunt:Donut):Boolean { return donut.hasChocolate(); }
var chocs:Array = donuts.filter(choco);

function randomBite(donut:Donut):Donut { /* bite donut, return the rest of it*/ }
var bitten:Array = donuts.map(randomBite);

We notice that, apart from the more beautiful code we generate, we do not have to write code to walk our list. The code also communicates exactly what it is doing. In the first instance, we are applying a filter, in the second instance a map. If we look at the loops, we have to go through the loop to understand what the code is doing.

These operations, which are applied to an entire list in one step are referred to, per Joe Amstrong's Programming Erlang, as list-at-a-time functions. Using a list-at-a-time operation makes a program small; and because we regard each operation on the list as a single conceptual operation, the programs we write become easier to understand. A rather nice side effect I have noticed is, you think more about the actual operation you want to perform on the list rather than how to construct a loop that iterates over the list, which in a way leads to more accurate and self-documenting programs.

fold (foldl, foldr), reduce

In Scala, you can write code like

1.+(2) // results in 3 [3]

The addition symbol, which in this case represents a binary operator--by definition a function that takes two arguments and returns a single value--can be seen as: fun(a:Object, b:Object):Object. You can represent this on Numbers in Actionscript as:


function plus(a:Number, b:Number):Number { return a + b; }
trace(plus(plus(1, 2), 3) == (1 + 2 + 3)) // true [4]


Writing all these plus pluses isn't terribly exciting, or interesting for that matter; but you already knew that. What if you could get your code to do all the plusing by passing it a list of the items to be plused? Or what if you could change the actual operation to be performed, by passing in a new function, and running it across the same set of items in the list?

Fold, in general, it is a way of 'inserting' a binary operator between the elements of a list to compute a single value. In the code block above, you can see how the plus function (a sum operation) is folded between the elements of the Array [1, 2, 3]. If we decided to get the value of multiplying all the values, well, we just change the implementation of the function and pass a mult instead of a plus, say.

When applying a fold, you normally have 3 arguments, the function (operator) to fold between the list's elements, the list itself, and a start value. So, to find the sum of an array, we start from 0, and so we have 0 + 1 + 2 + 3, or 3 + 2 + 1 + 0. The general function signature looks, in Actionscript 3, as: function fold(Function, *, Array):*.


I leave it to you to read more about the difference with foldl and foldr, and to look for other functional ideas such as currying (because Actionscript natively supports closures), and function composition--both currying and composition rely on the ability to return a function from a function.

My personal Actionscript 3 implementation of some functional constructs is:
package f
{
public class F
{

public static function map(f:Function, v:Array):Array {
return foldr(compose(cons, f), [], v) as Array;
}

public static function foldl(op:Function, z:*, v:Array):* {
if (0 == v.length)
return z;
return foldl(op, op(z, car(v)), cdr(v));
}

public static function foldr(op:Function, z:*, v:Array):* {
if (0 == v.length)
return z;
return op(car(v), foldr(op, z, cdr(v)));
}

public static function filter(f:Function, v:Array):Array {
var u:Array = [];
for (var i:int = 0, n:int = v.length; i < n; ++i)
if (f(v[i]))
u.push(v[i]);
return u;
}

public static function cons(a:*, b:*):Array { return arr(a).concat(arr(b)); }

public static function car(v:Array):* { return v[0]; }

public static function cdr(v:Array):Array { return v.slice(1); }

public static function compose(func:Function, g:Function):Function {
return function(x:*, ... args):* {
return func.apply(null, [g(x)].concat(args));
}
}

private static function arr(a:*):Array {
if (null == a)
a = [];
else if (!(a is Array))
a = [a];
return a as Array;
}
}
}


Actionscript is OO and functional. You can pass functions to and receive functions from functions. Passing functions around is very powerful. Using list-at-a-time operations will make your programs shorter. Importing some of the functional idioms (that are available to Actionscript) into your programs will allow you to look at your programs from a very different perspective and allow you to find some very elegant solutions, when the need (and opportunity) arises. Unless you really need it, for list operations see if your block of code can do without a for loop. Your programs will begin to look more elegant :)

Cheers,
eokyere

Links:
1. Array - Flex 2.0.1 Language Reference
2. Fold (higher-order function) - Wikipedia
3. The Role of the Study of Programming Languages in the Education of a Programmer

Notes:
1. I bring up Actionscript 1 code, to show that the language has supported functional constructs for quite a while now.

2. The function signature for both map and filter in the Array implementations, in Flex, look like: function(f:Function, i:int, v:Array), so our donut examples will actually be function choco(donut:Donut, i:int, v:Array); this is merely to make our signature just as the filter and map implementations expect, and do not have any effect on the actual computations we want to do, unless you actually need the index and array passed.

3. This is because, in Scala, any method that takes only one argument can be written with infix notation; so: foo.op("bar") is the same as foo op "bar". Also, the addition symbol '+' is a method you can call on a Number, and in Scala everything is an object, and the '+' symbol can actually be the name of a method, because it is just as valid as 'p' or 'plus'.

4. conceptually is same as +(+(1, 2), 3), or much nice in Scheme: (+ (+ 1 2) 3) or even (+ 1 2 3)