TDA383/DIT390

General Background

Wikipedia and links from there.

Turing Awards

Computer Science has no Nobel prize. The nearest we have is the Turing award. I've asked generations of Chalmers/GU students in computer science what this award is, who has won it, and for what. They typically have no idea. I think this reflects a failing on the part of the department, so here is a first attempt to fix our lack of historical awareness.

http://en.wikipedia.org/wiki/Turing_Award

Below is a list of researchers who won the Turing award mostly for work in concurrency, though many of the other winners too did related work.

You can read their acceptance speeches (the Turing lectures), and all the others, at

http://amturing.acm.org/lectures.cfm

The others you should read are, at least,

Clarke, Emerson and Sifakis (2007).
Wirth (1984).
Floyd (1978).

You will no doubt be tempted by the titles of several of the others. Give in! In fact, glancing through the whole lot (they are all informal and easy to read) will introduce you to several other related issues, whether to do with computers or programming languages, and is an excellent way to get a broad liberal computer science education. Learn from the masters!

The talks also frequently mention other researchers who did not get the Turing award (they only give one a year). It's useful to pick up names.

Classic Papers

Many of the papers below are still under copyright, so we cannot give a direct link. Instead, you will have to get them from the Chalmers library. Search with the paper title, except if otherwise indicated.

Robin Milner.

If I had to pick one person whose collected works give you a liberal education in computer science, it would be Robin Milner. The wikipedia page

http://en.wikipedia.org/wiki/Robin_Milner

gives a starting point, as do

http://en.wikipedia.org/wiki/Calculus_of_communicating_systems

and

http://en.wikipedia.org/wiki/Π-calculus

Items 1 and 2 below deal with papers by others describing Milner's work.

A Brief Scientific Biography of Robin Milner
by Gordon Plotkin, Colin Stirling & Mads Tofte,
available at

http://homepages.inf.ed.ac.uk/gdp/publications/Robin_sci_biog.pdf

runs to 16 pages, followed by a 7 page bibliography. And Milner wrote strikingly little, though almost everything he wrote started a huge amount of research activity.
There were any number of tributes paid to Milner in the months and years after he passed away in 2010, but the three below suffice to give a glimpse of the range of his work.
- Robin Milner, a Craftsman of Tools for the Mind
  by Plotkin, G.D.
  Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on
  DOI: 10.1109/LICS.2010.31
  Publication Year: 2010 , Page(s): 58 - 59
  
  A brief obituary by one of Milner's most eminent colleagues. Plotkin and Milner were together at Edinburgh for over two decades.
- Robin Milner's Work on Concurrency
  by Abramsky, Samson
  Electronic Notes in Theoretical Computer Science, 2010, Volume 265
  Another obituary, by another eminent computer scientist, focusing on Milner's work on concurrency.
- Robin Milner 1934--2010: verification, languages, and concurrency
  by Gordon, Andrew; Harper, Robert; Harrison, John; et al
  Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, 01/2011
From LCF to HOL: A Short History
by Mike Gordon,
in
Plotkin, G. ; Stirling, C. ; Tofte, M.
Proof, Language, and Interaction:Essays in Honour of Robin Milner
Page(s): 169 - 185
Copyright Year: 2000
MIT PRESS EBOOK CHAPTERS
Available from http://www.cl.cam.ac.uk/~mjcg/papers/HolHistory.pdf
Mike Gordon co-authored with Milner a book on LCF.

Elements of interaction: Turing award lecture
by Milner, Robin
Communications of the ACM, 01/1993

The page http://amturing.acm.org/award_winners/milner_1569367.cfm gives the citation and a brief bio.

The citation reads

"For three distinct and complete achievements:

LCF, the mechanization of Scott's Logic of Computable Functions, probably the first theoretically based yet practical tool for machine assisted proof construction;
ML, the first language to include polymorphic type inference together with a type-safe exception-handling mechanism;
CCS, a general theory of concurrency.

