Skip to content
/ cpa-lang-shootout Public

A repository of code listings for Communicating Process Architecture language and library test programs.

License

MIT license
2 stars 1 fork Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

kevin-chalmers/cpa-lang-shootout

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

143 Commits
src
src
 
 
.gitignore
.gitignore
 
 
.travis.yml
.travis.yml
 
 
README.md
README.md
 
 
build.sh
build.sh
 
 
license.md
license.md
 
 

Repository files navigation

Message-passing Concurrent Language Evaluation

This repository contains a collection of programs that evaluate languages with message-passing concurrency. The programs are designed to evaluate properties of message-passing concurrency rather than general language performance. Furthermore, a selection of features from process calculi are examined for each language. These are:

  • Synchronous communication.
  • First-order channels.
  • Higher-order channels.
  • First-order processes.
  • Higher-order processes.
  • Parallel execution statement.
  • Indexed parallel execution statement.
  • State ownership.
  • Process ownership.
  • Selection on incoming messages.
  • Indexed selection.
  • Selection based on incoming value.
  • Guarded selection.
  • Fair selection.
  • Selection with timer.
  • Other selection types.
  • Selection of outgoing messages.
  • Multi-party synchronisation.
  • Selection on multi-party synchronisation.

A description of these features is provided in the appendix below.

Classification

One of the aims of this work is the building of a classification for message-passing concurrent languages. The hope is that an understanding of common features and different approaches can be made by investigating the approaches to message-passing concurrency. At present, the classification is limited as only a handful of languages have been examined. The current classification is below:

TODO

Current Languages

The languages currently evaluated are:

Languages that have so far been discounted are:

  • Aha!
  • ALGOL 68
  • AmbientTalk
  • Ateji PX
  • Axum
  • BCPL
  • C=
  • Cω
  • Clojure
  • Concurrent Pascal, although SuperPascal may allow a similar analysis.

Details on why these languages are discounted is given in the Discounted Languages section.

Benchmark Results

There are currently three benchmark applications:

  1. Communication Time.
  2. Selection Time.
  3. Monte Carlo π (for multicore support analysis).

The benchmarks are described in the appendix below.

Contributing to the Evaluation

If you want to help, feel free to pull the repository, implement the benchmarks, undertake the evaluation, and make a pull request. At present, the following languages have been identified as potentially having message-passing concurrency support in the language or via the language's standard libraries but have not been completed.

Not all of these languages may support message-passing concurrency, as only a quick overview has been made. Languages may also be missing. If you know of a language missed please get in touch. Also, to be included a current implementation of the language is required. There are historic languages with message-passing concurrency, but seem to be unavailable today. For comparison purposes, the language must run on Linux.

Language selection criteria:

  1. the language must provide mechanisms to send a message between components as part of the core language features (e.g., keyword support and/or standard library) and not via an additional library.
  2. the message must be sent in a manner so that the receiver can choose when to receive it; therefore, giving the receiver control over its internal state. A method invocation on an object is therefore not a message. This criteria implies a receiver has some thread of execution independant to the sender.
  3. the receiver must be able to wait passively for a message to be received - that is, a busy spinning on a value to change is not a message. Having a queue between threads that a receiver tests for readiness is not suitable.
  4. a communication must be made using a single command, i.e., language keyword or standard library call. A slight concesion is made for yielding due to the use of coroutine approaches that often require an explicit yield statement, and languages that may define a communication in some form of block statement. This is to keep in the spirit of a message-pass being a single operation.
  5. messages must be any structured data type supported in the language. Conversion to bytes, strings, or another data serialization technique is not considered message-passing. Nor is any use of I/O mechanisms to simulate communication.

If you have to download a separate library, or write your own functions, to achieve message-passing then the criteria does not allow the language to be included. Future work will examine library support, but as numerous examples exist this is currently outside the scope of this work.

Currently Discounted Languages

