Inspired by this excellent post I wanted to implement a simple expression simplifier in Clojure using the algorithm used in the post. The post gives example implementations in F#, Scala, Haskell, C++, and Julia which all appear fairly elegant.
I have come up with two different implementations (see below) but I have a nagging feeling that they are both less than idiomatic.
My question is: What would an idiomatic Clojure implementation look like?
First implementation, based primarily on protocols:
(defprotocol Expr
(simplify1 [e])
(simplify [e]))
(defrecord Const [n]
Expr
(simplify1 [this] this)
(simplify [this] this))
(defrecord Variable [name]
Expr
(simplify1 [this] this)
(simplify [this] this))
(defrecord Add [l r]
Expr
(simplify1 [{:keys [l r] :as expr}]
(let [lclass (class l)
rclass (class r)]
(cond
(= lclass rclass Const)
(Const. (+ (:n l) (:n r)))
(and (= lclass Const) (= (:n l) 0))
r
(and (= rclass Const) (= (:n r) 0))
l
:else expr)))
(simplify [{:keys [l r]}]
(simplify1 (Add. (simplify l) (simplify r)))))
(defrecord Mult [l r]
Expr
(simplify1 [{:keys [l r] :as expr}]
(let [lclass (class l)
rclass (class r)]
(cond
(= lclass rclass Const)
(Const. (* (:n l) (:n r)))
(and (= lclass Const) (= (:n l) 0))
(Const. 0)
(and (= rclass Const) (= (:n r) 0))
(Const. 0)
(and (= lclass Const) (= (:n l) 1))
r
(and (= rclass Const) (= (:n r) 1))
l
:else expr)))
(simplify [{:keys [l r]}]
(simplify1 (Mult. (simplify l) (simplify r)))))
(defmulti print-expr class)
(defmethod print-expr Const [e]
(print-str (.value e)))
(defmethod print-expr ::expr [e]
(print-str "The expression cannot be simplified to a constant"))
(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))]
(-> e
simplify
print-expr))
Second implementation, primarily based on multimethods and more verbose than the first:
(defrecord Const [value])
(defrecord Variable [name])
(defrecord Add [l r])
(defrecord Mult [l r])
(derive Const ::expr)
(derive Variable ::expr)
(derive Add ::expr)
(derive Mult ::expr)
(defn sim-1-disp [{:keys [l r] :as e}]
(if (some #{(class e)} [Add Mult])
[(class e) (class l) (class r)]
(class e)))
(defmulti simplify class)
(defmulti simplify1 sim-1-disp)
(defmulti print-expr class)
(defmethod simplify Add [{:keys [l r]}]
(simplify1 (Add. (simplify l) (simplify r))))
(defmethod simplify Mult [{:keys [l r]}]
(simplify1 (Mult. (simplify l) (simplify r))))
(defmethod simplify ::expr [e]
e)
(defmethod simplify1 [Add Const Const] [{:keys [l r]}]
(Const. (+ (:value l) (:value r))))
(defmethod simplify1 [Add Const ::expr] [{:keys [l r] :as e}]
(if (= (:value l) 0)
r
e))
(defmethod simplify1 [Add ::expr Const] [{:keys [l r] :as e}]
(if (= (:value r) 0)
l
e))
(defmethod simplify1 [Mult Const Const] [{:keys [l r]}]
(Const. (* (.value l) (.value r))))
(defmethod simplify1 [Mult Const ::expr] [{:keys [l r] :as e}]
(cond (= (:value l) 0)
(Const. 0)
(= (:value l) 1)
r
:else e))
(defmethod simplify1 [Mult ::expr Const] [{:keys [l r] :as e}]
(cond (= (:value r) 0)
(Const. 0)
(= (:value r) 1)
l
:else e))
(defmethod simplify1 ::expr [e]
e)
(defmethod print-expr Const [e]
(print-str (.value e)))
(defmethod print-expr ::expr [e]
(print-str "The expression cannot be simplified to a constant"))
(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))]
(-> e
simplify
print-expr))
Not sure about being the idiomatic implementation, but I think as Guillermo Winkler mentioned
core.match
is a pretty natural alternative approach, especially with variants. As your linked article says, sum types are pretty neat.Example:
This lets you leverage pattern matching for terseness and have a similar elegance as some of your linked examples. There is a cost compared to your protocol/multimethod approaches though - those are sum types open to extension, including by other people's code without touching your source code. How useful that is depends on your application.
A few asides:
simplify
in terms ofclojure.walk/postwalk
withsimplify-1
as the function argument. This is maybe a tad easier to extend sincesimplify
no longer needs to know which expr variants are operations and can be simplified beyond callingsimplify-1
on them.core.typed
type for this, but my environment seems to have some issues loading that today so I can't check it.Think this should more or less fit: