Course title
L09944002
Foundations for Programming Languages

SASANO Isao
Course description
Computers work in accordance with 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 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.
Purpose of class
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.
Goals and objectives
  1. 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
  2. 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
  3. Understanding the mechanisms of parameter passing and being able to explain how the meaning of programs changes according to the mechanisms
  4. Being able to explain the classification of programming languages based on their computational models
  5. 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.
Relationship between 'Goals and Objectives' and 'Course Outcomes'

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% -
Evaluation method and criteria
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 basic questions related to the fundamental topics covered in this class, you can achieve a level of 60 points.
Language
English
Class schedule

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
- A type system for a tiny language
Chapter 14 of the reference book 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 thirteenth
Review the contents of all lectures. 190minutes
Total. - - 2650minutes
Feedback on exams, assignments, etc.
ways of feedback specific contents about "Other"
Feedback in the class
Textbooks and reference materials
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.
Prerequisites
You should have some experience of writing programs by some programming languages.
In principle I think it is possible to understand the contents without any experience of writing programs,
but you may actually feel difficulty.
Office hours and How to contact professors for questions
  • Wednesday 15:00-15:10 or any time agreed on by email via zoom
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates a basic problem-solving skills
Active-learning course
More than one class is interactive
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicable
N/A 該当しない
Education related SDGs:the Sustainable Development Goals
    Last modified : Sat Jun 29 04:20:11 JST 2024