ToC
TOC
Back to index/Generated with Clerk from src/emmy/pattern/rule.cljc@f807468

Rules

A 'rule' is a combination of a possibly-failing matcher (see emmy.match), an optional matcher predicate that can introduce NEW bindings, and a consequence function (see emmy.consequence)

  • the matcher (and its predicate) determine whether or not the rule applies to its data input, and
  • The consequence can either fail, or successfully return some arbitrary value or transformation of the bindings from the successful match

The final rule is a function from a data input to either failure or a successful transformation.

This namespace defines:

  • the machinery required to create rules, in both function and macro form
  • some basic rules
  • combinators to build more advanced rules and term rewriting systems out of basic rules. These are called "rule combinators".

Defining Rules

Rules are composed from matchers and consequences; these functions are politely aliased into this namespace to make it more self contained.

(def =>
"Convenient predicate that always passes."
(constantly true))
#object[clojure.core$constantly$fn__5740 0x79260985 "
clojure.core$constantly$fn__5740@79260985"
]
(def !=>
"Predicate that fails for all inputs."
(constantly false))
#object[clojure.core$constantly$fn__5740 0x611fce1c "
clojure.core$constantly$fn__5740@611fce1c"
]
(import-def c/succeed)
#'emmy.pattern.consequence/succeed
(import-def m/failure)
#'emmy.pattern.match/failure
(import-def m/failed?)
#'emmy.pattern.match/failed?

[[pattern*]] is effectively an alias for [[match/matcher]]; the macro form, [[pattern]], is able to take a pattern with un-quoted forms like ?x. See [[syntax/compile-pattern]] for details.

NOTE: These should almost certainly live in emmy.match. Can we alias a macro into this namespace with Potemkin?

