Figure 1. A conceptual view of a list component as two sequences.
Roy Patrick Tan
Dept. of Computer Science
Virginia Tech
660 McBryde Hall
Blacksburg, VA 24061-0106 USA
rtan@vt.edu
In the RESOLVE 2002 workshop, Weide's paper Good News and Bad News About Software Engineering Practice presented a pessimistic view of the impact of RESOLVE research. At one point, he wrote: "None of the RESOLVE innovations has had the slightest influence on CSTs [commercial software technologies], even via their inevitability." [Weide02a] Later, at the workshop itself, Dr. Weide presented a much more positive view of RESOLVE research; nonetheless the tone of the paper perhaps represents the frustration of the community over the relatively low impact of this research in the larger software engineering community.
I have often thought that this state of affairs is brought about partly by the lack of a programming language implementation that embodies the ideas espoused by RESOLVE, and the lack of a novel application for the ideas espoused by RESOLVE research. The Sulu programming language is partly an attempt at working towards alleviating this perceived lack.
To date, the most common vehicle for presenting RESOLVE components is to implement them in RESOLVE/C++. It is a testament to the flexibility of the C++ language, and the ingenuity of the community that people can program in the RESOLVE discipline using that language. But the idioms of RESOLVE/C++ is quite alien to regular C++ idioms. Showing RESOLVE-like components in a different programming language like Sulu may lessen the cognitive dissonance of looking at programs written with idioms different from the host programming language.
Sulu is not RESOLVE, but it is strongly influenced by it. In the same RESOLVE 2002 paper [Weide02a], Weide lists some of the ideas brought forth by the RESOLVE community. The following table shows how Sulu tries to incorporate those ideas into the language.
| Idea | How it is implemented in Sulu |
| separating specifications from implementations | Like RESOLVE, Sulu has both Concepts that hold specifications, and Realizations that holds implementation details. It has syntactic slots for executable design-by-contract specifications. The specification language is influenced by JML, the Java Modeling Language. [Leavens99] |
| allowing for multiple interchangeable implementations of a single specification | The separation of concepts and realizations in Sulu makes this trivial. All realizations must have corresponding concepts. |
| having a standard set of "horizontal", general-purpose, domain-independent components such as lists, trees, maps, etc., in a component library | This is currently work in progress, with example components for stacks, lists, and binary trees already implemented. |
| templates are a useful composition mechanism | Sulu concepts and realizations both allow generic template parameters. |
| having value semantics is useful even for user-defined types | Sulu uses swapping as the main data movement operator, and thus has value semantics, but minimizes the need for deep copying. |
| reasoning about programs that use pointers/references is complicated and error-prone | Having value semantics, reasoning about pointers/references is limited only to when the programmer uses a pointer component. |
| problems related to storage management, such as memory leaks, are serious | The Sulu interpreter, being implemented in Java, uses the Java garbage collection mechanism to implement memory management. But in theory, a Sulu compiler can be built with no need for garbage collection at all. |
Sulu is not RESOLVE, its syntax is divergent from the one presented in the Software Engineering Notes paper [Sitaraman94]. Most notably, Sulu is object-oriented. It uses what has become the standard obejct-oriented dot notation, and supports various forms of inheritance.
Additionally, the Sulu interpreter introduces an infrastructure that uses the formal specification to aid in automatically generating and executing unit tests. It is my hope that this infrastructure will prove to be a useful vehicle for research in automatic test-case generation.
Perhaps the best way to give a feel for how you can program in Sulu is through an example. In this section we will implement a List component using two stacks.
Figure 1 illustrates our conceptual view of a list component. We imagine a List as two sequences (let's call them leftSequence and rightSequence), both starting out empty. We have two insert methods insertLeft and insertRight. The insertLeft method will insert an item to the end of leftSequence, and insertRight will insert an item at the beginning of the rightSequence. We also have a method removeLeft that removes the end of the leftSequence (provided that it is not empty), and similarly, a removeRight method. Finally, we also have an advance and retreat method which shifts elements from the leftSequence to rightSequence and vice versa.
Figure 2 is the code for the List concept. For brevity, not all the specification is included. You might notice that the concept is a template, it takes a parameter Item, which must match the concept Abstractable. We will discuss this idea of matching in the next section.
/****** * A List is conceptually two sequences, a left one and a right one. ******/ concept List( Item: concept Abstractable() ) { model method leftSequence(): concept Sequence( concept MathObject() ); model method rightSequence(): concept Sequence( concept MathObject() ); method leftLength(): Int ensures leftLength == leftSequence().size(); method insertLeft( elem: Item ) ensures leftSequence() == old( leftSequence() ).append( elem.getMathObject() ) ); method removeLeft( elem: Item ); requires leftSequence().size() > 0 ensures old( leftSequence() ) == leftSequence().append( elem.getMathObject() ); method advance() requires rightSequence().size() > 0 ensures { leftSequence() == old( leftSequence() ).append( rightSequence().at(0) ); rightSequence() == old( rightSequence() ).removeFirst(); }; method retreat(); method rightLength(): Int; method insertRight( elem: Item ); method removeRight( elem: Item ); method length(): Int; }Figure 2. The List concept
Sulu specifications are executable. That is, there is an actual concept in Sulu called Sequence, and one or more realizations for it. We take care to separate the components that are in the specification world (components that inherit from MathObject) from components that are used in the implementation world (components that inherit from Object).
Methods that are prefixed by model are specification-only methods. Often, these methods are abstraction functions, mapping the internal state of the object to its representation in the specification world.
Figure 3 is a realization that implements a List concept using two stacks. Note that the type of Stack the realization uses is also left as a generic parameter. This provides great flexibility over what kinds of stack implementation to be used.
realization TwoStacks( ItemStack: concept Stack( Item ) ) implements List( Item ) { /* instance variables */ var left: ItemStack; var right: ItemStack; /* abstraction methods */ model method leftSequence(): concept Sequence(Item) { leftSequence := left.getSequence().reverse(); } model method rightSequence(): concept Sequence(Item) { rightSequence := right.getSequence(); } /* methods */ method insertLeft( elem: Item ) { left.push( elem ); } method removeLeft( elem: Item ) { left.pop( elem ); } method leftLength(): Int { leftLength := left.size(); } }Figure 3. This realization implements a List using two stacks
If you are familiar with Java, you may want to think of concepts as the equivalent of Java interfaces, and realizations as classes that implement the interface. Since concepts and realizations are generics, there is a need to "instantiate" the templates. This is done with the class construct in Sulu. Figure 4 illustrates how a List of String objects may be created and used.
// create a StringList class of String objects, using the TwoStack realization // which in turn uses a linked-list based stack. class StringList extends concept List(String) realization TwoStacks( concept Stack( String) realization LinkedList ); //Create a StringList object; var list: StringList; // create a console object to print out the strings var c: Console; // create a String object to hold the various strings var str: String; list.insertLeft("Hello"); list.insertRight("World"); list.retreat(); list.removeRight(str); c.println(str); //prints "Hello" list.removeRight(str); c.println(str); //prints "World"Figure 4. How a List component may be used
The class construct instantiates the generic concept and realization with fully determined types. In figure 4, we are saying that the StringList class is a List of Strings; it is implemented by the TwoStack realization, which in turn uses Stack objects implemented using a linked list. Hopefully, with the exception of the class construct, variable declaration, method calls, etc. will be familiar to developers used to modern object-oriented languages.
In this section, I discuss some of the more notable aspects of Sulu's language and runtime design. Specifically we talk about various object-oriented features of Sulu, its support for automated testing research, and a note on swapping as implemented in Sulu.
Sulu's architecture is designed such that it can support automated test-cases generation, execution, and evaluation. Many test-cases generation srategies, such as in [Edwards00] follow these steps:
As of this writing, the Sulu runtime is being developed to support a plug-in architecture that will allow it to run different test-cases generation algorithms.
The executable nature of Sulu's specifications contribute to two aspects of the evaluation of test-cases. The first is that execution of preconditions can act as a test-case filter test-cases that result in precondition failures are considered invalid.
Valid test cases (those that do not result in precondition failures) can then be run against method postcondition and invariat checks. Valid test-cases that result in postcondition and invariant failures means that that test-case found a bug. That is, runtime checking of specs can also be used as an oracle determining whether the component behaved correctly or not.
Finally, after running the test-cases, we may wish to determine how well the test-cases exercised the component under test. One increasingly popular way to do this is to use code coverage metrics. The Sulu runtime system already compiles statement coverage and decision coverage information, and work to support the collection modified condition-decision coverage is underway.
As can be seen from the example in Section 2, Sulu adopts the modern object-oriented dot notation. It also embraces the typical notion of encapsulation of data and functionality within an object's implementation -- a Sulu realization.
One of the core defining aspects of object-oriented languages is inheritance. Sulu also has inheritance. Concepts may inherit from other concepts, realizations "inherit" a concept's behavioral specification by implementing them, and realizations may inherit from other realizations as well, allowing it to reuse the parent realization's implementation.
For the sake of simplicity and ease of implementation, however, Sulu uses a single inheritance heirarchy. Multiple inheritance is not allowed; perhaps most notably, a realization is only allowed to implement one concept (and all that concept's ancestors). Moreover, a realization that inherit from another realization may only implement the parent realization's concept. That is, the inheritance hierarchy discussed in [Tan02] and shown in figure 5, is currently still impossible with Sulu.
One feature of the Sulu programming language is that the inheritance relationship also defines a matching relationship, instead of the traditional "is a" relationship. Sulu matching relationship essentially follows the work found in [Bruce02].
Sulu's use of the matching relationship stems from the need for binary operations. It is often the case where an object needs to operate on other objects of the same type. One class of operators, for example, are comparison operators.
Imagine we want to build a sorting machine. Properly designed, this sorting machine should be able to sort all kinds of objects that can be compared with each other. So perhaps we create a concept called Comparable, that all objects that can be compared to each other can inherit from. Perhaps it looks like this:
concept Comparable() { method greaterThan( other: concept Comparable() ): Bool; method lessThan( other: concept Comparable() ): Bool; method equals( other: concept Comparable() ): Bool; }
Using conventional OO design, we might want to build a subtyping hiererchy that looks like this:
What happens when we compare Strings with Integers? Should we be able to?
Conventional wisdom says that interface inheritance should define a subtyping [Liskov94] relationship. For the subtyping relationship to hold, however, input parameters must be contravariant, and output parameters must be covariant. Sulu parameters are always in-out, so they have to be invariant.
Practically, this means that Integer objects must be able to accept other types of Comparable objects (say, String objects) as the parameter to the lessThan method. In Java, and many other OO languages, the solution is to have use the instanceof oparator (or equivalent) , and throw an exception if the parameter is of the wrong type. Sulu does not have exceptions, but a similar solution may be to have an extra out parameter that tells you the status of the operation -- whether the comparison succeeded or not. While this solution preserves subtyping, I believe it is quite awkward.
method greaterThan( other: concept Comparable(), compared: Bool ): Bool { if( other instanceof Integer() ) { //do comparison here } else { compared := false; } }
A second possiblity is to junk the subtyping relationship and allow covariance.
concept Integer() extends Comparable() { method greaterThan( other: concept Integer() ): Bool; method lessThan( other: concept Integer() ): Bool; method equals( other: concept Integer() ): Bool; }
This is essentially the path that Meyer takes with Eiffel. The main problem with allowing covariant solutions is that it becomes impossible to build a sound static type checker for the language. That is, some type errors would only be detectable at runtime.
A third possibility is to use generic parameters to break up the monolithic hierarchy into several subtyping hierarchies. That is, we can add a parameter to the Comparable concept that determines what types of objects can be compared. Unfortunately, the resulting solution in Sulu necessitates self-referential parameters.
concept Comparable( SelfType: concept Comparable( SelfType ) ) { method greaterThan( other: SelfType ): Bool; method lessThan( other: SelfType ): Bool; method equals( other: SelfType ): Bool; }
Here is how one might create and use a fully instantiated integer class:
class Int: Integer( Int ) realization Builtin(); var a: Int; a := 1; //etc.
Figure 12 illustrates how using self-referential generic parameters can generate several subtyping hierarchies for the Comparable concept.
Finally, using this scheme, here's how a header for a SortingMachine concept would look like:
concept SortingMachine( Item: concept Comparable( Item ) ) { //...
While this works, you can imagine my frustration at the confusing, circular syntax!
Finally, the solution arrived by Bruce in [Bruce02] is also the approach used by Sulu. It essentially replaces subtyping with a new relationship called matching that allows covariance but only for self types. In Sulu, we've adopted a keyword called selftype:
concept Comparable() { method greaterThan( selftype ): Bool; method lessThan( selftype ): Bool; method equals( selftype ): Bool; }
Thus, an Integer realization may use the same signature for greaterThan, lessThan, and equals, but it is taken to mean that the types taken in by the methods are of the Integer realization, not any implementation of Comparable.
Using selftype has these advantages:
Sulu follows RESOLVE in that the main data movement operator is swapping, not assignment. In Sulu, variables map names to objects. Objects may be swapped between variables, or passed into and out of methods also via swapping, following the strategy used in [Harms91]. In a departure from RESOLVE, however, all parameter passing in Sulu is in-out.
[Weide02b] presents the argument for using swapping as the data movement operator in a programming language. Because objects can only be swapped between variables, variables hold unique objects. This solves the problem of aliasing introduced by by-reference assignment. But because swapping can be implemented under the hood as a constant time operation, it solves many of the efficiency problems of by-value assignment.
Sulu, however, does allow assignment in one case. That is the case where a variable is assigned the return value of a method. This is permissible because methods always return new objects, and never aliases.
It is sometimes necessary, especially when dealing with low-level implementation of data structures, that a programmer needs some way of sharing references to objects. For example, if one needs to implement tail-sharing lists. Sulu is envisioned to provide various pointer components for this. Currently, a ChainPointer component is provided that an be used for implementing various acyclic data structures.
In this paper, I have presented a brief overview of the Sulu programming language, and a couple of language design issues that I found challenging to tackle. However, there are still many outstanding issues that need to be resolved (as it were) for the Sulu programming language; there is much that still needs to be done. Here are some:
Automated testing evaluation. This is the core focus of my research; as of this writing, the plug-in system for automated test-cases generation is still under development. There have been various strategies that have been implemented, with varying levels of automation [Cheon02, Edwards00, Mungara03 ] that can be adapted for Sulu.
More components. There is a need to write more components for the programming language. Traditional data-structure type of components to be sure, but also I/O components and GUI components as well. Determining how well the swapping paradigm works for GUI programming may be an interesting topic to explore. There is also a need for a larger number of fully specified components.
Bug fixes and documentation. Because of its relative newness, Sulu is not as stable and bug-free as I would like it to be; the syntax and semantics of the language is also not as completely well documented as I'd like (I hope this paper has helped in alleviating that problem, however slightly).
IDE integration. Integration with Eclipse, syntax-coloring files for vim and emacs, or even giving Sulu its own editor would be nice to have.
I hope that I have piqued the reader's interest in the Sulu programming language. Sulu is still being actively developed; if the reader is interested in contributing to this work, he or she is encouraged to check out the sulu-lang project at Sourceforge [Sulu-sfg]. Any help for this project is certainly welcome.