\section{Related Work}

The design of ObjectSisal has roots in earlier research efforts,
including Clu's abstract data type mechanism~\cite{Liskov77},
Dennis and Weng's work on tail-recusive computing with
streams~\cite{DennisWen79,Dennis94}, proposals for structuring
nondeterminate computations~\cite{Dennis77}, and the common understandings
of inheritance and encapsulation as these notions have evolved
in object-oriented programming paradigms.

Here we compare ObjectSisal with
other advanced languages and systems devised for programming distributed
systems, both object-oriented and others that offer the benefits of
high-level structured programming in real-time applications. Our
discussion considers how well each programming environment supports
principles of modular
software construction.\footnote{Modularity mechanisms for concurrent,
object-oriented programming are discussed in~\cite{AghaEtAl93}, but no
definition of modularity is given and the sort of program modularity
described apprears to be quite limited. For example, no properties
corresponding to our Recursive
Construction and Secure Arguments principles are discussed.}

In \cite{Dennis94} we listed six principles of modular
software construction:

\begin{enumerate}

\item
{\em Information Hiding Principle:} The user of a module must
not need to know anything about the internal mechanism
of the module to make effective use of it.

\item
{\em Invariant Behavior Principle:} The functional behavior
of a module must be independent of the site and context from
which it is invoked.

\item
{\em Data Generality Principle:} The interface to a module
must be capable of passing any data object an application may require.

\item
{\em Secure Arguments Principle:} A module
must not be able to affect the behavior of another
module through a shared argument.

\item
{\em Recursive Construction Principle:} A program constructed
from modules must be usable as a component in building larger
programs or modules.

\item
{\em System Resource Management Principle:} Resource management
for data objects must be performed by the computer system, not
by program modules.

\end{enumerate}

We believe that the ObjectSisal Language provides a programming
framework that satisfies all six of these principles. Most other
approaches to distributed object-oriented computation do not.

Some tools for concurrent object-oriented programming make
explicit use of sequential processes.
The Ada language uses {\em tasking} to spawn concurrent processes
that can operate on objects using methods encaspsulated in
{\em packages}.
ConcurrentSmalltalk~\cite{IshikawaTok87} uses processes so that
the concurrent version can be made compatible with its sequential parent,
Smalltalk 80. In the ``composable'' lanaguage CC++~\cite{ChandyKes93},
C++ is augmented with processes and
a synchronizing mechanism to coordinate operations on objects.


Orca~\cite{BalKaaTen92}, is intended to support concurrent applications
on a network of machines that does not support a
common address space. An Orca program 
consists of processes that execute operations on objects. By using
relatively coarse grain operations, operations
on objects at remote sites can be executed efficiently in
comparison to the fine-grain read and write primitives used in
other approaches to distributed computing.
However, nested objects (objects that are components of other
objects), lead to inefficiencies due to the complexity of ensuring
atomicity of operations.

These tools all view objects in the traditional object-oriented
manner---as entities having ``state''---which leads to all of the
difficulties concerning coordination of actions and conflicts with
principles of modularity discussed above. They
fail to satisfy the principles Data Generality and
Recursive Construction, and most of them also fail to support
the Resource Management Principle. Data Generality is violated
because it is normally not possible to
pass an arbitrary data value (object) in a message sent from one
process to another. (A general mechanism must be able to pass
addresses of component objects, and these addresses
must have the same meaning in the context of any process,
a property not usually satisfied.) The principle of Recursive
Program Construction is usually violated
because there is no syntactic construct that permits encapsulation of
a set of processes to present the same form of interface
to users as the class construct provides for object types.
The Resource Management principle is violated when processes are
statically bound to processors, and cannot be migrated by the system
to balance resource usage; memory management is limited by the binding
of allocation actions to processes.

Several approaches to distributed object-oriented
programming do not have the problems of explicit processes.
The most studied and developed of these are the actor-based paradigms
developed by Agha and Hewitt~\cite{Agha90}, the work of Yonezawa and
his assocites on ABCL~\cite{Yonezawa90}, and others, for example
POOL-T~\cite{America87}. In these systems, a computation is performed
by a collection of
{\em actors} that respond to {\em messages} containing data (argument
values and objects) and the name of a {\em method} to be executed
on the object. Sending a message corresponds to performing
a function or procedure call
in a conventional language, but the method defines an operation
characteristic of the object, and is encapsulated with object data
in a {\em class} definition.

Because the methods of a class may alter values of object attributes,
undisciplined behavior would occur if concurrent execution of methods
for the same object were permitted. Therefore, actor languages
provide synchronization mechanisms that may be used to ensure that
the effect of operations is as if they have been strictly interleaved.
Many different schemes have been described in the literature;
however they all have the property of permitting accesses and
updates of objects to be arbitrarily interleaved, therby
permitting nondeterminate (nonrepeatable) behavior. Because
actor languages permit messages to contain objects that may be
updated by methods, they also do not satisfy the Secure Arguments
Principle.

The actor-based systems generally satisfy Data Generality and
Resource Mangement principles of software modularity. They
satisfy the Data Generality principle by permitting any object to
be sent in a message, and the Resource Mangement
Principle through use of system memory management (including
automatic garbage collection). They also support the Information Hiding
principle through the class encapsulation facility.

Support of the Recursive Construction Principle demands a means
for combining modules (class definitions) into new modules that
can be reused in different contexts with invariant behavior. This
principle is supported by mechanisms for importing class
definitions into other classes and for binding methods to
operation calls. Dynamic binding that supports type polymorphism
is good; however, dynamic binding mechanisms that lead to context-dependent
behavior are in violation of the Invariant Behavior principle.
In ObjectSisal, static binding of methods (functions) to
function invocations is employed, so recursive construction is
supported with a guarantee of invariant behavior.


UFO (United Functions and Objects) \cite{Sargeant93} is perhaps
the best-known work attempting to combine the
features of object-oriented and functional
programming styles. Besides a purely functional subset, UFO supports
``stateful'' objects in the same way as other concurrent
object-oriented languages, supporting the view that objects
may be updated by concurrent operations.
Calls upon the functions and
procedures of a class of stateful objects are handled as messages,
using mechanisms similar to those of the actor-based languages.

It is asserted in~\cite{Sargeant93}
that functions in UFO are not permitted to modify their arguments, as
demanded by our Secure Arguments Principle. It appears
that this is to be implemented by compile-time determination of whether
any argument to a function can contain a stateful object to which a
procedural method could be applied. In ObjectSisal we expect the Secure
Arguments Principle to be met because most data are values. However, it is
conceivable that use of the nondeterminate merge operator can lead to
the creation of data objects that can exhibit changing behavior. We must be
certain that such data objects cannot be made components of function
arguments, but we have not yet done a careful study of this question.

Although UFO and ObjectSisal share the common motivation of realizing
the benefits of the functional programming style in distributed
computing applications, two
very different approaches to the problem of state are used. 
In using stateful objects, we believe UFO imports weaknesses of
concurrent object-oriented programming, including, in particular, the
property that programs that utilize ``objects'' are susceptible to
nondeterminate behavior, whether or not intended.

In ObjectSisal, we insist that all objects
are immutable and that those situations that appear to require
``state'' can be supported using history-sensitive functions on 
data streams to build state machines, and by using the merge of streams
when nondeterminate behavior is required. One property of this
design is that ObjectSisal programs cannot deadlock except in case of
memory exhaustion, a property not achieved by other programming tools for
object-oriented software engineering.

In~\cite{ShapiroTak87}, Shapiro and Takeuchi have shown how
object-oriented programming may be done using Concurrent Prolog.
Shared logic variables are used to implement
streams of events flowing between objects, which are processes
executing self-recursive functions. Because Concurrent Prolog
allows nondeterminacy in the way subgoals are selected, programs
written in Concurrent Prolog are subject to the same hazards as
in other object-oriented styles. Indeed, the nondeterminate
merge has a simple implementation in Concurrent Prolog.

Many object-oriented languages are typeless or rely on runtime detection
of some kinds of type errors. ObjectSisal does not utilize dynamic binding,
so every function interface can be fully type-checked before program execution;
no type errors should show up during program execution.
Sisal types are sets of immutable data objects with operations forming
abstract heterogeneous algebras; hence the type system is not burdened with
duties relating to protection or concurrency control, as is done in some
object-oriented languages.

Before leaving object-oriented programming systems, we note that there
is an acknowledged interference between the goals of inheritance (making
the methods of one class available to other classes that define subtypes)
and mechanisms designed to support coordination between access and update
operations. A thorough analysis of this problem has been done by
Matsuoka and Yonezawa~\cite{MatsuokaYon93}, yielding no completely
satisfactory solution. As a consequence, the designers of many concurrent
object-oriented languages have elected to forgo implementing inheritance.
In ObjectSisal the problem may not arise because ``messages'' (function
calls in ObjectSisal) are never selected or queued. The Maude
language~\cite{Meseguer93} also appears to avoid the anomaly by adopting
a ``declarative'' semantics based on a formal rewriting logic.

Erlang~\cite{ArmstrongVir90} is a ``declarative'' programming langauge
that has been used experimentally to implement a prototype telephone
switching system~\cite{PerssonOldEri92}. In a distributed context,
an Erlang program creates explicit processes, and uses message passing
for interprocess communication. The use and benefit of functional
programming lies in the construction of the individual
proocess code. There appears to be no means in Erlang for encapsulating a
group of processes into a higher level program module.

These features of Erlang are at odds with the principles of Data
Generality, Secure Arguments, Recursive Construction, and Resource
Management. If a system to be built is amenable to static resource
management, that is, compile-time partitioning and scheduling is feasible,
then Erlang provides support for writing the application as a single
layer of concurrent modules that coordinate through message-passing.
However there is no way to group sets of these modules into larger
system components that may be used similarly. Furthremore, Data Generality
is limited by the data types that may be packed into messages.

In this paper we have not addressed the question of applying
functional programming principles and software modularity principles
to the issues of database systems. Most object-oriented
database systems are based on a transaction-oriented
view~\cite{OzsuDayVal94}. A particularly sophisticated
design is Thor~\cite{LiskovDayShr94}.
As in actor-based object-oriented languages, consistency of the set of
stored objects is maintained by imposing mutual exclusion on calls to
methods of object classes. This is done either by some atomicity
scheme using two-phase commit, or by means of locks. Thor supports
applications written in Theta~\cite{LiskovEtAl95}, a sequential
object-oriented language evolved from Clu.

It seems that ObjectSisal would work well for object-oriented databases.
An implementation would treat all objects as persistent and use a garbage
collector to reclaim memory of abandoned objects. The ``associations'' of the
Rumbaugh OMT method can be built using standard classes (of immutable
objects); ``stores'' may be realized as state machines, if determinate,
and using the nondeterminate merge of transaction streams otherwise.

