Parallel Algol

(Idealised) Parallel Algol (IPA) refers to a family of programming languages which resemble the behaviour of Algol-like languages coupled with of concurrent programming primitive. This can be either fine-grained (e.g. using semaphores to control access to shared variables) or coarse-grained (e.g. using await constructs, monitors, etc.).

The first version of Parallel Algol (along with a game semantics) is reported in Ghica and Murawski 2008 to have been formulated by Samson Abramsky at a lecture given at the Newton institute in 1995. However, no public record of that lecture seems available.

The first published formulation is due to Stephen Brookes, and first appeared at LICS 1996. The conference paper was included in the two-volume book on Algol-like languages. An expanded journal version appeared in Brookes 2002. This version of IPA comes with a coarse-grained await construct. A denotational semantics in terms of possible worlds, traces, and functor categories is provided.

Another version of IPA is presented by Ghica and Murawski 2008. Instead of the coarse-grained await construct of Brookes, it uses first-class semaphores to control access to shared variables. It also comes with a operational semantics, as well as a game semantics which is fully abstract for may-equivalence.

References

The first version of IPA appeared at LICS 1996:

Brookes, S. 1996. ‘The Essence of Parallel Algol’. In Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, 164–73. New Brunswick, NJ, USA: IEEE Comput. Soc. Press. https://doi.org/10.1109/LICS.1996.561315. slides

The journal version of that paper is

Brookes, Stephen. 2002. ‘The Essence of Parallel Algol’. Information and Computation 179 (1): 118–49. https://doi.org/10.1006/inco.2002.2995.

@article{brookes_essence_2002,
	title = {The {Essence} of {Parallel} {Algol}},
	volume = {179},
	issn = {08905401},
	doi = {10.1006/inco.2002.2995},
	number = {1},
	journal = {Information and Computation},
	author = {Brookes, Stephen},
	year = {2002},
	pages = {118--149}
}

An operational semantics for a variant of IPA with semaphores appeared at FoSSaCS 2004, and then in Information and Computation:

Ghica, Dan R., and Andrzej S. Murawski. 2008. ‘Angelic Semantics of Fine-Grained Concurrency’. Annals of Pure and Applied Logic 151 (2–3): 89–114. https://doi.org/10.1016/j.apal.2007.10.005. pdf

@article{ghica_angelic_2008,
	title = {Angelic semantics of fine-grained concurrency},
	volume = {151},
	doi = {10.1016/j.apal.2007.10.005},
	number = {2-3},
	journal = {Annals of Pure and Applied Logic},
	author = {Ghica, Dan R. and Murawski, Andrzej S.},
	year = {2008},
	pages = {89--114}
}