(defn pattern*
"Builds the pattern portion of a rule from the supplied pattern form or matcher
combinator and optional predicate `pred`.
See [[emmy.pattern.syntax]] for the allowed syntax pattern, or [[emmy.pattern.match]]
for details on matcher combinators.
See [[match/matcher]] for more detailed documentation."
([form]
(m/matcher form))
([form pred]
(if (and pred (not= pred =>))
(m/matcher form pred)
(m/matcher form))))
#object[emmy.pattern.rule$pattern_STAR_ 0x45f5fa1b "
emmy.pattern.rule$pattern_STAR_@45f5fa1b"
]
(u/sci-macro pattern
"Takes an unevaluated pattern form (or matcher combinator) and an optional
predicate `pred`, and returns a matcher appropriate for passing to [[rule*]]."
([form]
`(pattern*
~(ps/compile-pattern form)))
([form pred]
`(pattern*
~(ps/compile-pattern form)
~@(when pred [pred]))))
#'emmy.pattern.rule/pattern
(u/sci-macro consequence
"Accepts a skeleton expression `form` and returns a function from a pattern
matcher's binding map to a data structure of identical shape to `skel`, with:
- all variable binding forms like `?x` replaced by their entries in the
binding map
- same with any segment or reverse-segment binding form like `??x` or `$$x`,
with the added note that these will be spliced in
- any `unquote` or `unquote-splicing` forms respected.
Compared to [[template]], these two forms are equivalent:
```clojure
(fn [m] (template m <form>))
(consequence <form>)
```"
[form]
(let [sym (gensym)]
`(fn [~sym]
~(c/compile-skeleton sym form))))
#'emmy.pattern.rule/consequence
(u/sci-macro template
"Provided with a single `form`, [[template]] is similar to Clojure's `unquote`
facility, except that symbols are not prefixed by namespace. For example:
```clojure
(let [x 10]
(template (+ ~x y z ~@[4 5])))
;;=> (+ 10 y z 4 5)
```
When you provide a binding map `m`, [[template]] returns its input form, but
replaces any:
- variable binding form like `?x`
- segment binding form like `??x`
- reverse-segment binding form, like `$$x`
with the appropriate entry in `m`. (`m` can be a symbol referencing a binding
map in the environment.)
Splices and unquote splices are respected. For example:
```clojure
(let [m {'?x 10 '?y 12 '??z [1 2 3]}]
(template m (+ ?x ?y ??z ~m ~@[1 2])))
;;=> (+ 10 12 1 2 3 {?x 10, ?y 12, ??z [1 2 3]} 1 2)
```"
([form]
(c/compile-skeleton {} form))
([m form]
(let [sym (gensym)]
`(let [~sym ~m]
~(c/compile-skeleton sym form)))))
#'emmy.pattern.rule/template
(defn rule*
"Functional version of [[rule]]. See [[rule]] for documentation."
[match handler]
(let [match (if (fn? match)
match
(m/matcher match))]
(fn [data]
(let [result (match data)]
(if (m/failed? result)
m/failure
(c/unwrap
(or (handler result)
m/failure)))))))
#object[emmy.pattern.rule$rule_STAR_ 0x430ca0d6 "
emmy.pattern.rule$rule_STAR_@430ca0d6"
]
(defn ^:no-doc compile-rule
"Returns compiled, macro-ready input for [[rule*]] based on the contract
described by [[rule]]."
([p consequent-fn]
`(rule* (pattern ~p)
~consequent-fn))
([p pred skeleton]
`(rule* (pattern ~p ~pred)
(consequence ~skeleton))))
#object[emmy.pattern.rule$compile_rule 0xa2fe313 "
emmy.pattern.rule$compile_rule@a2fe313"
]
(u/sci-macro rule
"Accepts either:
- A pattern written using the syntax from `emmy.pattern.syntax` and a consequence
function from binding map => failure or return form, or
- A pattern, predicate and a consequence _skeleton_,
And returns a rule. A rule is a function from some data object to either
- A special `failure` singleton (test for this with [[failed?]]), or
- A successful transformation provided by a consequence function.
In the 2-argument case, you must provide an explicit function of the binding
map. A return of `failure`, `nil` or `false` will cause the whole rule to
fail. To successfully return `nil` or `false`, wrap the result in [[succeed]].
Notes for the 3-argument case:
- If the predicate returns `nil`, `false` or `failure`, the rule fails.
- The predicate can succeed by returning anything else. If the return value is
a map, the rule will call the consequence function with this map merged in to
the bindings.
- the third form is a consequence 'skeleton' instead of an explicit function
See [[consequence]] for details."
([pattern consequent-fn]
(compile-rule pattern consequent-fn))
([pattern pred skeleton]
(compile-rule pattern pred skeleton)))
#'emmy.pattern.rule/rule

Rules, Rule Combinators

The following section defines a small set of basic rules, as well as a series of rule "combinators". These are functions that take one or more rules as inputs and return a new rule.

