CSCI.4430/6969 Programming Languages-- Spring 2012

Instructor: Carlos Varela
Office: Lally 308 (x 6912)
Office Hours: Mondays and Thursdays, 1:30-2:30pm; or by appointment
Meeting Place: Sage 3510
Meeting Hours: Mondays and Thursdays 10:00-11:50am
TAs: Shigeru Imai, Jonathan Crall (50%)
TAs' Office: Amos Eaton 217
TAs' Office Hours:
Shigeru: Wednesdays 2:00-3:30pm, Fridays 10:00-11:30am, or by appointment.
Jonathan: Tuesdays 12:20-1:50pm, or by appointment.
Home page: http://www.cs.rpi.edu/academics/courses/spring12/proglang/
For questions about the course, please email: proglang AT cs DOT rpi DOT edu.

News

Programming Assignment 3 is available (April 11th, 2012)
Test cases used for grading for PA2 are available
Programming Assignment 2 is available (March 2nd, 2012)
Programming Assignment 1 is available (January 26th, 2012)

Course Description

This course will enable students to understand essential aspects of programming languages --e.g., theoretical foundations, syntax, semantics, types, scope of variables, data abstraction, control abstraction, parameter passing and expression evaluation mechanisms. Students will also be exposed to different programming paradigms (computation models) including logic programming, functional programming, and concurrent and distributed object-oriented programming. Students will write programming assignments in Prolog, Oz, and SALSA.

Pre-requisites

CSCI.2400 Models of Computation.

Course Themes

Programming Language Essentials. Logic, Functional, Concurrent Object-Oriented Programming Paradigms.

Learning Outcomes

When the students have successfully completed this course, they will be able to:

understand the essential aspects of programming languages, including theoretical foundations such as the lambda calculus, predicate calculus and the actor model,
compare and apply multiple programming paradigms,
design and develop logic, functional, and concurrent (distributed and mobile) programs.

Course Contents

Introduction

Brief history of programming languages
Syntax
Semantics
Essentials
Paradigms

Logic Programming

Horn clauses
Resolution and unification
Search and backtracking

Functional and Imperative Programming

Lambda calculus
Scope of variables
Data abstraction/control abstraction
Static/dynamic scoping
Parameter passing mechanisms
Expression evaluation orders
Types
Recursion
Higher-order programming
Lazy evaluation
State (Imperative programming)

Concurrent and Distributed Object-Oriented Programming

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

Tentative Course Syllabus

Date	Topic	Handouts	Grade
01/23	Introduction to programming languages: history, syntax, semantics, essentials, paradigms. Logic programming: introduction, Horn clauses	Intro,PLP11A.pdf rainy.pl
01/26	Logic programming: predicate calculus--Programming Assignment 1 Due 02/10	PLP11B.pdf	20%
01/30	Prolog: resolution, unification, search, backtracking, cut, lists	PLP11C.pdf append.pl crossword.pl cut.pl cut2.pl cut3.pl cut4.pl cut5.pl loop.pl not2.pl
02/02	Prolog: arithmetic, equalities, I/O, meta-interpreters, natural language parsing	PLP11D.pdf browse.pl reverse.pl sentences.pl sentences2.pl
02/06	Logic programming: accumulators, difference lists	PLP11E,Sections3.4.3-3.4.4.pdf accumulators.pl accumulators.oz
02/09	Lambda calculus: alpha-renaming, beta conversion, applicative and normal evaluation orders, Church-Rosser theorem, combinators	PLP11E,Sections3.4.3-3.4.4.pdf dlists.oz
02/13	Higher order programming, Oz -- Programming Assignment 2 Due 03/02	LambdaCalculus.pdf	20%
02/16	Introduction to programming concepts: lists, pattern matching	LambdaCalculus2.pdf combinators.oz eta.oz hop.oz lambda-booleans.oz lambda-numbers.oz rec.oz seq.oz
02/23	Introduction to programming concepts: correctness, complexity	Chapter1.pdf comb.oz concepts.oz lists.oz pascal.oz scope.oz store.oz
02/27	Declarative programming, grammars, syntax and semantics.	Section2.1.pdf rainy.oz recursion.oz
03/01	Single-assignment store, kernel language syntax	Section2.2-2.3.pdf single-assignment.oz
03/05	Kernel language semantics: concepts, abstract machine	Section2.4.1-2.4.2.pdf kernel.oz scope2.oz
03/08	Kernel language semantics: non-suspendable, suspendable statements, closures	Sections2.4.3-2.4.4.pdf dataflow.oz
03/19	From kernel to practical language, exceptions	Sections2.4.5,2.6,2.7.pdf case-semantics.oz semantics.oz
03/22	Review for Exam I
03/26	Exam I		20%
03/29	Memory management, tail-form optimization, garbage collection	Section2.5.pdf memleak.oz
04/02	Exam I analysis
04/05	Iterative computation, higher order programming, abstract data types	Sections3.1-3.2,3.6-3.7.pdf fold.oz sqrt.oz stackADT.oz
04/09	State, object-oriented programming, inheritance, polymorphism	Sections6.1-6.4,7.1-7.2.pdf c.java c1.java c2.java c3.java oop.oz
04/12	Actors: a model of concurrent computation -- Programming Assignment 3 Due 04/27	actors.pdf	20%
04/16	SALSA concurrency: actor creation, asynchronous message passing, state encapsulation, token-passing continuations, named tokens, join blocks, first-class continuations	SALSA-Concurrency.pdf Calculator.salsa Cell.salsa CellTester.salsa Fibonacci.salsa HelloWorld.salsa NDCellTester.salsa
04/19	SALSA distribution and mobility: universal naming, location-transparent communication, actor migration	SALSA-Distributed.pdf AddressBook.salsa AddUser.salsa Cell.salsa CellTester.salsa GetCellValue.salsa GetEmail.salsa Migrate.salsa MigrateCell.salsa MovingCellTester.salsa readme.txt
04/23	Concurrent and distributed programming patterns	SALSA-Patterns.pdf
04/26	Declarative concurrency	Chapter4.pdf dconcurrency.oz
04/30	Dynamic and static typing, parameter passing mechanisms, lazy evaluation	Sections2.8.3,4.5,6.1-6.4.pdf callbyneed.oz lazy-eval.oz
05/03	Review for Exam II
05/07	Exam II		20%
	Class Participation Extra-Credit		5%

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

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

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

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

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

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

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 will receive a failing grade for this course.

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

Last Updated -- January 23rd, 2012.