What is Functional Programming?
Roger Hui
 

Presented on 2011-10-03 as “evening entertainment” at the Dyalog ’11 Conference in Boston, in an interleaved session with John Scholes.

Slide 0. When I compared notes with John for the first time on Sunday, I was astonished and gratified to discover that two people who have worked together for years, when given the same topic, can have presentations that are so different.

Slide 1. Howard Aiken was Ken Iverson’s thesis advisor and mentor.

Slide 2.

Slide 3. Lest you think that FP is only an ivory tower concept, let me point out that Unix pipes can be considered compositions of functions.

Slide 4. During a breakfast at the recent Minnowbrook conference, John told the following story.

In the early days of APL, Al Rose (of Gilman & Rose fame) went on tours promoting the language. In a lecture in London he told the audience that he had the text of the Psalms in the computer, and solicited “any question on the Psalms”. The audience asked him to find the most frequently occurring word in the Psalms. Rose, the showman that he was, stood silent in thought for a minute, then started typing in the solution.

When John finished telling the story, I asked him, “Has it been a minute yet?”

Slide 5. The problem can be solved readily in J using the key operator. (I could have told you that “the” was the most frequently occurring word in the Psalms, without use of a computer.)

Slide 6. The J solution translates readily to APL. This translatability is characteristic of well-defined components. Primitives in a programming language tend to be the best components around.

The APL solution can be stated as a d-fn (dynamic function), or as a f∘g∘h composition. That the two forms give the same result can be checked with the fork introduced in this conference.

I asked my colleague Joey Tuttle to solve this same problem using Unix pipes. He reports that the J solution is faster by a factor of 60.

Slide 7.

Slide 8. I looked around for a concrete example of systems. The first thing I thought of was one located not too far from the Dyalog offices in Bramley.

On second thought, the example isn’t too good. As you can see, some errors have crept into the interface. And the components aren’t so easy to understand. They are a 4000-year-old mystery.

Slide 9. Then, in honor of Gitte and Morten, I thought of another excellent Danish export.

How do Lego blocks stack up as a system?

Slide 10. As you can see, the interface is well-designed indeed.

Are the components something you understand? It’s child’s play.

Slide 11. I am going to adapt this system to explain some function compositions called combinators.

Black blocks denote left arguments and white blocks denote right arguments. Colored blocks denote functions.

Slide 12. One block connected to another is monadic application; two blocks connected to another is dyadic application.

Slide 13. On the left is the composition most often talked about in conventional mathematical notation. When dyadic functions are involved, a richer set of compositions is possible. It is one of Ken’s under-appreciated contributions that he defined these new compositions.

Slide 14. Dual is like compose except that you apply the inverse function at the end. Here, the inverse of the blue block is denoted by the transparent blue block.

Dual/under is a very powerful concept, a tool of thought par excellence. The J Wiki essay Under has over one hundred examples of its use.

Slide 15. Atop is another composition. Note that it took Ken more than 2 years after compose to come up with atop.

Slide 16. And another eight years later before he came up with fork. He took his time, but produced good results.

Slide 17.



created:  2011-09-23 06:20
updated:2011-11-04 22:55