I'm a recovering programmer who has been designing video games since the 1980s, doing things that seem baroquely hardcore in retrospect, like writing Super Nintendo games entirely in assembly language. These days I use whatever tools are the most fun and give me the biggest advantage.
james.hague @ gmail.com
Where are the comments?
Functional Programming ArchaeologyJohn Backus's Turing Award Lecture from 1977, Can Programming be Liberated from the Von Neumann Style? (warning: large PDF) was a key event in the history of functional programming. All of the ideas in the paper by no means originated with Backus, and Dijkstra publicly criticized it for being poorly thought through, but it did spur interest in functional programming research which eventually led to languages such as Haskell. And the paper is historically interesting as the crystallization of the beliefs about the benefits of functional programming at the time. There are two which jump out at me.
The first is concurrency as a primary motivation. If a program is just a series of side effect-free expressions, then there's no requirement that programs be executed sequentially. In a function call like this:
The second belief which has dropped off the radar since 1977 is the concept of an algebra of programs. Take this simple C expression:
xis a truth value--either 0 or 1--then
!xgives the same result as these expressions:
Now in C this isn't all that useful. And in Erlang or Haskell it's not all that useful either, unless you avoid writing explicitly recursive functions with named values and instead express programs as a series of canned manipulations. This is the so-called point-free style which has a reputation for density to the point of opaqueness.
In Haskell code, point-free style is common, but not aggressively so. Rather than trying to work out a way to express a computation as the application of existing primitives, it's usually easier to write an explicitly recursive function. Haskell programmers aren't taught to lean on core primitive functions wherever possible, and core primitive functions weren't necessarily designed with that goal in mind. Sure, there's the usual
foldand so on, but not a set of functions that would allow 90% of all programs to be expressed as application of those primitives.
Can Programing be Liberated... introduced fp, a language which didn't catch on and left very little in the way of tutorials or useful programming examples. fp was clearly influenced by Ken Iverson's APL, a language initially defined n 1962 (and unlike fp, you can still hunt down production code written in APL). The APL lineage continued after Backus's paper, eventually leading to APL2 and J (both of which involved Iverson) and a second branch of languages created by a friend of Iverson, Arthur Whitney: A+, K, and Q. Viewed in the right light, J is a melding of APL and fp. And the "build a program using core primitives" technique lives on in J.
Here's a simple problem: given an array (or list, if you prefer), return the indices of values which are greater than 5. For example, this input:
[3,4,6]. How can we transform the original array to
3 4 6without explicit loops, recursion, or named values?
First, we can find out which elements in the input list are greater than 5. This doesn't give us their positions, but it's a start.
mapbuilt in. The above example checks if each element of the input array is greater than 5 and returns an array of the results (0 = false, 1 = true).
There's another J primitive that builds a list of values from 0 up to n-1:
#is the length function.) Stare at this for a moment, and you'll see that the result is a list of the valid indices for the input array. So far we've got two different arrays created from the same input:
0 0 0 1 1 0 1(where a 1 means "greater than 5") and
0 1 2 3 4 5 6(the list of indices for the array). Now we take a bit of a leap. Pair these two array together: (first element of the first array, first element of the second array), etc., like this:
3 4 6. It turns out that J has an operator for pairing up arrays like this, where the first element is a count and the second is a value to repeat count times. Sort of a run-length expander. The key is that a count of zero can be viewed as "delete me" and a count of 1 as "copy me as is." Or in actual J code:
#in this case, with an operand on each side of it, is the "expand" function.) If you're ever going to teach a beginning programming course, go ahead and learn J first, so you can remember what it's like to be an utterly confused beginner.
In the APL/J/K worlds, there's a collection of well-known phrases (that is, short sequences of functions) for operations like this, each made up of primitives. It's the community of programmers with the most experience working in a point-free style. Though I doubt those programmers consider themselves to be working with "an algebra of programs," as Backus envisioned, the documentation is sprinkled with snippets of code declared to be equivalent to primitives or other sequences of functions.