ThinkRelevance: The Podcast - Episode 009 - Alan Dipert

Reference: ThinkRelevance: The Podcast - Episode 009 - Alan Dipert

I wish they had more time to talk about function level programming. J is an example of a function level language.

And a great article by Backus about function-level programming introduces the idea and its benefits. The basic idea is that we stop talking about "functions returning values" and start talking about "functions which behave like other functions". For instance, the function that constantly returns 1.

The benefit is that you can create an algrebra of program transformations which allows two functions to be compared for equality. ^1

For example:

    (defn sum1 [l] (reduce + l))

    (defn sum2 [l] (reduce + l))

A compiler could easily check the equality of these functions since they have the same definition. Note that the Clojure compiler does not even do this simple kind of check.

An even simpler example:

    (def const1  (constantly 1))
    (def always1 (constantly 1))

These two functions are obviously equivalent and it could be trivial to make the compiler recognize this. These are examples of programming at the function level. At the function level, you program with at least first-order functions instead of with 0-order values.

Let us imagine that we have this function that sums two lists:

    (defn sumlists [l1 l2]
      (reduce + (concat l1 l2)))

And an equivalent function:

    (defn addlists [l1 l2]
      (apply + [(reduce + l1) (reduce + l2)]))

It is easy to see that they do the same thing, but very difficult for the compiler to do so. (I used apply to make it first-order.) But with the proper transformation rules, these can be made equivalient:

    if f is distributive then
      reduce f (concat l1 l2) <=> apply f [(reduce f l1) (reduce f l2)]

    + is distributive

This basically says that reduce is distributive over concat. Now we can transform one into the other and infer their equivalence. These transformations can allow the compiler to deeply optimize at a high level.

Backus's idea is that we only program at first-order or higher so that we can guarantee to always be able to transform the programs and determine function identity. Clojure allows us to program at the 0-order (value) level. Many functions will not be able to participate in the function-level world.

However, there is a large subset of most programs that are at the function-level, and some that are not that could easily be translated into that level. Could we augment the Clojure compiler to recognize this information and allow an = function for functions?

Sounds like a job for core.logic.

1. Christophe Grand has discussed a good use case for equality of functions here.