Advanced Topics in Programming Languages

Hours:

• Sun 10:00-12:00, Room 321 (Binyan 90)
• Mon 12:00-14:00, Room 226 (Binyan 90)

Instructor: Michael Elhadad
            email: elhadad@cs.bgu.ac.il
            Tel: 647-7874
            Room: 317
            Office Hours: Sun 12:00-14:00

Exam Solution is available.

I will accept assignments until July 20th.

Assignments

• Assignment 4 is available. Due date is June 17, 2001 (or later...)
• Assignment 3 is available. Due date is June 4, 2001.
• Assignment 2 is available. Due date is May 6, 2001. Grades for HW2
• Assignment 1 is available. Due date is Mar 25, 2001. Grades for HW1

Objectives

``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.''

• 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

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.

Resources

• Define-record and variant-case for MzScheme/DrScheme. For scm and systems supporting slib, just do (require 'struct).
• Update to Chapter 6 of "Essentials of Programming Languages"
• Chapter 13 of "Essentials of Programming Languages" on "Type Inference"
• Threads in SCM (with same fringe)
• Notes on Y combinator by Eli Barzilay
• Coroutines in SCM
• Same fringe using threads in C
• Notes on multithreading in C (Part 1) (postscript)
• Notes on multithreading in C (Part 2) (postscript)
• Online supplement to the book Concurrent Programming in Java by Doug Lea
• JCSP home page (Communicating Sequential Processes for Java).
• Reality Check by Douglas Schmidt, a review of the "double check" pattern, with application to the "singleton" pattern (code in C++).
• Lazy instantiation By Philip Bishop and Nigel Warren: another description of the singleton pattern, with discussion of the double check pattern in Java.
• Singletons, critical sections, and reader/writer locks by Allan Holub: more on singletons, with additional material on reader-writer locks (locks that enable any number of readers to access a resource, but only a single writer at a time).
• the Java Memory Model by Bill Pugh: an in-depth presentation of the Java Memory Model and how it interacts with the Java Thread model; explanations why the semantics of threads in Java is not sufficiently defined.
• CTJ Javadoc reference.
• JCSP jar file (jcsp1-0-rc3.jar).
• JCSP tutorial (6 slides per page).
• CTJ tutorial
• CTJ distribution

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.
• Lecture 3 and 4: alpha reduction. Variable renaming. eta conversion. Reduction strategies. Applicative order. Church-Rosser Theorem.
• Week 3: 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 4: Interpreters: base interpreter. Adding conditionals. Local bindings. Procedures. Variable assignment. (Simple) recursion. Dynamic scope vs. static scope.