Curl Blog : Tags : zuzu

Curl Blog

3 Posts tagged with the zuzu tag

Serializing deeply linked data structures

Posted by cbarber Oct 14, 2008

(Cross posted from the Zuzu Curl blog)

Upon expanding the test cases for my tree classes in ZUZU.LIB.CONTAINERS, I discovered that in one degenerate case involving a pessimally balanced splay tree, attempting to serialize the tree using the default compiler-generated serialization routines resulted in a stack overflow. The problem was that I had a test case that accesses each element in the tree in order before attempting to clone the tree using serialization. For most self-balancing trees, this is not a problem, but for splay trees, this results in a tree that is as unbalanced as possible -- essentially just a long linked list. Because the compiler-generated object-serialize method recursively serializes the classes fields, serializing the tree nodes blows up the stack. This is a potential problem when serializing any linked data structure that may have arbitrarily large depth.

The way around this problem is to implement an explicit non-recursive object-serialize method and object-deserialize constructor for affected classes. The general algorithm is fairly simple:

Iterate non-recursively over the nodes in the datastructure. For each node, temporarily null out its pointers and serialize the node normally. The SerializeOutputStream will remember the objects and will not dump them out again if the same object is serialized later.
If the number of nodes was not known in advance, serialize out a sentinel value to delimit the end of the nodes.
Iterate over the nodes again in the same order and serialize the fields in order.

When deserializing, just reverse this process.

The following example demonstrates this problem for a simple linked list data structure. Note that in the linked list case the algorithm only requires a single
iteration because the next pointer is always just the next element to be serialized. To see the stack overflow, comment out the object-serialize and object-deserialize members.

Example

Note how I used the class version as an optimization to avoid serializing an extra null for each instance.

Fixing this for my tree classes was a little bit more complicated but the principle is the same. You can see my changes here.

2 Comments 0 References Permalink Tags: programming, serialization, stack-overflow, zuzu

An 'unimplemented' syntax

Posted by cbarber Oct 1, 2008

(Cross posted from the Zuzu Curl blog.)

Frequently I find that I want to quickly sketch out the interface of a function or class method and compile it without actually implementing its body. If the function does not return any arguments, I can simply leave the body empty, but if it does return something, I might need to write a fake return statement to make the compiler happy. In either case, I usually want to leave myself a reminder that the code still needs to be implemented. In Curl, this can easily be done using an exception:

{define-proc {foo}:String
  {error "not implemented yet"}
}

The compiler knows that the 'error' function will always throw an exception and will therefore not complain that the function lacks a return statement. To create your own function like 'error', you only need to make a procedure that always throws an exception and that has a declared return type of 'never-returns':

{define-proc {unimplemented}:never-returns
  {error "not implemented yet"}
}

I have done one better than this by creating an 'unimplemented' syntax in the ZUZU.LIB.SYNTAX package that uses Curl's 'this-function' syntax to add the name of the unimplemented function to the error message. For example:

Run example

You can find the source of this macro here.

The ability to extend the syntax like this makes Curl a much more expressive language than most widely used languages today.

0 Comments 0 References Permalink Tags: macro, unimplemented, never-returns, programming, extending-curl, zuzu

Running applets directly from Google Code

Posted by cbarber Sep 17, 2008

One thing I have always liked about Curl is the lack of an independent compile/link step. You can run Curl applets directly from source code just using the Curl RTE, which will compile and link the code dynamically as needed. This gives Curl the immediacy and flexibility of scripting languages like JavaScript while retaining the performance of a compiled language. It also means that you can run Curl applets directly from a source code repository with a web interface that can be configured to return the appropriate Curl applet MIME type (text/vnd.curl). Luckily for me, Google Code provides such a repository, so I am able to configure applets in my ZUZU libraries to be run directly from the repository.

Here is an example:

http://zuzu-curl.googlecode.com/svn/trunk/zuzu-curl/LIB/applets/example.curl

(I don't know how to embed an OBJECT tag in this blog infrastructure. See
the version of this post on the Zuzu Curl blog to see an embedded example.)

This example applet takes arguments in the "query" portion of the URL to set the title of the example and to load the initial contents of the example either from another file or from the query itself (as in this case). This allows me to use the same example applet to show different editable examples in my blog. The embedded example applet used in the training section of the Curl Developer's Site uses the same trick; for example, see here.

Look here for instructions on how to configure your Google Code repository to serve Curl applets. This trick may work on other Subversion-based code hosting services such as SourceForge, but I have not tried it.