Joyce (programming language)
Encyclopedia
Joyce is a secure, concurrent
programming language
designed by Per Brinch Hansen
in the 1980s. It is based on the sequential language Pascal
and the principles of Communicating Sequential Processes
(CSP). It was created to address the shortcomings of CSP to be applied itself as a programming language, and to povide a tool, primarily for teaching, for distributed system
implementation.
The language is based around the concept of agents; concurrently executed pocesses that communicate only by the use of channels and message passing
. Agents may activate sub-agents dynamically and recursively
. The development of Joyce formed the foundation of the language SuperPascal
, also developed by Brinch Hansen around 1993.
Agents
An agent is a procedure consisting of a set of statements and possibly nested definitions of other agents. An agent may dynamically activate sub-agents which execute concurrently with their creator. An agent can terminate only when all of its sub-agents have also terminated. For example, an agent
The activation of an agent creates new instances of all local variables and the value of each formal parameter is copied to a local variable. Hence, agents cannot access variables of other agents and are allowed only to communicate through the use of channels. This restriction prevents problems associated with the use of shared variables such as race condition
s.
Communication
Agents communicate through entities called channels. Channels have an alphabet, defining the set of symbols which may be transmitted. Channels are created dynamically and accessed through the use of port variables. A port type is defined by a distinct set of symbols constituting its alphabet. Symbols with multiple values are defined with a specific type. For example:
The symbol
And then a channel entity, internal to the agent creating it, can be activated as follows:
Symbols can then be sent and received on channels using the CSP-style input and output operators
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....
designed by Per Brinch Hansen
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
in the 1980s. It is based on the 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...
and the principles of Communicating Sequential Processes
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
(CSP). It was created to address the shortcomings of CSP to be applied itself as a programming language, and to povide a tool, primarily for teaching, for distributed system
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
implementation.
The language is based around the concept of agents; concurrently executed pocesses that communicate only by the use of channels and message passing
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
. Agents may activate sub-agents dynamically and recursively
Recursion (computer science)
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
. The development of Joyce formed the foundation of the language SuperPascal
SuperPascal
Super Pascal is an imperative, concurrent computing programming language 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...
, also developed by Brinch Hansen around 1993.
Features
Joyce is based on a small subset of Pascal, extended with features inspired from CSP for concurrency. The following sections describe the some of the more novel features that were introduced.Agents
An agent is a procedure consisting of a set of statements and possibly nested definitions of other agents. An agent may dynamically activate sub-agents which execute concurrently with their creator. An agent can terminate only when all of its sub-agents have also terminated. For example, an agent
process2 activates process1:
agent process1(x, y: integer);
begin
...
end;
agent process2;
use process1;
begin
process1(9, 17);
end;
The activation of an agent creates new instances of all local variables and the value of each formal parameter is copied to a local variable. Hence, agents cannot access variables of other agents and are allowed only to communicate through the use of channels. This restriction prevents problems associated with the use of shared variables such as race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
s.
Communication
Agents communicate through entities called channels. Channels have an alphabet, defining the set of symbols which may be transmitted. Channels are created dynamically and accessed through the use of port variables. A port type is defined by a distinct set of symbols constituting its alphabet. Symbols with multiple values are defined with a specific type. For example:
stream = [int(integer), eos];
The symbol
int(integer) denotes a message symbol called int of any integer value. The second typeless symbol declaration eos (end of stream) is known as a signal. Once a port type has been defined, a port variable of that type can be declared:
out : stream
in : stream
And then a channel entity, internal to the agent creating it, can be activated as follows:
+out;
Symbols can then be sent and received on channels using the CSP-style input and output operators
? and ! respectively. A communication can only occur if there is a receiving agent matching the sending agent. The receiving agent must expect to receive the symbol type being sent. For example, the value 9 followed by the eos symbol is sent on port out:
out ! int(9)
out ! eos
And an integer message is received into a variable of a matching type, followed by the eos:
received : integer
in ? int(received)
in ? eos
Polling statements
Polling statements are based the CSP concept of guarded alternatives. A polling statement is made up of a set of statements, each guarded by an input channel statement. When a communication is matched between a transmitting agent and a guard, the guard is executed, followed by the corresponding statement. For example:
poll
in ? X -> x := x + 1 |
in ? Y -> y := y + 1
end
Where the port in is monitored for the signals X or Y, on a matching communication, the corresponding variables x or y are incremented.
Security
Joyce was designed to be a secure language in the sense that a compiler would be able to detect all violations of the language rules.
Example program
The following is a complete example program, taken from the original paper introducing the Joyce programming language, implementing an algorithm to generate prime numbers based on a sieving techniqueGenerating primesIn computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers....
. A sieve agent is sent a stream of integers from its predecessor, the first being a prime. It removes all multiples of this prime from the stream and activates a successor. This continues until the eos signal is propagated along the set of sieves.
agent sieve(inp, out: stream);
var more: boolean; x, y: integer;
succ: stream;
begin
poll
inp?int(x) -> +succ;
sieve(succ, out); more := true |
inp?eos -> out!eos; more := false
end;
while more do
poll
inp?int(y) ->
if y mod x <> 0 then succ!int(y) |
inp?eos -> out!int(x);
succ!eos; more := false
end;
end;
The following agent initialises the set of sieve agents and inputs into them a stream of integers between 3 and 9999.
agent primes;
use generate, sieve, print;
var a, b: stream;
begin
+a; +b; generate(a, 3, 2, 4999);
sieve(a, b); print(b)
end;
Implementation
Stack allocation
Due to concurrent execution of agent procedures, a conventional sequential stack allocation scheme cannot be used as the activation records of the agent calls do not follow a last-in first-out pattern. Instead, the creator-subagent relationships form a tree-structured stack. A simple scheme is used to implement this behaviour, which works by allocating new activation records at the top of the stack, and linking subagents' activation records to their creator's record. These records are freed only when the agent has terminated and they are at the top of the stack. The effectiveness of this scheme depends on the structure and behaviour of a program, which in some cases will result in poor memory usage. A more effective scheme was implemented in the SuperPascalSuperPascalSuper Pascal is an imperative, concurrent computing programming language 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...
language.
External links
- Per Brinch Hansen Archive - A collection of Brinch Hansen's papers.