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
)

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.