DefstructDesign

Overview

What is DEFSTRUCT?

DEFSTRUCT is a Common Lisp (CL) macro which defines a struct. A struct refers to a structured type which basically means a type with named slots. It is somewhat like a struct in the C programming language but a lot more powerful. For example, structs exhibit some inheritance behavior. Numerous options may be passed into DEFSTRUCT giving the user great flexibility and power when creating structs.

The macro defines a new struct with named slots and, optionally, initial values for those slots. It expands one or more constructor functions used to create instances of the struct. It also expands functions to access the values of each slot, create copies of a struct instance, and test that a struct is of a given type (a predicate function). Though they will have to wait until the CLOS is implemented, DEFSTRUCT also may define printer methods for the struct. Finally, DEFSTRUCT arranges for SETF to be able to set the values of the slots.

How is DEFSTRUCT used?

One creates a new struct definition by calling the DEFSTRUCT macro. There are numerous options that can be passed with somewhat complex results but for now only some simple cases will be illustrated. A simple struct definition looks like:
(defstruct foo a b) => FOO
This simple example creates a new type: a struct named FOO. This struct has two slots, named A and B which have been given no initial values. That just defines the FOO struct. Next, one has to create an instance using the constructor function (which was automatically created by the macro when FOO was defined):
(setf s1 (make-foo :a 10 :b 20)) => #S(FOO :A 10 :B 20)
This created a new instance of FOO with the slot values (which are keyword arguments to the constructor) A = 10 and B = 20. It also bound this instance to S1. The macro also created reader functions to get the current value of a slot and arranged for SETF to work on setting the value:
(foo-a s1) => 10
(setf (foo-a s1) 50) => 50
(foo-a s1) => 50

As previously mentioned, there are many options which can be passed to DEFSTRUCT. The general syntax for doing so involves passing a list with the first element being the struct name and subsequent elements being keyword options (sometimes a naked keyword, other times a keyword-value pair). For example:
(defstruct (foo (:constructor create-foo) (:copier NIL)) a b) => FOO
This struct definition uses the :constructor keyword to specify that the constructor function be named CREATE-FOO (instead of the default MAKE-FOO) and that no copier function be created at all (the default would have been a copier function named COPY-FOO). This is a very simple example of using DEFSTRUCT options. All the possible combinations, their effects, and their syntax is somewhat complicated and the HyperSpec should be consulted for details.

DEFSTRUCT Design

The Challenge

At first glance, implementing structs in Main.CLforJava might seem simple. They look like simple data structures with inheritance features that one should be able to easily implement within Java. The tricky part, however, is that structs in CL can be redefined "on the fly" in such a way that previous instances of that struct remain valid and unchanged. One might define a struct named FOO with two slots named 'A' and 'B.' After several unique instances of the struct FOO are created it would then be possible to redefine FOO to be a struct with one slot named 'C.' New instances of FOO would have only the one slot named 'C' while the old instances of FOO would still exist with their original two slots named 'A' and 'B.'

Since these struct definitions are represented in Main.CLforJava by Java classes, it is essentially required that Java classes be redefined at runtime in such a way that does not invalidate or change previous instances of the class. Redefining a class at runtime is certainly possible in Java. One can unload a class, redefine it, and load it again. But this approach has several problems, the most serious being that it can only be done if all references to said class are first removed. Thus, the old FOO definition mentioned above would no longer be valid. This approach is clearly not adequate for implementing structs in Main.CLforJava. Therefore, it is necessary to define at runtime an entirely new class for each newly defined (or redefined) struct. This is accomplished by directly manipulating Java bytecode to build, at runtime, a set of new classes for supporting each new definition of a struct.

Core DEFSTRUCT parts

DEFSTRUCT is implemented in Main.CLforJava using the following pieces (see the attachment Defstruct.png at the bottom of this page for a UML diagram of how the interfaces and implementing classes all work together).

• defstruct.lsp -- This is the macro definition and a lot of helper functions that process all the arguments to DEFSTRUCT and properly expand the various functions
• lisp.system.compiler.IntermediateCodeGenerator.java (aka ICG) -- the ICG defines a special operator, %DEFSTRUCT, which handles setting up new struct definitions by generating code directly for the JVM to create new classes for each struct definition. During this class creation the ICG ensures that certain fields, such as typeName, are properly set for each new struct definition.
• lisp.extensions.type.Defstruct.java -- the top level interface that all structs implement. Each new struct definition causes the generation of a new interface inherited from this one (done in the ICG).
• lisp.system.DefstructImpl.java -- the superclass for all structs. Each new struct definition causes the generation of a new implementation class which extends this (done in the ICG).
• lisp.system.function.MakeDefstructInstance.java -- the function which creates new instances of structs
• lisp.system.function.GetDefstructSlot.java -- the function that gets the value of a struct's slot
• lisp.system.function.SetDefstructSlot.java -- the function that sets the value of a struct's slot
• lisp.system.function.CopyStruct.java -- the function which is called by the copier function expanded by the macro. DefstructImpl? implements the Cloneable interface and overrides Object.clone() allowing our copier function to work.

