A Programming Idiom You've Never Heard Of

Here are some sequences of events:

Take the rake out of the shed, use it to pile up the leaves in the backyard, then put the rake back in the shed.
Fly to Seattle, see the sights, then fly home.
Put the key in the door, open it, then take the key out of the door.
Wake-up your phone, check the time, then put it back to sleep.

See the pattern? You do something, then do something else, then you undo the first thing. Or more accurately, the last step is the inverse of the first. Once you're aware of this pattern, you'll see it everywhere. Pick up the cup, take a sip of coffee, put the cup down. And it's all over the place in code, too:

Open a file, read the contents, close the file.
Allocate a block of memory, use it for something, free it.
Load the contents of a memory address into a register, modify it, store it back in memory.

While this is easy to explain and give examples of, it's not simple to implement. All we want is an operation that looks like idiom(Function1, Function2), so we could write the "open a file..." example above as idiom(Open, Read). The catch is that there needs to be a programmatic way to determine that the inverse of "open" is "close." Is there a programming languages where functions have inverses?

Surprisingly, yes: J. And this idiom I keep talking about is even a built-in function in J, called under. In English, and not J's terse syntax, the open file example is stated as "read under open."

One non-obvious use of "under" in J is to compute the magnitude of a vector. Magnitude is an easy algorithm: square each component, sum them up, then take the square root of the result. Hmmm...the third step is the inverse of the first. Sum under square. Or in actual J code:

mag =: +/ &.: *:

+/ is "sum." The ampersand, period, colon sequence is "under." And *: is "square."

(Also see the follow-up.)

permalink January 3, 2012

A Programming Idiom You've Never Heard Of

previously

archives