CSCI.4430/6969 Programming Languages-- Fall 2006

Instructor: Carlos Varela
Office: 109 Amos Eaton (x 6912)
Office Hours: Mo, Th, 3-4pm; or by appointment
Meeting Place: Amos Eaton, Room 214
Meeting Hours: Mo, Th, 12:00-1:50pm
TA: Brian Boodman
TA Office: Amos Eaton, 217
TA Office Hours: Tu 3:30-5pm and We 1-2pm

For questions about the course, please email: proglang AT cs DOT rpi DOT edu.

WebCT

News:

Programming Assignment 1 is available.
Programming Assignment 2 is available.
Programming Assignment 3 is available.

Course Objectives

This course will study essential aspects of programming languages --e.g., their theoretical foundations, syntax, semantics, types, scope of variables, data abstraction, control abstraction, parameter passing and expression evaluation mechanisms-- using a multi-paradigm programming language, Oz. We will also introduce different programming paradigms (computation models) including functional programming, imperative programming, concurrent and distributed programming, and logic programming. The course will include programming assignments in Oz, SALSA and Prolog.

Pre-requisites

CSCI.2400 Models of Computation.

Course Contents

Introduction

Brief history of programming languages
Lambda calculus
Syntax
Semantics
Essentials
Paradigms

Programming Language Essentials

Scope of variables
Data abstraction/Control abstraction
Static/Dynamic scoping
Parameter passing mechanisms
Expression evaluation orders
Types

Functional and Imperative Programming

Recursion
Higher-order programming
Lazy evaluation
State (Imperative programming)

Concurrent and Distributed Programming

Actors
Synchronous vs asynchronous communication, message passing
Token-passing continuations, join blocks, first-class continuations
Universal naming, remote message passing, migration (Distributed programming)

Logic Programming

Horn clauses
Resolution and unification
Search and backtracking

Reading Material

Concepts, Techniques, and Models of Computer Programming by Van Roy, and Haridi. 1st Edition. MIT Press 2004. (Required Textbook)

URL: http://www.info.ucl.ac.be/people/PVR/book.html

Essentials of Programming Languages by Friedman, Wand, and Haynes. 2nd Edition. MIT Press. (Recommended Textbook)

URL: http://www.cs.indiana.edu/eopl/

Programming Language Pragmatics by Scott. 2nd Edition. Morgan Kaufmann Publishers. (Recommended Textbook)

URL: http://www.cs.rochester.edu/u/scott/pragmatics/

A Foundation for Actor Computation by Agha, Mason, Smith, Talcott. pp. 1-27.

In Journal of Functional Programming, 1996.
URL: http://osl.cs.uiuc.edu/Papers/actor-semantics.ps

Programming Dynamically Reconfigurable Open Systems with SALSA by Varela and Agha.

In ACM SigPlan Notices 36(12):20-34, OOPSLA 2001 Intriguing Technology Track, December 2001.
URL: http://www.cs.rpi.edu/~cvarela/oopsla2001.pdf

Tentative Course Syllabus

Date	Topic	Handouts	Grade
08/28	Introduction to programming languages: history, lambda calculus, syntax, semantics	lecture1.pdf
08/31	Lambda calculus: beta conversion, applicative and normal evaluation orders, Church-Rosser theorem, combinators	lecture2.pdf 1.oz
09/07	Higher order programming, Oz	lecture3.pdf 2.oz
09/11	Introduction to programming concepts: lists, pattern matching	Sections1.1-1.8.pdf 3.oz
09/14	Introduction to programming concepts: correctness, complexity	Sections1.9-1.17.pdf 4.oz
09/18	Declarative programming, grammars, syntax and semantics.	Section2.1.pdf 5.oz
09/21	Single-assignment store, kernel language syntax	Sections2.2-2.3.pdf 6.oz
09/25	Kernel language semantics: concepts, abstract machine	Sections2.4.1-2.4.2.pdf 7.oz
09/28	Kernel language semantics: non-suspendable statements, closures	Sections2.4.3-2.4.4.pdf 8.oz
10/02	Kernel language semantics: suspendable statements	Sections2.4.5-2.7.pdf 9.oz
10/05	From kernel to practical language, memory management, exceptions -- Programming Assignment 1 Due 10/06	Sections2.5.pdf 10.oz	20%
10/10	Iterative computation	Sections3.1-3.2.pdf 11.oz
10/12	Higher order programming, abstract data types, state	Sections3.6-3.7.pdf 12.oz
10/16	Dynamic and static typing, parameter passing mechanisms	Sections2.8.3,6.1-6.4.4.pdf 13.oz
10/19	Exam I review
10/23	Exam I		20%
10/26	Concurrent object-oriented programming: Java	Java,Sections7.7,8.6.pdf mm.zip
10/30	Concurrent object-oriented programming: active objects	Sections7.2,7.8,8.6.pdf 14.oz
11/02	SALSA: actors, token-passing continuations, join blocks, first-class continuations	SALSA-Concurrency.pdf examples.zip
11/06	Distributed programming: universal naming, remote communication, actor migration	dist-examples.zip SALSA-Distributed.pdf
11/09	Logic programming: Horn clauses	append.pl PLP11.3A.pdf
11/13	Prolog: resolution, unification, search, backtracking, cut -- Programming Assignment 2 Due 11/14	prolog_examples.zip PLP11.3B.pdf	20%
11/16	Prolog: arithmetic, equalities, I/O, meta-interpreters, natural language parsing	prolog-examples.zip PLP11.3C.pdf
11/20	Logic programming: accumulators, difference lists, Oz search	15.oz Sections3.4.3-3.4.4.pdf
11/27	Declarative concurrency	16.oz Chapter4.pdf
11/30	Lazy evaluation -- Programming Assignment 3 Due 12/01	17.oz Section4.5.pdf	20%
12/04	Exam II Review
12/07	Exam II		20%

Software

Academic Integrity

The Rensselaer Handbook of Student Rights and Responsibilities defines several types of academic dishonesty, all of which are applicable to this class. Students found in violation of academic dishonesty policies may receive a failing grade for this course.

Please contact the instructor if there is any question about academic (dis)honesty.

Last Updated -- August 28th, 2006.