Friday, October 5, 2007

Func it up with JavaScript

UPDATE: David Pollak has a great introduction to FP via JavaScript and Ruby.

Using functional programming paradigms in JavaScript are non-existent, clumsy, verbose and difficult to read in most cases. "Oliver Steel":http://osteele.com/ has built an excellent little library that does the grunt work for you when trying to get your func on.

To Func || ! Func
Most people go about their imperial programming days without a thought of functional programming techniques and how they can be applied to their daily problems. In most part this is due to the inherent difficulties with _doing_ functional programming in their tool of choice.

I urge you to do some further investigation (read Why Functional Programming Matters) into functional programming techniques even if you think you'll never use them anywhere. This is not intended to be an exercise in (academic) pointlessness but to place you outside of your comfort zone and expand your thinking across different domains. The depth of knowledge gained from this will enable you to solve problems from a larger pool of tools (sometimes allowing you to bring functional programming paradigms to bare on a problem or simply augmenting your existing tools for a more efficient or elegant solution to problems).

Learn to get your Func on!

From a pure functional programming language perspective this approach to problem solving offers the following advantages over the imperative and OOP approaches:
  • No (re-)assignment
  • No side effects
  • No flow of control
Functional calls can therefore have no other effect that to compute its result. In a pure functional language there are no assignments statements. Once you assign a value to a variable the variable never changes. In this sense variables in a functional language have more in common with algebraic variables that the normal programming stock we're used to.

At first this seems like a debilitating restriction but after giving your brain some time to expand you'll find that this simple restriction eliminates one of the largest sources of bugs in programming and makes the order of execution irrelevant as no side-effect can change the value of an expression and it can be evaluated at any time.

Gone are the days of worrying about orchestrating the flow control of your program. Your programs are now referentially transparent because expressions, variables and their values can be freely evaluated and replaced at any time.

Elements of Func
From a strict academic sense functional programming refers to programs that has a main body which is a function that receives it's input as its arguments and delivers the output/transformation as it's result.

So far this definition should not seem too foreign to most people that have worked with c/c++. Where this departs from the general imperative meme is that the main function is generally defined in terms of other functions, which in
turn are defined in terms of still more functions, until at the lowest level the functions are first-class citizens (language primitives).

These functions are much like ordinary mathematical functions (in that the same input will always deliver the same output).

Higher-order programming (HOP), function level programming (FLP) and partial function application (PFA) are all styles used in functional programming.

Programming Transcendence
HOP is the ability to use functions as values, in other words you can pass functions as arguments to other functions and functions can be returned as a value of other functions. An example of HOP in JavaScript would be something like the simple sort() method that you can apply to an array.

In its simplest form the sort() function takes an unordered/ordered array and sorts the array:

var a = [2,3,1,4]
document.write(a.sort())
// prints "1,2,3,4"

The sort() method however allows you to use a comparison function as an optional argument, allowing you to pass it a function as a parameter, ergo implementing HOP. Let's assume we've got an array of date objects that we want to sort in a chronological order:

array_of_dates.sort{ function (x, y) { return x.date - y.date; } }

Here we pass in an anonymous function as our comparison function to sort(). The anonymous function is called for each object in the array of dates and it must return a negative value when x < x ="="> y.

This technique is best used when you have at least two functions that perform the same take with a slight variance. Here you would then combine the functions by replacing the part(s) that are different with a function call to a separate function which is passed in to the more general function as a function parameter.

The Functional library implements string lambdas that allow you to express some of the functional programming tools more succinctly. The traditional JavaScript way of doing say a map or filter would be something like this:

map(function(x){return x+1}, [1,2,3]) // returns [2,3,4]
filter(function(x){return x>2}, [1,2,3,4]] // returns [3,4]
some(function(w){return w.length < 3}, 'are there any short words?'.split(' ')) // returns false

Instead, string lambdas allow you to write this in the following way:

map('x+1', [1,2,3])
select('x>2', [1,2,3,4])
some('_.length < 3', 'are there any short words?'.split(' '))

Here are some other way to bend a program to your functional will using simply map, reduce and filter:

// Double the items in a list:
map('*2', [1,2,3]) // [2, 4, 6]

// Find just the odd numbers:
filter('%2', [1,2,3,4]) // [1, 3]

// Find just the evens:
filter(not('%2'), [1,2,3,4]) // [2, 4]

// Find the length of the longest word:
reduce(Math.max, 0, map('_.length', 'how long is the longest word?'.split(' '))) // 7

// Parse a binary array:
reduce('2*x+y', 0, [1,0,1,0]) // 10

// Parse a (non-negative) decimal string:
reduce('x*10+y', 0, map('.charCodeAt(0)-48', '123'.split(/(?=.)/))) // 123
Much more succinct, clear to read and easier to understand.

Func Levels
Value-level programming manipulates values, transforming a sequence of inputs into an output. Function-level programming manipulates functions, applying operations to functions to construct a new function. This new function transforms the inputs into outputs.

How can we make JavaScript dance to a functional-level programming paradigm using the Functional library as meter? Here's some example's:

// Find the reciprocal only of values that test true:
map(guard('1/'), [1,2,null,4]) // [1, 0.5, null, 0.25]

// Apply '10+' only to even values, leaving the odd ones alone:
map(guard('10+', not('%2')), [1,2,3,4]) // [1, 12, 3, 14]

// Write a version of map that only applies to the evens:
var even = not('%2');
var mapEvens = map.prefilterAt(0, guard.rcurry(even));
mapEvens('10+', [1,2,3,4])

// Find the first power of two that's greater than 100:
until('>100', '2*')(1) // 128

// Or, the first three-digit power of two (these are equivalent):
until('String(_).length>2', '2*')(1)
until(compose('>2', pluck('length'), String), '2*')(1)
until(sequence(String, pluck('length'), '>2'), '2*')(1)
Hot/Medium/Mild Curry?
Partial function application (aka currying) transforms a function that takes n arguments into a function that takes only one argument and returns a curried function of n - 1 arguments.

In English please! OK, let's try:

Currying is the process of partially, or incrementally, supplying arguments to a function. Curried functions are delayed functions expecting the remainder of the arguments to be supplied. Once all the arguments are supplied, the function evaluates normally. So, curried functions lead to lazy execution of the complete function.

From the definitions above it is clear that partial function application, or specialisation, creates a new function out of an old one. To illustrate how we apply this with Functional we'll implement between(x, y, z) which determines whether y is bounded by x and z. We then curry the first and last arguments to produce a function that tests whether a number is positive:

// Function that needs to be curried
function increasing(a, b, c)
{
return a < b && b < c;
}

// Define the set of positive numbers via lazy evaluation
var positive = increasing.partial(0, _, Infinity);

// Determine if each of the values -1, 0 and 1 fall in our range
map(positive, [-1, 0, 1]) // [false, false, true]

// Define the set of negative numbers via lazy evaluation
var negative = increasing.partial(-Infinity, _, 0);

// Determine if each of -1, 0 and 1 fall in our range
map(negative, [-1, 0, 1]) // [true, false, false]
Currying leads to lazy evaluation which allows you to work with structures like the infinite sets we created above. Cool eh?!

Epilogue
Functional does a great job at making your life easier if you want to experiment with functional programming in JavaScript without getting yourself tangled up in the verbose, standard syntax. The creator does however offer a word of warning with regards to performance if you use this lib in production. Functional is also confirmed to work in Firefox 2.0, Safari 3.0, and MSIE 6.0.


About Me

My photo
I love solving real-world problems with code and systems (web apps, distributed systems and all the bits and pieces in-between).