For various reasons, some languages originally considered for the study have been discounted. These languages, and some information for there discounting, are listed below:

  • Aha!. Appears to be unavailable now.
  • ALGOL 68 - but may be stretching the definition. ALGOL 68 requires explicit use of shared values and semaphores to enable message passing. This violates criteria 4.
  • AmbientTalk - instructions available here. On analysis, AmbientTalk does not meet criteria 2 (the message must be sent in a manner so that the receiver can choose when to receive it; therefore, giving the receiver control over its internal state). This is because messages are essentially asynchronous method calls on actors, not a communication that the actor can decide when to engage in.
  • Ateji PX - seems to be unavailable now.
  • Axum - but looks like this is closed.
  • BCPL - details here - but looks like a complicated mechanism to allow communication. On examination, although BCPL does have coroutine support, message-passing has to be implemented by the programmer. As such, BCPL is dicounted.
  • C= - although unsure how easy it is to communicate between concurrent components. Appears to be unavailable now.
  • Cω - Microsoft Research page. Might not be suitable. After some investigation, Cω became the Joins Concurrency Library for .NET, although this is not a standard library and therefore does not meet the criteria. A Cω compiler can be downloaded, but it requires .NET 1.1, which is no longer supported. Thus, Cω has been discounted from the list.
  • Clojure - instructions available here. At present this does not seem to meet the criteria. The agents package provides simple agents that respond to function calls but have no control over their state. The core.async package does provide the functionality, but it is not core Clojure and therefore does not meet criteria 1.
  • Concurrent Pascal - although it might be a stretch saying this is live. A compiler for microcontrollers is available here. After some investigation it appears that Concurrent Pascal is not available. No version exists that can be executed on Linux.
  • Smalltalk. Smalltalk's concurrency support is limited to forking processes and a semaphore for synchronisation. As such, it does not meet the criteria for message passing.

Language Timeline

This section indicates when languages where released. The aim is to illustrate any clusters of development.

  1. (2) Prolog
  2. (1) Standard ML (as ML)
  3. (0)
  4. (0)
  5. (0)
  6. (1) Icon
  7. (0)
  8. (0)
  9. (0)
  10. (0)
  11. (1) SIGNAL
  12. (4) Ada, Esterel, occam, SISAL
  13. (0)
  14. (0)
  15. (3) Eiffel, Erlang, LabVIEW
  16. (1) Perl
  17. (3) Object REXX, PicoLisp, Tcl
  18. (1) SequenceL
  19. (3) Haskell, J, Python
  20. (1) Oz
  21. (1) μC++
  22. (4) Concurrent ML, Euphoria, Lua, SuperPascal
  23. (2) Newsquek, Racket
  24. (4) Java, Limbo, Mercury, Ruby
  25. (1) Ocaml
  26. (1) E
  27. (1) Logtalk
  28. (1) SystemC
  29. (4) C#, Hume, Join Java, Unicon
  30. (4) CAL Actor Language, D, SALSA, SpecC
  31. (2) Io, SystemVerilog
  32. (4) Aikido, ChucK, Falcon, Go!
  33. (1) Scala
  34. (3) F#, Neko, XC
  35. (1) Sequoia++
  36. (1) Dodo, Manticore
  37. (2) Nim, PREESM
  38. (3) Clump, Go, ProcessJ
  39. (2) Fancy, Rust
  40. (3) Elixir, Kotlin, Red
  41. (1) Julia
  42. (2) Wren, Zonnon
  43. (4) Goaldi, Oforth, Pony, Swift
  44. (2) Panda, Perl 6
  45. (1) Fantom
  46. (0)
  47. (0)

Unknown - FortranM, JoCaml, MPD, Mythryl, Phix, SR, Zkl

Additional References

There are a few sites which provide useful information on programming languages:

Appendix

Properties

The properties taken from process calculi are:

Synchronous Communication

Generally, process calculi work with synchronous communication - that is two or more processes must agree to communicate and do so as a single atomic operation. For example, in CSP:

channel a, b

P = a -> b -> SKIP
Q = b -> SKIP

SYSTEM = P [{b} || {b}] Q