(defn pass
"Rule that always succeeds by returning its input data unchanged."
[data] data)
#object[emmy.pattern.rule$pass 0x155fa364 "
emmy.pattern.rule$pass@155fa364"
]
(defn fail
"Rule that always fails with an explicit `failure`, no matter the input."
[_] failure)
#object[emmy.pattern.rule$fail 0x7f10a6f6 "
emmy.pattern.rule$fail@7f10a6f6"
]
(defn predicate
"Returns a rule that will pass its input data on unchanged if `(f data)` returns
true and fail otherwise."
[f]
(fn [data]
(if (f data)
data
failure)))
#object[emmy.pattern.rule$predicate 0x593cb3d2 "
emmy.pattern.rule$predicate@593cb3d2"
]
(defn return
"Returns a rule that matches any input and always returns `x`."
[x]
(fn [_] x))
#object[emmy.pattern.rule$return 0x2c7ef49d "
emmy.pattern.rule$return@2c7ef49d"
]
(defn branch
"Takes a rule `r` and returns a new rule that calls `r` with its input.
The returned rule returns:
- `(succeed-r (r data)) if `(r data)` is successful,
- `(fail-r data) otherwise."
[r succeed-r fail-r]
(fn [data]
(let [result (r data)]
(if (failed? result)
(fail-r data)
(succeed-r result)))))
#object[emmy.pattern.rule$branch 0x44d236f5 "
emmy.pattern.rule$branch@44d236f5"
]
(defn choice*
"Identical to the multi-arity [[choice]], but accepts an explicit sequence."
[rules]
(fn [data]
(loop [rules rules]
(if (empty? rules)
failure
(let [answer ((first rules) data)]
(if (failed? answer)
(recur (rest rules))
answer))))))
#object[emmy.pattern.rule$choice_STAR_ 0x3e0f1f8f "
emmy.pattern.rule$choice_STAR_@3e0f1f8f"
]
(defn choice
"Accepts any number of `rules` and returns a new `rule` that attempts to apply
each rule in `rules` to its input data. Returns the first non-failing rule's
result, or `failure` if no rule succeeds.
NOTE: The zero-arity `(choice)` returns [[fail]], a rule that fails for any
input.
See [[choice*]] for an identical function that accepts an explicit sequence."
([] fail)
([r] r)
([r & rs]
(choice* (cons r rs))))
#object[emmy.pattern.rule$choice 0x21199bf "
emmy.pattern.rule$choice@21199bf"
]
(defn pipe*
"Identical to the multi-arity [[pipe]], but accepts an explicit sequence."
[rules]
(fn [data]
(reduce (fn [prev r]
(let [result (r prev)]
(if (failed? result)
(reduced failure)
result)))
data
rules)))
#object[emmy.pattern.rule$pipe_STAR_ 0x59104f7c "
emmy.pattern.rule$pipe_STAR_@59104f7c"
]
(defn pipe
"Accepts any number of `rules` and returns a new `rule` that attempts to pipe
its input `data` through each rule in `rules`. Only succeeds if every rule
succeeds on the previous rule's successful output.
NOTE: The zero-arity `(pipe)` returns [[pass]], a rule that succeeds for any
input by returning the input unchanged.
See [[pipe*]] for an identical function that accepts an explicit sequence."
([] pass)
([r] r)
([r & rs]
(pipe* (cons r rs))))
#object[emmy.pattern.rule$pipe 0xc20bf35 "
emmy.pattern.rule$pipe@c20bf35"
]
(defn n-times
"Returns a rule that applies the rule `r` iteratively `n` times to the input
data, failing if any application fails.
For example, these forms are equivalent, except that the [[n-times]] version
will fail immediately if any application fails vs passing on its failure:
```clojure
(n-times 3 my-rule)
(fn [data]
(my-rule (my-rule (my-rule data))))
```"
[n r]
(pipe* (repeat n r)))
#object[emmy.pattern.rule$n_times 0x4a952a59 "
emmy.pattern.rule$n_times@4a952a59"
]
(defn attempt?
"Returns `true` if `r` was marked as an 'attempt' rule, i.e., a rule that will
never fail, but return its input on a failed match."
[r]
(::attempt? (meta r) false))
#object[emmy.pattern.rule$attempt_QMARK_ 0x44479ed5 "
emmy.pattern.rule$attempt_QMARK_@44479ed5"
]
(defn as-attempt
"Marks the supplied rule as an 'attempt' rule that won't fail."
[r]
(vary-meta r assoc ::attempt? true))
#object[emmy.pattern.rule$as_attempt 0x1ff7528e "
emmy.pattern.rule$as_attempt@1ff7528e"
]
(defn attempt
"Takes a rule `r` and returns a new rule that return either `(r data)` if `r` is
successful, or its original input on failure.
NOTE that the returned rule will never fail! This makes it inappropriate to
use with [[choice]], for example, if you expect any rule supplied after this
one to ever be matched. [[attempt]] rules are great choices for the final rule
passed to [[choice]], however."
[r]
(if (attempt? r)
r
(as-attempt
(choice r pass))))
#object[emmy.pattern.rule$attempt 0x16278f52 "
emmy.pattern.rule$attempt@16278f52"
]
(defn guard
"Takes a predicate function `f` and a rule `r`, and returns a new rule that will
return `(r data)` if `(f data)` is true, fail otherwise."
[f r]
(pipe (predicate f) r))
#object[emmy.pattern.rule$guard 0x7503b82d "
emmy.pattern.rule$guard@7503b82d"
]
(defn iterated
"Similar to `clojure.core/iterate` for rule application.
Takes a rule `r` and returns a new rule that will return the last non-failing
result of the sequence `[data (r data) (r (r data)) ...]`
This might be `data` itself if `r` fails on first application. This means that
the returned rule will never fail."
[r]
(as-attempt
(fn [data]
(let [result (r data)]
(if (failed? result)
data
(recur result))))))
#object[emmy.pattern.rule$iterated 0xdca316e "
emmy.pattern.rule$iterated@dca316e"
]
(defn while
"Returns a new rule which repeatedly applies `r` as long as `f` continues to
return `true` between the input and output of the rule `r` applied iteratively
to the input `data`.
See [[until]] for a similar function that treats its predicate differently."
[f r]
(as-attempt
(fn rec [data]
((pipe (attempt r)
(fn [data*]
(if (f data data*)
(rec data*)
data*)))
data))))
#object[emmy.pattern.rule$while 0x288c717b "
emmy.pattern.rule$while@288c717b"
]
(defn until
"Returns a new rule which repeatedly applies `r` until `f` returns `true`
between the input and output of the rule `r` applied iteratively to the input
`data`, signaling completion.
See [[while]] for a similar function that treats its predicate differently."
[f r]
(as-attempt
(fn [data]
(let [data* ((attempt r) data)]
(if (f data data*)
data*
(recur data*))))))
#object[emmy.pattern.rule$until 0x27b3627 "
emmy.pattern.rule$until@27b3627"
]
(defn fixed-point
"Takes a rule `r` and returns a new rule that applies `r` to `data` iteratively
until (= input (r input))."
[r]
(until = r))
#object[emmy.pattern.rule$fixed_point 0x6ad13495 "
emmy.pattern.rule$fixed_point@6ad13495"
]
(defn trace
"Takes a rule `r` and returns a new version of `r` tagged with a unique `id`.
The returned rule calls the side-effecting `f` with
```clojure
{:id id, :in data}
```
Before calling `r` with `data`, and calls `f` with
```clojure
{:id id, :out (r data)}
```
when the rule returns."
([r]
(trace r prn))
([r f]
(let [id (gensym "t_")]
(fn [data]
(f {:id id, :in data})
(let [result (r data)]
(f {:id id, :out result})
result)))))
#object[emmy.pattern.rule$trace 0x36cc29e0 "
emmy.pattern.rule$trace@36cc29e0"
]

