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.
Showing posts with label Language. Show all posts
Showing posts with label Language. Show all posts

Wednesday, May 23, 2007

Getting lazy

Recently, in v250 of the muSE core library, I added support for stack optimization of tail calls - finally!

muSE has been missing the ability to do tail recursion for ever and now its finally there. The absence of tail recursion support had a rather ugly but practical consequence for the language - the while and for looping constructs had a reason to exist because you couldn't loop otherwise without blowing the stack top. I'm glad to note that they can now be safely RIP-d.

Tail call optimization as implemented does not apply to tail calls of native functions. It only applies to applications of user defined functions that appear in the tail position in a block.

As a by-product of the tail call optimization, I was surprised to find it easy to implement lazy evaluation. There's an experimental primitive lcons which can be used to construct a list lazily. This operator is inspired by Dan Friedman's TR44: CONS should not evaluate its arguments technical report. Some classic examples can be found in examples/lcons-v238.scm in the source tree.

Wednesday, January 10, 2007

Specifying function arguments using key-value pairs

Since v129 in the processes branch, two new primitives call/keywords and apply/keywords have been added to let function argument be specified in an order that's different from the declaration order. These primitives do not change the evaluation complexity of functions at all, but simply expose a function's declared arguments as "keywords".


(call/keywords f 'key1 val1 'key2 val2 ...)

Evaluates the given function by explicitly binding each named argument to the given value. Can also be used on macros, in which case the value positions are used without being evaluated. This is the counterpart of the normal position based evaluation.

(apply/keywords f alist)

If you store a set of argument bindings in an alist, you can apply a function to those bindings using apply/keywords. This is the counterpart of the position-based apply.


Any arguments that don't feature in the supplied key-value pairs take on their current value in the environment. This lets you specify common arguments using just a let binding or a global define. Such common arguments are therefore said to be implemented via a limited form of dynamic scoping.

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.

Tuesday, September 12, 2006

Pattern matching bind

muSE uniformly uses pattern matching to bind symbols to values. It is used in fn, case and let expressions - which therefore differ slightly from standard Scheme. Not only was it easier to use the same technique in all three expressions, it has resulted in greater expressive power for let and case, obviating the need to do first, rest and such destructuring operations on lists.

muSE's pattern matching bind can deconstruct lists and match constants such as numbers, strings and symbols. Here's an example using fn and case - Suppose we need to create a function that adds up the pair-wise product of its arguments. i.e -

> (f 1 2 3 4 5 6)
should yield -
1 * 2 + 3 * 4 + 5 * 6
= 45

We can write f like this -


(define f
(fn args
(case args
(() 0)
((x y . etc) (+ (* x y) (apply f etc))))))

Note that args is used by itself without an enclosing parentheses to get the arguments of the function as a list - this itself is a pattern match. Also note that NIL can be notated as () without a quote character.

Similarly, let also allows you to deconstruct lists. Apart from that, the behaviour of let in muSE is similar to let* in Scheme. There are no other kinds of let in muSE because so far this one has been sufficient.