Spring 2000 - Michael Elhadad
Advanced Topics in Programming Languages
Hours:
Class:
- Mon 12:00-14:00, Room 103 (Binyan 34)
- Tue 10:00-12:00, Room 003 (Binyan 34)
Staff:
Instructor: Michael Elhadad
email: elhadad@cs.bgu.ac.il
Tel: 647-7874
Room: 316
Office Hours: Sun 14:00-16:00
Solution to Final Exam
Solution
Assignments
Objectives
The course will present essential concepts of programming languages. The
strategy will be to study interpreters of languages, explaining the design
decisions faced when inventing programming languages and implementing them.
The goal of the course is, quoting from Hal Abelson:
``to change your view of your programming, and your view of
yourself as a programmer. (To make) you see yourself as a designer
of languages rather than only a user of languages, as a person who
chooses the rules by which languages are put together, rather than
only a follower of rules that other people have chosen.''
To achieve this transformation of your personality, the following issues
will be addressed and progressively anchored in your mind (mingo-bingo,
breath deeply):
- Formal Description of Programming Languages and Semantics
- Operational Semantics vs Denotational Semantics
- Structure of Interpreters
- Parameter Passing Modes
- Functional Programming - Theory, Usage and Implementation Issues
- Modeling control: Continuations - Continuation passing interpreters
- Applications: multithreading, coroutines, exceptions.
- Deriving Compilers from Interpreters
The course will closely follow the textbook:
Essentials of Programming Languages
Daniel Friedman, Mitchell Wand and Christopher Haynes
The MIT Press, 1992.
Home page of the book
Four points characterize the approach taken to describe programming
languages:
- Interpreters are used to model languages. Interpreters are formal
descriptions that can be executed.
- Models are presented as Scheme programs instead of an abstract
notation.
- Low-level implementations are systematically derived from high-level
abstractions. Algebraic manipulations of programs are used, and we will
reason about the correctness of program transformations.
- Data abstractions are used systematically to separate algorithms from
internal representation.
In addition, we will explore recent applications of the principles
discussed in the course by looking at language constructs supporting
exceptions and multithreading in Java and C++.
Resources
Lecture Notes
- Lecture 1: Scheme - quick review:
recursion, syntactic abstraction. Syntactic description with BNF, Deriving
Programs from BNF specifications.
- Lecture 2: lambda calculus - Free
variables vs. bound variables. beta reduction.
- Week 3: alpha reduction. Variable
renaming. eta conversion. Reduction strategies. Applicative order.
Church-Rosser Theorem.
- Week 4: Recursion in $\lambda$
calculus and the Y-operator. Approaches to Semantics of Programming
Languages: operational, structured operational, denotational semantics.
Reasoning about programs, program transformations. Language vs.
Meta-language. Expressed values vs. Denoted values.
- Week 5: Interpreters: base
interpreter. Adding conditionals. Local bindings. Procedures. Variable
assignment. (Simple) recursion. Dynamic scope vs. static scope.
Last modified 23 Feb 2000
Michael Elhadad