Historical comments related to the topics of SEG-2106

Here is a list of notes on famous computer scientists, historical developments, standardization, applications etc. classified according to the chapters of the SEG-2106 course.

Section 1: Requirement engineering, structural and behavioral modeling using state machines

• State machine modeling

• Structured programming and the GOTO (by Dijkstra) - famous paper: GOTO statement considered harmful (ACM Comm. March 1968) - more explanations by W. Wulf: A case against the GOTO (ACM Annual COnf. 1972) - NOTE: Dijkstra is also known for the shortest path routing algorithm (nowadays used in the Internet)
• Program testing or proving ? - (Hoare - Floyd, Dijkstra)
• Knuth - The Art of Computer Programming
• Parnas - information hiding principle - the reliability issue
• Model-based development (version française)
• State machine modeling and object-orientation
• Standardization committees: Official international bodies: ISO, ITU; national standardization bodies: CSA (Canadian Standards Association), DIN (Deutsche Industrie Norm), ANSI (USA, American National Standards Institute); industry groups: IETF, OMG
• Bran Selic - from Nortel to ObjecTime to Rational to IBM to consultant

• Communicating state machines
  • Message passing or rendezvous communication
  • Self-stabilization (by Dijkstra)
  • Early work on protocol verification: Bochmann (verification by hand), West (tool), Gouda (automating the design

Section 2: Languages, grammars, and analyzers

6. Introduction to languages and compilers
• The development of "good" programming languages (Algol, Pascal, Simula, concurrency, Euler, functional languages)
• Who has created the programming languages that are used in practice ?
• P-code and Wirth's Pascal compiler (with boot-strapping)
7. Lexical analysis: formal languages, regular expressions, finite state machines, deterministic and non-deterministic finite automata, transformation from regular expression to DFA, tools for lexical analysis (Lex)
• Kleene
8. Syntax analysis: parse trees, ambiguity, context-free grammars, LL(1) parsing method, semantic analysis and semantic attributes (this section may or may not be covered), different notations for specifying languages, Chomsky’s hierarchy
• Naur, Algol and BNF
• Attribute grammars (Knuth, Bochmann, compiler writing systems)
• Turing machines and decidability

Section 3: Concurrency: specification, verification, and implementation

9. Concurrency: concept of concurrency, sub-program level concurrency, semaphores, monitors, message passing, Java threads
• The invention of semaphores (by Dijkstra)
• The invention of the monitor concept (by Hoare and Brinch-Hansen) - high-level language for writing operating systems
• History of concurrency in programming languages
• History of dynamic process creation and communication in programming languages and operating systems
10. Implementation design