Written by Eric Normand. Published: March 30, 2013
Sign up for weekly Clojure tips, software design, and a Clojure coding challenge.
Function-Level Programming
Clojure Gazette
Issue 1.35 — March 30, 2013
Back from Clojure/West
Hi, all!
Sorry for missing a week, but I had a lot of catching up to do after Clojure/West. The conference was a blast. I learned a lot and met some really great people.
Also, the Kickstarter Video project was successfully completed. The creation of those videos is underway!
Enjoy the issue! Eric Normand <ericwnormand@gmail.com>
Function-Level Programming
John Backus is a well-known computer scientist famous for his work in the development of FORTRAN and Algol. He is the Backus in Backus-Naur Form (BNF), which is the standard way for representing context-free grammars.
Backus also developed a model or paradigm of programming called "Function-Level Programming" (FP). In Function-Level Programming, one creates 0th-order functions (functions of values to values) by combining existing 0th-order functions using 1st-order functions.
In most Lisps, these meta-levels (orders) are mixed. A function is a value and so can be passed to any other function. By separating out these levels and carefully choosing the built-in functions, algebraic properties of your programs can be derived. One can, for instance, automatically transform a program into a more efficient yet provably equivalent program. One might also be able to determine that a function is commutative.
I am no expert on the subject, but I find this area of research fascinating and would like to share some resources that I have found useful.
The term "Functional Programming" and "Function-Level Programming" were often used interchangeably in the literature of the time. Backus was very influential in formalizing the idea of functional programming. That influence has given us what we think of today as functional programming: higher order functions, referential transparency, first-class functions, etc.
In 1977, John Backus was awarded the ACM Turing Award for his work on FORTRAN and BNF. He used his lecture to describe Function-Level Programming and these notes he authored were later published. This contains the most approachable description of FP.
In this video from 1987, John Backus uses meticulously prepared presentation boards to explain the idea of Function-Level Programming.
J is a modern Function-Level programming language heavily influenced by APL. Check out some of the examples for some mind-bendingly short programs. Also, many of the Project Euler problems have been solved in J with only a few characters. The succinctness comes from using point-free style and from single-character functional forms.
