News

muvee Reveal - the latest incarnation of muvee's flagship product - has just been released on 11 June 2008! The behaviours of the 8 bundled styles are specified using muSE, in addition to all the styles developed for the now discontinued muvee autoProducer 6.1.

Sunday, November 26, 2006

Static guarded patterns

muSE makes use of pattern matching binding in its let, case and fn constructs. These patterns can destructure lists and test for equality against numbers, symbols and any quoted constants. In several situations, it is desirable to make the binding operation succeed only if the pattern satisfies a more complex condition that can be expressed only in code.

With revision 36 of muSE trunk, support for static guarded patterns have been added, which allows you to specify conditions that a pattern must satisfy in order for the binding operation to succeed.

In any language with pattern matching binding, a guard typically has two components - 1) a pattern to match and bind and 2) a condition that the bound variables must satisfy additionally, for the binding operation to be considered to be successful. A fairly straight forward s-expression form of a guard therefore is

(guard PATTERN TEST-BODY)
where the PATTERN introduces variables and the TEST-BODY makes use of the introduced variables in an expression that evaluates to a boolean value (in muSE, () is 'false' and anything else is 'true').

We can exploit the fact that the above guard form is structurally and semantically identical to a predicate expressed as a closure and reuse that mechanism to add support for guards in patterns. There is, therefore, no need to introduce another special symbol guard.

Hence, you can place guards wherever a pattern is expected - in let, arguments to fn itself and, most importantly, the case expression. The current implementation of guards does not allow the guard body to refer to the lexical context. It can only refer to the global context and that's why the guard mechanism is called static.

If you use an fn expression directly in a pattern, like
(a b (fn (c d) (< c d)))
against a value '(1 2 (3 4)), it is not possible to tell whether you intended the third element of the list to be decomposed into 3 elements, binding the first to the symbol fn or you intended for the fn expression to be used as a guard. To resolve this ambiguity, we call upon muSE's read-time expression evaluation to really place a predicate object at the third position - like this -
(a b {fn (c d) (< c d)})
. Now, the pattern matcher actually sees a function object in the third position and knows to treat it as a guarded pattern. This pattern will bind 4 variables a, b, c and d if it succeeds.

There is limited support for dynamic guards in patterns. You can use muSE's dynamic scoping mechanism fn: instead of fn in cases where you need the guard body to refer to variables in the immediately enclosing lexical closure.

No comments: