Freshmaking!

UNFINISHED, but I’ll just post it for now, cause who knows when I’ll get around to this again!

One thing I don’t like doing is labeling things as “advanced”. I remember back in the day when I was just-barely-a-teenager and I was figuring out C. I read through a book or two and got to the topic of “linked lists”. I remember back then thinking that sort of stuff was considered, in my and the book’s opinion, “advanced”–and that I thought was pretty hardcore knowing how to do it. I knew that knowing it didn’t necessarily make me the best programmer in the world… but I had to have definitely been somewhere in the top 10. Maybe even the top 5.

Today, I’m a tiny bit wiser than I was back then.

For functional programmers, currying and/or partial application may be well understood early in the learning process. Actionscript 3.0, an ECMAScript language, is actually extremely versitile, even when it comes to those crazy Functional Programming topics. Still, AS3’s “classical OOP” appearance can make some of those functional programming paradigms a rough fit.

So I won’t say that this stuff is “advanced”, but if you’re not intamitely familiar with AS3, and if you’re not already comfortable with closures and partial application from other languages, then this is probably going to hurt, at least a little bit.

For the record, I’m a beginner at this sort of stuff. Keep your eyes peeled for mistakes!

In Actionscript, you might have a function named multiply which accepts two integers, x and y. The function returns another integer which is the product of x and y:

function multiply(x:int, y:int):int { return x*y; }

Nothing amazing there. Here’s the OCaml (a functional language) version of multiply:

# let multiply x y = x * y;;
val multiply : int -> int -> int = <fun>

You can probably figure out what’s going on here, even if you’ve never seen a dialect of ML before. The stuff after the hash mark (#) is what I typed in, the following line was echo’d to the console when I hit my Enter key.

So what’s all this crazy arrow stuff about? One way to read it is that “the function multiply takes in two ints and returns an int”. That is, you can treat the first two “ints” as parameters, and say that the rightmost int as the return value. A function which took in three floats and returned an int (as a completely made up example), would look like:

float -> float -> float -> int

In that context, the whole arrow thing sounds pretty dumb. Why represent function parameters and return values in such a convoluted way?

Currying

The trick is a pretty simple one. It turns out that every function in a lambda-calculus functional language returns something, and that no functions ever really takes more than a single argument at a time. Reducing a function which takes a series of arguments into a series of functions which each take a single argument is called “currying”.

Take our multiply function, for example. We can rewrite the arrow stuff we got from OCaml like this:

(int -> (int -> int))

Where each set of parenthesis denote a particular function. The fuction’s parameter and return value are separated by the arrow, like this:

(parameter -> return_value)

So we can break this down as follows:

1) (int -> (function here)) can be read as "our function takes an int and returns a function"
2) (int -> int) "...and THAT function takes an int and returns another int"

So hopefully the notation makes a little bit more sense… but how is that at all useful?

Partial Application

The nice thing about this is that you can now “partially apply” some arguments to your functions. Let’s recap:

1) We have a FunctionA which takes an “int” and returns a FunctionB.
2) We have a FunctionB which takes an “int” and returns an int

If we called our multiply in OCaml with the arguments 2 and 5, it would look like this:

# multiply 2 5;;
- : int = 10

So, in this example, our FunctionA (multiply in this case) would take a value of 2 and return FunctionB (anonymous in this case) which then takes a value of 5 and returns an int 10.

So “FunctionA(2)” returns a specific FunctionB with the value of 2 “already applied”. What if we could save this FunctionB with the 2 already applied and reuse it later on? I mean, instead of “FunctionB”, we might even call “Function A with the value of 2 applied already” something like double.

This is easy to do in OCaml (and most functional languages), and the code may illustrate the process more clearly:

# let double = multiply 2;;
val double : int -> int = <fun>
# double 5;;
- : int = 10

So we define our double function as the function which “multiply 2″ returns.

When you come from languages like Actionscript 3.0, C++, or whatever, this can be a little bit hard to swallow. It might seem like multiply is a function which takes two values and returns one, so how can you call it with only one parameter? What you have to remember is that this just isn’t the case in a lambda-calculus functional language. multiply DOES NOT take two values… it takes ONE value which returns a function. I know I’ve been mentioning this a lot, but it’s very important to understand that.