In addition, he formulated and strongly advanced full abstraction, the study of the relationship between operational and denotational semantics."

Functions as processes
by Milner, Robin
Mathematical structures in computer science
ISSN: 0960-1295 EISSN: 1469-8072
YEAR: 1992 VOL: 2 ISSUE: 2 PAGE: 119-
DOI: 10.1017/S0960129500001407
Available also from https://hal.inria.fr/inria-00075405/en/
Shows that communication is the only primitive needed to set up computation!

A Calculus of Communicating Systems
by Robin Milner
Lecture Notes in Computer Science
Volume 92 1980

The original typewritten book, available online from the Chalmers library. This material was developed into the book

Communication and Concurrency
by Robin Milner
Prentice Hall International Series in Computer Science, Paperback – September 6, 1995
Available to borrow from the Chalmers library.

If you follow up the links and bibliographies in the above papers and web pages, you should be able to find most of Milner's works. Most of his work post 1990 is relevant to concurrency, and some of it is very informal and easy to read, but we have restricted ourselves to a few works most appropriate to the level of our course. Please let us know of any others that you think should be included here.

Tony Hoare.

C. A. R. Hoare is together with Milner probably the researcher who has been in the field longest and had a comparable impact.

http://en.wikipedia.org/wiki/Tony_Hoare http://en.wikipedia.org/wiki/Hoare_logic

and

http://en.wikipedia.org/wiki/Communicating_sequential_processes

will lead you to many more links. A few of Hoare's most important works:

Monitors: an operating system structuring concept by Tony Hoare

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/401/CS-TR-73-401.pdf

You can read the CACM 1974 typeset paper via the library.
Communicating Sequential Processes by Tony Hoare Communications of the ACM 1978

Can be read via the library, or at http://www.cs.ucf.edu/courses/cop4020/sum2009/CSP-hoare.pdf
Communicating Sequential Processes (book by Tony Hoare)

is available online at http://www.usingcsp.com/cspbook.pdf
Algorithm 64: Quicksort

Comm. ACM 4 (7): 321. (1961)
doi:10.1145/366622.366644

It is almost unbelievable what an early work this algorithm was, and how fortunate we are that the inventor is still with us!
An axiomatic basis for computer programming by Hoare, C. A. R.

Communications of the ACM 12 (10): 576–580. (October 1969).
doi:10.1145/363235.363259.

What we now call axiomatic semantics (pre- and post-conditions, or a version of contracts), as opposed to operational or denotational semantics.

Edsger Dijkstra

A towering figure, particularly in the early days of concurrent programming, and very insistent on properly defining concepts such as priority that tended to be used informally late into the 1970's. He is associated with the first definition of semaphores, and was also a brilliant programmer who invented the concept of guarded commands, a version of which turns up in Promela.

In addition to the usual wikipedia links

http://en.wikipedia.org/wiki/Edsger_W._Dijkstra http://en.wikipedia.org/wiki/Semaphore_(programming) http://en.wikipedia.org/wiki/Guarded_Command_Language http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dining_philosophers_problem

you can read Tony Hoare's obituary here:

http://scitation.aip.org/content/aip/magazine/physicstoday/article/56/3/10.1063/1.1570789

Cooperating sequential processes by E. W.Dijkstra

appeared in Programming Languages edited by F. Genuys, Academic Press. (1968). Available online now at http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html

Behind the old-fashioned notation lurk surprisingly modern treatments of semaphores and still standard problems.
Guarded commands, non-determinacy and formal derivation of programs

by E. W.Dijkstra Communications of the ACM 18 (1975), 8: 453–457.

Available online at http://www.cs.utexas.edu/users/EWD/ewd04xx/EWD472.PDF
Letters to the editor: go to statement considered harmful by Dijkstra, E. W.
Communications of the ACM 11 (3): 147–148. (March 1968).
doi:10.1145/362929.362947. ISSN 0001-0782.

