pattern.rule — sicmutils 0.19.0

This namespace provides an API for building rules out of the matchers and matcher combinators declared in pattern.match, along with a series of combinators for building advanced term-rewriting systems.

!=> clj/s

Predicate that fails for all inputs.

=> clj/s

Convenient predicate that always passes.

as-attempt clj/s

(as-attempt r)

Marks the supplied rule as an 'attempt' rule that won't fail.

attempt clj/s

(attempt r)

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.

attempt? clj/s

(attempt? r)

Returns true if r was marked as an 'attempt' rule, ie, a rule that will never fail, but return its input on a failed match.

bottom-up clj/s

(bottom-up the-rule)

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.

branch clj/s

(branch r succeed-r fail-r)

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.

choice clj/s

(choice)

(choice r)

(choice r & rs)

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.

choice* clj/s

(choice* rules)

Identical to the multi-arity choice, but accepts an explicit sequence.

consequence clj/s macro

(consequence form)

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:

(fn [m] (template m <form>))
(consequence <form>)

fail clj/s

(fail _)

Rule that always fails with an explicit failure, no matter the input.

failed? clj/s≠

clj

(failed? x)

Returns true if x is equivalent to the failure sentinel failure, false otherwise.

cljs

failure clj/s≠

clj

Singleton object representing the failure of a matcher to match its input. Check for failure with failed?

fixed-point clj/s

(fixed-point r)

Takes a rule r and returns a new rule that applies r to data iteratively until (= input (r input)).

guard clj/s

(guard f r)

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.

iterated clj/s

(iterated r)

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.

iterated-bottom-up clj/s

(iterated-bottom-up the-rule)

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.

iterated-top-down clj/s

(iterated-top-down the-rule)

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.

n-times clj/s

(n-times n r)

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:

(n-times 3 my-rule)
(fn [data]
  (my-rule (my-rule (my-rule data))))

pass clj/s

(pass data)

Rule that always succeeds by returning its input data unchanged.

pattern clj/s macro

(pattern form)

(pattern form pred)

Takes an unevaluated pattern form (or matcher combinator) and an optional predicate pred, and returns a matcher appropriate for passing to rule*.

pattern* clj/s

(pattern* form)

(pattern* form pred)

Builds the pattern portion of a rule from the supplied pattern form or matcher combinator and optional predicate pred.

See pattern.syntax for the allowed syntax pattern, or pattern.match for details on matcher combinators.

See match/matcher for more detailed documentation.

pipe clj/s

(pipe)

(pipe r)

(pipe r & rs)

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.

pipe* clj/s

(pipe* rules)

Identical to the multi-arity pipe, but accepts an explicit sequence.

predicate clj/s

(predicate f)

Returns a rule that will pass its input data on unchanged if (f data) returns true and fail otherwise.

return clj/s

(return x)

Returns a rule that matches any input and always returns x.

rule clj/s macro

(rule pattern consequent-fn)

(rule pattern pred skeleton)

Accepts either:

• A pattern written using the syntax from 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.

rule* clj/s

(rule* match handler)

Functional version of rule. See rule for documentation.

rule-simplifier clj/s

(rule-simplifier & rules)

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.

ruleset clj/s macro

(ruleset & patterns-and-consequences)

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.

ruleset* clj/s

(ruleset* & rules)

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.

succeed clj/s≠

clj

(succeed x)

Wraps the argument x in a form that will always successfully return from a consequence function, whatever its value.

Use succeed to return nil or false from a consequence function. For all other return values, returning (succeed x) is identical to returning x

cljs

template clj/s macro

(template form)

(template m form)

Provided with a single form, template is similar to Clojure's unquote facility, except that symbols are not prefixed by namespace. For example:

(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:

(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)

term-rewriting clj/s

(term-rewriting & rules)

Alias for rule-simplifier.

top-down clj/s

(top-down the-rule)

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.

trace clj/s

(trace r)

(trace r f)

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

{:id id, :in data}

Before calling r with data, and calls f with

{:id id, :out (r data)}

when the rule returns.

until clj/s

(until f r)

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.

while clj/s

(while f r)

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.