Computers run according to programs, which are described in programming languages. Programming languages are defined by giving
their syntax and semantics. We illustrate how to give the semantics of programs (the results of executing the programs) by
showing operational semantics and axiomatic semantics to tiny languages. In general, semantics of programs are not known (to
computers) without executing the programs. Types, which are part of semantics of programs, are known to computers without
executing programs in statically-typed languages, in which types are analyzed in compile time (before executing the programs).
A set of rules concerning types in a statically-typed language is called a type system and we give a type system for a tiny
subset of the C language. As the classification of programming languages by their computational models we illustrate imperative,
functional, logic, and object-oriented languages. We also present major concepts of programming languages such as the scope
rules of variables and the mechanisms of parameter passing.
A programming language is a system for describing computations. Each language abstracts computations from various viewpoints
and provides ways for describing compuations. For example, languages typically provide variables, functions, and types. The
way a language abstracts compuations has a profound effect on programming in the language. We learn typical abstractions provided
by languages being used now so that we can select an appropriate language by taking into account such abstractions. We also
learn major concepts of programming languages such as the scope rules of variables and the mechanisms of parameter passing
so that we know the differences of such concepts among lanugages. Semantics form a basis for analyzing or verifying programs.
We learn semantics so that we have means for precisely specifying behaviors of programs.
- Understanding the formal description of the semantics of programming languages and being able to describe semantics of short programs in tiny languages based on axiomatic and operational semantics
- Understanding the scope rules (static and dynamic) of variables and being able to explain how the meaning of programs changes according to the scope rules
- Understanding the mechanisms of parameter passing and being able to explain how the meaning of programs changes according to the mechanisms
- Being able to explain the classification of programming languages based on their computational models
- For a simple program of a simple statically-typed language, being able to judge whether or not the program is consistent with respect to the type system of the language.
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1. | Classification of programming languages and a simple example of programming languages | Section 8.1 of the reference book | 180minutes |
| 2. | Imperative languages (1) - Assignments - Structured programming - Control flow |
Section 3.1, 3.2, and 3.3 of the reference book | 190minutes |
| 3. | Imperative languages (2) - Break statements, continue statements, goto statements, and return statements |
Section 3.4 of the reference book | 190minutes |
| 4. | Imperative languages (3) - Compilation of sentences - Short-circuit evaluation - Assertions |
p. 109 and p. 87 of the reference book | 190minutes |
| 5. | Imperative languages (4) - Hoare triple - Hoare logic |
Section 3.6 of the reference book | 190minutes |
| 6. | Imperative language (5) and a small examination - Procedures - Parameter-passing mechanisms - Scope rules of variables |
Section 5.2 and 5.3 of the reference book | 190minutes |
| 7. | Mid-term examination and explanation of the answers - Paper-and-pencil test for checking the understanding of the contents of the lectures from the first to the seventh (We resume the lecture after the mid-term examination.) |
Review the contents of all the lectures until the last one. | 190minutes |
| 8. | Operational semantics (1) - An operational semantics for a tiny C language - Definition of the meaning of expressions - Definition of the meaning of sentences |
Section 13.3 of the reference book provides an operational semantics, although it is for a functional language. This lecture provides one for an imperative language, but the basic ideas are similar. Since imperative languages support assignments, we have to care about the states, which the reference book does not provide the explanation for. Each student is recommended to try to consider how to define an operational semantics for an imperative language. | 190minutes |
| 9. | Type system - Variable declarations in the C language - A type system for a tiny C language |
Review variable declarations of the C language. | 190minutes |
| 10. | Lambda calculus - Syntax of the lambda expressions - Beta transformation |
Chapter 14 of the reference book | 190minutes |
| 11. | Object-oriented languages - Classes - Inheritance - Virtual functions |
Chapter 6 and 7 of the reference book | 190minutes |
| 12. | Logic programming | Chapter 11 of the reference book | 190minutes |
| 13. | Functional programming and a small examination | Chapter 8 and 9 of the reference book | 190minutes |
| 14. | Final examination and explanation of the answers - Paper-and-pencil test for checking the understanding of the contents of the lectures from the first to the fourteenth |
Review the contents of all lectures. | 190minutes |
| 15. | |||
| Total. | - | - | 2650minutes |
| small exam | mid-term exam | final exam | Total. | |
|---|---|---|---|---|
| 1. | 2% | 16% | 15% | 33% |
| 2. | 2% | 8% | 7% | 17% |
| 3. | 2% | 8% | 7% | 17% |
| 4. | 2% | 8% | 14% | 24% |
| 5. | 2% | 0% | 7% | 9% |
| Total. | 10% | 40% | 50% | - |
Mid-term exam is evaluated on a 40-point scale, final exam a 50-point, and small exams a 10-point. When the mid-term exam
is M point, the final exam F point, and the small exams S point, the overall score is S+M+F*(100-(S+M))/50.
If you can solve simple problems that ask you about basic things of the topics covered in this class,
you are in the level of obtaining 60-point.
If you can solve simple problems that ask you about basic things of the topics covered in this class,
you are in the level of obtaining 60-point.
We make materials public on a web page.
A reference book is:
- Programming languages concepts & constructs 2nd edition, Ravi Sethi, Addison-Wesley, 1996.
This class is largely based on this book. Currently it takes time to purchase this book.
A recommended book is:
- Concepts in programming languages, John C. Mitchell, Cambridge University Press, 2001.
A reference book is:
- Programming languages concepts & constructs 2nd edition, Ravi Sethi, Addison-Wesley, 1996.
This class is largely based on this book. Currently it takes time to purchase this book.
A recommended book is:
- Concepts in programming languages, John C. Mitchell, Cambridge University Press, 2001.
- Friday 13:10-14:50 or any time agreed on by email
- Course that cultivates a basic problem-solving skills
| Work experience | Work experience and relevance to the course content if applicatable |
|---|---|
| N/A | N/A |
Last modified : Thu Mar 21 14:45:28 JST 2019