Q will always wait until P is ready to communicate via b, and vice-versa. Not all languages support synchronous communication.

First-order Channels

Does the language have a channel-like construct? Although process calculi generally have channels for inter-process communication, not all languages do. Typically, actor-style concurrent languages do not have channels.

Higher-order Channels

The π-Calculus permits channels to be sent as messages, thus reconfiguring the communication network. For example (adapted from Wikipedia):

(new x)(x<z>.0 | x(y).y<x>.x(y).0) | z(v).v<v>.0

z is communicated over channel x in the first step:

(new x)(0 | z<x>.x(y).0) | z(v).v<v>.0

x is communicated over channel z in the next step:

(new x)(0 | x(y).0) | x<x>.0

In the final step, x is communicated via channel x:

(new x)(0 | 0) | 0

If the language's channels support sending any type, this will typically include channels.

First-order Processes

Assigning an active process to a variable is not a process calculus feature except in the higher-order π-Calculus. First-order processes are included for two reasons:

  1. Languages without channels will use a process variable to send messages to.
  2. To discuss higher-order processes below.

If a process launch can be assigned to a variable, then the language supports first-order processes. Actor-style concurrency requires this feature, although other languages do support it.

Higher-order Processes

The higher-order π-Calculus supports sending of process variables across a channel. For example:

x<R>.P | x(Y).Q

It has been shown that in the π-Calculus process mobility can be simulated via channel mobility. However, the ability to send a process name is used extensively in actor-style concurrency to build communication networks. Typically, if a language supports first-order processes it supports higher-order processes.

Parallel Execution Statement

In process calculi, an operator defining parallel execution is normally provided. In CSP:

P |[{a}]| Q

P ||| Q

In π-Calculus:

P | Q

Few languages directly support a parallel execution statement. occam is one such example:

PAR
    P()
    Q()
    R()

Indexed Parallel Execution Statement

CSP supports a parallel execution statement:

Q = || i : {0..10} @ [A(x)] P(x)

Where A is the alphabet of the replicated process P. CSP works on alphabetised replication, so a set of any type can be used.

Typically, such a statement is provided in a language as a parallel for or equivalent.

State Ownership

Does the language ensure no data is shared between processes? This is key concept in concurrency safety. Generally, languages supporting reference passing and pointers do not promote state ownership.

Process Ownership

When a process is created it exists and is owned within the creating context. This can be tested by spawning a child process and checking if the owning process waits for child processes to complete when it ends. In process calculi this is implicit the parallel operator must be completed before a process can continue to the next operation.

Selection on Incoming Messages

A key feature of process calculi is the ability to emit behaviour based on a choice. Process calculi may provide different mechanisms for choice. For example, CSP specifies both internal and external choice.

An example of choice in CSP is:

channel a, b, c

P = (a -> P) [] (b -> SKIP)
Q = a -> SKIP
R = b -> SKIP

When run in parallel, P may communicate on a first or b first. Depending on that choice the system can deadlock.

In the properties selection between incoming and outgoing messages has been seperated. This is because many languages will support input selection, but few support output selection. This property is met by being able to select from a range of incoming message sources. To do so will normally require first-order channels.

Indexed Selection

The ability to select from an array or similar range of incoming message sources via an index. In CSP this is called a replicated choice (either internal or external). For example:

channel a, b, c

P = a -> SKIP
Q = b -> SKIP
R = c -> SKIP
S = [] x : {a, b, c} @ x -> S

S will select either a, b, or c and complete the communication with the relevant process. It will do so three times until it deadlocks.

This feature appears to be uncommon in languages. It could be seen as an equivalant to a select for statement. occam provides an ALT FOR statement for this purpose.

Selection Based on Incoming Value

The ability to select an incoming message based on the value of the message. In process calculi this is quite common:

channel a : Bool

P = (a.true -> P) [] (a.false -> SKIP)

In languages this is less common as it normally requires a read to be commited before the value is checked. Actor-style concurrency does provide a partial implementation based on the message type.

