 (defn clause->rhs
   [message bindings clause]
   (cond
+    (key-exists-without-binding-clause? clause)
+    (conj bindings `[])
+
     (key-exists-with-binding-clause? clause)
     (conj bindings (key-exists-with-binding-clause->rhs-match message clause))
 
-    (key-exists-without-binding-clause? clause)
+    (path-exists-without-binding-clause? clause)
     (conj bindings `[])
 
     (path-exists-with-binding-clause? clause)
     (conj bindings (path-exists-with-binding-clause->rhs-match message clause))
 
-    (path-exists-without-binding-clause? clause)
+    (key-matches-without-binding-clause? clause)
     (conj bindings `[])
 
     (key-matches-with-binding-clause? clause)
     (conj bindings (key-matches-with-binding-clause->rhs-match message clause))
 
-    (key-matches-without-binding-clause? clause)
+    (path-matches-without-binding-clause? clause)
     (conj bindings `[])
 
     (path-matches-with-binding-clause? clause)
     (conj bindings (path-matches-with-binding-clause->rhs-match message clause))
-
-    (path-matches-without-binding-clause? clause)
-    (conj bindings `[])
 
     (optional-clause? clause)
     (clause->rhs message bindings (optional-clause-clause clause))))

   matcher path-matches-with-binding-clause-matcher
   binding path-matches-with-binding-clause-binding])

(define-record-type
  ^{:doc "A clause that matches the value of a map at the `path` using a `matcher`."}
  PathMatchesWithoutBindingClause
  (make-path-matches-without-binding-clause path matcher)
  path-matches-without-binding-clause?
  [path path-matches-without-binding-clause-path
   matcher path-matches-without-binding-clause-matcher])

(def path? "Is something a valid path?" (some-fn list? vector?))

(defn path-matches-with-binding-clause
  [path matcher bind]
  {:pre [(and (path? path) (matcher? matcher))]}
  (make-path-matches-with-binding-clause path matcher bind))

(defn path-matches-without-binding-clause
  [path matcher]
  {:pre [(and (path? path) (matcher? matcher))]}
  (make-path-matches-without-binding-clause path matcher))

;; 3.
(define-record-type KeyExistsWithBindingClause
  ^{:doc "A clause that asserts the existence of a non-nil value in a map at the `key`. When evaluated, binds it's result to `binding`."}
  (make-key-exists-with-binding-clause key matcher binding)
  key-exists-with-binding-clause?
  [key key-exists-with-binding-clause-key
   matcher key-exists-with-binding-clause-matcher
   binding key-exists-with-binding-clause-binding])

(define-record-type KeyExistsWithoutBindingClause
  ^{:doc "A clause that asserts the existence of a non-nil value in a map at the `key`."}
  (make-key-exists-without-binding-clause key matcher)
  key-exists-without-binding-clause?
  [key key-exists-without-binding-clause-key
   matcher key-exists-without-binding-clause-matcher])

(defn key-exists-with-binding-clause
  "Returns a clause that asserts the existence of a non-nil value at `key`."
  [key bind]
  (make-key-exists-with-binding-clause key the-existence-matcher bind))

(defn key-exists-without-binding-clause
  "Returns a clause that asserts the existence of a non-nil value at `key`."
  [key]
  (make-key-exists-without-binding-clause key the-existence-matcher))

;; 4.
(define-record-type
  ^{:doc "A clause that asserts the existence of a non-nil value in a map at the `path`. When evaluated, binds it's result to `binding`."}
  PathExistsWithBindingClause
  (make-path-exists-with-binding-clause path matcher binding)
  path-exists-with-binding-clause?
  [path path-exists-with-binding-clause-path
   matcher path-exists-with-binding-clause-matcher
   binding path-exists-with-binding-clause-binding])

(define-record-type
  ^{:doc "A clause that asserts the existence of a non-nil value in a map at the `path`."}
  PathExistsWithoutBindingClause
  (make-path-exists-without-binding-clause path matcher)
  path-exists-without-binding-clause?
  [path path-exists-without-binding-clause-path
   matcher path-exists-without-binding-clause-matcher])

(defn path-exists-with-binding-clause
  "Returns a clause that asserts the existence of a non-nil value at `key`."
  [path bind]
  (make-path-exists-with-binding-clause path the-existence-matcher bind))

(defn path-exists-without-binding-clause
  "Returns a clause that asserts the existence of a non-nil value at `key`."
  [path]
  (make-path-exists-without-binding-clause path the-existence-matcher))

;; 5.
(define-record-type

   matcher key-matches-with-binding-clause-matcher
   binding key-matches-with-binding-clause-binding])

(defn key-matches-without-binding-clause
  "Returns a clause that matches a `key` with a certain `matcher`."
  [key matcher]
  {:pre [(matcher? matcher)]}
  (make-key-matches-without-binding-clause key matcher))

(defn key-matches-with-binding-clause
  "Returns a clause that matches a `key` with a certain `matcher`, binding the
