cdiggins.com

A vast number computer algorithms can be expressed in terms of map, filter, and reduce operations.

• Map takes a list and a function and transforms each value by applying the function to each value.
• Filter takes a list and a predicate function (i.e. a function which returns a boolean value) and returns a new list containing only values for which the predicate returns false.
• Reduce takes a list and an associative function which combines two elements to produce a new value. The function is applied consecutively to values in the list pairwise until a single value is reached.

All three functions can be easily implemented in parallel. This observation forms the basis of the Google map-reduce project.

In an intermediate langauge for compiling functional languages, such as Cat, these three operations can be combined to create a single super primitive, which we can call MFR. The MFR primitive is implementation defined to run the algorithms in parallel as makes sense.

This function can be used to implement all three primitives as follows:

• define map { [pop true] [] MFR }
• define filter { [] swap [] MFR }
• define reduce { [] swap [pop true] swap MFR }

Of course it is not a reasonable thing to expect programmers to always use MFR correctly in their programs. We learn to think in terms of map/reduce/filter and using those primitives makes code more readable.

The thing is that it is trivial for programs written in a stack-based language like Cat to be automatically rewritten by the compiler in term of MFR.

This is all fairly straightforward, but AFAIK it differs significantly from the apprach used to compile other functional languages.