Function-level programming a la Backus

flp.clj

(ns flp
  "Function-level programming a la Backus; see
   http://www.stanford.edu/class/cs242/readings/backus.pdf"
  (:refer-clojure :exclude [/]))

;;; Functional Forms - combine existing functions to form new ones.

(def ^{:doc "Composition"} ° comp)

(defn / [f]
  "Insert"
  (partial reduce f))

(defn α [f]
  "ApplyToAll"
  (partial map (partial apply f)))

;;; Functions - take and return non-functions (atoms).

(defn Trans [coll]
  "Transpose"
  (apply map vector coll))

;;; Compute the inner product.

(def IP (° (/ +) (α *) Trans))

(comment
  (IP [[1 2 3] [6 5 4]]) ;=> 28
)

Backus compares unrestricted lambda calculus to unrestricted flow control. Consider "functions as values" - what does this actually mean? If functions are values, why can't they be compared for equality, or even carry a useful notion of identity?

Consider also the composition of functions in the lambda calculus. This mechanism allows one to "create" new values of ambiguous identity. What can it possibly mean to "create" a value? Functions taking and returning scalars suffer no such ambiguity.

Backus solves these aberrations by categorizing higher order functions as Functional Forms, in a class separate from Functions. Functional Forms take and return only Functions. Functions take and return only Atoms, or the set of values that are neither Functional Forms nor Functions.

This dichotomy makes programs written in function-level style "confluent" - fragments of function-level programs can be meaningfully compared for equality, avoiding the halting problem introduced when comparing regular unrestricted functional programs.

Alan,
I think the question of what it means to create a new value via composition is misleading. Functional composition does not create new values, at least not any more so than does addition. What I mean is that (comp f g) is no more an act of creation of a value than is (+ 2 3). The latter is just more familiar.

Functions do have a notion of identity: f is equal to g means that f and g are defined on the same domain D, and for all x in D, (f x) is equal to (g x). This definition of identity is not effective when D is infinite, but that is just the nature of things.

It is hard to say many interesting things about functions in general. One typically introduces restrictions which impose structure, say by talking about linear functions, differentiable functions, computable functions, etc. We could restrict ourselves to functions with finite domains and so retain an effective (that is, guaranteed to terminate) notion of functional equality, but that seems a bit drastic. Or one can try for more fine-grained distinctions, say between data and codata. You might enjoy taking a look at http://blog.sigfpe.com/2007/07/data-and-codata.html.

I think that's the point: (comp f g) is not "creating", while (define f (lambda ...)) must be. FLP does not allow the latter.