Expression Matchers

The next group of rule combinators are designed to accept an expression built out of Clojure data structures and apply the rule in either depth-first or breadth-first fashion.

(defn- try-subexpressions
"Given a rule `the-rule` and a possibly-nested expression `expr`, attempts to
apply `the-rule` to all subexpressions in breadth-first order. If the
transformed form is equivalent, returns its input so that [[identical?]]
checks before and after don't break.
Descends correctly into vectors, sequences and dictionaries.
NOTE: [[try-subexpressions]] assumes that [[the-rule]] will always succeed,
returning its input on a failed match."
[the-rule expr]
(cond (sequential? expr)
(let [processed (doall (map the-rule expr))]
(if (= expr processed)
expr
(if (vector? expr)
(vec processed)
processed)))
(map? expr)
(let [processed (u/map-vals the-rule expr)]
(if (= expr processed)
expr
processed))
:else expr))
#object[emmy.pattern.rule$try_subexpressions 0x7d8091eb "
emmy.pattern.rule$try_subexpressions@7d8091eb"
]
(defn bottom-up
"Given some rule `the-rule`, returns a new rule that accepts potentially nested
`data` and applies `the-rule` to all subexpressions in depth-first order, from
the leaves on up.
The transformation is applied a single time to all subexpressions.
See [[iterated-bottom-up]] for a version that will iterate to convergence."
[the-rule]
(let [r (attempt the-rule)]
(as-attempt
(fn rec [expression]
(r (try-subexpressions rec expression))))))
#object[emmy.pattern.rule$bottom_up 0x26114a72 "
emmy.pattern.rule$bottom_up@26114a72"
]
(defn top-down
"Given some rule `the-rule`, returns a new rule that accepts potentially nested
`data` and applies `the-rule` to all subexpressions on the way down AND back
up a traversal. This is a sort of hybrid of breadth-first, depth-first.
The transformation is applied a single time to all subexpressions.
See [[iterated-top-down]] for a version that will iterate to convergence."
[the-rule]
(let [r (attempt the-rule)]
(as-attempt
(fn rec [expr]
(r (try-subexpressions rec (r expr)))))))
#object[emmy.pattern.rule$top_down 0x4507b7b9 "
emmy.pattern.rule$top_down@4507b7b9"
]
(defn iterated-bottom-up
"Version of [[bottom-up]] that iterates on each subexpression to convergence
before each subexpression returns. Any change in a subexpression triggers a
new iterated-bottom-up replacement of that subexpression.
The returned rule keeps an internal memoization cache and will return
immediately for subexpressions it's seen before."
[the-rule]
(let [r (attempt the-rule)
rec (atom nil)]
(letfn [(rec* [expr]
(let [processed (try-subexpressions @rec expr)
answer (r processed)]
(if (= answer processed)
answer
(@rec answer))))]
(reset! rec (memoize rec*))
(as-attempt @rec))))
#object[emmy.pattern.rule$iterated_bottom_up 0x125305d0 "
emmy.pattern.rule$iterated_bottom_up@125305d0"
]
(defn iterated-top-down
"Version of [[top-down]] that iterates on each subexpression to convergence
before each subexpression returns. Any change in a subexpression triggers a
new iterated-top-down replacement of that subexpression.
The returned rule keeps an internal memoization cache and will return
immediately for subexpressions it's seen before."
[the-rule]
(let [r (attempt the-rule)
rec (atom nil)]
(letfn [(rec* [expr]
(let [answer (r expr)]
(if (= answer expr)
(let [processed (try-subexpressions @rec expr)
answer (r processed)]
(if (= answer processed)
answer
(@rec answer)))
(@rec answer))))]
(reset! rec (memoize rec*))
(as-attempt @rec))))
#object[emmy.pattern.rule$iterated_top_down 0x6ba5c1b8 "
emmy.pattern.rule$iterated_top_down@6ba5c1b8"
]

