A Makeshift Solution to Expression Problem
In the previous post I tried to demonstrate the expression problem and its implications. In this post I will present a solution. As I mentioned last time I interpret the static type safety clause as no monkeypatching. Otherwise there is no solution for expression problem in Clojure, since it’s a dynamic langulage with no static type checking.
Let me remind you the little shape language we’ll be using in the examples again:
(area (make-circle 1)) ; => 3.141592...
(area (make-square 2)) ; => 4
We will add two new constructs, defcase & deffunction:
(defcase make-circle [radius])
(defcase make-square [edge])
(deffunction area [shape])
Notice that none of these are now function definitions. So what do defcase & deffunction do? We’ll come to that. I think the first question we should ask is where are the particular implementations of area for circles and squares? OK, I lied to you, we need to add three new constructs, not two:
(area (make-circle 1)) ; => IllegalArgumentException: area is not defined for case circle
(area (make-square 2)) ; => IllegalArgumentException: area is not defined for case square
(defimplementation area [circle]
(* Math/PI (:radius circle) (:radius circle)))
(defimplementation area [square]
(* (:edge square) (:edge square)))
(area (make-circle 1)) ; => 3.141592...
(area (make-square 2)) ; => 4
I guess you have realized by now that defcase, deffunction & defimplementation are all macros. Since macros are not the easiest things to understand I wanted to show their usage before revealing their code.
defimplementation
Did you notice above, area had thrown an IllegalArgumentException when we called it before we defined an implementation? But then it worked once we supplied the implementation. Clearly there’s some hidden state. defimplementation must be storing[1] the implementation of area for the given case somewhere:
(defmacro defimplementation [function-name [arg] body]
(swap! functions assoc [(keyword function-name) (keyword arg)] (eval `(fn [~arg] ~body)))
nil)
If you are not familiar with Clojure, here is an annotated version of the important form in this macro:
;; Change the value of atom named 'functions' atomically...
(swap! functions
;; ...by associating...
assoc
;; ...the key, that is a vector whose first element is a
;; keyword (similar to an interned string) of the name of
;; the function (:area in our example) and the second
;; element is a keyword of the name of the case...
;; (:circle or :square in our example)
[(keyword function-name) (keyword arg)]
;; ...with the a function that takes an argument whose
;; name is whatever is 'arg' set to, containing instructions
;; that are passed to the macro with its 'body' argument.
(eval `(fn [~arg] ~body)))
We we define the implementations of each function for each case using defimplementation and if an implementation is not found for a given (function × case) pair an IllegalArgumentException will be raised.
Before we move onto the other macros, let’s take a look at functions. Nothing special really[2]:
(def functions (atom {}))
;; After we run the two defimplementation calls:
(= (keys (deref functions))
'([:area :circle] [:area :square])) ; => true
defcase & deffunction
Here’s the code for defcase:
(defmacro defcase [case-name args]
(let [case-key (keyword (apply str (drop 5 (name case-name))))
arg-names (map keyword args)]
`(def ~case-name (fn ~args ~(apply assoc
{:case case-key}
(interleave (map keyword args) args))))))
What it does is pretty simple actually. It builds a function that builds a map of its arguments. This map contains, in addition to the arguments, a :case key. See it in action here:
(make-circle 1) ; => {:radius 1, :case :circle}
(make-square 2) ; => {:edge 2, :case :square}
deffunction is what ties it all. Remember how we built the keys of the functions map? Once we have this tuple of function name and case name, we can get the corresponding value, which is a function object, from functions and all that is left to do is to call it with the shape given:
(defmacro deffunction [fn-name [arg]]
`(def ~fn-name (fn [~arg]
(let [case-key# (:case ~arg)
default# (fn [arg2#] (throw (IllegalArgumentException. (str ~(name fn-name) " is not defined for case " (name case-key#)))))
impl-key# [~(keyword fn-name) case-key#]
impl-fn# (get @functions impl-key# default#)]
(impl-fn# ~arg)))))
Perhaps looking at what deffunction expands to helps understanding it:
(macroexpand '(deffunction area [shape]))
;; Produces something like:
(def area (fn [shape]
(let [case-key_ (:case shape)
default_ (fn [arg2__351__auto__] (throw (IllegalArgumentException. (str "area" " is not defined for case " (name case-key_)))))
impl-key_ [:area case-key_]
impl-fn_ (get @functions impl-key_ default_)]
(impl-fn_ shape))))
;; If you were to call this function as below:
(area (make-circle 1))
;; It could be substituted with the following form:
((get @functions [:area :circle] (fn [arg2] ...)) (make-circle 1))
This is all the machinery we need to support open extension. Remember; the consumers don’t need to know the implementation details of defcase, deffunction and defimplementation. They don’t need to know even the existence of functions. From their perspective they would add cases and functions without modifying existing code and it would just work.
Adding New Functions
Let’s add a new function that calculates the circumference/perimeter of a shape:
(deffunction circumference [shape])
(defimplementation circumference [circle]
(* 2 Math/PI (:radius circle)))
(defimplementation circumference [square]
(* 4 (:edge square)))
(circumference (make-circle 1)) ; => 6.283185...
(circumference (make-square 2)) ; => 8
Adding New Cases
Adding a new case is the same as the first two:
(defcase make-rectangle [a b])
(defimplementation area [rectangle]
(* (:a rectangle) (:b rectangle)))
(defimplementation circumference [rectangle]
(* 2 (+ (:a rectangle) (:b rectangle))))
(area (make-rectangle 0.5 2)) ; => 1.0
(circumference (make-rectangle 0.5 2)) ; => 5.0
Conclusion
My solution works but it shouldn’t be used in production. Clojure’s answer to expression problem is multimethods and protocols. My makeshift solution is, hopefully, only good for educational purposes.
It would be nice be able to know if a case is applicable to a function at compile time. But it would be an unreasonable expectation from a dynamic language. This is what tests are for, they are executable specifications of your code. But I digress. If you need compile time guarantees you can use a statically typed langulage like Haskell or Scala. Actually I have seen a method that seems to satisfy all the conditions of expression problem. But it was quite complex:
- complex
- (adj) consisting of many different and connected parts.
The reason why I chose Clojure for this post (and the previous one) is because it’s a language designed to keep complexity under control. Open extension, for example, is built into the language.
That’s it from me. I won’t go into the details of multimethods or protocols, you can easily find out about them.
| [1] | This is probably not a great use of macros. I’m not an expert but as far as I know macros should return forms instead of causing side effects. Actually it is possible to write defimplementation as a function but it wouldn’t have been as nice looking. In any case consumers of this code shouldn’t worry about the internals. |
| [2] | I used an atom but I suppose a var would do here as well. Since cases and functions are unlikely to be defined run-time functions will only be modified at startup. The important point here is that it should be somewhat hidden. Smoke and mirrors. |
If you have any questions, suggestions or corrections feel free to drop me a line.