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

Friday, October 27, 2006

Polymorphic higher order functions

Its been a while since my last posting. That's because a lot of changes have been happening under the hood. Objects (vectors and hashtables) now have printed representations, higher order functions are now polymorphic - they can be used on lists, vectors and hashtables, the diagnostic messages are now more extensive and several hashtable bugs have been fixed. There is a fairly serious language departure from standard Scheme which doesn't have polymorphic operators, but I chose this for ease of use. Here, I describe what's available as of revision 21 in the svn repository.

The following operations are now applicable to lists, vectors and hashtables. Wherever you see collection, it means you can use any of those. -


(map (fn (x) ...) collection)

Creates a structurally similar collection with all the values transformed using the given function. The hashtable keys are not processed.


(join list1 list2 ...)
(join vector1 vector2 ...)
(join hashtable1 hashtable2 ...)

Concatenates all the objects into a single collection. All objects must be of the same type. Lists get concatenated into a single list, vectors get concatenated into a single vector. For hashtables, a union hashtable is created with all the key-value pairs of all the hashtables.

If two hashtables have the same key, the value for that key will be the value in the hashtable that's later in the argument sequence. You can influence this by supplying an optional reduction function as the first argument to join. The default behaviour is as though the reduction function is (fn (v1 v2) v2).


(length collection)

You can use the same length function to get the size of any data structure. A synonym size is available as well for clarity.


(find item collection)

Finds the item in the given collection and returns something that you can use to locate the item within the collection, or () if the item cannot be found. In the case of lists, it returns the remainder of the list starting from the object. In the case of vectors, it returns the index of the item. In the case of hashtables, it returns the key for which the given item is the value.


(reduce (fn (acc x) ...) initial collection)

Uses the given reduction function and reduces the given collection of values to a single value. This is the foldl operation that must be familiar to functional programming afficionados. This function only uses the values in the data structures. The keys of a hashtable, for example, are not touched.


(for-each func collection)

Invokes the function for each entry in the data structure. The result value is always (). The function is expected to have the signature -
(fn (obj) ...)
It is to be noted that the iteration always happens over the value objects. You don't have access to the keys of hashtables or the indices of vectors when using for-each. For a more generalized iteration construct, see collect below. This (new) behaviour is since v120.

(andmap predicate collection)

Returns T if all elements satisfy the predicate and () if even one doesn't. The signature of the predicate has the same signature constraints as that for for-each.


(ormap predicate collection)

Returns () if none of the elements satisfy the predicate. If even one satisfies the predicate, returns a reference into the data structure (like find) using which you can locate the element. The predicate signature constraints are the same as for andmap and for-each. You can use ormap as a generalized version of find.


(collect collection predicate mapper [reduction-fn])

This is an experimental generalized construct that fuses filtering, mapping and reduction operations into a single loop. The predicate selects elements from the collection, the mapper transforms the elements and the (optional) reduction-fn combines multiple values into a single entry in the result.

The predicate has to have the signature (fn (x) ...) for lists. For vectors, it is expected to have the signature (fn (index . value) ...) and for hashtables, it must be (fn (key  . value) ...). If you want to run the mapper on every element, you can simply pass () as the predicate - indicating that you don't wish to do the test.

Once an element passes the predicate test, it is passed to the mapper function. If no mapper function is given, the identity map is assumed and in this case collect behaves like a pure filter.

  1. For lists, the mapper function should have the usual signature (fn (x) ...).

  2. For vectors, the signature is expected to be (fn (index . value) ...). The index will be the filtered index of the value and not the original index in the vector. The mapper function is expected to return a pair of the form (result-index . result-value). The result is used to determine where in the result vector the result-value should be placed. The result vector is automatically resized to fit the set of returned indices. The (optional) reduction-fn is used to determine how to combine multiple values if more than one value is mapped to the same result index.

  3. For hashtables, the case is similar to that of vectors, except that instead of index-value pairs, the mapper works with (key . value) pairs and is expected to return a (result-key . result-value) pair. The reduction function is also applied similar to the case of vectors.


Friday, September 15, 2006

Anonymous symbols

muSE has a notion of anonymous symbols - symbols which do not have a textual representation - which are useful in situations where you need to keep a set of properties together, and in macros to introduce new variables into the generated expressions. The difference between named and anonymous symbols (apart from the textual representation) is that named symbols persist for the life time of the muSE execution environment whereas anonymous symbols and their property lists are garbage collected when there are no references to them.

Anonymous symbols are created using (new) . You can use an anonymous symbol as the first argument to the get and put functions to edit its property list.

Tuesday, September 12, 2006

Hashtables are functions

In the same spirit as vectors, hashtables can be thought of as functions that map keys to values. muSE hashtables are presented exactly like that and don't need special accessor functions.


> (define rgb (mk-hashtable))
> (rgb 'red 255)
> (rgb 'green 255)
> (rgb 'blue 255)

If you load the above definitions, you can get an alist from the hash table using -
> (hashtable->alist rgb)
which will give
((red . 255) (green . 255) (blue . 255))
(The order is unspecified, though.)

You can retrieve the green component using (rgb 'green). If you supply a key that is not present in the hashtable, the function will return (). In muSE therefore, it is not possible to distinguish between a key with a value that is () and a key that is not present in the hashtable. This fact is used to remove a key from the hashtable if you pass () as the value argument. For example -

> (rgb 'green ())
> (hashtable->alist rgb)
((red . 255) (blue . 255))

This is not really a restriction and you can use a hashtable as a set by setting the value to any non-NIL value.

Hashtables accept integers, strings and symbols as keys. Therefore, you can use a hashtable like a sparse vector if need be, since they both have the same invocation interface.

Vectors are functions

A vector is, conceptually, a function from an index to an object and in muSE, a vector is exactly that - a normal function. Here's an example -

(define rgb (mk-vector 3))

Now rgb is a 3-element vector, with all the slots set to (). Here's how to set the three color components -


(rgb 0 255) ; Red
(rgb 1 255) ; Green
(rgb 2 255) ; Blue

To get the green component, for example, you use (rgb 1). If you pass an index out of range, you always get ().

You can create a vector from data using the vector function like this -
(vector 255 255 255)

Other vector manipulation functions are more or less the same as standard Scheme - such as vector-length, list->vector and vector->list.