Term Rewriting

Term-rewriting systems often declare sets of rules meant to be attempted one after the other, just like [[choice]]; but failure for term-rewriting should return the term with no transformation.

(defn ruleset*
"Given some number of `rules`, returns a new rule that will act like [[choice]]
and attempt to apply each rule to the input data, returning the first match.
If all `rules` fail, the returned rule will return its input `data`.
See [[ruleset]] for a macro that allows inline rule definition."
[& rules]
(attempt
(apply choice rules)))
#object[emmy.pattern.rule$ruleset_STAR_ 0x47cb4464 "
emmy.pattern.rule$ruleset_STAR_@47cb4464"
]
(u/sci-macro ruleset
"Accepts triplets of the form:
<pattern> <predicate> <consequence-template>
and returns a new rule that will attempt to match the rules compiled from each
triplet in sequence, returning the filled-in `<consequence-template>` of the
first successful match.
If none of the rules match, the returned rule returns its input data
unchanged.
See [[ruleset*]] for a function version that takes explicit
already-constructed rules."
[& patterns-and-consequences]
{:pre (zero? (mod (count patterns-and-consequences) 3))}
(let [inputs (partition 3 patterns-and-consequences)
rules (map #(apply compile-rule %) inputs)]
`(ruleset* ~@rules)))
#'emmy.pattern.rule/ruleset
(defn rule-simplifier
"Given some number of `rules`, returns a new rule that will attempt to apply
each rule to its input expression (and every subexpression of the input,
bottom up), iterating until no rule causes any change in any level of the
supplied expression."
[& rules]
(iterated-bottom-up
(apply pipe (map attempt rules))))
#object[emmy.pattern.rule$rule_simplifier 0x3f89995b "
emmy.pattern.rule$rule_simplifier@3f89995b"
]
(defn term-rewriting
"Alias for [[rule-simplifier]]."
[& rules]
(apply rule-simplifier rules))
#object[emmy.pattern.rule$term_rewriting 0x357e66ff "
emmy.pattern.rule$term_rewriting@357e66ff"
]