The Central Problem of Formal Methods: Model Validation; Program Derivation; Program Verification. Introduction to Hoare Logic. Program Annotation and Automated Static Checking. The ESC/Java2 tool.
Limitations of ESC/Java2: Examples where correctness or completeness fails.
The Caduceus tool for program verification: usage with Coq and Simplify. The Caduceus workflow.
Simple examples proved with automatic tactics. More complex examples. Case reasoning; frame conditions; modular reasoning.
Introduction to the mathematics of program construction.
Correct by verification versus correct
by construction. Description versus calculation.
Historical perspective on the PF-transform.
Point-free notation and reasoning. Rules of the
PF-transform.
PF-transform: when everything becomes a relation. Introduction to the binary relation
calculus. Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties. Galois connections.
No lecture (Lecturer away in an international advisory board meeting)
Lecture 14
Date: 28/01/08
Topics:
Constructive proofs. A PF-approach to
polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphism in one
equation. Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
First part (two hours): Assessment0708 (paper presentations).
Second part (one hour): Discussion. Open issues and hot topics in the mathematics of program
construction. Research directions in correct by construction.
Introduction to the mathematics of program construction
Date:
12/01/09 (Monday, 10h-13h) Sala 1
Topics:Overview of the scientific method applied to software design.Correct by verification versus correct by construction. Calculate versus invent & verify.The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the LerNET? doctoral school at Piriapolis, Uruguay, 2008)
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties.
Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
A PF-approach to polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphic functions in one equation.
Inductive predicates and relations. The catamorphism concept.
Universal property and its corollaries.
Mutual recursion. Calculation of for/while loops from systems of mutually recursive equations over linear types.
Notes:
Theorems for free: a (calculational) introduction (slides)
Relational algebra: a Kleene algebra central to the mathematics of program construction (slides)
Introduction to the mathematics of program construction
Date:
12/01/09 (Monday, 10h-13h) Sala 1
Topics:Overview of the scientific method applied to software design.Correct by verification versus correct by construction. Calculate versus invent & verify.The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the LerNET? doctoral school at Piriapolis, Uruguay, 2008)
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties.
Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
A PF-approach to polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphic functions in one equation.
Inductive predicates and relations. The catamorphism concept.
Universal property and its corollaries.
Mutual recursion. Calculation of for/while loops from systems of mutually recursive equations over linear types.
Notes:
Theorems for free: a (calculational) introduction (slides)
Relational algebra: a Kleene algebra central to the mathematics of program construction (slides)
Introduction to the mathematics of program construction
Date: 27/09/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Overview of the scientific method applied to software design. Correct by verification versus correct by construction. Calculate versus invent & verify. The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the Ler-NET doctoral school at Piriapolis, Uruguay, 2008)
04/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary relations. Union and meet. Universal
constructions and properties. Galois connections underpinning relation algebra.
Extended static checking(ESC) in the PF-style.
PF-transform: extended static checking by calculation
Date:
11/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Verification conditions in the PF-style. Arrow notation. Relation to Hoare triples and Hoare logic. Handling nondeterminism. Calculus of proof obligations (proof rules). Case study: verifying a model of a journaled file system. Manual proofs in conjunction with model checking in Alloy. Open issues and research topics.
Notes:
Hands on a Grand Challenge in Computing: Proving a Journaled File System Correct (PDF)
Lecture 4
Module assessment: paper recitation
Date:
18/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics: Provisional schedule as follows:
10h00 - Carlos Eduardo Bastos e Marques da Silva: Variations on a Alloy-Centric Tool-chain in Verifying a Journaled File System Model
10h18 - Constantin Taivan: Reverse Program Calculation Supported by Code Slicing
10h36 - Frederico Miguel Goulão Valente: Generic Pointfree Lenses
10h54 - Henrique Manuel Fernandes de Castro: A Relational Model for Confined Separation Logic
11h12 Coffee break
11h30 - Nuno Filipe Moreira Macedo: First steps in Pointfree Functional Dependency Theory
11h48 - Nuno Miguel Almeida Luz: Strategic Term Rewriting and its Application to a VDM to SQL Convertion
12h06 - Paulo José Correia Bernardes: On the design of a Periodic Table of VDM specifications
12h24 - Eduardo Augusto Peixoto da Silva Brito: Tupling Calculation Eliminates Multiple Data Traversals
12h42 - Pedro Miguel Ribeiro Martins: Proving correctness using Free Theorems
13h00 Closing
Material:
Zip file containing all papers and presentations (11MB)
Lecture 5
A revision of propositional and first-order logics
Date:
25/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: Luís Pinto
Topics:
Propositional Logic (PL): Syntax; Semantics; Proof system; Adequacy of the proof system
First-Order Logic (FOL): Syntax; Semantics; Proof system; Theory for equality
Intuitionistic Logic: Natural deduction systems (propositional and first-order)
Notes:
A revision of propositional and first-order logics (PDF)
Lecture 6
Validity Checking in Propositional and Forst-Order Logic
Date:
08/11/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: José Bacelar Almeida
Topics:
Propositional Logic: general remarks; normal forms (NNF, CNF, DNF); validity/satisfiability in CNFs.
First-Order Logic: general remarks; normal forms (NNF, prenex, Herbrand/Skolem); Herbrand's theorem; semi-decidability; decidable fragments.
First-Order Theories: basic concepts; some theories of interest; SMT provers.
Notes:
Validity Checking in Propositional and First-Order Logic (PDF)
Bibliography:
Any standard textbook on Mathematical Logic addresses most of the topics mentioned in the Lecture (e.g. [11] from the list of recommended books).
A nice survey on the subject is
Henk Barendregt. Lambda calculi with types. In S. Abramsky, D. Gabbay, and T. Maibaum, editors, Handbook of Logic in Computer Science, volume 2, pages 117–309. Oxford Science Publications, 1992.
Henk Barendregt and Herman Geuvers. Proof-assistants using dependent type systems. In John Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning, pages 1149–1238. Elsevier and MIT Press, 2001.
Gilles Barthe and Thierry Coquand. An introduction to dependent type theory. In Gilles Barthe, Peter Dybjer, Luís Pinto, and João Saraiva, editors, APPSEM, volume 2395 of Lecture Notes in Computer Science, pages 1–41. Springer, 2000.
Lecture 9
A Practical Approach to the Coq Proof-Assistant
Date:
29/11/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: José Bacelar Almeida
Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development. Coq’Art: The Calculus of Inductive Constructions, volume XXV of Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag, 2004.
Loc Correnson, Pascal Cuoq, Armand Puccetti, and Julien Signoles. Frama-C user manual. from the Frama-C website, http://frama-c.com, 2010.
Patrick Baudin, Jean-Christophe Fillitre, Claude March, Benjamin Monate, Yannick Moy, and Virgile Prevosto. ACSL: ANSI/ISO C Specification Language. Preliminary Design (version 1.4). from the Frama-C website, http://frama-c.com, 2010.
Yannick Moy and Claude March´e. Jessie Plugin Tutorial. LRI, February 2010. Beryllium Version.
Each student must complete and write the solutions of this assignment alone. The deadline is : *20/02/2008
*The answers must be send by e-mail to the following emails: \{nam,amf,sbb,luis\} at ncc.up.pt.
Part II
Students are expected to work in groups of two; each group will be assessed based on the following three components.
Should be sent by e-mail to this address. The deadline is the date of the presentations session.
Caduceus Mini-project
A list of examples of programs verified with Caduceus can be found here.
Select a program with a similar level of difficulty (not listed in the examples). Write an adequate specification and verify the program using Caduceus and the Coq proof assistant.
Groups should write a short report on their work (with proof scripts attached) and prepare a short talk (5 minutes) to be given in the final presentations session (see date below).
Paper Reading
Each group should select one paper from the following list. Please send a mail to this address with your choice. Papers will be allocated on a first come, first served basis. Groups will give a talk (20 minutes) on the paper in the presentations session (see date below).
Efficient Weakest Preconditions. K. Rustan M. Leino. link
Boogie: A Modular Reusable Verifier for Object-Oriented Programs. Mike Barnett, Bor-Yuh Evan Chang, Robert deLine, Bart Jacobs, and K. Rustan M. Leino. link
Foundational Proof-Carrying Code. Andrew W. Appel. link
Proof Obligations Preserving Compilation (Extended abstract). Gilles Barthe, Tamara Rezk and Ando Saabas. link
Beyond Assertions: Advanced Specification and Verification with JML and ESC / Java2. Patrice Chalin, Joseph Kiniry, Gary T. Leavens and Erki Poll. link
A Certifying Compiler for Java. Christopher Colby, Peter Lee, George C. Necula, Fred Blau, Mark Plesko, Kenneth Cline. link
A Tutorial on Recursive Types in Coq. Eduardo Gimenez and Pierre Casteran. link
Universes: Lightweight Ownership for JML. Werner Dietl and Peter Mueller. link
Dates
Deadline for delivery of Caduceus mini-project report: February 4
Presentations session and deadline for delivery of Coq Exercises: February 11
Part III
Reading and presenting a paper in the field (one paper per student)
Formulae-as-types as a notion of control
Groups:
1. Bruno Oliveira and Vitor Rodrigues: Theme 5
2. Alexandre Madeira and Miguel Ferreira: Theme 1
3. Hugo Pacheco and Miguel Marques: Theme 2
4. Luis Santos and Ricardo Freitas: Theme 6
5. Hugo Conceição: Theme 3
6. José Pedro Oliveira: Theme 4
Part II
Coq mini-projects:
Binary Integers
The aim of this mini-project is to enconde binary integers as lists of booleans. That is:
Require Import ZArith.
Require Import List.
Require Import Bool.
Open Scope Z_scope.
Definition BInt := list bool.
Fixpoint toZ (x : BInt) : Z :=
match x with
| nil => 0
| true :: xs => 1 + 2*(toZ xs)
| false :: xs => 2*(toZ xs)
end.
(observe that the head of the list is the least significant bit)
- Define the following functions:
bSucc - computes the successor of a binary integer
bAdd - computes the addition of two binary integers
bMult - computes multiplication of two binary integers
- Prove the correctness of those functions (e.g. forall x, toZ (bSucc x)=1+(toZ x))
NOTE: in the definition of bAdd, it is convenient to simultaneously define a function bAddCarry (performs addition with carry). Use the "Fixpoint ... with ..." to accomplish these simultaneous definitions.
Declarative Arrays
A possible encoding of arrays in Coq is through axiomatization of the corresponding theory. E.g. (taken from the Why tool)
(* The type of arrays *)
Parameter raw_array : Set -> Set.
Definition array (T:Set) := prod Z (raw_array T).
(* Array length *)
Definition array_length (T:Set) (t:array T) : Z := let (n, _) := t in n.
(* Functions to create, access and modify arrays *)
Parameter raw_new : forall T:Set, T -> raw_array T.
Definition new (T:Set) (n:Z) (a:T) : array T := (n, raw_new a).
Parameter raw_access : forall T:Set, raw_array T -> Z -> T.
Definition access (T:Set) (t:array T) (i:Z) : T :=
let (_, r) := t in raw_access r i.
Parameter
raw_update : forall T:Set, raw_array T -> Z -> T -> raw_array T.
Definition update (T:Set) (t:array T) (i:Z) (v:T) : array T :=
(array_length t, let (_, r) := t in raw_update r i v).
(* Update does not change length *)
Lemma array_length_update :
forall (T:Set) (t:array T) (i:Z) (v:T),
array_length (update t i v) = array_length t.
Proof.
trivial.
Qed.
(* Axioms *)
Axiom
new_def :
forall (T:Set) (n:Z) (v0:T) (i:Z),
(0 <= i < n)%Z -> access (new n v0) i = v0.
Axiom
update_def_1 :
forall (T:Set) (t:array T) (v:T) (i:Z),
(0 <= i < array_length t)%Z -> access (update t i v) i = v.
Axiom
update_def_2 :
forall (T:Set) (t:array T) (v:T) (i j:Z),
(0 <= i < array_length t)%Z ->
(0 <= j < array_length t)%Z ->
i <> j -> access (update t i v) j = access t j.
- Define a function sumArray to compute the sum of elements in an array.
- Formulate and prove the correctness of the previously defined function.
Paper Reading
A Tutorial on Recursive Types in Coq. Eduardo Gimenez and Pierre Casteran. link
Efficient Weakest Preconditions. K. Rustan M. Leino. link
Boogie: A Modular Reusable Verifier for Object-Oriented Programs. Mike Barnett, Bor-Yuh Evan Chang, Robert deLine, Bart Jacobs, and K. Rustan M. Leino. link
A Certifying Compiler for Java. Christopher Colby, Peter Lee, George C. Necula, Fred Blau, Mark Plesko, Kenneth Cline. link
Foundational Proof-Carrying Code. Andrew W. Appel. link
Proof Obligations Preserving Compilation (Extended abstract). Gilles Barthe, Tamara Rezk and Ando Saabas. link
Universes: Lightweight Ownership for JML. Werner Dietl and Peter Mueller. link
Beyond Assertions: Advanced Specification and Verification with JML and ESC / Java2. Patrice Chalin, Joseph Kiniry, Gary T. Leavens and Erki Poll. link
Part III
Workshop "Program Semantics, Verification, and Construction" 16/02/2008
10h-11h45
Part 1:
1. Alexandre Madeira, Miguel Ferreira. "Combinatory logic"
2. Hugo Pacheco. "Expressibility: the simply typed lambda-calculus (vs. the pure
system), system T"
3. Bruno Oliveira, Vitor Rodrigues. "Type systems I"
4. Luis Santos, Ricardo Freitas. "Type system II"
Part 2: 12h-13h45
1. Bruno Oliveira. "Efficient Weakest Preconditions"
2. Vitor Rodrigues, Ricado Freitas. "Beyond assertions: Advanced
specification and verification with JML and ESC/Java2"
3. Alexandre Madeira. "Pointfree Factorization of Operation Refinement"
4. Hugo Pacheco. "Tupling calculation eliminates multiple data traversal"
Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford University Press, Oxford, UK, 1994.
Roland C. Backhouse. Program construction and verification. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1986.
Henk P. Barendregt. The Lambda Calculus: Its Syntax and Semantics, volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, second, revised edition, 1984.
Henk P. Barendregt. Lambda calculi with types. In S. Abramsky, D. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 2, chapter 2, pages 117?309. Oxford University Press, 1992.
Yves Bertot and Pierre Casteran. Interactive Theorem Proving and Program Development. Springer Verlag, 2004.
Richard Bird and Oege de Moor. Algebra of Programming. Prentice Hall, 1997.
Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and Types, volume 7 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989. (online version)
M. Hennessy. The Semantics of Programming Languages. Wiley, 1990.
H. R. Nielson and F. Nielson. Semantics with Applications : A Formal Introduction. Wiley, 1992. (online version)
Glynn Winskel. The Formal Semantics of Programming Languages: An introduction. Foundations of Computing. The MIT Press, Cambridge, Massachusetts, 1993.
Jean Goubault-Larrecq and Ian Mackie. Proof Theory and Automated Deduction. Kluwer Academic Press, 1997.
TWiki's Education/MapiFc webThe Education/MapiFc web of TWiki. TWiki is a Web-Based Collaboration Platform for the Enterprise.http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFcCopyright 2020 by contributing authors2020-10-30T14:39:25ZWebStatisticshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebStatistics2020-10-30T14:39:25ZStatistics for Education/MapiFc Web Month: Topic views: Topic saves: File uploads: Most popular topic views: Top contributors for topic ... (last changed by TWikiGuest)TWikiGuestWebHomehttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebHome2012-09-27T17:01:05ZRSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ... (last changed by JoseNunoOliveira)JoseNunoOliveiraWebSideBarhttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebSideBar2011-04-12T09:25:57ZWebHome Overview Recommended Books Syllabus and Course Material Assessment (last changed by JorgeSousaPinto)JorgeSousaPintoCourseAssessmenthttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/CourseAssessment2011-04-12T09:24:48ZResults I II III Final Carlos Silva 16 15 13 15 Constantin Taivan 16 12 11 13 Frederico Valente 13 6 10 11 Henrique ... (last changed by JorgeSousaPinto)JorgeSousaPintoAssessment0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment08092010-12-07T22:42:59ZAssessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaAssessment0910http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment09102010-12-07T17:02:40ZAssessment Part I Paper reading and presentations Part II Home assessment: December 13 to December 27 Part III JorgeSousaPinto 07 Dec 2010 (last changed by JorgeSousaPinto)JorgeSousaPinto1011http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/10112010-12-07T16:58:04ZProgram Semantics, Verification, and Construction (Previous instance: 2008/2009) 2010/2011 Course leader: Jorge Sousa Pinto ( jsp(AT)di(DOT)uminho(DOT)pt ) Lecture ... (last changed by JorgeSousaPinto)JorgeSousaPinto0910http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/09102010-09-24T17:02:53ZProgram Semantics, Verification, and Construction (Previous instance: 2008/2009) 2009/2010 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)JoseNunoOliveira0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/08092010-09-24T16:39:02ZProgram Semantics, Verification, and Construction (Previous instance: 2007/2008) 2008/2009 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)JoseNunoOliveiraTopics0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics08092008-11-04T00:02:15ZAssessment (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaRecommendedBookshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/RecommendedBooks2008-11-03T22:21:05ZRecommended Books 1. Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford ... (last changed by NelmaMoreira)NelmaMoreiraSyllabus0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus07082008-09-27T11:45:31ZChapter I: Overview of Foundations (5 3 hours) 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaAssessment0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment07082008-09-27T11:44:49ZFinal Grades Nome Part I Part II Part III Final Andreia Sofia da Costa Teixeira 16 16 16 16 Arif Rahman 10 14 14 13 Daniela ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeida0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/07082008-09-27T11:43:58ZProgram Semantics, Verification, and Construction 2007/2008 Lecture 1 Date: 15/10/07 Notes: psvc.pdf Lecture 2 Date: 22/10/07 Topics: Deduction ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaWebPreferenceshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebPreferences2008-09-27T11:39:23ZEducation/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaTopics0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics07082008-09-27T11:38:33ZAssessment (last changed by JoseBacelarAlmeida)JoseBacelarAlmeida
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ...
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ...
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ...
(Program Semantics, Verification, and Construction)
Overview.
The reliability of computing systems plays an essential role in modern society, where so many areas of human activity depend on technology. The deliverables of software projects may no longer be limited to code; the ability to produce certified code is now crucial. Code may be certified as being functionally correct, or as possessing certain execution properties (for instance, a program may be certified as not trying to access unauthorised resources).
The ability to certify software in this way requires a sound knowledge of the theory of programming languages and mathematical reasoning tools, as well as acquaintance with tool-assisted techniques. This course gives an overview of the theory of programming languages at an advanced level and then goes on to apply the theory to methods for obtaining correct, certified software.
Aims.
to present in a systematic way a vast set of results in fundamental areas of Theoretical Computer Science, in particular Logic, Lambda-calculus, Type Theory and Programming Language Semantics, as well as the relationships between them;
to introduce several rigorous approaches to the production of correct software, namely in:
Program Verification , the activity that aims to establish that a program effectively behaves according to its specification, or that its behaviour is characterised by a set of given properties;
in Mathematical Program Construction , a method for obtaining correct programs from specifications, strongly based on program calculation.
Lecturing Team.
The team consists of members of the Department of Informatics of the University of Minho and the Department of Computer Science of the University of Porto (Faculty of Science).
All team members are working, and have worked actively in the past few years, on topics that are directly related to the subjects covered by this course, as detailed below.
José Bacelar Almeida (DI-UM) has worked on the verification of security protocols, and has experience in using proof-assistants for program development.
Sabine Broda (DCC-FCUP) has worked on Mathematical Logic, lambda-calculus, and Type Theory.
Mário Florido (DCC-FCUP) has worked on lambda-calculus, type systems, and program transformation.
Maria J. Frade (DI-UM) has worked on lambda-calculus, type systems, and Proof Theory.
Nelma Moreira (DCC-FCUP) has worked on Automata Theory, Proof Theory, and proof assistants.
José N. Oliveira (DI-UM) has worked extensively on Formal Methods in Software Engineering and is a pioneer of this area in Portugal.
Jorge Sousa Pinto (DI-UM) has worked on Linear Logic, lambda-calculus, and functional program transformation.
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ...
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ...
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ...
This is a subscription service to be automatically notified by e-mail when topics change in this Education/MapiFc web. This is a convenient service, so you do not have to come back and check all the time if something has changed. To subscribe, please add a bullet with your WikiName in alphabetical order to this list:
Each TWiki web has an automatic e-mail notification service that sends you an e-mail with links to all of the topics modified since the last alert.
Users subscribe to email notifications using their WikiName or an alternative email address, and can specify the webs/topics they wish to track using one of these bullet list formats:
three spaces * [ webname . ] wikiName - SMTP mail address three spaces * [ webName . ] wikiName three spaces * SMTP mail address three spaces * SMTP mail address : topics three spaces * [ webname . ] wikiName : topics
In the above examples, topics is a space-separated list of topic names. The user may further customize the specific content they will receive using the following formats:
Specify topics without a Web. prefix
Topics must exist in this web.
Topics may be specified using * wildcards
Each topic may optionally be preceded by a '+' or '-' sign. The '+' sign means "subscribe to this topic" (the same as not putting anything). The '-' sign means "unsubscribe" or "don't send notifications regarding this topic". This allows users to elect to filter out certain topics (and their children, to an arbitrary depth). Topic filters ('-') take precedence over topic includes ('+').
Each topic may optionally be followed by an integer in parentheses, indicating the depth of the tree of children below that topic. Changes in all these children will be detected and reported along with changes to the topic itself. Note This uses the TWiki "Topic parent" feature.
Each topic may optionally be immediately followed by an exclamation mark ! or a question mark ? with no intervening spaces, indicating that the topic (and children if there is a tree depth specifier as well) should be mailed out as complete topics instead of change summaries. ! causes the topic to be mailed every time even if there have been no changes, ? will mail the topic only if there have been changes to it. This only makes sense for subscriptions.
For example:
Subscribe Daisy to all changes to topics in this web.
* daisy.cutter@flowers.com
Subscribe Daisy to all changes in all webs that start with Web.
* daisy.cutter@flowers.com: Web*
Subscribe Daisy to changes to topics starting with Petal, and their immediate children, WeedKillers and children to a depth of 3, and all topics that match start with Pretty and end with Flowers e.g. PrettyPinkFlowers
Subscribe Daisy to the full content of NewsLetter whenever it has changed
* daisy@flowers.com: TWiki.NewsLetter?
Subscribe buttercup to NewsLetter and its immediate children, even if it hasn't changed.
* buttercup@flowers.com: TWiki.NewsLetter! (1)
Subscribe GardenGroup (which includes Petunia) to all changed topics under AllnewsLetters to a depth of 3. Then unsubscribe Petunia from the ManureNewsLetter, which she would normally get as a member of GardenGroup? :
A user may be listed many times in the WebNotify topic. Where a user has several lines in WebNotify that all match the same topic, they will only be notified about changes that topic once (though they will still receive individual mails for news topics).
If a TWiki group is listed for notification, the group will be recursively expanded to the e-mail addresses of all members.
Tip: List names in alphabetical order to make it easier to find the names.
Note for System Administrators: Notification is supported by an add-on to the TWiki kernel called the MailerContrib. See the MailerContrib topic for details of how to set up this service.
Note: If you prefer a news feed, point your reader to WebRss (for RSS 1.0 feeds) or WebAtom (for ATOM 1.0 feeds). Learn more at WebRssBase and WebAtomBase, respectively.
Related topics:WebChangesAlert, TWikiUsers, TWikiRegistration
Web-specific background color: (Pick a lighter one of the StandardColors).
Set WEBBGCOLOR = #D0D0D0
Note: This setting is automatically configured when you create a web
Image, URL and alternate tooltip text of web's logo. Note: Don't add your own local logos to the TWikiLogos topic; create your own logos topic instead.
If yes, Set SITEMAPLIST = on, and add the "what" and "use to..." description for the site map. Make sure to list only links that include the name of the web, e.g. Education/MapiFc.Topic links.
Set SITEMAPLIST = on
Set SITEMAPWHAT = MAP/i - Foundations of Computing
Set SITEMAPUSETO = Option I: Program Semantics, Verification, and Construction
Exclude web from a web="all" search: (Set to on for hidden webs)
Set NOSEARCHALL =
Prevent automatic linking of WikiWords and acronyms (if set to on); link WikiWords (if empty); can be overwritten by web preferences:
#Set NOAUTOLINK =
Note: You can still use the [[...][...]] syntax to link topics if you disabled WikiWord linking. The <noautolink> ... </noautolink> syntax can be used to prevents links within a block of text.
Default template for new topics for this web:
WebTopicEditTemplate? : Default template for new topics in this web. (Site-level is used if topic does not exist)
Comma separated list of forms that can be attached to topics in this web. See TWikiForms for more information.
Set WEBFORMS =
Users or groups who are not / are allowed to view / change / rename topics in the Education/MapiFc web: (See TWikiAccessControl). Remove the # to enable any of these settings. Remember that an empty setting is a valid setting; setting DENYWEBVIEW to nothing means that anyone can view the web.
Preferences are used as TWikiVariables by enclosing the name in percent signs. Example:
When you write variable %WEBBGCOLOR% , it gets expanded to #D0D0D0
The sequential order of the preference settings is significant. Define preferences that use other preferences first, i.e. set WEBCOPYRIGHT before WIKIWEBMASTER since %WEBCOPYRIGHT% uses the %WIKIWEBMASTER% variable.
You can introduce your own preferences variables and use them in your topics and templates.
TWiki search results for \.*
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc
The Education/MapiFc web of TWiki. TWiki is a Web-Based Collaboration Platform for the Enterprise.en-usCopyright 2020 by contributing authorsTWiki Administrator [webmaster@di.uminho.pt]The contributing authors of TWikiTWikiDIUM.Education/MapiFc
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc
/twiki/pub/Main/LocalLogos/um_eengP.jpgWebHome
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebHome
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ... (last changed by JoseNunoOliveira)2012-09-27T17:01:05ZJoseNunoOliveiraWebSideBar
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebSideBar
WebHome Overview Recommended Books Syllabus and Course Material Assessment (last changed by JorgeSousaPinto)2011-04-12T09:25:57ZJorgeSousaPintoCourseAssessment
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/CourseAssessment
Results I II III Final Carlos Silva 16 15 13 15 Constantin Taivan 16 12 11 13 Frederico Valente 13 6 10 11 Henrique ... (last changed by JorgeSousaPinto)2011-04-12T09:24:48ZJorgeSousaPintoAssessment0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0809
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ... (last changed by JoseBacelarAlmeida)2010-12-07T22:42:59ZJoseBacelarAlmeidaAssessment0910
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0910
Assessment Part I Paper reading and presentations Part II Home assessment: December 13 to December 27 Part III JorgeSousaPinto 07 Dec 2010 (last changed by JorgeSousaPinto)2010-12-07T17:02:40ZJorgeSousaPinto1011
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/1011
Program Semantics, Verification, and Construction (Previous instance: 2008/2009) 2010/2011 Course leader: Jorge Sousa Pinto ( jsp(AT)di(DOT)uminho(DOT)pt ) Lecture ... (last changed by JorgeSousaPinto)2010-12-07T16:58:04ZJorgeSousaPinto0910
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0910
Program Semantics, Verification, and Construction (Previous instance: 2008/2009) 2009/2010 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)2010-09-24T17:02:53ZJoseNunoOliveira0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0809
Program Semantics, Verification, and Construction (Previous instance: 2007/2008) 2008/2009 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)2010-09-24T16:39:02ZJoseNunoOliveiraTopics0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics0809
Assessment (last changed by JoseBacelarAlmeida)2008-11-04T00:02:15ZJoseBacelarAlmeidaRecommendedBooks
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/RecommendedBooks
Recommended Books 1. Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford ... (last changed by NelmaMoreira)2008-11-03T22:21:05ZNelmaMoreiraSyllabus0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus0708
Chapter I: Overview of Foundations (5 3 hours) 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem ... (last changed by JoseBacelarAlmeida)2008-09-27T11:45:31ZJoseBacelarAlmeidaAssessment0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0708
Final Grades Nome Part I Part II Part III Final Andreia Sofia da Costa Teixeira 16 16 16 16 Arif Rahman 10 14 14 13 Daniela ... (last changed by JoseBacelarAlmeida)2008-09-27T11:44:49ZJoseBacelarAlmeida0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0708
Program Semantics, Verification, and Construction 2007/2008 Lecture 1 Date: 15/10/07 Notes: psvc.pdf Lecture 2 Date: 22/10/07 Topics: Deduction ... (last changed by JoseBacelarAlmeida)2008-09-27T11:43:58ZJoseBacelarAlmeidaWebPreferences
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebPreferences
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ... (last changed by JoseBacelarAlmeida)2008-09-27T11:39:23ZJoseBacelarAlmeidaTopics0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics0708
Assessment (last changed by JoseBacelarAlmeida)2008-09-27T11:38:33ZJoseBacelarAlmeidaSyllabus0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus0809
Chapter I: Overview of Foundations 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem) 4. ... (last changed by JoseBacelarAlmeida)2008-09-27T11:31:35ZJoseBacelarAlmeida
The Central Problem of Formal Methods: Model Validation; Program Derivation; Program Verification. Introduction to Hoare Logic. Program Annotation and Automated Static Checking. The ESC/Java2 tool.
Limitations of ESC/Java2: Examples where correctness or completeness fails.
The Caduceus tool for program verification: usage with Coq and Simplify. The Caduceus workflow.
Simple examples proved with automatic tactics. More complex examples. Case reasoning; frame conditions; modular reasoning.
Introduction to the mathematics of program construction.
Correct by verification versus correct
by construction. Description versus calculation.
Historical perspective on the PF-transform.
Point-free notation and reasoning. Rules of the
PF-transform.
PF-transform: when everything becomes a relation. Introduction to the binary relation
calculus. Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties. Galois connections.
No lecture (Lecturer away in an international advisory board meeting)
Lecture 14
Date: 28/01/08
Topics:
Constructive proofs. A PF-approach to
polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphism in one
equation. Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
First part (two hours): Assessment0708 (paper presentations).
Second part (one hour): Discussion. Open issues and hot topics in the mathematics of program
construction. Research directions in correct by construction.
Introduction to the mathematics of program construction
Date:
12/01/09 (Monday, 10h-13h) Sala 1
Topics:Overview of the scientific method applied to software design.Correct by verification versus correct by construction. Calculate versus invent & verify.The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the LerNET? doctoral school at Piriapolis, Uruguay, 2008)
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties.
Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
A PF-approach to polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphic functions in one equation.
Inductive predicates and relations. The catamorphism concept.
Universal property and its corollaries.
Mutual recursion. Calculation of for/while loops from systems of mutually recursive equations over linear types.
Notes:
Theorems for free: a (calculational) introduction (slides)
Relational algebra: a Kleene algebra central to the mathematics of program construction (slides)
Introduction to the mathematics of program construction
Date:
12/01/09 (Monday, 10h-13h) Sala 1
Topics:Overview of the scientific method applied to software design.Correct by verification versus correct by construction. Calculate versus invent & verify.The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the LerNET? doctoral school at Piriapolis, Uruguay, 2008)
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary
relations. Products and Sums. Universal
constructions and properties.
Extended static checking (ESC) in the
PF-style. Induction-free calculation of preconditions
and invariants. Three case studies.
A PF-approach to polymorphic type checking. Reynolds' relation on
functions. The free-theorem of polymorphic functions in one equation.
Inductive predicates and relations. The catamorphism concept.
Universal property and its corollaries.
Mutual recursion. Calculation of for/while loops from systems of mutually recursive equations over linear types.
Notes:
Theorems for free: a (calculational) introduction (slides)
Relational algebra: a Kleene algebra central to the mathematics of program construction (slides)
Introduction to the mathematics of program construction
Date: 27/09/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Overview of the scientific method applied to software design. Correct by verification versus correct by construction. Calculate versus invent & verify. The e=m+c equation: description versus calculation. Point-free (PF) and point-wise (PW) notations. PF-transform for (algebraic) reasoning.
Analogy with the Laplace transform (historical perspective).
Binary relations as a building block for logic in computer science.
Introduction to the binary relation calculus.
Notes:
Theory and applications of the PF-transform Lectures 1-2 (01-56) (slides of the Ler-NET doctoral school at Piriapolis, Uruguay, 2008)
04/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Taxonomy of binary relations. Functions.
Conditions and coreflexives. PF-transform of n-ary relations. Union and meet. Universal
constructions and properties. Galois connections underpinning relation algebra.
Extended static checking(ESC) in the PF-style.
PF-transform: extended static checking by calculation
Date:
11/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics:
Verification conditions in the PF-style. Arrow notation. Relation to Hoare triples and Hoare logic. Handling nondeterminism. Calculus of proof obligations (proof rules). Case study: verifying a model of a journaled file system. Manual proofs in conjunction with model checking in Alloy. Open issues and research topics.
Notes:
Hands on a Grand Challenge in Computing: Proving a Journaled File System Correct (PDF)
Lecture 4
Module assessment: paper recitation
Date:
18/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: J.N. Oliveira
Topics: Provisional schedule as follows:
10h00 - Carlos Eduardo Bastos e Marques da Silva: Variations on a Alloy-Centric Tool-chain in Verifying a Journaled File System Model
10h18 - Constantin Taivan: Reverse Program Calculation Supported by Code Slicing
10h36 - Frederico Miguel Goulão Valente: Generic Pointfree Lenses
10h54 - Henrique Manuel Fernandes de Castro: A Relational Model for Confined Separation Logic
11h12 Coffee break
11h30 - Nuno Filipe Moreira Macedo: First steps in Pointfree Functional Dependency Theory
11h48 - Nuno Miguel Almeida Luz: Strategic Term Rewriting and its Application to a VDM to SQL Convertion
12h06 - Paulo José Correia Bernardes: On the design of a Periodic Table of VDM specifications
12h24 - Eduardo Augusto Peixoto da Silva Brito: Tupling Calculation Eliminates Multiple Data Traversals
12h42 - Pedro Miguel Ribeiro Martins: Proving correctness using Free Theorems
13h00 Closing
Material:
Zip file containing all papers and presentations (11MB)
Lecture 5
A revision of propositional and first-order logics
Date:
25/10/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: Luís Pinto
Topics:
Propositional Logic (PL): Syntax; Semantics; Proof system; Adequacy of the proof system
First-Order Logic (FOL): Syntax; Semantics; Proof system; Theory for equality
Intuitionistic Logic: Natural deduction systems (propositional and first-order)
Notes:
A revision of propositional and first-order logics (PDF)
Lecture 6
Validity Checking in Propositional and Forst-Order Logic
Date:
08/11/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: José Bacelar Almeida
Topics:
Propositional Logic: general remarks; normal forms (NNF, CNF, DNF); validity/satisfiability in CNFs.
First-Order Logic: general remarks; normal forms (NNF, prenex, Herbrand/Skolem); Herbrand's theorem; semi-decidability; decidable fragments.
First-Order Theories: basic concepts; some theories of interest; SMT provers.
Notes:
Validity Checking in Propositional and First-Order Logic (PDF)
Bibliography:
Any standard textbook on Mathematical Logic addresses most of the topics mentioned in the Lecture (e.g. [11] from the list of recommended books).
A nice survey on the subject is
Henk Barendregt. Lambda calculi with types. In S. Abramsky, D. Gabbay, and T. Maibaum, editors, Handbook of Logic in Computer Science, volume 2, pages 117–309. Oxford Science Publications, 1992.
Henk Barendregt and Herman Geuvers. Proof-assistants using dependent type systems. In John Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning, pages 1149–1238. Elsevier and MIT Press, 2001.
Gilles Barthe and Thierry Coquand. An introduction to dependent type theory. In Gilles Barthe, Peter Dybjer, Luís Pinto, and João Saraiva, editors, APPSEM, volume 2395 of Lecture Notes in Computer Science, pages 1–41. Springer, 2000.
Lecture 9
A Practical Approach to the Coq Proof-Assistant
Date:
29/11/10 (Monday, 10h-13h). Room: DI A.1, Lecturer: José Bacelar Almeida
Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development. Coq’Art: The Calculus of Inductive Constructions, volume XXV of Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag, 2004.
Loc Correnson, Pascal Cuoq, Armand Puccetti, and Julien Signoles. Frama-C user manual. from the Frama-C website, http://frama-c.com, 2010.
Patrick Baudin, Jean-Christophe Fillitre, Claude March, Benjamin Monate, Yannick Moy, and Virgile Prevosto. ACSL: ANSI/ISO C Specification Language. Preliminary Design (version 1.4). from the Frama-C website, http://frama-c.com, 2010.
Yannick Moy and Claude March´e. Jessie Plugin Tutorial. LRI, February 2010. Beryllium Version.
Each student must complete and write the solutions of this assignment alone. The deadline is : *20/02/2008
*The answers must be send by e-mail to the following emails: \{nam,amf,sbb,luis\} at ncc.up.pt.
Part II
Students are expected to work in groups of two; each group will be assessed based on the following three components.
Should be sent by e-mail to this address. The deadline is the date of the presentations session.
Caduceus Mini-project
A list of examples of programs verified with Caduceus can be found here.
Select a program with a similar level of difficulty (not listed in the examples). Write an adequate specification and verify the program using Caduceus and the Coq proof assistant.
Groups should write a short report on their work (with proof scripts attached) and prepare a short talk (5 minutes) to be given in the final presentations session (see date below).
Paper Reading
Each group should select one paper from the following list. Please send a mail to this address with your choice. Papers will be allocated on a first come, first served basis. Groups will give a talk (20 minutes) on the paper in the presentations session (see date below).
Efficient Weakest Preconditions. K. Rustan M. Leino. link
Boogie: A Modular Reusable Verifier for Object-Oriented Programs. Mike Barnett, Bor-Yuh Evan Chang, Robert deLine, Bart Jacobs, and K. Rustan M. Leino. link
Foundational Proof-Carrying Code. Andrew W. Appel. link
Proof Obligations Preserving Compilation (Extended abstract). Gilles Barthe, Tamara Rezk and Ando Saabas. link
Beyond Assertions: Advanced Specification and Verification with JML and ESC / Java2. Patrice Chalin, Joseph Kiniry, Gary T. Leavens and Erki Poll. link
A Certifying Compiler for Java. Christopher Colby, Peter Lee, George C. Necula, Fred Blau, Mark Plesko, Kenneth Cline. link
A Tutorial on Recursive Types in Coq. Eduardo Gimenez and Pierre Casteran. link
Universes: Lightweight Ownership for JML. Werner Dietl and Peter Mueller. link
Dates
Deadline for delivery of Caduceus mini-project report: February 4
Presentations session and deadline for delivery of Coq Exercises: February 11
Part III
Reading and presenting a paper in the field (one paper per student)
Formulae-as-types as a notion of control
Groups:
1. Bruno Oliveira and Vitor Rodrigues: Theme 5
2. Alexandre Madeira and Miguel Ferreira: Theme 1
3. Hugo Pacheco and Miguel Marques: Theme 2
4. Luis Santos and Ricardo Freitas: Theme 6
5. Hugo Conceição: Theme 3
6. José Pedro Oliveira: Theme 4
Part II
Coq mini-projects:
Binary Integers
The aim of this mini-project is to enconde binary integers as lists of booleans. That is:
Require Import ZArith.
Require Import List.
Require Import Bool.
Open Scope Z_scope.
Definition BInt := list bool.
Fixpoint toZ (x : BInt) : Z :=
match x with
| nil => 0
| true :: xs => 1 + 2*(toZ xs)
| false :: xs => 2*(toZ xs)
end.
(observe that the head of the list is the least significant bit)
- Define the following functions:
bSucc - computes the successor of a binary integer
bAdd - computes the addition of two binary integers
bMult - computes multiplication of two binary integers
- Prove the correctness of those functions (e.g. forall x, toZ (bSucc x)=1+(toZ x))
NOTE: in the definition of bAdd, it is convenient to simultaneously define a function bAddCarry (performs addition with carry). Use the "Fixpoint ... with ..." to accomplish these simultaneous definitions.
Declarative Arrays
A possible encoding of arrays in Coq is through axiomatization of the corresponding theory. E.g. (taken from the Why tool)
(* The type of arrays *)
Parameter raw_array : Set -> Set.
Definition array (T:Set) := prod Z (raw_array T).
(* Array length *)
Definition array_length (T:Set) (t:array T) : Z := let (n, _) := t in n.
(* Functions to create, access and modify arrays *)
Parameter raw_new : forall T:Set, T -> raw_array T.
Definition new (T:Set) (n:Z) (a:T) : array T := (n, raw_new a).
Parameter raw_access : forall T:Set, raw_array T -> Z -> T.
Definition access (T:Set) (t:array T) (i:Z) : T :=
let (_, r) := t in raw_access r i.
Parameter
raw_update : forall T:Set, raw_array T -> Z -> T -> raw_array T.
Definition update (T:Set) (t:array T) (i:Z) (v:T) : array T :=
(array_length t, let (_, r) := t in raw_update r i v).
(* Update does not change length *)
Lemma array_length_update :
forall (T:Set) (t:array T) (i:Z) (v:T),
array_length (update t i v) = array_length t.
Proof.
trivial.
Qed.
(* Axioms *)
Axiom
new_def :
forall (T:Set) (n:Z) (v0:T) (i:Z),
(0 <= i < n)%Z -> access (new n v0) i = v0.
Axiom
update_def_1 :
forall (T:Set) (t:array T) (v:T) (i:Z),
(0 <= i < array_length t)%Z -> access (update t i v) i = v.
Axiom
update_def_2 :
forall (T:Set) (t:array T) (v:T) (i j:Z),
(0 <= i < array_length t)%Z ->
(0 <= j < array_length t)%Z ->
i <> j -> access (update t i v) j = access t j.
- Define a function sumArray to compute the sum of elements in an array.
- Formulate and prove the correctness of the previously defined function.
Paper Reading
A Tutorial on Recursive Types in Coq. Eduardo Gimenez and Pierre Casteran. link
Efficient Weakest Preconditions. K. Rustan M. Leino. link
Boogie: A Modular Reusable Verifier for Object-Oriented Programs. Mike Barnett, Bor-Yuh Evan Chang, Robert deLine, Bart Jacobs, and K. Rustan M. Leino. link
A Certifying Compiler for Java. Christopher Colby, Peter Lee, George C. Necula, Fred Blau, Mark Plesko, Kenneth Cline. link
Foundational Proof-Carrying Code. Andrew W. Appel. link
Proof Obligations Preserving Compilation (Extended abstract). Gilles Barthe, Tamara Rezk and Ando Saabas. link
Universes: Lightweight Ownership for JML. Werner Dietl and Peter Mueller. link
Beyond Assertions: Advanced Specification and Verification with JML and ESC / Java2. Patrice Chalin, Joseph Kiniry, Gary T. Leavens and Erki Poll. link
Part III
Workshop "Program Semantics, Verification, and Construction" 16/02/2008
10h-11h45
Part 1:
1. Alexandre Madeira, Miguel Ferreira. "Combinatory logic"
2. Hugo Pacheco. "Expressibility: the simply typed lambda-calculus (vs. the pure
system), system T"
3. Bruno Oliveira, Vitor Rodrigues. "Type systems I"
4. Luis Santos, Ricardo Freitas. "Type system II"
Part 2: 12h-13h45
1. Bruno Oliveira. "Efficient Weakest Preconditions"
2. Vitor Rodrigues, Ricado Freitas. "Beyond assertions: Advanced
specification and verification with JML and ESC/Java2"
3. Alexandre Madeira. "Pointfree Factorization of Operation Refinement"
4. Hugo Pacheco. "Tupling calculation eliminates multiple data traversal"
Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford University Press, Oxford, UK, 1994.
Roland C. Backhouse. Program construction and verification. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1986.
Henk P. Barendregt. The Lambda Calculus: Its Syntax and Semantics, volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, second, revised edition, 1984.
Henk P. Barendregt. Lambda calculi with types. In S. Abramsky, D. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 2, chapter 2, pages 117?309. Oxford University Press, 1992.
Yves Bertot and Pierre Casteran. Interactive Theorem Proving and Program Development. Springer Verlag, 2004.
Richard Bird and Oege de Moor. Algebra of Programming. Prentice Hall, 1997.
Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and Types, volume 7 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989. (online version)
M. Hennessy. The Semantics of Programming Languages. Wiley, 1990.
H. R. Nielson and F. Nielson. Semantics with Applications : A Formal Introduction. Wiley, 1992. (online version)
Glynn Winskel. The Formal Semantics of Programming Languages: An introduction. Foundations of Computing. The MIT Press, Cambridge, Massachusetts, 1993.
Jean Goubault-Larrecq and Ian Mackie. Proof Theory and Automated Deduction. Kluwer Academic Press, 1997.
TWiki's Education/MapiFc webThe Education/MapiFc web of TWiki. TWiki is a Web-Based Collaboration Platform for the Enterprise.http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFcCopyright 2020 by contributing authors2020-10-30T14:39:25ZWebStatisticshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebStatistics2020-10-30T14:39:25ZStatistics for Education/MapiFc Web Month: Topic views: Topic saves: File uploads: Most popular topic views: Top contributors for topic ... (last changed by TWikiGuest)TWikiGuestWebHomehttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebHome2012-09-27T17:01:05ZRSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ... (last changed by JoseNunoOliveira)JoseNunoOliveiraWebSideBarhttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebSideBar2011-04-12T09:25:57ZWebHome Overview Recommended Books Syllabus and Course Material Assessment (last changed by JorgeSousaPinto)JorgeSousaPintoCourseAssessmenthttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/CourseAssessment2011-04-12T09:24:48ZResults I II III Final Carlos Silva 16 15 13 15 Constantin Taivan 16 12 11 13 Frederico Valente 13 6 10 11 Henrique ... (last changed by JorgeSousaPinto)JorgeSousaPintoAssessment0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment08092010-12-07T22:42:59ZAssessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaAssessment0910http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment09102010-12-07T17:02:40ZAssessment Part I Paper reading and presentations Part II Home assessment: December 13 to December 27 Part III JorgeSousaPinto 07 Dec 2010 (last changed by JorgeSousaPinto)JorgeSousaPinto1011http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/10112010-12-07T16:58:04ZProgram Semantics, Verification, and Construction (Previous instance: 2008/2009) 2010/2011 Course leader: Jorge Sousa Pinto ( jsp(AT)di(DOT)uminho(DOT)pt ) Lecture ... (last changed by JorgeSousaPinto)JorgeSousaPinto0910http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/09102010-09-24T17:02:53ZProgram Semantics, Verification, and Construction (Previous instance: 2008/2009) 2009/2010 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)JoseNunoOliveira0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/08092010-09-24T16:39:02ZProgram Semantics, Verification, and Construction (Previous instance: 2007/2008) 2008/2009 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)JoseNunoOliveiraTopics0809http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics08092008-11-04T00:02:15ZAssessment (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaRecommendedBookshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/RecommendedBooks2008-11-03T22:21:05ZRecommended Books 1. Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford ... (last changed by NelmaMoreira)NelmaMoreiraSyllabus0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus07082008-09-27T11:45:31ZChapter I: Overview of Foundations (5 3 hours) 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaAssessment0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment07082008-09-27T11:44:49ZFinal Grades Nome Part I Part II Part III Final Andreia Sofia da Costa Teixeira 16 16 16 16 Arif Rahman 10 14 14 13 Daniela ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeida0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/07082008-09-27T11:43:58ZProgram Semantics, Verification, and Construction 2007/2008 Lecture 1 Date: 15/10/07 Notes: psvc.pdf Lecture 2 Date: 22/10/07 Topics: Deduction ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaWebPreferenceshttp://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebPreferences2008-09-27T11:39:23ZEducation/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ... (last changed by JoseBacelarAlmeida)JoseBacelarAlmeidaTopics0708http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics07082008-09-27T11:38:33ZAssessment (last changed by JoseBacelarAlmeida)JoseBacelarAlmeida
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ...
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ...
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ...
(Program Semantics, Verification, and Construction)
Overview.
The reliability of computing systems plays an essential role in modern society, where so many areas of human activity depend on technology. The deliverables of software projects may no longer be limited to code; the ability to produce certified code is now crucial. Code may be certified as being functionally correct, or as possessing certain execution properties (for instance, a program may be certified as not trying to access unauthorised resources).
The ability to certify software in this way requires a sound knowledge of the theory of programming languages and mathematical reasoning tools, as well as acquaintance with tool-assisted techniques. This course gives an overview of the theory of programming languages at an advanced level and then goes on to apply the theory to methods for obtaining correct, certified software.
Aims.
to present in a systematic way a vast set of results in fundamental areas of Theoretical Computer Science, in particular Logic, Lambda-calculus, Type Theory and Programming Language Semantics, as well as the relationships between them;
to introduce several rigorous approaches to the production of correct software, namely in:
Program Verification , the activity that aims to establish that a program effectively behaves according to its specification, or that its behaviour is characterised by a set of given properties;
in Mathematical Program Construction , a method for obtaining correct programs from specifications, strongly based on program calculation.
Lecturing Team.
The team consists of members of the Department of Informatics of the University of Minho and the Department of Computer Science of the University of Porto (Faculty of Science).
All team members are working, and have worked actively in the past few years, on topics that are directly related to the subjects covered by this course, as detailed below.
José Bacelar Almeida (DI-UM) has worked on the verification of security protocols, and has experience in using proof-assistants for program development.
Sabine Broda (DCC-FCUP) has worked on Mathematical Logic, lambda-calculus, and Type Theory.
Mário Florido (DCC-FCUP) has worked on lambda-calculus, type systems, and program transformation.
Maria J. Frade (DI-UM) has worked on lambda-calculus, type systems, and Proof Theory.
Nelma Moreira (DCC-FCUP) has worked on Automata Theory, Proof Theory, and proof assistants.
José N. Oliveira (DI-UM) has worked extensively on Formal Methods in Software Engineering and is a pioneer of this area in Portugal.
Jorge Sousa Pinto (DI-UM) has worked on Linear Logic, lambda-calculus, and functional program transformation.
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ...
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ...
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ...
This is a subscription service to be automatically notified by e-mail when topics change in this Education/MapiFc web. This is a convenient service, so you do not have to come back and check all the time if something has changed. To subscribe, please add a bullet with your WikiName in alphabetical order to this list:
Each TWiki web has an automatic e-mail notification service that sends you an e-mail with links to all of the topics modified since the last alert.
Users subscribe to email notifications using their WikiName or an alternative email address, and can specify the webs/topics they wish to track using one of these bullet list formats:
three spaces * [ webname . ] wikiName - SMTP mail address three spaces * [ webName . ] wikiName three spaces * SMTP mail address three spaces * SMTP mail address : topics three spaces * [ webname . ] wikiName : topics
In the above examples, topics is a space-separated list of topic names. The user may further customize the specific content they will receive using the following formats:
Specify topics without a Web. prefix
Topics must exist in this web.
Topics may be specified using * wildcards
Each topic may optionally be preceded by a '+' or '-' sign. The '+' sign means "subscribe to this topic" (the same as not putting anything). The '-' sign means "unsubscribe" or "don't send notifications regarding this topic". This allows users to elect to filter out certain topics (and their children, to an arbitrary depth). Topic filters ('-') take precedence over topic includes ('+').
Each topic may optionally be followed by an integer in parentheses, indicating the depth of the tree of children below that topic. Changes in all these children will be detected and reported along with changes to the topic itself. Note This uses the TWiki "Topic parent" feature.
Each topic may optionally be immediately followed by an exclamation mark ! or a question mark ? with no intervening spaces, indicating that the topic (and children if there is a tree depth specifier as well) should be mailed out as complete topics instead of change summaries. ! causes the topic to be mailed every time even if there have been no changes, ? will mail the topic only if there have been changes to it. This only makes sense for subscriptions.
For example:
Subscribe Daisy to all changes to topics in this web.
* daisy.cutter@flowers.com
Subscribe Daisy to all changes in all webs that start with Web.
* daisy.cutter@flowers.com: Web*
Subscribe Daisy to changes to topics starting with Petal, and their immediate children, WeedKillers and children to a depth of 3, and all topics that match start with Pretty and end with Flowers e.g. PrettyPinkFlowers
Subscribe Daisy to the full content of NewsLetter whenever it has changed
* daisy@flowers.com: TWiki.NewsLetter?
Subscribe buttercup to NewsLetter and its immediate children, even if it hasn't changed.
* buttercup@flowers.com: TWiki.NewsLetter! (1)
Subscribe GardenGroup (which includes Petunia) to all changed topics under AllnewsLetters to a depth of 3. Then unsubscribe Petunia from the ManureNewsLetter, which she would normally get as a member of GardenGroup? :
A user may be listed many times in the WebNotify topic. Where a user has several lines in WebNotify that all match the same topic, they will only be notified about changes that topic once (though they will still receive individual mails for news topics).
If a TWiki group is listed for notification, the group will be recursively expanded to the e-mail addresses of all members.
Tip: List names in alphabetical order to make it easier to find the names.
Note for System Administrators: Notification is supported by an add-on to the TWiki kernel called the MailerContrib. See the MailerContrib topic for details of how to set up this service.
Note: If you prefer a news feed, point your reader to WebRss (for RSS 1.0 feeds) or WebAtom (for ATOM 1.0 feeds). Learn more at WebRssBase and WebAtomBase, respectively.
Related topics:WebChangesAlert, TWikiUsers, TWikiRegistration
Web-specific background color: (Pick a lighter one of the StandardColors).
Set WEBBGCOLOR = #D0D0D0
Note: This setting is automatically configured when you create a web
Image, URL and alternate tooltip text of web's logo. Note: Don't add your own local logos to the TWikiLogos topic; create your own logos topic instead.
If yes, Set SITEMAPLIST = on, and add the "what" and "use to..." description for the site map. Make sure to list only links that include the name of the web, e.g. Education/MapiFc.Topic links.
Set SITEMAPLIST = on
Set SITEMAPWHAT = MAP/i - Foundations of Computing
Set SITEMAPUSETO = Option I: Program Semantics, Verification, and Construction
Exclude web from a web="all" search: (Set to on for hidden webs)
Set NOSEARCHALL =
Prevent automatic linking of WikiWords and acronyms (if set to on); link WikiWords (if empty); can be overwritten by web preferences:
#Set NOAUTOLINK =
Note: You can still use the [[...][...]] syntax to link topics if you disabled WikiWord linking. The <noautolink> ... </noautolink> syntax can be used to prevents links within a block of text.
Default template for new topics for this web:
WebTopicEditTemplate? : Default template for new topics in this web. (Site-level is used if topic does not exist)
Comma separated list of forms that can be attached to topics in this web. See TWikiForms for more information.
Set WEBFORMS =
Users or groups who are not / are allowed to view / change / rename topics in the Education/MapiFc web: (See TWikiAccessControl). Remove the # to enable any of these settings. Remember that an empty setting is a valid setting; setting DENYWEBVIEW to nothing means that anyone can view the web.
Preferences are used as TWikiVariables by enclosing the name in percent signs. Example:
When you write variable %WEBBGCOLOR% , it gets expanded to #D0D0D0
The sequential order of the preference settings is significant. Define preferences that use other preferences first, i.e. set WEBCOPYRIGHT before WIKIWEBMASTER since %WEBCOPYRIGHT% uses the %WIKIWEBMASTER% variable.
You can introduce your own preferences variables and use them in your topics and templates.
TWiki search results for \.*
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc
The Education/MapiFc web of TWiki. TWiki is a Web-Based Collaboration Platform for the Enterprise.en-usCopyright 2020 by contributing authorsTWiki Administrator [webmaster@di.uminho.pt]The contributing authors of TWikiTWikiDIUM.Education/MapiFc
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc
/twiki/pub/Main/LocalLogos/um_eengP.jpgWebHome
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebHome
RSD Rigorous Software Development (Program Semantics, Verification, and Construction) Overview. The reliability of computing systems plays an essential role in modern ... (last changed by JoseNunoOliveira)2012-09-27T17:01:05ZJoseNunoOliveiraWebSideBar
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebSideBar
WebHome Overview Recommended Books Syllabus and Course Material Assessment (last changed by JorgeSousaPinto)2011-04-12T09:25:57ZJorgeSousaPintoCourseAssessment
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/CourseAssessment
Results I II III Final Carlos Silva 16 15 13 15 Constantin Taivan 16 12 11 13 Frederico Valente 13 6 10 11 Henrique ... (last changed by JorgeSousaPinto)2011-04-12T09:24:48ZJorgeSousaPintoAssessment0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0809
Assessment Part I Write and present a short report in one of the topics. Bibliography. Formulae as types as a notion of control Groups: 1. Bruno Oliveira and ... (last changed by JoseBacelarAlmeida)2010-12-07T22:42:59ZJoseBacelarAlmeidaAssessment0910
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0910
Assessment Part I Paper reading and presentations Part II Home assessment: December 13 to December 27 Part III JorgeSousaPinto 07 Dec 2010 (last changed by JorgeSousaPinto)2010-12-07T17:02:40ZJorgeSousaPinto1011
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/1011
Program Semantics, Verification, and Construction (Previous instance: 2008/2009) 2010/2011 Course leader: Jorge Sousa Pinto ( jsp(AT)di(DOT)uminho(DOT)pt ) Lecture ... (last changed by JorgeSousaPinto)2010-12-07T16:58:04ZJorgeSousaPinto0910
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0910
Program Semantics, Verification, and Construction (Previous instance: 2008/2009) 2009/2010 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)2010-09-24T17:02:53ZJoseNunoOliveira0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0809
Program Semantics, Verification, and Construction (Previous instance: 2007/2008) 2008/2009 Course coordinator: Nelma Moreira ( nam(AT)ncc(DOT)up(DOT)pt ) Lecture ... (last changed by JoseNunoOliveira)2010-09-24T16:39:02ZJoseNunoOliveiraTopics0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics0809
Assessment (last changed by JoseBacelarAlmeida)2008-11-04T00:02:15ZJoseBacelarAlmeidaRecommendedBooks
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/RecommendedBooks
Recommended Books 1. Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science (vol. 3): Semantic Structures, pages 1?168. Oxford ... (last changed by NelmaMoreira)2008-11-03T22:21:05ZNelmaMoreiraSyllabus0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus0708
Chapter I: Overview of Foundations (5 3 hours) 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem ... (last changed by JoseBacelarAlmeida)2008-09-27T11:45:31ZJoseBacelarAlmeidaAssessment0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Assessment0708
Final Grades Nome Part I Part II Part III Final Andreia Sofia da Costa Teixeira 16 16 16 16 Arif Rahman 10 14 14 13 Daniela ... (last changed by JoseBacelarAlmeida)2008-09-27T11:44:49ZJoseBacelarAlmeida0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/0708
Program Semantics, Verification, and Construction 2007/2008 Lecture 1 Date: 15/10/07 Notes: psvc.pdf Lecture 2 Date: 22/10/07 Topics: Deduction ... (last changed by JoseBacelarAlmeida)2008-09-27T11:43:58ZJoseBacelarAlmeidaWebPreferences
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/WebPreferences
Education/MapiFc Web Preferences The following settings are web preferences of the Education/MapiFc web. These preferences overwrite the site level preferences ... (last changed by JoseBacelarAlmeida)2008-09-27T11:39:23ZJoseBacelarAlmeidaTopics0708
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Topics0708
Assessment (last changed by JoseBacelarAlmeida)2008-09-27T11:38:33ZJoseBacelarAlmeidaSyllabus0809
http://wiki.di.uminho.pt/twiki/bin/view/Education/MapiFc/Syllabus0809
Chapter I: Overview of Foundations 1. Intuitionistic logic 2. Natural deduction 3. lambda calculus (terms, reduction, the Church Rosser Theorem) 4. ... (last changed by JoseBacelarAlmeida)2008-09-27T11:31:35ZJoseBacelarAlmeida