Sather 1.1 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:

[email protected]

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

[email protected]

[email protected]

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.

The Sather treatment of NaNs is particularly tricky; IEEE wants NaN to be neither equal nor unequal to anything else, including other NaNs. Because Sather defines ‘x /= y’ as ‘x.is_eq(y).not’ (page 116), to get the IEEE notion of unequal is necessary to write ‘x=x and y=y and x/=y’. Other comparison operators present similar difficulties.

1.5.9 pSather

Parallel Sather (pSather) is a parallel extension of the language, developed and in use at ICSI. It extends serial Sather with threads, synchronization, and data distribution.

pSather differs from concurrent object-oriented languages that try to unify the notions of objects and processes by following the actors model [1]. There can be a grave performance impact for the implicit synchronization this model imposes on threads even when they do not conflict. While allowing for actors, pSather treats object-orientation and parallelism as orthogonal concepts, explicitly exposing the synchronization with new language constructs.

pSather follows the Sather philosophy of shielding programmers from common sources of bugs. One of the great difficulties of parallel programming is avoiding bugs introduced by incorrect synchronization. Such bugs cause completely erroneous values to be silently propagated, threads to be starved out of computational time, or programs to deadlock. They can be especially troublesome because they may only manifest themselves under timing conditions that rarely occur (race conditions) and may be sensitive enough that they don’t appear when a program is instrumented for debugging (heisenbugs). pSather makes it easier to write deadlock and starvation free code by providing structured facilities for synchronization. A lock statement automatically performs unlocking when its body exits, even if this occurs under exceptional conditions. It automatically avoids deadlocks when multiple locks are used together. It also guarantees reasonable properties of fairness when several threads are contending for the same lock.

Data placement

pSather allows the programmer to direct data placement. Machines do not need to have large latencies to make data placement important. Because processor speeds are outpacing memory speeds, attention to locality can have a profound effect on the performance of even ordinary serial programs. Some existing languages can make life difficult for the performance-minded programmer because they do not allow much leeway in expressing placement. For example, extensions allowing the programmer to describe array layout as block-cyclic is helpful for matrix-oriented code but of no use for general data structures.

Because high performance appears to require explicit human-directed placement, pSather implements a shared memory abstraction using the most efficient facilities of the target platform available, while allowing the programmer to provide placement directives for control and data (without requiring them). This decouples the performance-related placement from code correctness, making it easy to develop and maintain code enjoying the language benefits available to serial code. Parallel programs can be developed on simulators running on serial machines. A powerful object-oriented approach is to write both serial and parallel machine versions of the fundamental classes in such a way that a user’s code remains unchanged when moving between them.

1.6 History

Sather is still growing rapidly. The initial Sather compiler (for ‘Version 0′ of the language) was written in Sather (bootstrapped by hand-translating to C) over the summer of 1990. ICSI made the language publicly available (version 0.1) June of 1991 [4]. The project has been snowballing since then, with language updates to 0.2 and 0.5, each compiler bootstrapped from the previous. These versions of the language are most indebted to Stephen Omohundro, Chu-Cheow Lim, and Heinz Schmidt. pSather co-evolved with primary contributions by Jerome Feldman, Chu-Cheow Lim, Franco Mazzanti and Stephan Murer. The first pSather compiler [3] was implemented by Chu-cheow Lim on the Sequent Symmetry, workstations and the CM-5.

Sather 1.0 was a major language change, introducing bound routines, iterators, proper separation of typing and code inclusion, contravariant typing, strongly typed parameterization, exceptions, stronger optional runtime checks and a new library design [6]. The 1.0 compiler was a completely fresh effort by Stephen Omohundro, David Stoutamire and Robert Greisemer. It was written in 0.5 with the 1.0 features introduced as they became functional. The 1.0 compiler was first released in the summer of 1994, and Stephen left the project shortly afterwards. The pSather 1.0 design was largely due to Jerome Feldman, Stephan Murer and David Stoutamire.

This document describes Sather 1.1, released the summer of 1996. The compiler was originally designed and implemented by S. Omohundro, D. Stoutamire and (later) Robert Griesemer. Boris Vaysman is the current Sather czar and feature implementor. Claudio Fleiner implemented most of the common optimizations , a lot of debugging support, the pSather runtime and back-end support for pSather. Michael Philippsen implmented the front/middle support for pSather. Holger Klawitter implemented type checking of parametrized classes. Arno Jacobsen worked on bound iterators. Illya Varnasky implemented inlining support and Trevor Paring implemented an early version of common subexpression elimination.

