Program semantics and verification 1000-215bSWP
1. Formal description of programming languages
2. Operational and denotational methods of program semantics definition
3. Semantic definitions of basic programming constructs
4. Mathematical underpinnings of denotational semantics
5. Basic notions of program correctness: partial and total correctness
6. Proof methods for program correctness
7. Hoare's logic, its application and formal properties
8. Basic notions of universal algebra and their role in programming language descriptions
Prerequisities:
- Introductory programming (1000-211bWPI and/or 1000bWPF)
- Foundations of mathematics (1000-211bPM)
- Languages, automata and computations (1000-214bJAO)
Course coordinators
Type of course
Mode
Requirements
Learning outcomes
Knowledge. Students know and understand:
- the concepts of syntax and semantics of programming languages, methods of defining them, and definitions of simple programming constructs (K_W02, K_W03, K_W13);
- mathematical foundations of defining semantics of programming languages (K_W13);
- the notion of program correctness with respect to a formal specification (K_W02, K_W04, K_W13);
- formal methods of proving partial and total correctness of simple programs (K_W04, K_W10, K_W13).
Skills. Students are able to:
- define semantics of simple programming constructs and understand the working of programming constructs from their semantic descriptions (K_U01, K_U03);
- apply formal verification methods to prove correctness of simple programs (K_U03,K_U07);
- justify the correctness of programs referring to their semantics (K_U03).
Competence. Students are ready to:
- know the limits of their knowledge and understand the need of further education (K_K01)
- understand and appreciate the importance of precision and rigour in formulating problems and justifying the correctness of their solutions (K_K03).
Assessment criteria
Final grade based on a written exam and homework exercises given during the semester.
Bibliography
1. M. Hennessy. The Semantics of Programming Languages. Wiley, 1990.
2. M. Fernandez. Programming Languages and Operational Semantics: An Introduction. College Publications, 2004.
3. H. Riis Nielson, F. Nielson. Semantics with Applications: An Appetizer. Springer, 2007.
4. M. Gordon. The Denotational Description of Programming Languages. Springer-Verlag, 1979.
5. D. Gries. The Science of Programming. Springer-Verlag, 1981.
6. E. Dijkstra. A Discipline of Programming. Prentice-Hall 1976.