Fall 1998 - Michael Elhadad -
Teaching
201-2-4411-01
Hours:
Class:
- Sun 10:00-12:00, Room 110 (Binyan 32)
- Tue 18:00-20:00, Room 303 (Binyan 34)
Staff:
Instructor: Michael Elhadad
email: elhadad@cs.bgu.ac.il
Tel: 646-1627
Room: 307
Office Hours: Sun 12:00-14:00
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.
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++.
Course Schedule
- Week 1: Scheme - quick review:
recursion, syntactic abstraction. Syntactic description with BNF, Deriving
Programs from BNF specifications.
Parser code
- Week 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.
- Week 6: Parameter passing: arrays, call-by-value,
call-by-reference, Pascal-type parameters, call-by-name, lazy evaluation.
- Week 8-10: Introduction to multithreading and exceptions in Java
and C++, multithreading design patterns.
- Week 11-12: Modelling control: continuations, continuation passing
style (CPS), tail-recursion, conversion to CPS. Continuation passing
interpreters.
- Week 13: Deriving a Compiler from an Interpreter.
Interpreters and meta-interpreters in Prolog. Partial evaluation.
Homework
There will be 6 homework assignments during the course. Most of the
assignment will be Scheme or Java programming. Only a subset of the
assignments will be graded, but all are required. There will be one final
exam. Final grade will be based 75% on the final exam and 25% on homework.
Assignments must be sent to the class directory by email every week.
Bibliography
- Essentials of Programming Languages, D.P. Friedman, M. Wand
and C.T. Haynes, The MIT Press, Cambridge, MA, 1992.
- Lisp in Small Pieces, Christian Queinnec,
Cambridge University Press, Cambridge, UK, 1996.
- Structure and Interpretation of Computer Programs, H. Abelson and
G. Sussman, The MIT Press, Cambridge, MA, 2nd Edition (1995).
- Concurrent Java Programming, Sun Press, 1996.
Last modified Dec 27, 1998 / 02 Apr 2019
Michael Elhadad