CSCI.4430/6969 Programming Languages-- Spring 2005

Instructor: Carlos Varela
Office: 109 Amos Eaton (x 6912)
Office Hours: Mo, Th, 4-5pm; or by appointment
Meeting Place: Darrin, Room 308
Meeting Hours: Mo, Th, 2-3:50pm
TAs: Travis Desell, Mayuresh Kulkarni, Ying Yang
See News for current office hours
Travis's office hours: Amos Eaton 117, Tuesdays and Fridays 12:00 - 1:30 PM
Mayuresh's office hours: Bray Room, Science Center, Tuesdays and Fridays 10 - 11.30 AM
Ying's office hours: Bray Room, Science Center, Thursdays 8:30 -11:30 AM
For questions about the course, please email: proglang@cs.rpi.edu.

Course WebCT page

News

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 (including object-oriented programming), logic programming, and concurrent and distributed programming. The course will include programming assignments in Oz, Java, Prolog, and SALSA.

Pre-requisites

Models of Computation. The student should have at least one year of experience with a high-level programming language.

Course Contents

Introduction

History of Programming Languages
Lambda-Calculus
Syntax
Semantics
Concepts
Paradigms

Programming Language Concepts

Scope of Variables
Data Abstraction/Control Abstraction
Static/Dynamic Scoping
Parameter Passing Mechanisms
Expression Evaluation Mechanisms
Types

Functional Programming

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

Object-Oriented Programming

Objects and Classes
Inheritance
Objects and Types

Logic Programming

Predicate Calculus
Horn Clauses
Resolution and Unification
Search and Backtracking

Concurrent and Distributed Programming

Pi-Calculus, Actors
Synchronous and asynchronous communication, Message Passing
Token-Passing Continuations, Join Continuations, First-Class Continuations
Distributed Programming: Universal Naming, Remote Message Sending Protocol, Migration

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. Morgan Kaufmann Publishers. (Recommended Textbook)

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

An Introduction to the Pi-Calculus by Joachim Parrow. pp. 3-14.

In Handbook of Process Algebra, ed. Bergstra, Ponse, Smolka, pages 479-543, Elsevier 2001.
URL: http://www.it.kth.se/~joachim/intro.ps

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	Course Handouts	Grade
01/20	Introduction to Programming Languages: History, Lambda-Calculus, Syntax, Semantics	Lecture1.pdf
01/24	Lambda-Calculus: Beta-Conversion, Church-Rosser Theorem, Applicative and Normal Order Forms, Combinators	Lecture2.pdf 1.oz
01/27	Introduction to Programming Concepts, Oz	Lecture3.pdf 2.oz
01/31	Single-assignment store, kernel language syntax and semantics	Chapter1.ppt 3.oz
02/03	Scope of variables, static and dynamic scoping	Section2.1.ppt 4.oz
02/07	A declarative language	Sections2.2-2.3.ppt 5.oz
02/10	Static and dynamic typing	Section2.4.ppt 6.oz
02/14	Linguistic Abstractions, Memory Management and Exceptions	Sections2.5-2.7.ppt 7.oz
02/17	Abstract data types	Sections3.7,6.4.ppt 8.oz
02/22	Typing and Parameter passing	Sections2.8.3,6.4.4 9.oz
02/24	Types and type inference
02/28	Partial Exam		20%
03/03	Functional Programming: Control abstraction, procedures	10.oz
03/07	Iterative Computation and Higher-order Programming	Section3.1-2,3.6.ppt 11.oz
03/10	Non Declarative Needs, Program Design in the Small	Sections3.8-9.ppt 12.oz pa1test0.oz pa1test0-answers.oz MyList.oz
03/21	Lazy Evaluation - Programming Assignment 1 Due 03/22	Section4.5.ppt 13.oz	15%
03/24	Object-Oriented Programming: Objects, Classes, and Interfaces	Sections6.4.3,7.1-2.ppt 14.oz dd/c1.java dd/c2.java dd/c3.java
03/28	Polymorphism and Inheritance	Sections7.3-4,7.6-7.ppt verbose/Hello.oj verbose/VerboseClass.oj
03/31	Java: Interface multiple inheritance and class single inheritance	Section7.5.ppt verbose/World.oj verbose/AddMethod.oj mm/c4.java mm/c5.java mm/c.java
04/04	Active Objects -- Programming Assignment 2 Due 04/05	Section7.8.ppt 15.oz	15%
04/07	Logic Programming: Predicate Calculus	PLP11.3A.pdf PLP11.3B.pdf rainy.pl family.pl append.pl
04/11	Prolog: Resolution, Unification, Lists, Arithmetic	PLP11.3C.pdf sentences.pl,if.pl rainy2.pl,rainy3.pl rainy4.pl,rainy5.pl rainy6.pl,rainy7.pl rainy8.pl,rainy9.pl loop.pl,functoreg.pl family2.pl
04/14	Prolog: Search and Execution Order	PLP11.3D.pdf tictactoe.pl,sentences2.pl sentences3.pl,read_line2.pl loop2.pl,loop3.pl hascolor.pl,crossword.pl browse.pl,browse2.pl
04/18	Prolog: Backtracking -- Programming Assignment 3 Due 04/19	Section3.4.3-4.ppt not2.pl,append2.pl 16.oz	15%
04/21	Concurrent Programming: Pi-Calculus, Actors	SALSA-Concurrency.ppt Fibonacci.salsa , HelloWorld.salsa HelloWorld2.salsa , HelloWorld3.salsa
04/25	SALSA: Actor Creation, Message Passing, Internal State	SALSA-WWC.ppt examples/lock/File.salsa examples/lock/WriteLine.salsa examples/migrate/Migrate.salsa examples/migration/Agent.salsa examples/migration/RemoteSend.salsa examples/migration/Migrate.salsa
04/28	SALSA: Token-Passing Continuations, Join Continuations, First-Class Continuations	actors.pdf,pi-calculus.pdf examples/cell/Cell.salsa examples/cell/CellTester.salsa examples/cell/MovingCellTester.salsa
05/02	Distributed Programming: Universal Naming, Remote Communication, Actor Migration -- Programming Assignment 4 Due 05/03		15%
	Final Exam		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 -- January 20th, 2005.