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

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 func tions, etc.

Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs

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.

Function Level Programs as Mathematical Objects

This paper discusses in more detail the advantages of FP over other styles of programming.

J

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.