A group at the University of Karlsruhe under the direction of Gerhard Goos created a compiler for Sather 0.1. The language their compiler supports, Sather-K, diverged from the ICSI specification when Sather 1.0 was released. Karlsruhe has created a large class library called Karla using Sather-K. More information about Sather-K can be found at:

http://i44www.info.uni-karlsruhe.de/~frick/SatherK

1.6.1 The Name

Sather was developed at the International Computer Science Institute, a research institute affiliated with the computer science department of the University of California at Berkeley. The Sather language gets its name from the Sather Tower (popularly known as the Campanile), the best-known landmark on campus. A symbol of the city and the university, it is the Berkeley equivalent of the Golden Gate bridge across the bay. Erected in 1914, the tower is modeled after St. Mark’s Campanile in Venice, Italy. It is smaller and a bit younger than the Eiffel tower. The way most people say the name of the language rhymes with ‘bather’.

The name ‘Sather’ is a pun of sorts – Sather was originally envisioned as a smaller, efficient, cleaned-up alternative to the language Eiffel. However, since its conception the two languages have evolved to be quite distinct.

1.6.2 Sather’s Antecedents

Sather has adopted ideas from a number of other languages. Its primary debt is to Eiffel, designed by Bertrand Meyer, but it has also been influenced by C, C++, Cecil, CLOS, CLU, Common Lisp, Dylan, ML, Modula-3, Oberon, Objective C, Pascal, SAIL, School, Self, and Smalltalk.

Steve Omohundro was the original driving force behind Sather, keeping the language specification from being pillaged by the unwashed hordes and serving as point man for the Sather community until he left in 1994. Chu-Cheow Lim bootstrapped the original compiler and was largely responsible for the original 0.x compiler and the first implementation of pSather. David Stoutamire took over as language tsar and compiler writer after Stephen left. That position was, in turn, taken over by Boris Vaysman in late 1995.

Sather has been very much a group effort; many, many people have been involved in the language design discussions including: Subutai Ahmad, Krste Asanovic, Jonathan Bachrach, David Bailey, Joachim Beer, Jeff Bilmes, Chris Bitmead, Peter Blicher, John Boyland, Matthew Brand, Henry Cejtin, Alex Cozzi, Richard Durbin, Jerry Feldman, Carl Feynman, Claudio Fleiner, Ben Gomes, Gerhard Goos, Robert Griesemer, Hermann H?ertig, John Hauser, Ari Huttunen, Roberto Ierusalimschy, Arno Jacobsen, Matt Kennel, Holger Klawitter, Phil Kohn, Franz Kurfess, Franco Mazzanti, Stephan Murer, Michael Philippsen, Thomas Rauber, Steve Renals, Noemi de La Rocque Rodriguez, Hans Rohnert, Heinz Schmidt, Carlo Sequin, Andreas Stolcke, Clemens Szyperski, Martin Trapp, Boris Vaysman, and Bob Weiner. Countless others have assisted with practical matters such as porting the compiler and libraries.

1.6.3 References

[1] G. Agha, ”Actors: A Model of Concurrent Computation in Distributed Systems”, The MIT Press, Cambridge, Massachusetts, 1986.

[2] S. Burson, ”The Nightmare of C++”, Advanced Systems November 1994, pp. 57-62. Excerpted from The UNIX-Hater’s Handbook, IDG Books, San Mateo, CA, 1994.

[3] C. Lim. “A Parallel Object-Oriented System for Realizing Reusable and Efficient Data Abstractions,” PhD thesis, University of California at Berkeley, October 1993. Available at the Sather WWW page.

[4] C. Lim, A. Stolcke. ”Sather language design and performance evaluation.” TR-91-034, International Computer Science Institute, May 1991. Also available at the Sather WWW page.

[5] S. Murer, S. Omohundro, D. Stoutamire, C. Szyperski, ”Iteration abstraction in Sather”, Transactions on Programming Languages and Systems, Vol. 18, No. 1, Jan 1996 p. 1-15. Available at the Sather WWW page.

[6] S. Omohundro. ”The Sather programming language.” Dr. Dobb’s Journal, 18 (11) pp. 42-48, October 1993. Available at the Sather WWW page.

[7] C. Szyperski, S. Omohundro, S. Murer. “Engineering a programming language: The type and class system of Sather,” In Jurg Gutknecht, ed., Programming Languages and System Architectures, p. 208-227. Springer Verlag, Lecture Notes in Computer Science 782, November 1993. Available at the Sather WWW page.