Strand88

Jeff (Grambo) Graham <graham@TEETOT.ACUSD.EDU>
Mon, 3 Feb 1992 23:11:49 GMT

          From comp.compilers

Related articles
Strand88 graham@TEETOT.ACUSD.EDU (Jeff (Grambo) Graham) (1992-02-03)
More on Strand88 compilers-request@iecc.cambridge.ma.us (John R. Levine) (1992-03-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Jeff (Grambo) Graham <graham@TEETOT.ACUSD.EDU>
Keywords: parallel
Organization: Compilers Central
Date: Mon, 3 Feb 1992 23:11:49 GMT

The Superperformance BRIEFS
Computing Service No.
                                                                                                    Route 39
__________________________________________________________________


March 1990


THE STRAND88 CONCURRENT PROGRAMMING ENVIRONMENT


United Kingdom


by Peter C Patton


INTRODUCTION


Strand is a concurrent programming environment comprising a novel,
expressive programming language and development environment together with
libraries of both concurrent and sequential programs which may be linked
to a concurrent Strand master program. In order to mature as a useful
technology, parallel processing must be supported by tools that allow the
development of concurrent programs which are portable across
multiprocessor and distributed multicomputer architectures.


The major means employed to implement real applications on parallel
processors today are low-level extensions to sequential languages like
FORTRAN, C, LISP, and Prolog. Extended conventional languages are
supported by a number of vendors and high quality compilers are available
for FORTRAN (e.g., Cray, Sequent, Alliant, Myrias, MasPar, Intel) and C
(e.g., Convex, Jade Simulations C++). 'The Ada environment has limited
designed-in concurrent programming features but does not rank in
expressive power with novel concurrent languages and must be considered as
an extended sequential language.






PROGRAMMING LANGUAGE VIEWPOINT


Programming languages may be classified with respect to viewpoint, i.e.,
whether they are prescriptive like machine languages, descriptive like
logic or denotative like mathematical notation. Exhibit 1 presents a
language triangle that plots programming languages qualitatively in a
threefold scheme with respect to viewpoint. Most programming languages
present a mixture of viewpoints; the utility of the triangle is to provide
a paradigm to classify in a comparative way existing languages and to
extrapolate the characteristics of potentially useful new ones. In
particular, the triangle represents an attempt to characterize the
differences between logic (descriptive) and functional (denotative)
programming languages, both of which have been called 'declarative'. The
language triangle, defined by the three language viewpoint poles
(prescriptive, denotative and descriptive) is an extension suggested by
Scott Danforth and Steven Tighe of PJ. Landin's prescriptive/ descriptive
spectrum that appeared in his article, 'The Next 700 Programming
Languages' in the March 1966 CACM, nearly twenty-five years ago.


                                                              Exhibit 1
                              A Programming Language Viewpoint Paradigm


                                                            DESCRIPTIVE
                                                                        Pure Logic Programming
                                                                  / \
                                                              / \ ThingLab, Bertrand
                                                          / \
                                                      / Prolog \ TABLOG
                                                  / \
                                OPS 5 / \ Bertrand
                                          / FCP Super \
                                      / Concurrent \ Miranda, SASL
                                  / Prolog \ w/ Absolute Sets
                              / Parlog \
                          / LogLISP \ Miranda, SASL
  Machine / \w/Relative Sets
Language / KL-1 \
              /_____________________________________________________\ Pure LISP
                            C FORTRAN LISP 1.5 APL FP
    PRESCRIPTIVE ADA DENOTATIVE




The prescriptive viewpoint is the traditional imperative, or
command-oriented paradigm. In this view, programming is accomplished by
instructing the computer to perform a series of steps, with the
understanding that if the computer obeys its instructions, the desired
answer will be generated. A prescriptive viewpoint makes no attempt to
assign a meaning to the program itself since it is simply a recipe or
prescription. Machine languages are always prescriptive.


In a denotative language, programs are composed of definitions and an
expression representing or denoting the desired result. This expression
denoting the result may refer to defined functions and other objects,
which may in turn make similar references. The computer's job is to
transform the result expressions, by using the definitions, into a
self-contained, simplified form much as a series of mathematical
substitutions. One therefore denotes the desired answer and asks, 'What
is the value of this expression?' Purely functional languages are
denotative.


Descriptive language programs are composed of constraints and possibly an
implicit goal to be satisfied in view of those constraints. A descriptive
program can be thought of as the request, 'Give me x, where x satisfies
the constraints...' The programmer thus describes the desired answer
indirectly, specifying a set of constraints to be satisfied, and the
language implementation tries to find an answer (or answers) that fit. It
is interesting to note that, as early as 1966, Landin recognized the
possibility of such languages, but efficient implementations to support
this approach were not then known. At that time, the possibility of
descriptive programming seemed intimately linked to the problem of
automatic program generation.


Prolog succeeded as a descriptive language primarily because it was able
to narrow the domain of constraints in a dean and effective way to
universally quantify first-order Horn clauses, and thereby provide a
simple and effective implementation mechanism. In addition to Logic
Programming systems, constraint systems such as Thinglab and Sketchpad are
essentially descriptive in viewpoint In these cases, the domain of a
program is a set of powerful algebraic constraints involving real numbers
and functions over them. Implementation mechanisms include relaxation,
propagation of known states or bottom-up reasoning, and propagation of
constraints or top-down reasoning.


Exhibit 1 represents a placement of several existing languages onto the
triangle as a computer science perspective of programming language
research. The reasoning behind the placements is as follows:


Machine languages are prescriptive. FORTRAN made a step forward when it
allowed functional expressions on the right side of assignment commands,
and this is why it lies toward the denotative pole. John Backus' FP
(Functional Programming) and pure LISP (LISP1.0) are purely denotative.
APL is essentially functional but includes prescriptive assignments to
objects such as arrays. IASP 1.5 includes prescriptive commands such as
setq and has therefore been placed even doser to the prescriptive pole by
Danforth and Tighe. Syracuse University Professor Alan Robinson's LogLISP
carries an of LISP's semantic baggage but moves up in the direction of the
descriptive pole.


Pure logic programming is descriptive. Prolog is primarily descriptive; it
becomes somewhat prescriptive because of cut and assert and slightly
denotative by virtue of is, an assignment statement. Both Concurrent
Prolog and Parlog sacrifice a great deal of descriptive purity in search
of efficiency, through the use of modes and guards, and are therefore
partially prescriptive.


Tablog provides a mixture of descriptive and denotative viewpoints.
Bertrand is a constraint language, i.e., a language for specifying
constraint systems based on rewrite rules and a pattern matcher. Miranda
is Kent University Professor David Turner's language, based on his earlier
SASL (St. Andrews Static Language). Both languages incorporate his KRC
(Kent Recursive Compiler) relative set construct, a move toward
descriptive programming. Using absolute sets moves a functional language
such as Miranda or SASL even closer to descriptive programming, since the
set is now the essence of a constraint equation solution.


The middle of the triangle represents the perfect expressive language for
concurrent programming, able to support any of the three viewpoints. The
Super language, developed as a successor to LogLISP by Professor Robinson,
has implemented for the Connection Machine at Syracuse and is probably
closer to the center than any concurrent programming language available
today.


STRAND88 is not placed on the triangle because it represents a sort of
metalanguage which lies on another sheet of the manifold above this
triangular 'language space.' Strand is essentially a dataflow language and
thus has a data-oriented rather than a control-oriented viewpoint for
programming a computer. Strand is able to incorporate modules written in
certain existing languages in such a way that it manages their
interprocess dataflow concurrently on a parallel processor and allows them
to function as cooperating sequential processes. The language component
alone of a Strand implementation would lie near the pure logic or denotive
corner of the triangle.


THE STRAND LANGUAGE


The language component of the Strand environment allows a variety of novel
implementation techniques. It is characterized by dynamic dataflow, single
assignment to variables and a flat (i.e., no hierarchy of processes or
operations) structure. Rule guards or constraints contain only simple
tests; hence no values are generated during guard evaluation. Equality
tests are only defined on ground terms; hence a text X==Y suspends until X
& Y are assigned values. Self-referential and cyclic data structures are
not supported. These definitions ensure that processes only read data
during matching and guard evaluation; data is written by independent
assignment operations expressed in rule bodies.


A Strand computation corresponds to a pool of concurrently executing
processes and a computation step involves removing a process from the
pool. If the process is a predefined process it is executed immediately-,
otherwise a reduction attempt is made. This involves selecting a rule from
the program, matching the process to the rule head and executing the rule
guard. If the preconditions specified by the head and guard are satisfied
then the process commits. This causes new instances of the processes
defined in the rule body to be added to the process pool. Processes can be
selected for reduction in any order or in parallel.


A simple algorithm is used to match a rule head with a process. This is
applied left to right textually and depth first in structures and may
succeed, fail, or suspend. A successful match generates a (possibly empty)
set of assignments i to variables in the rule head.


Numbers and strings match only if they are identical in both type and
value. Structures match if they are the same size and corresponding
arguments match. A variable V in a rule matches any term T in a process;
the assignment V/T is added to i. An attempt to match a variable in a
process with a non-variable in a rule head causes a match to suspend. All
other matches fail.


A variety of predefined guard tests are provided which can be used to
perform type checking, arithmetic comparison and term comparison. They are
executed from left to right textually after matching is complete. Each
test may succeed, fail or suspend. If all tests in a guard succeed then
the guard as a whole succeeds; if any test fails or suspends then the
guard as a whole fails or suspends, respectively. Tests generally suspend
if they encounter a variable during evaluation.


The predefined assignment process ':=' is used to assign values to
variables. A call X : = Y causes X to denote Y. Variables obey the single
assignment rule and can only be assigned a value once; any attempt to
assign to a non-variable is treated as an exception, like trying to divide
by zero.


An operational description model of program execution involves matching,
transitions, and computation as follows:


- Composite Matching: The procedure CMatch takes as arguments
          a process and a rule and executes the match algorithm
          followed by guard execution and returns either a match or
          suspend.


- States: The state of a computation is a multiple set up
          of processes. Every process either is or is not an
          assignment process of the form X := Y.


- Transitions: A transition rule specifies a mapping between
          states. Execution of a program P may include the following
          transitions:


          * Reduction
          * Assignment
          * Suspension


- Computation: A computation is a sequence of transitions that
          ends in a terminal state in which no further rules can be
          applied. A computation that ends in the state with no further
          process to perform is called a successful computation. A
          computation that ends in the state suspend is termed a
          suspending computation.




STRAND IMPLEMENTATION


The simplicity of the Strand design has led to a number of efficient and
portable implementations. Here we outline the essential features of one
such implementation, characterized by a small distributed run-time system.
The complete system including predefined processes, a distributed
asynchronous garbage collector and computation control compiles to less
than 128K bytes on commonly used processors.


The Strand Abstract Machine (SAM) consists of a reduction component and a
communication component within each processor in a parallel or distributed
system. The reduction component selects and executes processes from a
local process pool Its abstract instruction set supports the basic
operations required by the operational model; i.e., reading and writing of
data, and creation, termination and scheduling of processes.


Processes communicate by reading and writing shared variables; the
implementation ensures that each variable occurs only once and is located
at a single processor. Processes which reside at other processors may
access a variable via a remote reference. The reduction component
generates communication if a remote reference is encountered during a
reduction. The communication component receives and services these
messages; thus it is responsible for implementing read and write
operations associated with remote values.


The reduction component of the SAM is based on conventional uniprocessor
implementation techniques. Operations in the language are strictly
segregated between reading and writing, no writing occurs in the guard so
bindings to variables can be made unconditionally, and treatment of guard
failure is simplified since no storage need be reclaimed. No special
actions need be performed when committing to the use of a particular rule
(some systems require that computations be aborted or that variable
bindings created during guard execution be made public). As in
implementations of other flat languages, no process hierarchy such as that
employed in Prolog implementations is required.


Programming environments require facilities that allow them to survive
program exceptions (e.g., divide by zero, process failure), detect the
termination of computations and control computation execution. These
facilities are supported via a simple control primitive that associates a
stream with a computation. Exceptions are signaled as messages on this
stream, which is closed when the computation terminates. All other control
facilities are provided via source-to-source transformations.


Most abstract machines copy process arguments between a process and
registers before and after each reduction. In contrast, the SAM allows
values to be maintained in registers between process reductions. This
reduces data movement when recursion optimizations are applied. The
instructions for encoding control and construction of data are designed
around this concept.


Previous implementations have not dealt adequately with predefined
operations (e.g., arithmetic, type conversion). Typically, either a
separate process is spawned for each such operation or the programmer is
required to express the operations in the guard. The former is expensive
and the latter both complicates the implementation and may cause
operations to be repeated. In contrast, the SAM allows all predefined
processes to be compiled in fine; this is made possible by a mechanism
that creates a suspended process if data is not available.


As processes can suspend on more than one variable, previous
implementations have employed complex structures to implement process
suspension. Most processes suspend on only a single variable, thus it is
possible to employ simpler techniques to advantage. For example, a process
that suspends on a single variable can be simply finked to that variable
without intermediate structures. Processes that suspend on more than one
variable can be linked to a global queue.


As head matching and guard evaluation can only read data, switch
instructions can be used to compile all process definitions into
discrimination networks. This can be achieved without the large code size
increases associated with native code compilation.


The operational description fists two major transition rules: the
reduction rule reads values for matching and guard execution; the
assignment rule writes values. Both reading and writing may generate
communication if they encounter remote references. The language
implementation incorporates two simple algorithms, read and write, that
translate operations on remote terms into messages. These messages
request other processors to perform the appropriate actions. In outline,
the algorithms operate as follows:


- Write: This algorithm is invoked when an assignment
          operation encounters a remote reference. It generates a
          Write message to the remote processor, containing an address
          and a data structure. The receiving processor binds the
          variable specified by the address to the supplied term.


- Read: This algorithm is invoked when a read operation
          encounters a remote reference. it generates a Read message
          to the remote processor. This specifies the term required by
          the read operation and a return address for the value. A
          processor receiving a Read message returns the requested
          value, if and when it becomes available, using a Value
          message.




STRAND PROGRAM PORTABILITY


Strand has been successfully ported to a wide range of multiprocessor
architectures. In addition, applications developed on one parallel
architecture can be ported to any other with little or no reprogramming.
The key to system portability is the simplicity of the STRAND88
implementation. Machine-specific features only occur in the communication
component and are restricted to the mechanisms used to send and receive
messages; hence, implementations on different architectures differ chiefly
in the techniques used to implement message-passing.


On multicomputers such as the Intel, Symult and NCube machines, low-level
facilities provided by the underlying operating system are sufficient. On
local area networks, network protocols are used for the same purpose,
though obviously at substantially greater cost. On shared memory machines
such as Sequent, Encore, and Butterfly, monitors encapsulating message
queues located in shared memory are used to provide the necessary
functionality, careful design minimizes contention for shared resources.
In principle, an implementation specialized for shared memory machines can
avoid this simulated message passing. However, it is not dear that this
provides significant performance benefits for realistic applications.


The factors encourage portability of Strand applications as well.
Programs execute in the same manner whether located on a single computer
or distributed over several computers. In addition, the programming system
includes libraries that provide programmers with a variety of virtual
machines and load balancing tools. The same virtual machines are supported
on all architectures and thus enable portability. A virtual machine is a
collection of connected computing sites called nodes; a variety of these
machines are supported which differ only in the manner in which nodes are
connected. The connection topologies are designed to be convenient
programming structures and correspond to familiar organizations
encountered in problem solving (e.g., ring, mesh, tree etc.). Many
processes may execute at each node in a virtual machine. Tools are
provided to specify where, within a machine, a set of processes is to
execute. In addition to providing portability, virtual machines ease the
programming task and allow applications to scale when additional hardware
becomes available.


PROGRAMMING IN STRAND88


Most programs written in concurrent logic languages rely on six
fundamental techniques: producer/ consumers, incomplete messages, bounded
buffers, difference fists, short circuits and blackboards. The first
three of these techniques are used to express various stream-based
interprocess communication protocols. A difference list is a
representation of a list that allows it to be constructed in parallel by a
set of processes. The short circuit technique is used to detect when a
collection of processes has terminated. The blackboard technique allows
multiple processes to both read and atomically update a shared data
structure.


Efficient support and convenient expression of the fundamental techniques
have been important system design goals in Strand.




The bounded buffer protocol is the most complex of the three stream
communication protocols and is used here as an example of Strand coding.
This technique organizes communication between producer and consumer
processes so as to bound the number of unreceived messages and is achieved
using a message buffer via which all communication is conducted. The
producer only generates messages if there is space in the buffer; the
consumer is responsible for creating space when it removes elements:


producer(N,[M|Ms]):- % R1. Wait for Buffer
          N>0| % Still generating?
                    N1 is N - 1 % One less to generate
                    M := msg % Generate a message
                    producer(N1,Ms). % Recurse to generate more
producer(0,[M|Ms]):- % R2. All done?
          M := done % Close stream


consumer([msg|Ms],Buffer) :- % R3. Wait for msg
          Buffer := [X|Bs], % Extend buffer
          consumer(Ms,Bs). % Consume rest
consumer([done|Ms],_). % R4. Terminate


The following set of processes creates an initial buffer represented by a
list of five unbound variables. The producer process is given access to
the beginning of the buffer; the consumer is given access to both the
beginning and end.


                    Buffer := [M1,M2,M3,M4,M5|Mn],
                    producer(100,Buffer),
                    consumer(Buffer,Mn)


The producer waits for an element of the buffer to be available (Rl) and
then assigns this element a value representing a message (M:=msg). The
producer may terminate the protocol by adding a done message to the buffer
(R2). If no element is available, the producer suspends; this occurs due
to matching. The consumer suspends until messages are available and then
consumes them from the beginning of the buffer (R3). Each time it receives
a message, the consumer creates space in the buffer by appending an
unbound variable to the end (Buffer:= [X|Bs]). When the consumer receives
a done message it terminates (R4). Hence, execution of the initial set of
processes causes a 100 msg messages to flow from the producer to the
consumer, no more than five messages are outstanding at any one time.


A consequence of the single assignment rule in Strand is that variables
cannot be used directly to represent mutable data. Yet many programming
problems require the ability to represent information that changes over
time. A programming technique called a blackboard is used to resolve this
problem and is shown below as a Strand coding example.


A blackboard is a data structure maintained by a set of processes. The
technique for organizing this structure allows it to be updated
atomically; many processes can both read and write information on it. The
mutable data structure is encapsulated in a process to which other
processes send read and write requests. A predefined merger process can be
used to combine streams of requests generated by a varying number of
processes. The following code illustrates this technique using a simple
program that simulates a memory cell. The cell receives a stream of read
and write messages; it encapsulates an internal state that is initially
undefined (R1). A read message causes the current state to be returned via
an incomplete message (R2). A write message causes the state to be
modified to the value V contained in the message (R3). The cell terminates
when its input stream is closed (R4).


cell(Is) :-cell(Is,_). % R1. Initialize


cell([read(V)|Is],State) :- % R2. Read cell
          V : = State, % Return state
          cell(Is,State). % Use same state
cell([Write(V)|Is],_) % R3. Write cell
          cell(Is,V). % State modified to V
cell([],-). % R4. Terminate


The following set of processes *illustrates how many readers and writers
may access the cell:


reader1(R1),..readerN(RN),
writer1(W1),...writerM(WM),
merger([merger(R1),...merge(RN),merge(W1),...merge(WM)],Reqs),
cell(Reqs)


N reader and M writer processes produce streams of requests to the cell.
The merger process ensures that all requests eventually appear at the cell
input stream (Reqs).


A common use of blackboards is to encapsulate mutable structures. During
program development, the effect of updating can be achieved by copying.
Performance enhancement may replace copying with destructive operations.
Since these side-effects are encapsulated within a single process, it is
simple to ensure that other processes are not aware that the single
assignment rule is violated. Strand's user-defined data types and
operations allow these operations to be organized and implemented using
other languages (e.g., C and FORTRAN).


CONCLUDING REMARKS


There are a number of novel programming languages for mapping concurrent
algorithms onto parallel processors. The parallel processing research
program at MCC in Austin, Texas focused on novel concurrent languages and
identified and experimented with a number of them. While many of these
languages exhibit remarkable expressive power for concurrent computations,
most of them are research tools and years away from being deployable
'industrial strength' systems. In addition, many novel languages are
highly recursive in nature and difficult for programmers (other than their
creators) to use.


On the other hand, conventional language extensions are easier to use and
many are supported by capable optimizing compilers for actual parallel
processors. Unfortunately, code written in a proprietary extension (e.g.,
Myrias FORTRAN) is not transportable and an extended conventional language
does not have the expressive power of a language designed for concurrent
programming. The design of Strand was motivated by its creator's
experience with the implementation and application of research concurrent
programming systems when they found research languages too complex for
efficient and portable implementation on parallel architectures. Strand
makes the key concepts of concurrent logic programming accessible to
programmers in a somewhat simpler framework. Practical experience with
Strand suggests that their quest for simplicity has been successful. It
has been possible to achieve efficient Strand implementations on a broad
range of multiprocessor architectures; moreover, a wide variety of
applications have been developed by industrial partners and collaborators.
The most important area of application has proved to be the development of
concurrent programs which integrate program modules written in existing
sequential code.


This proven capability makes Strand and its currently available
implementation, STRAND88, a practical intermediate stage between extended
conventional (sequential) languages based on a prescriptive viewpoint
(e.g., Fortran, C), and novel (concurrent) languages based either on a
denotative viewpoint (e.g., LISP, Functional Programming) or a descriptive
viewpoint (e.g., Pure Logic, Prolog). A STRAND88 program is able to employ
the Strand language as the glue or binder to assemble existing sequential
FORTRAN and C programs and subroutines into a concurrent programming
paradigm.




REFERENCES:


Ian Foster and Stephen Taylor, Strand New Concepts in Parallel
Programming, Prentice-Hall, Englewood Cliffs, NJ. 1990, 323 pp.


Ian Foster, Systems Programming in Parallel Logic Languages,
Prentice-Hall, London, 1989.


Stephen Taylor, Parallel Logic Programming Techniques,
Prentice-Hall, Englewood Cliffs, NJ., 1989.




For more information contact:
:
Strand Software Technologies, Inc.
3368 Governor Drive, Suite F269
San Diego, California 92122
TEL: (619) 455-6090
FAX: (619) 450-3680 (attn: Strand Software)
E-Mail: 4956839@mcimail.com


or


Strand Software Technologies, Inc.
Grey Caine Road
Watford, Hertsfordshire
UK VD2-4JP
TEL: 0923 247707
FAX: 0923 247836
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.