Guarded Selection

The ability to activate a selection choice based on a boolean condition. In CSP:

channel a, b

P(x) = (x < 5 & a -> P(x + 1)) [] (x >= 5 & b -> SKIP)
Q = b -> SKIP

SYSTEM = P(0) [{a, b} || {b}] Q

While x is less than 5, P will increment x. Once x equals 5, P and Q will sync and terminate.

Some languages appear to support this feature, and it there is no consistent pattern seen yet across language types.

Fair Selection

Whether the selection can be considered fair as far as possible. Fair means that the probability of being selected is the same as other events in a selection operation over time. This can be achieved through random selection of ready guards, or deprioritising previously selected guards.

Fair selection is not a process calculi property. As long as a choice is made when possible that is enough. The probability of selection does not feature in the model. However, in practice languages attempt to support fair selection to allow easier reasoning.

Selection with Timer

Whether some form of timing can be used during a selection. Process calculi incorporating time do exist (e.g. Timed CSP). Because of this, and the prevalant use of timers in selection, timed selection has been added as a property to test for.

Other Selection Types

This criteria could include anything, but typically we want a default option that allows continuation if nothing is ready to select. In CSP, this can be modelled with SKIP:

channel a, b

P = (a -> P) [] (b -> SKIP) [] SKIP

Effectively we want to have a non-blocking selection option, which is a quite common design pattern.

Selection of Outgoing Messages

As input selection, but the ability to select based on output messages. At present, only Go seems to support this feature. In process calculi there is no differentiation between input and output selction.

Multi-party Synchronisation

The ability for more than two processes to syncrhonise at once. Typically supported by a barrier, but any object that allows a group of processes to agree to synchronise. In CSP all parties must agree to synchronise on an event for it to become ready:

channel a, b, c, d

P = a -> d -> P
Q = d -> b -> Q
R = c -> d -> R

P, Q, and R must agree to communicate on d if they are suitably composed in parallel.

Selection on Multi-party Synchronisation

The ability to select on a multi-party synchronisation point. CSP does not differentiate between event types, so a multi-party synchronisation point can be in a choice operation. This has yet to be found in a programming language, although libraries such as JCSP do support it.

Benchmarks

At present, three benchmarks have been used.

Communication Time

This benchmark measures the communication / coordination time of a message. Four processes are involved:

  • Prefix outputs 0, then outputs what it inputs.
  • Delta outputs its input on two channels sequentially.
  • Successor increments its input before output.
  • Consumer times how long it takes to receive N inputs.

The processes are connected together to produce the natural numbers. A rough CSP equivalent is:

channel a, b, c, d : Int

ID = c?x -> a!x -> ID

PREFIX(n) = a!n -> ID

DELTA = a?x -> b!x -> d!x -> DELTA

SUCC = b?x -> c!(x + 1) -> SUCC

CONSUMER = d?x -> CONSUMER

COMMSTIME = (((PREFIX(0) [{a,c} || {a,b,d}] DELTA) [{a,b,c,d} || {b,c}] SUCC) [{a,b,c,d} || {d}] CONSUMER)

The Communicaton Time benchmark (also referred to as commstime) was originally developed in occam by Peter Welch at the University of Kent.

Select Time

This benchmark measures how long it takes to select a message from a N inputs. A single reading process services multiple inputs from N writers. The reader times how long it takes to perform a single selection for different sizes of N.

Some languages (typically actor-based ones with mailbox systems) do not fair well when N is greater than the number of threads as the reader cannot service the writers fast enough and the mailbox expands.

Monte Carlo π

A simple data-parallel benchmark designed to test if the language has multi-core support. Speed-up measures are derived based on 2, 4, and 8 processes being run. It is not the time taken to perform the benchmark but the speedup that is important.

About

A repository of code listings for Communicating Process Architecture language and library test programs.

Resources

Readme

License

MIT license
Activity

Stars

2 stars

Watchers

3 watching

Forks

1 fork
Report repository

Releases

No releases published

Packages

No packages published

Languages