Hörerkreis: Studenten/-innen der Informatik und Mathematik

Voraussetzungen: Vordiplom

Note: The lectures are taught in English.

Empfehlenswert für:
Für eine spätere theoretische Beschäftigung mit Programmiersprachen ist diese Vorlesung unabdingbar. Es bestehen ausserdem starke Querbezüge zu den Gebieten Logik, Programmverifikation und Lambda-Kalkül.

Lernziele:

• Das Verstehen der grundlegenden mathematischen Techniken, um die Semantik einer Programmiersprache präzise zu definieren.
• Das Anwenden dieser Techniken auf Probleme wie Äquivalenz verschiedener Sprachbeschreibungen, Korrektheit von Übersetzern, Programmkorrektheit, Sicherheit von Typsystemen, Korrektheit von Programmtransformationen etc.

Inhalt:
Eine einfache imperative Programmiersprache WHILE wird aus verschiedenen Blickwinkeln beschrieben und analysiert:

1. Introduction
   The syntax of WHILE. Concrete vs abstract syntax. Evaluation of arithmetic and boolean expressions.(Isabelle [pdf] [ps.gz])
2. Operational Semantics
   1. Big-step semantics
      The rules. Derivation trees. Lemma while b do s is equivalent to if b do s;while b do s else skip.(Isabelle [pdf] [ps.gz])
   2. Rule induction
      Inductively defined sets and the principle of rule induction. Examples: natural numbers and transitive reflexive closure, together with proofs of various closure properties. Rule induction for big-step semantics of WHILE. Theorem: WHILE is deterministic (Isabelle [pdf] [ps.gz])
   3. Small-step semantics
      The rules [pdf] [ps.gz]. Derivation sequences. Theorem: Agreement of big-step and small-step semantics.(Isabelle [pdf] [ps.gz])
   4. Extensions of WHILE
      
      1. Nondeterminism. Big-step semantics hides nontermination. Small-step semantics more appropriate.
      2. Parallelism. Big-step semantics not possible. Interleaving small-step semantics.
      3. Local variables.
      4. Procedures. Static and dynamic scope for variables and procedures. Big-step semantics for a) dynamic scope for variables and procedures, b) dynamic scope for variables and static scope for procedures, c) static scope of variable and procedures.
   5. Application: a compiler for WHILE
      A 3-instruction machine. Its operational single-step semantics. The compiler. Detailed proof of the equivalence of running the source program and running the compiled program.(Isabelle [pdf] [ps.gz])
3. Type Systems
   Static vs dynamic typing.
   1. Types for WHILE.
      Merging the syntax of arithmetic and boolean expression. Types bool and int. Variable declarations.
   2. A monomorphic type system
      
      1. The type system
         Typing rules for expressions and statements. The need for semantics to talk about correctness of the type system.
      2. The semantics
         The need to separate booleans and integers. Semantics of expressions and statements. Theorem: Typed WHILE is type safe, i.e. type correct statements transform type correct states into type correct states.
   3. A polymorphic type system.
      
      1. Type checking
         Type variables. Typing rules and semantics unchanged! A rephrased type safety theorem based on substitutions for type variables: type correct statements guarantee type safe execution starting from any state that is type correct w.r.t. an instance of the polymorphic variable declarations.
      2. Type inference
         How to reconstruct the missing type declarations using type checking and unification, i.e. Prolog.
   A classification of various programming language according to static/dynamic and monomorphic/polymorphic.
4. Denotational Semantics
   1. Inductive definitions and rule induction
      A set theoretic treatment of rules. Definition: The set I_R defined by a set of rules R is the least R-closed set.
      1. The derivation of rule induction.
      2. Theorem: I_R is the least fixpoint of the consequence operator induced by R. If R is finitary, I_R is the union of all finite iterations of R starting from the empty set.
   2. A denotational semantics based on sets
      The semantics of while-loops as a least fixpoint of a function which can be expressed by inference rules. Equivalence proof of denotational and operational semantics.
   3. Complete partial orders
      Definition of complete partial orders (cpos) and continuity. The Fixpoint Theorem. Discrete cpos, product cpos, function cpos, lifting.
   4. A cpo-based denotational semantics for While.
   5. Extensions of WHILE
      1. Local variables and procedures. Static scoping only.
      2. Exceptions and continuations.
      3. The Knaster-Tarski fixpoint theorem.
         Every monotone function on a complete lattice has a least fixpoint.
      4. Nondeterminism. Relational semantics already defined but too weak because it does not distinguish possible and guaranteed termination. Definition of the set of start states that guarantee termination using the Knaster-Tarski fixpoint theorem to obtain the least fixpoint of a monotone function (in the case of loops).
5. Axiomatic Semantics (Hoare Logic)
   1. From Floyd to Hoare. Partial and total correctness. The rules of Hoare logic.
   2. Syntax of assertions: first-order arithmetic.
   3. Semantics of assertions and Hoare triples: validity w.r.t. a state and an interpretation of the logical variables.
   4. Soundness of Hoare logic: proof by rule induction.
   5. Completeness of Hoare logic: impossible for effective proof systems. Relative completeness: use semantics (|=) rather than proof system (|-) of the assertion language. Prove relative completeness via weakest liberal precondition and expressiveness, i.e. the ability to express the wlp in the assertion language.
   6. Verification conditions. Extraction of (weakest) preconditions and verification conditions in the presence of loop invariants. Proof of soundness and completeness of this approach.
   7. Total correctness. Completeness requires "expressive" language of arithmetic (beyond polynomials).
   8. Extensions of WHILE
      1. Nondeterminism
      2. Arrays
      3. Procedures: The problem. An adaption rule. A complete system based on a generalized consequence rule. (Soundness only sketched, completeness not proved.)
   9. Time complexity
      1. Exact execution times.
      2. Timed Hoare triples and their validity.
      3. Proof rules for timed Hoare triples.

Übungsschein:
Einen Schein erhält, wer mindestens 40% der Punkte aus den Hausaufgaben und Programmieraufgaben erreicht und erfolgreich an der Semestralprüfung teilnimmt.

Literatur:
Die Vorlesung orientiert sich stark an folgenden beiden Büchern

• Hanne Riis Nielson, Flemming Nielson: Semantics with Applications: A Formal Introduction.
• Glynn Winskel: The Formal Semantics of Programming Languages. MIT Press.

Gerwin Klein

Last modified: Wed Feb 13 15:34:04 CET 2002