CMU 15-671
Models of Software Systems
Fall 1997

Course Information

Garlan
Handout 1
August 25, 1997

Course Staff:

  Who e-mail address Office,
Phone
Office Hours (or
by appointment)

Instructor

David Garlan garlan@cs.cmu.edu WeH 8020
(x8-5056)
Mon 12:00-1:00

Teaching Assistant

Shawn Hurley shawnh@cs.cmu.edu WeH 4615-4
(x8-3759)
Fri 10:30-11:30

Secretary

Heather Marko heatherm@cs.cmu.edu WeH 8120,
(x8-2568)
 

Objectives

Scientific foundations for software engineering depend on the use of precise, abstract models and logics for characterizing and reasoning about properties of software systems. There are a number of basic models and logics that over time have proven to be particularly important and pervasive in the study of software systems. This course is concerned with that body of knowledge. It considers many of the standard models for representing sequential and concurrent systems, such as state machines, algebras and traces. It shows how different logics can be used to specify properties of software systems, such as functional correctness, deadlock freedom, and internal consistency. Concepts such as composition mechanisms, abstraction relations, invariants, non-determinism, inductive and denotational descriptions are recurrent themes throughout the course.

By the end of the course you should be able to understand the strengths and weaknesses of certain models and logics, including state machines, algebraic and trace models, and temporal logics. You should be able to apply this understanding to select and describe abstract formal models for certain classes of systems. Further, you should be able to reason formally about the elementary properties of modeled systems.

Organization

Lectures. Class meet Monday & Wednesday, 10:30-11:50 am, in Doherty 1211.

Computing. Some of the assignments may make use of tools that are part of the SCS software engineering environment. You will need an account on an SCS SunOS machine to use these tools. If you are an MSE student you will already have such an account. Other students should see the instructor after the first class to get an application form. There are a set of documents that describe the MSE tool facilities.

On-line materials. Most of our course materials will be available electronically via the Web. To access this material point your favorite web browser to

URL: http://www.cs.cmu.edu/afs/cs/academic/class/15671-f97/www/

There is also a class afs directory: /afs/cs/academic/class/15671-f97. It will contain various templates and documents that can be helpful in completing your homework.

Communication. We have set up three mechanisms for out-of-class interaction.

1. The Course Bulletin Board. We will use cmu.cs.class.cs671 to post questions/answers about homework and lectures. So you should plan to read it regularly. Feel free to use it yourself to post about topics of general interest for the other students.

2. Office Hours: The instructor and the TA has weekly office hours, listed above.

3. Email: We welcome email about the course at any time.

Readings. Most lectures will have a reading assignment that we expect you to complete before you come to class. Many of the reading assignments will be drawn from the the required textbook for the course: An Introduction to Formal Specification and Z, by Potter, Sinclair, Till [PST]. Additionally, the course has an optional reference book: The Z Notation: A Reference Manual, Second Edition, by J. M. Spivey. Some readings are in the form of handouts to supplement some lectures; other additional readings are technical papers. These will be distributed as needed throughout the course.
Finally, there a number of additional books that will be put on reserve. These are noted in References at the end of this document.

Homeworks and Lab Exercises. The course is organized around (roughly) weekly homeworks. The purpose of the assignments is to give you practice in using the models and logics of the course. In some cases where a model is supported by tools we may also assign one or more ungraded lab exercises. These are intended to give you practice in using the tools before you have to apply them on the homework problems. We encourage you to discuss your homework with other students, but the final write-up must be your own work.

Homeworks will be graded on a pass/fail basis. Occasionally, we will take special note of a homework that is exceptionally well done. Homework assignments will typically be assigned on a Monday and due at the beginning of class a week later. To give you the most opportunities to learn from the homework assignments, we will allow you to redo a homework that didn't receive a passing grade. A redone homework must be turned in at the class following the one on which it is handed back.

Extra copies of handout materials. Extra copies of lecture slides, handouts, homework assignments, etc. will be available from Heather Marko, WeH 8120 and in the shelves next to the door to WeH 4615.

Exams. There will be a (take-home) mid-term (handed out October 11, due October 13) and a (in-class) final examination.

Homework Presentations. For some homework assignments we will ask students to present their results on the day it is due. The purpose of this is to give the presenter practice at explaining a solution to others and to give the rest of the class a chance to see how someone else solved the problem. These presentations will be assigned on a rotating basis, as necessary and will be ungraded.

Grading. The course grade will be determined as a combination of four factors: homework exercises (50%), midterm exam (15%) final exam (25%), instructorsí judgment (10%).

(Go to the current version of the syllabus with links)

Schedule

# Date Topic Subtopic Reading Homework
1 M 8/25 Introduction Course info; whatís a model?
2 W 8/27 Foundations Logic [Handout 1, 1-2]
3 *W 9/3 Sets, Relations, Functions [4.1-3,5] HW 1
4 M 9/8 Proof Techniques I [Handout 2, 9.5-6] HW 2
5 W 9/10 Proof Techniques II [Handout 3,4]
6 M 9/15 State Machines Basic concepts [Handout 5] HW 3
7 W 9/17 Variations [Handout 6]
8 M 9/22 Reasoning [Handout 7] HW 4
9 W 9/24 Statecharts [Ha87]
10 M 9/29 Z Introduction to Z [4.4-6,130-155] HW 5
11 W 10/1 Reasoning about Z Specs [7-8(skim),6.5.8,9.1-4]
12 M 10/6 Examples [Handout 8,DG90] HW 6
13 W 10/8 Abstraction in Z [Handouts 9-11, 10]
Midterm out
14 *W 10/15 Larch Algebras [SEM, Ch 11]
15 M 10/20 Interfaces [GH93] HW 7
16 W 10/22 Concurrency Introduction to Concurrency [AS83, Handouts 12-13]
17 M 10/27 Petri Nets Introduction to Petri Nets [Pet77] HW 8
18 W 10/29 Reasoning about Petri Nets [Jen91]
19 M 11/3 CSP Introduction to CSP [] HW 9
20 W 11/5 Reasoning with CSP []
21 M 11/10 Nondeterminism [] HW 10
22 W 11/12 Case Study [AGI97, Handout13]
23 M 11/17 Temporal Logic Linear Temporal Logic [] HW 11
24 W 11/19 Other Temporal Logic []
25 M 11/24 Temporal Logic of Actions [] HW 12
26 *M 12/1 Applications [12] HW 13
27 W 12/3 Review for Final

Bold refers to PST

* marks classes that follow a holiday

References