Think about what’s happening here:

* multiply is a function which takes in an int and returns a function
* The function it returns takes an int and returns an int

So it follows that:
* When we call “multiply 2″ it returns a function which takes an int and returns an int

If we assign that function a name, “double” in this case. We then expect this double function to take an integer and return another integer. When we call “double 5;;”, we get an integer back, which is 10 in this case. A call to “double” with a 6, for instance, would generate a “12″, as you might expect.

Currying in Actionscript 3.0

With most of the theory and OCaml examples out of the way, we can focus on our familiar Actionscript 3 coding. AS3 doesn’t conform to lambda-calculus’ “everything is a function that returns something” philosophy, so we’ll have to put in a little bit of extra effort to get going. Let’s start by directly translating our curried multiply function over to Actionscript 3.0, then we’ll work on abstracting and generalizing it:

package  {
	import flash.display.Sprite;

	public class PartialMultiply extends Sprite{

		public function PartialMultiply() {

			// From FunctionA/FunctionB analogy
			// FunctionA is the same as curried_multiply
			// FunctionB is the function returned from "multiply 2"
			var FunctionB:Function = curried_multiply(2);

			// This will trace 10
			trace( FunctionB(5) );

			var double:Function = curried_multiply(2);

			// Also traces 10
			trace( double(5) );

			// Strange syntax for using curried_multiply directly
			// Also traces 10
			trace( curried_multiply(2)(5) );

		}

		private function curried_multiply(x:int):Function {	// Function which takes an int and returns a function
			return function(y:int):int {		// Which takes an int and returns an int
					return x * y;
			}
		}

	}

}

Our curried_multiply function was built as a direct translation of the process lambda-calculus uses to break apart functions. curried_multiply takes in one int argument and returns a function which, in turn, takes in one int argument and returns an int… just like our curried OCaml version!

You can use the first few lines of code to compare with the FunctionA/FunctionB example I was going on about earlier, and see that the double function works as well. If you’re having trouble understanding why or how the “2″ argument is “remembered” in FunctionB or the double function, be sure to look up closure and understand how it works (I recently posted a write up on this, also geared toward Actionscript 3).

Lastly, this line may look a little weird:

trace( curried_multiply(2)(5) );

Just remember that curried_multiply(2) will return a function. In leiu of assigning that return function to a variable, we just tack on the argument list and let it go.

The currying of the function is a little bit difficult to follow and chances are you won’t want to constantly be re-implementing this stuff everywhere. Luckily, Actionscript 3.0 has the ability to allow us to implement a way to apply partial application to anything.

But it’s hairy. Really, really hairy. Bigfoot hairy.

Generic Partial Application

I’ll just throw the code at you, then we’ll talk about it as there’s a little bit of witchcraftery involved:

package  {
	import flash.display.Sprite;

	public class PartialApplication extends Sprite {

		public function PartialApplication()
		{

			var partial_multiply:Function = partial_apply(multiply);
			var double:Function = partial_multiply(2);

			trace( double(5) );

		}

		private function multiply(x:uint, y:uint):uint { return x * y; }

		private function partial_apply(f:Function):Function
		{
			return function():Function
			{
				var partial_arguments:Array = arguments.slice();
				return function():* {
					partial_arguments = partial_arguments.concat(arguments);
					return f.apply(null, partial_arguments);
				}
			}
		}

	}

}

The idea here is to define a function normally and then, if we decide we want to use partial application with it, we send it to a partial_apply function, which returns another function that we can use to do what we want. First, let’s just blindly assume that our partial_apply does this, and we’ll worry about the implementation after that.

We have our straightforward multiply AS3 function which takes two arguments and returns an int. We decide that we want to use this function for some partial application stuff, so we send it through partial_apply and save the result to a a function variable named “partial_apply”, which we can then use for partial application. We can send our first argument to partial apply and get a double function. If we wanted to use the function without partial application, you could do:

partial_multiply(2)(5);

But, of course, this is that unusual syntax and has fairly poor runtime performance. In this case, it’d be better to just call your original multiply. Don’t use this stuff “just because”.