How does it all work?

It is important to note that a given struct definition in Main.CLforJava actually has two names. Its lispName is the name given the struct when it is defined, i.e. FOO. Its javaName is a unique, automatically generated name that looks something like Defstruct235245465. The Main.CLforJava user refers to the struct by its lispName, while everything going on under the hood is actually using its javaName.

When a Main.CLforJava user defines a struct ( (defstruct foo a b)) here is what happens:

1. First, a lot of list processing goes on that parses all the arguments (options, slot names, slot types, initial values, etc.) to DEFSTRUCT. Thorough error checking is performed to ensure that all the supplied arguments are valid and sane per the HyperSpec.
2. The DEFSTRUCT macro expands a call that looks like (compiler::%defstruct (java-name java-name included-struct-name) (slot-name :type type) (slot-name :type type)). The %defstruct is a special operator that tell the ICG to generate all the classes needed for this new struct definition. The following are created: an interface, an abstract factory, a regular factory, and an implementation class. The implementation class has a parent field. During the building of these classes this field is set to null if this is a top-level struct or it is set to point to an instance of this struct's parent if the :include option was used.
3. Functions are also expanded (based upon the many different options that might have been passed to DEFSTRUCT) for constructing new instances of this struct, copying instances of this struct, accessing the values of the slots of this struct, etc.

So, now we have a struct definition and a bunch of functions were defined which allow us to use this struct. Here are some things that can be done with a struct:

• Create a new instance of the struct -- Unless otherwise specified by the supplied options, a constructor was expanded with a name like MAKE-FOO. This function can be called to create a new instance of our struct: (make-foo :a 10 :b 20). This creates the new struct instance and sets its slot values. Under the hood, this is accomplished by calling system::%make-defstruct-instance with a list including the struct's javaName and the values for its slots. This function, in turn, finds the factory for that struct definition and calls its newInstance method.
• Access a slot's value -- Unless otherwise specified by the supplied options, an accessor function is created for each slot. Its default form is something like FOO-A (to access a slot named 'A'). Under the hood, this calls system::%get-defstruct-slot. This function, in turn, looks for a slot of the appropriate name in this struct. If it cannot find a slot of that name then it goes to the struct named in the parent field, if any, and looks there. We keep following the chain of parents until the slot is found (or the chain ends). It then either returns the value in that slot or throws an exception if the slot was never found.
• Set a slot's value -- The DEFSTRUCT macro arranges for SETF to be able to set a slot's value by referencing its accessor function: (setf (foo-a) new-value) (unless the given slot was specified as :read-only). Ultimately, the Java function system::%set-defstruct-slot is called to perform this. It finds the slot in the same manner used by the accessor functions and sets its value.
• Copy a struct instance -- Unless otherwise specified by the supplied options, a copier function is created with a name like COPY-FOO. This simply returns a fresh copy of the struct instance. Under the hood the Java function system::%copy-struct is called. Since all structs implement the Java Cloneable interface, it is a simple matter for this function to return a copy. The list of slots for a given struct (actually it is a Java array of slot names) is static final so we have no problems using Cloneable in this case.

Still to be done

In the DEFSTRUCT macro itself (defstruct.lsp), all the basic functionality for a normal struct is present except for dealing with the printer methods (will have to wait for CLOS). In the meantime, there is only one default printer for structs (which is implemented in Java as part of the DefstructImpl? superclass). The code for the above printer functionality has been written but is currently commented out and replaced with a function definition instead of creating a method. This is a temporary fix to allow things to work, but when CLOS is available, the commented out code should be used instead.

Also, documentation for defstruct has only been partially dealt with. We currently can get the documentation and pass it around but we currently don't do anything with documentation; in other words, the documentation data is discarded. This is due to the fact that the documentation system is not currently working correctly in our system.

Current Status of DefstructDesign

Status: Done. All that is left is the printer methods (see the Still to be done section above)

Release Level: Green

Open bug count: