\section{Principles}
\label{principles}

We have found the treatment of object-oriented methodology
given by Rumbaugh and his colleagues \cite{RumbaughEtAl91}
to be a solid exposition of the concepts and how they apply
to real problems of software engineering.
Rumbaugh considers three models for use in formulating the
requirements of an application: the {\em object model}, the
{\em dynamic model}, and the {\em functional model}. Here
and in the examples given in later sections of this paper,
we show how systems described in terms of these models may
be implemented using ObjectSisal.

We have chosen Sisal~2~\cite{OldehoeftBohCanFeo92} as the
functional programming language
for expressing our examples because it includes stream data
types that are important for our treatment of state machines
and nondeterminate
computation. ObjectSisal includes extensions to provide for the
encapsulation of sets of operations in {\em classes},
and to support inheritance through subtypes. The nondeterminate
{\em merge} operation~\cite{Dennis77} is provided as the sole means
for expressing nondeterminacy.

In ObjectSisal, an object model of the OMT takes the form of a static
hierarchy of class definitions that define a root type and
a collection of subtypes, in which each type or subtype is,
formally, a set of immutable objects together with fixed
operations, as explained below. A dynamic model of the OMT
takes the form of a Sisal function (usually an operation of the
class of the object supposed to have ``state'') that processes
a stream of events to yield a stream of responses. This is
illustrated by the phone line unit discussed in Section~\ref{phone}.

We limit our treatment of the OMT functional model to pure functions,
which are invoked by class operations as required to handle events.
Thus we omit treatment of {\em associations} of OMT and
databases, which will be the subject of future work.


\subsection{Objects, Classes, and Inheritance}

\begin{figure}
{\small\center
\begin{verbatim}
class Object is

  % Attributes

  attribute_1: type_1;
  attribute_2: type_2;
    -----
    -----

  % Operations

  function Operation_1
    -----
    -----
  end function Operation_1

  function Operation_2
    -----
    -----
  end function Operation_2

    -----
    -----

end class Object;
\end{verbatim}}
\caption{\label{class-sisal}The {\tt class} construct
   in ObjectSisal.}
\end{figure}

In ObjectSisal a class of objects is denoted as shown
in Figure~\ref{class-sisal}. A class consists of a set of attributes
and a set of operations. In consonance with principles of
functional programming, a class represents an (immutable)
{\em abstract data type}; each object of type {\tt Object}
has fixed attribute values.

Figure~\ref{operation-sisal} shows a typical operation, in this
case a {\tt Create} operation that creates a new object of type
{\tt Object}. The keyword {\tt object} begins a phrase having
syntax similar to that of the Sisal record constructor; its value
is an object of the class with specified attribute values. The
keyword {\tt private} may preceed {\tt function} to indicate
that the operation is only accessible to other operations of the
class, and is invisible outside.

\begin{figure}
{\small\center
\begin{verbatim}
  function Create ( null returns Object )

    object Object [
      attribute_1: value_1;
      attribute_2: value_2 ]

  end function Create
\end{verbatim}

\caption{\label{operation-sisal}An operation of the {\tt Object}
   class.}}
\end{figure}

No means is provided
for modifying an attribute value of an existing object.
The consequence of insisting on this purity is that
parallelism is exposed without needlessly introducing
unrepeatable behavior, as our examples will illustrate.

Subtype declarations are permitted in ObjectSisal by
an alternate header for a class:

{\small
\begin{verbatim}
  class Object is SuperClass with
    -----
    -----
  end class Object;
\end{verbatim}
}

\noindent
In this case, attributes and operations of the
class {\tt SuperClass} may be referenced by
implementations of operations of the subclass
{\tt Object}. Of course, reuse of the names
of attributes and operations in a subtype
hierarchy is not permitted. A subtype is simply
the immutable supertype, extended with additional
data components and operations, and is itself a
(immutable) derived abstract data type. (It is not
a subtype in the sense of set membership, even
though we may regard objects of the subtype as
``elements'' of the supertype class.) The immutable
property of ObjectSisal objects avoids the reputed
problems of ``subtyping'' in object-oriented
languages.

A nice example of a subtype hierarchy in an
application is the weather monitoring station
example presented in \cite{Blooch94}, pages 293--326.
The weather station reads data periodically from
weather instruments, and keeps track of daily maximum
and minimum values. It normally displays the current
values reported by its sensors, but it also accepts
interactive commands from a keypad that
request display of historical (max/min) readings
and support additional weather station functions.

The weather station has sensors for
temperature, humidity, pressure, wind speed, and wind direction in
the complete example. Here we omit humidity and wind speed for
simplicity. The three
remaining sensors generate the subtype hierarchy drawn in
Figure~\ref{weather-obj} using the OMT diagramming
notation. The class {\tt HistoricalSensor} is a supertype
of the {\tt TemperatureSensor} and {\tt PressureSensor} classes,
and includes attributes
for daily max and min values. It also has the operation {\tt NewExtremes}
which may be invoked by subtype operations to yield new {\tt Sensor}
instances with freshly calculated extreme values.
The code to do this is illustrated in Figure~\ref{sensor-sisal}.

\begin{figure}
\begin{center}

\illustrationx{weather-obj}{3.2in}

\end{center}
\caption{\label{weather-obj}Portion of the object model
   for the weather monitoring station.}
\end{figure}


\begin{figure}\small\center
\begin{verbatim}
class Sensor is
  value: real;
end class Sensor

class HistoricalSensor is Sensor with

  daily_high: real;
  daily_low:  real;
  time_stamp: integer;

  function NewExtremes (
    S: HistoricalSensor;
    time: integer;
    temp: Temperature;
    returns HistoricalSensor )
    let
      v := S.value;
      dh, dl := if NewDay (time, time_stamp)
        then v, v
        else (
         if v > S.daily_high then v else S.daily_high end if
         if v < S.daily_low then v else S.daily_low end if )
        end if 
    in
      S [ daily_high: dh; daily_low: dl; time_stamp: time ]
    end let
  end function NewExtremes;
end class HistoricalSensor

class TemperatureSensor is HistoricalSensor with

  function SampleTemperature (
    TS: TemperatureSensor;
    time: integer;
    returns TemperatureSensor)
    let
      temp := ReadAirTemperature ();
      new_TS := NewExtremes  (TS [value: temp], time, temp);
    in
      new_TS
    end let
  end function SampleTemperature
end class TemperatureSensor
\end{verbatim}
\caption{\label{sensor-sisal}Sensor classes
for the weather station example.}
\end{figure}


\subsection{Streams and State Machines}

\begin{figure}\small\center
\begin{verbatim}
function StreamAdd (
   D: stream of integer;
   returns stream of integer )
   Accumulate ( D, 0 )
end function StreamAdd

function Accumulate (
   D: stream of integer;
   S: integer
   returns stream of integer )
   let
      sum := S + stream_first (D);
   in
      [ sum ] || Accumulate ( stream_rest (D), sum )
   end let
end function Accumulate
\end{verbatim}
\caption{\label{streams-sisal}A simple stream-processing function
    written in Sisal.}
\end{figure}

The Sisal language includes stream data types and the operations\\
{\tt stream\_first} and {\tt stream\_rest} that
yield the initial element of the given stream of values,
and the stream consisting of the remaining
elements, respectively. Figure~\ref{streams-sisal}
illustrates how a simple stream-processing computation may be
expressed in Sisal as a tail-recursive function.

In~\cite{Dennis95a} we have shown how such tail-recursive functions
may be automatically transformed into iterative processes for
efficient code construction. Several stream-processing modules
may be combined to express a processing system in which pairs
of modules are in producer/consumer relationships that permit
all modules to be executing simultaneously~\cite{Dennis95b}.

This facility permits distributed simulation to be implemented
in a programming style that does not allow non-repeatable
(nondeterminate) behavior (to an observer).
The logic simulation program discussed in Section~\ref{logic}
is an example.

A stream-processing function provides a natural style for expressing
a dynamic model of the OMT. The set of states may be an enumeration
type

{\small
\begin{verbatim}
 type State = union [ q0, q1, ... qn: null ];
\end{verbatim}
}

\noindent
and the sequences of input and output events may be elements of
data streams

{\small
\begin{verbatim}
 type InEvent = union [ s0: in_info_0; .. sm: in_info_m ]
 type InStream = stream of InEvent;
 type OutEvent = union [ y0: info_0; .. ym: info_m ]
 type OutStream = stream of OutEvent;
\end{verbatim}
}

\noindent
where the type of each alternative in the unions is chosen to
represent the information conveyed by each kind of input or output event.
Then the function representing the state machine may be written
as shown in Figure~\ref{state-machine}. In this code the functions
{\tt TransitionFunction} and {\tt OutputFunction} are the usual
functions specifying state transitions and output symbols of a
Mealy-type finite state machine. The coding of the phone line unit
given in the appendix follows this scheme.

\begin{figure}\small\center
\begin{verbatim}
function StateMachine (
     S: stream of InEvent;
     returns stream of OutEvent )

  MachineStep ( S, union State [ q0 ] )

end function StateMachine

function MachineStep (
     S: stream of InEvent;
     Q: State;
     returns stream of OutEvent )

  let
    first := stream_first ( S );
    rest := stream_rest ( S );

    new_q := TransitionFunction ( first, Q );
    new_y := OutputFunction ( first, Q );
  in
    stream [ new_y ] || MachineStep ( rest, new_q )
  end let 

end function StateMachine
\end{verbatim}
\caption{\label{state-machine}Expressing a dynamic (state-machine)
   model of the OMT in ObjectSisal.}
\end{figure}

\begin{figure}
\begin{center}

\illustrationx{stream-cycle}{3.0in}

\end{center}
\caption{\label{stream-cycle}A combination of
    stream-processing functions.}
\end{figure}

In some situations it is necessary to combine two stream-processing
functions {\tt f} and {\tt g} as shown in Figure~\ref{stream-cycle}. This
might be written as

\begin{verbatim}
  let
     out_stream, y_stream := f (in_stream, x_stream );
     x_stream := g ( y_stream );
  in
     out_stream
  end let
\end{verbatim}

\noindent
However, this is not permitted in Sisal because
the value name {\tt x\_stream} is used before it has been defined.
This design decision was made so that Sisal could have
{\em strict} semantics, that is, all arguments of any
operation are completely evaluated before the operation
may be applied. Because we wish a stream in ObjectSisal
to have the properties of a {\em non-strict} list thereby
permitting concurrent operation of producer and consumer
modules, we
include in ObjectSisal a feature that permits the value
name of a stream argument to be introduced and referenced
earlier in the program text than its ``left-hand-side''
appearance. Thus the above example may be written in ObjectSisal as

\begin{verbatim}
  let
     out_stream, y_stream := f (in_stream, future_stream x_stream );
     x := g ( y_stream );
  in
     out_stream
  end let
\end{verbatim}

\noindent
In this, the key word {\tt future\_stream} asserts that the
function argument {\tt x\_stream} denotes a stream of values
and should be treated non-strictly.
Illustrations of use of this feature occur in the
weather station and telephone exchange examples that follow.


\subsection{Nondeterminate Computation}

While the logic simulation example has repeatable behavior
and can benefit from being written using inherently repeatable
programming methods, other computations cannot because they
are inherently nondeterminate. The weather station with its
asynchronous input from the keypad is an example. The local
telephone switching system discussed
in Section~\ref{phone} is a more elaborate example.

\begin{figure}
\begin{center}

\illustrationx{weather-flow}{3.2in}

\end{center}
\caption{\label{weather-flow}Flow of events in
   the weather monitoring station.}
\end{figure}

The state of the weather station will be represented
by a collection of attributes of a {\tt WeatherStation}
class in ObjectSisal. The set of attributes
includes the set of {\tt Sensor} objects. Two kinds of events
call for two kinds of transactions to be performed by the
weather station.
A {\em sample transaction} is initiated by a clock tick and
selected sensors are sampled according to the granularity of
current time. A {\em keypad transaction} causes a temporary change
in the display to present a user with certain derived measurement
data, the dew point temperature, or max and min values, for example.

Figure~\ref{weather-flow} shows how the {\tt Process} operation of
the {\tt WeatherStation} class is constructed using the merge
operator to combine the two streams of transaction requests. The
function {\tt ExecuteTransaction}
processes the resulting stream of requests. The ObjectSisal
code corresponding to the
diagram is given in Figure~\ref{weather-sisal}. This code
would have repeatable (determinate) behavior except for its
use of the {\tt merge} operation.

\begin{figure}\small
\begin{verbatim}
class WeatherStation is

  sensors: record [
    T_sensor: TemperatureSensor;
    P_sensor: PressureSensor;
    WD_sensor: WindDirectionSensor ];

  clock: Clock;

  keypad: KeyPad;

  function Create ( null returns WeatherStation )
    -----
    -----
  end function Create

  function Process ( WS: WeatherStation returns null )
    let
      command_stream := ParseInput (keypad);
      sample_stream :=
        GenerateSampleRequests (sensors, clock);
      transaction_stream :=
        merge (command_stream, sample_stream);
    in
      ProcessTransactions ( WS, transaction_stream )
    end let
  end function Process

  function ProcessTransactions (
      WS: WeatherStation;
      Ts: stream of Transaction;
      returns WeatherStation )
    let
      Tf := stream_first (tr_strm);
      WS_new := ExecuteTransaction ( WS, Tf )
    in
      ProcessTransactions ( WS_new, stream_rest (Ts) )
    end let
  end function ProcessTransactions

end class WeatherStation
\end{verbatim}
\caption{\label{weather-sisal}The weather station program.}
\end{figure}

In the telephone exchange we need a means of merging a number
of streams unknown at compile time. To support this requirement
in ObjectSisal, we extend the set of reduction operators that may
be used in a Sisal {\tt for} construct to include the merge operation.
Thus the expression

\begin{verbatim}
 for i in [1..n]
   S : stream of T := ... ;
 returns merge of S[i]
 end for
\end{verbatim}

\noindent
yields the stream resulting from merging the {\tt n} streams
defined in the body of the {\tt for} loop.

These principles, and the examples that follow, show that
the notion of ``object with state'' is not an essential element
of an object-oriented software engineering methodology.