As an aside, you could actually assign your partial_apply(multiply) function to a variable named ‘multiply’, and essentially ‘override’ your implementation of multiply. I don’t reccommend doing this generally, but it’s food for though.

Lastly, we can create double directly by doing this:

var double:Function = partial_apply(multiply)(2);

Our partial_apply(f:Function)

So here’s the craziness once again, our partial_apply function:

private function partial_apply(f:Function):Function  {
	return function():Function  {
		var partial_arguments:Array = arguments.slice();
		return function():* {
			partial_arguments = partial_arguments.concat(arguments);
			return f.apply(null, partial_arguments);
		}
	}
}

There are a number of things that make this little chunk of code scary. Luckily, you wouldn’t regularly be writing stuff like this, but understanding it goes a long way.

First, we want a function which will accept a function as input, and return a version which we can use for partial application. This is where our declaration of partial apply comes in. Pretty straightforward so far.

When partial_apply is called, we get our function to use for partial application. The function should accept some arguments that it can apply to yet another function. Our multiply function only takes two arguments total, but we want to be able to use this partial_apply for functions with any number of parameters. In other words, if we had an add3(x:int, y:int, z:int), we might want to create a function which already has x defined (and takes two arguments), OR we may want to create a function which already has x AND y defined (and would only take one additional argument).

But if you look at the code, we have this:

return function():Function  {

The anonymous function we use doesn’t appear to take ANY arguments at all!

Actionscript 3 is usually pretty good at avoided weird, unexpected behavior (take notes, C++!), but this is one case where you can get knocked on your ass. It turns out that any Actionscript function is required to have at least as many arguments as it has parameters, but any Actionscript function will take more than that amount. In other words, a function like add3 as defined in the last paragraph would have to take at least three arguments, but calling add3 with four or more parameters would compile and run just fine!

How is this useful? Well, it turns out that every single Actionscript function also has an ‘arguments’ object which is essentially an array (with array methods and everything, in spite of the documentation) with a few extra properties (such as “callee”). You can use this array to access any variables passed to a function, even those which aren’t named in the parameter list.

For example, a function foo():void could be called like this:

foo(1, 2, 3, 4);

…and the arguments could be traced like this:

for(var i:uint;i<arguments.length;i++) trace(arguments[i]);

So even though our anonymous function(s) don’t list any parameters, they’re still built to process any number of parameters thrown at them.

So, once again, our partial_apply function:

private function partial_apply(f:Function):Function {
	return function():Function {
		var partial_arguments:Array = arguments.slice();
		return function():* {
			partial_arguments = partial_arguments.concat(arguments);
			return f.apply(null, partial_arguments);
		}
	}
}

So our first anonymous function would be like your partial_multiply in our example. It takes some arguments to apply to the function, and returns a function which expects “the rest” of the arguments.

We want to save the arguments passed into this function to their own array, seperate from the arguments array. We do this because the nested function, when called, will overwrite these values if we don’t. Our array will be kept alive through the closure. To save a copy of our array, we use the Array’s slice object which, when called with its default parameter values, will just return a copy of the entire array.

Our innermost function will be provided with another list of arguments that should “complete” the entire list of arguments required by the function we’re trying to use. Once again, no parameters are supplied explicitly, but we generally expect that there will be enough to “finish up” the function (there are scary runtime errors lurking here, could be avoided and/or caught with some thought). We tack our arguments array onto the end of the array we saved in the last step to complete our list of arguments.

Lastly, every function in actionscript has a .call and .apply method. The .call method is essentially what is used in regular function calls. The .apply method is used when you want to supply an array as your arguments to a function. We go ahead and apply our “constructed” array to the function we initially passed in, and return whatever value that function wants (untyped return value to the rescue, for the first time in my life!).

You’re probably very, very confused at all of this. While I can’t say I’m the best at explaining anything, I will say that this stuff, especially my partial_apply function, might just be difficult to understand. The best thing to do, probably, is to study what’s there, read up on other examples, and work through it as best as possible.

A Useful Example

Some pretty nasty stuff there–so can we use it for anything?! The answer is: I don’t really know. I just learned about this stuff recently, and I wrote this article to work my way through it

I’ll come up with something later on!