Super Pascal is an imperative, concurrent computing

Concurrent computing

Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel...

 programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

 developed by Brinch Hansen. It was designed as a publication language: a thinking tool to enable the clear and concise expression of concepts in parallel programming. This is in contrast with implementation languages which are often complicated with machine details and historical conventions. It was created to address the need at the time for a parallel publication language. Arguably, few languages today are expressive and concise enough to be used as thinking tools.

History and development

SuperPascal is based on Niklaus Wirth

Niklaus Wirth

Niklaus Emil Wirth is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award for developing a sequence of innovative computer languages.-Biography:Wirth...

's sequential language Pascal

Pascal (programming language)

Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...

, extending it with features for safe and efficient concurrency. Pascal itself was used heavily as a publication language in the 1970s; it was used to teach structured programming

Structured programming

Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops - in contrast to using simple tests and jumps such as the goto statement which could...

 practices and featured in text books, for example, on compilers and programming languages. Brinch Hansen had earlier developed the language Concurrent Pascal, one of the earliest concurrent languages for the design of operating systems and real-time control systems.

The requirements of SuperPascal were based on the experience gained by Brinch Hansen over three years in developing a set of model parallel programs, which implemented methods for common problems in computational science. This experimentation allowed him to make the following conclusions about the future of parallel scientific computing:

• Future parallel computers will be general-purpose, allowing programmers to think in terms of problem-orientated process configurations. This was based on his experience programming networks of transputers, which were general-purpose processors able to be connected in arrays, trees or hypercubes.

• Regular problems in computational science require only deterministic parallelism, that is, expecting communication from a particular channel, rather than from several.

• Parallel scientific algorithms can be developed in an elegant publication language and tested on a sequential computer. When it is established an algorithm
  Algorithm
  In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
  
   works, it can easily be implemented in a parallel implementation language.

These then led to the following requirements for a parallel publication language:

• The language should extend a widely used standard language with deterministic parallelism and message communication. The extensions should be in the spirit of the standard language.

• The language should make it possible to program arbitrary configurations of parallel processes connected by communication channels. These configurations may be defined iteratively or recursively and created dynamically.

• The language should enable a single-pass compiler to check that parallel processes do not interfere in a time-dependent manner.

Features

The key ideas in the design of SuperPascal was to provide a secure programming, with abstract concepts for parallelism.

Security

SuperPascal is secure in that it should enable its compiler and run-time system to detect as many cases as possible in which the language concepts break down and produce meaningless results. SuperPascal imposes restrictions on the use of variables that enable a single-pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables, eliminating time-dependent errors. Several features in Pascal were ambiguous or insecure and were omitted from SuperPascal, such as labels and goto statements, pointers and forward declarations.

Parallelism

The parallel features of SuperPascal are a subset of occam 2

Occam (programming language)

occam is a concurrent programming language that builds on the Communicating Sequential Processes process algebra, and shares many of its features. It is named after William of Ockham of Occam's Razor fame....

, with the added generality of dynamic process arrays and recursive parallel processes.

A parallel statement denotes that the fixed number of statements it contains must be executed in parallel. For example:

parallel

    source |

    sink

end

A forall statement denotes the parallel execution of a statement by a dynamic number of processes, for example:

forall i := 0 to 10 do

    something

Channels and communication

Parallel processes communicate by sending typed messages through channels created dynamically. Channels are not variables in themselves, but are identified by a unique value known as the channel reference, which are held by channel variables. A channel is declared, for example, by the declaration

type channel = *(boolean, integer);

var c: channel;

which defines a new (mixed) type named channel and a variable of this type named c. A mixed type channel is restricted to transmitting only the specified types, in this case boolean and integer values. The channel c is initialised by the open statement:

open(c)

Message communication is then achieved with the send(channel, value) and receive(channel, variable) statements. The expression or variable providing the value for send, and the variable in receive, must both be of the same type as the first channel argument. The following example shows the use of these functions in a process that receives a value from the left channel and outputs it on the right one.

var left, right: channel; a: number;

receive(left, a);

send(right, a)

The functions send and receive can both take multiple input and output arguments respectively:

send(channel, e1, e2,..., en);

receive(channel, v1, v2,..., vn)

The following run-time communication errors can occur.

