++plus Essay, Research Paper
Introduction
——————————————————————————–
Sather is an object oriented language designed to be simple, efficient, safe, and non-proprietary. It aims to meet the needs of modern research groups and to foster the development of a large, freely available, high-quality library of efficient well-written classes for a wide variety of computational tasks. It was originally based on Eiffel but now incorporates ideas and approaches from several languages. One way of placing it in the ’space of languages’ is to say that it attempts to be as efficient as C, C++, or Fortran, as elegant but safer than Eiffel or CLU, and to support higher-order functions as well as Common Lisp, Scheme, or Smalltalk.
Sather has garbage collection, statically-checked strong (contravariant) typing, multiple inheritance, separate implementation and type inheritance, parameterized classes, dynamic dispatch, iteration abstraction, higher-order routines and iters, exception handling, assertions, preconditions, postconditions, and class invariants. Sather code can be compiled into C code and can efficiently link with object files of other languages. pSather, the parallel and distributed extension, presents a shared memory abstraction to the programmer while allowing explicit placement of data and threads.
Sather and the ICSI Sather compiler have a very unrestrictive license aimed at encouraging contribution to the public library without precluding the use of Sather for proprietary projects.
This chapter will provide a basic introduction for new users, pointing to sources of information about the language and the compiler. It also contains a summary of Sather features – for those familiar with another object-oriented language, this section provides an overview of the key features of Sather.
1.1 Acknowledgements
This text has its roots in the Sather 1.1 specification, the Eclectic tutorial and Holger’s iterator tutorial. This document also contains several organizational ideas and some text from S. Omohundro’s originally planned Sather book.
This text has benefitted from corrections, comments and suggestions from several people including Cary D. Renzema, Jerome Feldman, Claudio Fleiner and Arno Jacobsen. Particular thanks to Cary, Arno and Feldman for detailed error reports. Arno also made several suggestions regarding terminology and examples that have been incorporated.
1.2 How to read this Document
This document is meant to be a complete description of Sather 1.1, and is intended as an introduction to the language for a person with some programming background. It is more expository in nature than the specification and contains sections that motivate particular aspects of the language, such as the overloading rules. In addition, it deals with some more abstract design issues that arise when programming in Sather (such as the effect of the contra-variant subtyping rule).
1.3 Sources of Information
This section briefly introduces some concepts important to Sather that the reader may not have been exposed to in C++ [2]. It isn’t meant as a complete language tutorial. More information of a tutorial nature is available from the WWW page:
http://www.icsi.berkeley.edu/Sather
At the time of this writing, the only compiler implementing the 1.1 language specification is available from ICSI. It is freely available, includes source for class libraries and the compiler, and compiles into ANSI C. This compiler has been ported to a wide range of UNIX and PC operating systems.
1.4 Obtaining the Compiler
The ICSI Sather 1.1 compiler can be obtained by anonymous ftp at
ftp.icsi.berkeley.edu: /pub/sather
Other sites also mirror the Sather distribution. The distribution includes installation instructions, ‘man’ pages, the standard libraries and source for the compiler (in Sather). Documentation, tutorials and up-to-date information are also available at the Sather WWW page:
http://www.icsi.berkeley.edu/~sather
ICSI also maintains a library of contributed Sather code at this page.
There is a newsgroup devoted to Sather:
comp.lang.sather
There is also a Sather mailing list if you wish to be informed of Sather releases; to subscribe, send email to:
sather-request@icsi.berkeley.edu
It is not necessary to be on the mailing list if you read the Sather newsgroup.
1.4.1 How do I ask questions?
If it appears to be a problem that others would have encountered (on platform ‘X’, I tried to install it but the it failed to link with the error ‘Y’), then the newsgroup is a good place to ask. If you have problems with the compiler or questions that are not of general interest, mail to one of
sather-bugs@icsi.berkeley.edu
psather-bugs@icsi.berkeley.edu
This is also where you want to send bug reports.
1.5 Summary of Features
This section provides a summary of Sather’s features, with particular attention to features that are not found in the most common object oriented languages.
1.5.1 Basic Concepts
Data structures in Sather are constructed from objects, each of which has a specific concrete type that determines the operations that may be performed on it. Abstract types specify a set of operations without providing an implementation and correspond to sets of concrete types. The implementation of concrete types is defined by textual units called classes; abstract types are specified by textual units called abstract classes. Sather programs consist of classes and abstract class specifications. Each Sather variable has a declared type which determines the types of objects it may hold.
Classes define the following features: attributes which make up the internal state of objects, shareds and constants which are shared by all objects of a type, and methods which may be either routines or iterators. Any features are by default public, but may be declared private to allow only the class in which it appears access to it. An attribute or shared may instead be declared readonly to allow only the class in which it appears to modify it. Accessor routines are automatically defined for reading or writing attributes, shareds, and constants. The set of non-private methods in a class defines the interface of the corresponding type. Method definitions consist of statements; for their construction expressions are used. There are special literal expressions for boolean, character, string, integer, and floating point objects.
Certain conditions are described as fatal errors. These conditions should never occur in correct programs and all implementations of Sather must be able to detect them. For efficiency reasons, however, implementations may provide the option of disabling checking for certain conditions.
1.5.2 Garbage Collection and Checking
Like many object-oriented languages, Sather is garbage collected, so programmers never have to free memory explicitly. The runtime system does this automatically when it is safe to do so. Idiomatic Sather applications generate far less garbage than typical Smalltalk or Lisp programs, so the cost of collecting tends to be lower. Sather does allow the programmer to manually deallocate objects, letting the garbage collector handle the remainder. With checking compiled in, the system will catch dangling references from manual deallocation before any harm can be done.
More generally, when checking options have been turned on by compiler flags, the resulting program cannot crash disastrously or mysteriously. All sources of errors that cause crashes are either eliminated at compile-time or funneled into a few situations (such as accessing beyond array bounds) that are found at run-time precisely at the source of the error.
1.5.3 No Implicit Calls
Sather does as little as possible behind the user’s back at runtime. There are no implicitly constructed temporary objects, and therefore no rules to learn or circumvent. This extends to class constructors: all calls that can construct an object are explicitly written by the programmer. In Sather, constructors are ordinary routines distinguished only by a convenient but optional calling syntax (page 107). With garbage collection there is no need for destructors; however, explicit finalization is available when desired (page 143).
Sather never converts types implicitly, such as from integer to character, integer to floating point, single to double precision, or subclass to superclass. With neither implicit construction nor conversion, Sather resolves routine overloading (choosing one of several similarly named operations based on argument types) much more clearly than C++. The programmer can easily deduce which routine will be called (page 47).
In Sather, the redefinition of operators is orthogonal to the rest of the language. There is ‘’syntactic sugar” (page 116) for standard infix mathematical symbols such as ‘+’ and ‘^’ as calls to otherwise ordinary routines with names ‘plus’ and ‘pow’. ‘a+b’ is just another way of writing ‘a.plus(b)’. Similarly, ‘a[i]‘ translates to ‘a.aget(i)’ when used in an expression. An assignment ‘a[i] := expr’ translates into ‘a.aset(i,expr)’.
1.5.4 Separation of Subtyping and Code Inclusion
In many object-oriented languages, the term ‘inheritance’ is used to mean two things simultaneously. One is subtyping, which is the requirement that a class provide implementations for the abstract methods in a supertype. The other is code inheritance (called code inclusion in Sather parlance) which allows a class to reuse a portion of the implementation of another class. In many languages it is not possible to include code without subtyping or vice versa.
Sather provides separate mechanisms for these two concepts. Abstract classes represent interfaces: sets of signatures that subtypes of the abstract class must provide. Other kinds of classes provide implementation. Classes may include implementation from other classes using a special ‘include’ clause; this does not affect the subtyping relationship between classes. Separating these two concepts simplifies the language considerably and makes it easier to understand code. Because it is only possible to subtype from abstract classes, and abstract classes only specify an interface without code, sometimes in Sather one factors what would be a single class in C++ into two classes: an abstract class specifying the interface and a code class specifying code to be included. This often leads to cleaner designs.
Issues surrounding the decision to explicitly separate subtyping and code inclusion in Sather are discussed in the ICSI technical report TR 93-064: ”Engineering a Programming Language: The Type and Class System of Sather,” also published as [7]. It is available at the Sather WWW page.
1.5.5 Iterators
Early versions of Sather used a conventional ‘until…loop…end’ statement much like other languages. This made Sather susceptible to bugs that afflict looping constructs. Code which controls loop iteration is known for tricky ”fencepost errors” (incorrect initialization or termination). Traditional iteration constructs also require the internal implementation details of data structures to be exposed when iterating over their elements.
Simple looping constructs are more powerful when combined with heavy use of cursor objects (sometimes called ‘iterators’ in other languages, although Sather uses that term for something else entirely) to iterate through the contents of container objects. Cursor objects can be found in most C++ libraries, and they allow useful iteration abstraction. However, they have a number of problems. They must be explicitly initialized, incremented, and tested in the loop. Cursor objects require maintaining a parallel cursor object hierarchy alongside each container class hierarchy. Since creation is explicit, cursors aren’t elegant for describing nested or recursive control structures. They can also prevent a number of important optimizations in inner loops.
An important language improvement in Sather 1.0 over earlier versions was the addition of iterators. Iterators are methods that encapsulate user defined looping control structures just as routines do for algorithms. Code using iterators is more concise, yet more readable than code using the cursor objects needed in C++. It is also safer, because the creation, increment, and termination check are bound together inviolably at one point. Each class may define many sorts of iterators, whereas a traditional approach requires a different yet intimately coupled class for each kind of iteration over the major class. Sather iterators are part of the class interface just like routines.
Iterators act as a lingua-franca for operating on collections of items. Matrices define iterators to yield rows and columns; tree classes have recursive iters to traverse the nodes in pre-order, in-order, and post-order; graph classes have iters to traverse vertices or edges breadth-first and depth-first. Other container classes such as hash tables, queues, etc. all provide iters to yield and sometimes to set elements. Arbitrary iterators may be used together in loops with other code.
The rationale of the Sather iterator construct and comparisons with related constructs in other languages can be found in the ICSI technical report TR 93-045: ”Sather Iters: Object-Oriented Iteration Abstraction,” also published as [5]. It is available at the Sather WWW page.
1.5.6 Closures
Sather provides higher-order functions through method closures, which are similar to closures and function pointers in other languages. These allow binding some or all arguments to arbitrary routines and iterators but defer the remaining arguments and execution until a later time. They support writing code in an applicative style, although iterators eliminate much of the motivation for programming that way. They are also useful for building control structures at run-time, for example, registering call-backs with a windowing system. Like other Sather methods, method closures follow static typing and behave with contravariant conformance.
1.5.7 Immutable and Reference Objects
Sather distinguishes between reference objects and immutable objects. Imutable objects never change once they are created. When one wishes to modify an immutable object, one is compelled to create a whole new object that reflects the modification.
Experienced C programmers immediately understand the difference when told about the internal representation the ICSI compiler uses: immutable types are implemented with stack or register allocated C ’struct’s while reference types are pointers to the heap. Because of that difference, reference objects can be referred to from more than one variable (aliased), but immutable objects never appear to be. Many of the built-in types (integers, characters, floating point) are immutable classes. There are a handful of other differences between reference and immutable types; for example, reference objects must be explicitly allocated, but immutable objects ‘just are’.
Immutable types can have several performance advantages over reference types. Immutable types have no heap management overhead, they don’t reserve space to store a type tag, and the absence of aliasing makes more compiler optimizations possible. For a small class like ‘CPX’ (complex number), all these factors combine to give a significant win over a reference class implementation. Balanced against these positive factors in using an immutable object is the overhead that some C compilers introduce in passing the entire object on the stack. This problem is worse in immutable classes with many attributes. Unfortunately the efficiency of an immutable class is directly tied to how smart the C compiler is; at this time ‘gcc’ is not very bright in this respect, although other compilers are.
Immutable classes aren’t strictly necessary; reference classes with immutable semantics work too. For example, the reference class ‘INTI’ implements immutable infinite precision integers and can be used like the built-in immutable class ‘INT’. The standard string class ‘STR’ is also a reference type but behaves with immutable semantics. Explicitly declaring immutable classes allows the compiler to enforce immutable semantics and provides a hint for good code generation. Common immutable classes are defined in the standard libraries; defining a new immutable class is unusual.
1.5.8 IEEE Floating-Point
Sather attempts to conform to the IEEE 754-1985 specification for its floating point types. Unfortunately, many platforms make it difficult to do so. For example, underflow is often improperly implemented to flush to zero rather than use IEEE’s gradual underflow. This happens because gradual underflow is a special case and can be quite slow if implemented using traps. When benchmarks include simulations which cause many underflows, marketing pressures make flush-to-zero the default.
There are many other problems. Microsoft’s C and C++ compilers defeat the purpose of the invalid flag by using it exclusively to detect floating-point stack overflows, so programmers cannot use it. There is no portable C interface to IEEE exception flags and their behavior with respect to ’setjmp’ is suspect. Threads packages often fail to address proper handling of IEEE exceptions and rounding modes.
Correct IEEE support from various platforms was the single worst porting problem of the Sather 1.0 compiler. In 1.1, we give up and make full IEEE compliance optional. Sather implementations are expected to conform to the spirit, if not the letter, of IEEE 754, although proper exceptions, extended types, underflow handling, and correct handling of positive and negative zero are specifically not required.