This famous letter started the movement known as Structured Programming, also the title of a book by O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare, Academic Press, London, 1972 ISBN 0-12-200550-3 which also includes the beginning of object oriented programming.

The ideas behind the "goto" problem have been so thoroughly absorbed that even beginning students expect to only need sequencing, conditionals and loops. In 1968, most people were puzzled as to how one could program without arbitrary jumps.

Summary of links

A small selection of classic papers.

E. D. Dijkstra (1968) "Cooperating sequential processes"

http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html
Tony Hoare, "Monitors: an operating system structuring concept"

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/401/CS-TR-73-401.pdf

(you can read the CACM 1974 typeset paper via the library)
Tony Hoare's CSP book is online.

http://www.usingcsp.com/cspbook.pdf

His paper of the same name, CACM 1978, can be read via the library, or at

http://www.cs.ucf.edu/courses/cop4020/sum2009/CSP-hoare.pdf
Carriero and Gelernter's LINDA paper is available at

http://www.ics.uci.edu/~andre/informatics223s2011/caprierogelernter.pdf

For most other references from the textbook, you will have to use the library. As and when we locate other versions online, we will add links here. A major failing of Ben-Ari is that he does not link to Milner's work. Read his papers from the library. E.g., his original CCS (calculus of communicating systems) book.

Several of the references in Ben-Ari's textbook (see the Bibliography at the end) are to books, and these are typically not available online. But the papers are, through the library. Look them up! Bibliographies and lists of references, whether in your textbook or in the papers I hope you will read, are not there to be ignored. The original papers have a freshness that can never be recaptured in a re-telling. Reading the original literature is an essential part of becoming a scientist.

Miscellaneous Links

See "Det dunkelt sagda är det dunkelt tänkta" in

http://en.wikiquote.org/wiki/Swedish_proverbs
http://en.wikipedia.org/wiki/Therac-25
There are many reports about the Gaisal train accident, but most deal with politics. The timing issue and the mix-up between the various safety systems is mentioned in

http://www.financialexpress.com/old/ie/daily/19990814/ige14049.html

Here are two paragraphs from the report referring to the programming-related errors:

"Chandra thought that it is a matter of 15 minutes and the train will make it to Gaisal much before Brahmputra crosses it and then shift to the up-line. He granted paper-line clear to Awadh-Assam Express but his fatal error was that he failed to inform Gaisal about it. He should have told Gaisal station master to ensure that Awadh-Assam has reached, before giving clearance to Brahmputra Mail, an official, part of CCRS inquiry, said.

What the Kishanganj ASM did not know was that Awadh-Assam driver was waiting at the next station, Panjipara, for 12 minutes awaiting paper-line clear. The driver knew he was on the wrong line and wanted to continue only after receiving clearance from Panjipara, which was given to him, in utter complacency. So he proceeded towards Gaisal, unaware that Gaisal did not know about his arrival. The Gaisal station staff, meanwhile, did not know about the approaching Awadh-Assam and gave clearance to Brahmputra for arrival."

##Poster Exhibition

The teaching team will be glad to organize a student poster exhibition if there is interest. The idea is that you (individually or in teams of any size) prepare a brief presentation on any paper or work you choose, classic or recent, in an area at least distantly related to concurrency. You do not give a lecture to the class; instead, you prepare a few minutes' worth of slides, diagrams, animation or films (any or all of those) and stand next to a handwritten poster announcing your topic. Visitors come to you if they wish, and ask whatever they want. You answer as best you can.

Participation is entirely voluntary and carries no credit towards your grade. You do a poster presentation if you wish, and visit the exhibition if you wish. The purpose is only to give you an occasion to get (back) into the habit of finding out something and telling others about it.

We will decide when and where to hold the exhibition once we know how many students would like to take part, so please express your interest via the Google group. If you wish, we can help you pick a paper.