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

1. 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.

2. If the number of nodes was not known in advance, serialize out a sentinel value to delimit the end of the nodes.

3. 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.

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.

This is my first post here, so I should start by introducing myself. I am Christopher Barber, and I have been a software developer/architect here at Curl since 1999. At Curl, I have worked primarily on the compiler for the Curl language and on other internals of the Curl RTE with occasional forays into GUI development (e.g., the Coverage Viewer in the Curl IDE). Prior to joining Curl, I worked on an online brokerage for D.E.Shaw, helped to develop an early web search engine and worked on distributed systems research projects at BBN, and worked on back-office systems for the cellular telephone and credit industries at the company now known as Lightbridge. During my career, I have programmed significantly in COBOL, BASIC, C, C++, Perl, Tcl, Python, and several other languages, but for the last eight years I have been programming almost exclusively in Curl (yes, that's right, Curl is written in Curl!).

In my posts here, I intend to mostly discuss various aspects of programming in the Curl language and runtime environment. Topics will likely include Curl programming idioms, extending the Curl syntax using macros, discussions of open source projects I may be participating in, and "under the hood" examinations of the Curl technology. Today, I thought I would start out by highlighting a few of the attributes of the Curl which most appeal to me as a programmer:

• immediacy - Programming in Curl has the same experience of immediacy I used to get composing HTML pages. All you need to program in Curl, is the Curl RTE and your favorite web browser and text editor. Just type the applet in the editor, save it in a file with a .curl extension and browse the file to run the applet. The RTE will dynamically compile the code from source directly into machine code and run it. While the IDE is quite useful and highly recommended for serious Curl development, it is not strictly necessary, and I often find myself doing without the IDE for simple projects.

• speed - Curl is a compiled language and does not suffer from the inherent performance issues of interpreted languages such JavaScript. Furthermore, the RTE will persistently cache previously compiled packages to avoid unnecessary recompilation. While it is not as fast as highly optimized C code, it is fast enough to allow the Curl IDE to be implemented entirely using Curl code that is dynamically compiled on the client, just like a regular Curl applet.

• markup - Curl is not just a programming language but is also a markup language with all the capabilities of HTML and more. It is easy to write documents in Curl, and in fact all of Curl's documentation is itself written in Curl. Many of our internal design and planning documents are also written in Curl. It is easy to embed executable examples in Curl documentation or write custom table formats and the like. Curl API documentation can be defined directly in the code without having to be hidden in comments using an unrelated syntax such as Javadoc.

• static/dynamic typing - My years of programming in C/C++ gave me an appreciation of the benefits of static typing, specifically the ability for the compiler to find and report type errors at compile-time and to optimize based on type declarations. Likewise, my experience with Tcl, Perl and Python gave me a great appreciation of the flexibility of dynamic typing. The Curl language is fully statically typed but provides an "out" in the form of the abstract any type. Variables of type any may hold any value and may be used as if they were declared with the proper static type. This allows me to mix static and dynamic typing idioms in my code as desired.

• extensibility - The Curl language allows you to extend the syntax extensively by means of a powerful procedural macro system. It is possible to define new control flow syntaxes, create shorthand syntaxes for common idioms, and even to embed other programming language syntaxes in Curl code. Curl's macro system provides some access to the compilation environment, making it possible to write macros that can infer types or do conditional compilation. Much of Curl's standard syntax is implemented using macros.

• multiparadigm - Curl is a language that supports multiple programming paradigms. Programmers are not forced to use an idiom that does not fit either their preferred programming style or the task at hand. In addition to the paradigms already mentioned, Curl supports object-oriented, procedural and functional programming styles. The code underlying the Curl RTE itself is largely object-oriented, but makes use of other styles when appropriate.

Of course, there are many other aspects of the technology and specific features that I like, but I will leave those to future posts.

Christopher