Closure under composition

August 21, 2017

set-theoryclojure

In the very beginning of my path to becoming a functional programmer I had to learn about closures not once, but twice.

Lexical closures

The first time was when I learned about lexical closures, which are a way of attaching an environment to a given function capturing some or all of its free variables.

For example, the following function has a free variable y, meaning, it is not bound by any lexically-surrounding binding:

clj
(fn [x] (x y))

And here we have the same function with y captured by the binding of the let:

clj
(let [y "Hola!"]
  (fn [x] (x y)))

The aha moment comes when you realise that the runtime of your language keeps the environment formed by the captured variables around for as long as the function itself lives:

clj
(def call-with-hola! (let [y "¡Hola!"]
                       (fn [x] (x y))))
(call-with-hola! identity)
;; => "¡Hola!"

Another realisation we might have is that now we have the tools to create objects, understanding objects as a data structure that bundles together data and behaviour:

clj
(defn new-rectangle [x y x' y']
  (let [∆X (- x' x)
        ∆Y (- y' y)]
    {:area (fn [] (* ∆X ∆Y))
     :perimeter (fn [] (+ ∆X ∆Y))}))

(def r (new-rectangle 0 0 5 10))

((:area r))
;; => 50

((:perimeter r))
;; => 15

Set Theory closures

The second time was when I learned about the meaning of closure in mathematics:

A set of functions is said to be closed under composition if, when you compose (or apply one function after another) any two functions from the set, the resulting function is still within the same set.

For example, the natural numbers are closed under addition (+), because the result of adding two natural numbers will always be a natural number. The same cannot be said of subtraction, because the result of subtracting two natural numbers might be a natural number, zero, or a negative number.

Another example more close to programming is when working with functions and function composition, composing two functions will always result in another function:

haskell
addClosingExclamation = (++ "!")
addOpeningExclamation = ("¡" ++)
addExclamation = addOpeningExclamation . addClosingExclamation
addExclamation "Hola"
-- => "¡Hola!"

Another, more broad example in programming is when composing expressions, composing two expressions will always result in another expression, and this is why in functional programming everything is an expression, even statements:

clj
(let [x (let [y "¡Hola!"]
          y)]
  x)

Programming with this type of closures feels like driving a highway with guardrails, you are safe, and you cannot make mistakes when combining the values with the operation they are closed under. Also, knowing about this gives you better judgment on wether things compose or not.

Things that don't close-under

For example: locks, monads, objects, exceptions, macros,… In a lot of situations the meaning of composition is not that the composition operation forms a closure, but rather that the effects of combining them, gives you the expected composed effect.

For example, let's see how exceptions and macros do not compose in the context of everything's an expression so common in functional languages.

Exceptions do not compose because combining two expressions that may throw exceptions do not gives back an expression that may throw, or report, two exceptions:

clj
(defn pair-results [x y]
  [(x) (y)])
(pair-results (fn [] (assert false "ka"))
              (fn [] (assert false "boom!")))
;; => AssertionError Assert failed: ka

Lexical macros in Lisp do not close under neither because depending on the order of evaluation of two different macros, a value or an error might happen:

clj
(defmacro sleep-units% [value unit]
  `(* ~value
        ~(case unit
           seconds 1
           minutes 60
           hours 3600)))

(sleep-units% 5 seconds)
;; => 5

(sleep-units% 5 (rand-nth ['seconds 'minutes]))
;; => IllegalArgumentException No matching clause

It seems like when you need to use macros, you move into a limbo were you are not exactly sure if you are allowed to use the full power of the language.

The above examples are just to proof that those things, in the context of functional languages of everything's an expression, do not automatically compose and that you have to put some effort in designing them to do so.

Conclusion

One of the ultimate goals of functional programming is to turn into composable as many imperative programming constructions as possible, even then, things still may be composable in one context but not in another. Whether this is something software engineers should always strive for is open to discussion, but I think that keeping it present when designing software will do more good than harm. After all, the core of functional programming is composition, and for functional programmers composition is the way of handling complexity.

anler.me

Thanks for reading!

© 2024-present. Anler Hdez. All rights reserved.