• Channel contention occurs when two parallel processes both attempt to send or receive on the same channel simultaneously.
• A message type error occurs when two parallel processes attempt to communicate through the same channel and the output expression and input variable are of different types.
• Deadlock occurs when a send or receive operation waits indefinitely for completion.

Parallel recursion
Recursive procedures can be combined with parallel and forall statements to create parallel recursive processes. The following example shows how a pipeline of processes can be recursively defined using a parallel statement.

procedure pipeline(min, max: integer; left, right: channel);

var middle: channel;

begin

  if min < max then

    begin

      open(middle);

      parallel

        node(min, left, middle) |

        pipeline(min + 1, max, middle, right)

      end

    end

  else node(min, left, right)

end;

Another example is the recursive definition of a process tree:

procedure tree(depth: integer, bottom: channel);

var left, right: channel;

begin

  if depth > 0 then

    begin

      open(left, right);

      parallel

        tree(depth - 1, left) |

        tree(depth - 1, right) |

        root(bottom, left, right)

      end

    end

  else leaf(bottom)

Interference control

The most difficult aspect of concurrent programming is unpredictable or non-reproducible behaviour caused by time-dependent errors. Time-dependent errors are caused by interference between parallel processes, due to variable updates or channel conflicts. If processes sharing a variable, update it at unpredictable times, the resulting behaviour of the program is time-dependent. Similarly, if two processes simultaneously try to send or receive on a shared channel, the resulting effect is time-dependent.

SuperPascal enforces certain restrictions on the use of variables and communication to minimise or eliminate time-dependent errors. With variables, a simple rule is required: parallel processes can only update disjoint sets of variables. For example, in a parallel statement a target variable cannot be updated by more than a single process, but an expression variable (which can't be updated) may be used by multiple processes. In some circumstances, when a variable such as an array is the target of multiple parallel processes, and the programmer knows its element-wise usage is disjoint, then the disjointness restriction may be overridden with a preceding [sic] statement.

Structure and syntax

SuperPascal is a block structured language, with the same basic syntax as Pascal. A program consists of a header, global variable definitions, function or procedure definitions and a main procedure. Functions and procedures consists of blocks, where a block is a set of statements. Statements are separated by semicolons, as opposed to languages like C

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

 or Java (programming language)

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, where they are terminated by semicolons.

The following is an example of a complete SuperPascal program, which constructs a pipeline communication structure with 100 nodes. A master node sends an integer token to the first node, this is then passed along the pipeline and incremented at each step, and finally received by the master node and printed out.

program pipeline;



const

    len = 100;



type

    channel = *(integer);



var

    left, right: channel;

    value: integer;



procedure node(i: integer; left, right: channel);

var value: integer;

begin

    receive(left, value);

    send(right, value+1)

end;



procedure create(left, right: channel);

type row = array [0..len] of channel;

var c: row; i: integer;

begin

    c[0] := left;

    c[len] := right;

    for i := 1 to len-1 do

        open(c[i]);

    forall i := 1 to len do

        node(i, c[i-1], c[i])

end;



begin

    open(left, right);



    parallel

        send(left, 0) |

        create(left, right) |

        receive(right, value)

    end;



    writeln('The resulting value is ', value)

end.

Implementation

The SuperPascal software can be accessed freely from the Brinch Hansen Archive. It consists of a compiler and interpreter, which are both written in normal, sequential Pascal (ISO Level 1 standard Pascal). This is supported by the GNU Pascal compiler (and not by the Free Pascal compiler

Free Pascal

Free Pascal Compiler is a free Pascal and Object Pascal compiler.In addition to its own Object Pascal dialect, Free Pascal supports, to varying degrees, the dialects of several other compilers, including those of Turbo Pascal, Delphi, and some historical Macintosh compilers...

), with the following small modification to the code.

The file interpret.p uses the non-standard clock function (line 1786), which is used to obtain the system time. Instead, the Extended Pascal getTimeStamp function can be used (which is supported by the GNU Pascal compiler), by declaring a variable of type TimeStamp, setting that with the current time using getTimeStamp and assigning the Second field of the TimeStamp to the variable t.

As a note for 64-bit operating systems; the GNU Pascal compiler will need to be compiled and installed from source.

External links

• Per Brinch Hansen Archive - A collection of Brinch Hansen's papers and the SuperPascal software which can be downloaded in a compressed file, and contains the full language specification and useful documentation.
• Pascal Wikibook - Description of the Pascal programming language.