CSCI.4430/6430 Programming Languages-- Spring 2015

Instructor: Carlos Varela
Office: Lally 308 (x 6912)
Office Hours: Mondays and Thursdays, 3:00-3:50pm; or by appointment
Meeting Place: Sage 3510
Meeting Hours: Mondays and Thursdays 4:00-5:50pm
TAs: Linyun Fu, Antwane Mason
TAs' Office Hours:

Antwane: Monday 9-11am at Amos Eaton 217 and Friday 9-11am at Amos Eaton 217.
Linyun: Tuesdays and Wednesdays 9-11am at Amos Eaton 217.

Home page: http://www.cs.rpi.edu/academics/courses/spring15/proglang/
For questions about the course, please email: proglang AT cs DOT rpi DOT edu, or use the discussion board on the LMS course site.

Announcements

PA 1 description is now available at http://www.cs.rpi.edu//academics/courses/spring15/proglang/pa1/pa1.html

PA 2 description is now available at http://www.cs.rpi.edu//academics/courses/spring15/proglang/pa2/pa2.html

PA 3 description is now available at http://www.cs.rpi.edu//academics/courses/spring15/proglang/pa3/pa3.html

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/26	Introduction to programming languages: history, syntax, semantics, essentials, paradigms. Logic programming: introduction, Horn clauses	Introduction, PLP Chapter 11 Part A rainy.pl
01/29	Logic programming: predicate calculus--Programming Assignment 1 Due 02/18	PLP Chapter 11 Part B family.pl	20%
02/02	Snow cancellation
02/05	Prolog: resolution, unification, search, backtracking, cut, lists	All PLP Chapter 11 Part C append.pl cut.pl cut2.pl cut3.pl cut4.pl cut5.pl loop.pl not2.pl
02/09	Prolog: arithmetic, equalities, I/O, meta-interpreters, natural language parsing, difference lists	All PLP Chapter 11 Part D browse.pl crossword.pl nestedloop.pl sentences.pl sentences2.pl sentences3.pl
02/12	Declarative programming: accumulators, difference lists	All CTM Chapters 3.4.3---3.4.4 rainy.oz append.oz accumulators.oz accumulators.pl dlists.oz dlists.pl
02/19	Lambda calculus: alpha-renaming, beta conversion, applicative and normal evaluation orders, Church-Rosser theorem, combinators	PDCS Chapter 2 Part A functions.oz
02/23	Higher order programming, Oz -- Programming Assignment 2 Due 03/11	All PDCS Chapter 2 Part B PA 2 combinators.oz eta.oz hop.oz lambda-booleans.oz lambda-numbers.oz rec.oz seq.oz	20%
02/26	Introduction to programming concepts: lists, pattern matching, correctness, complexity	All CTM Chapter 1.1-1.11 comb.oz lists.oz pascal.oz scope.oz
03/02	Declarative programming, grammars, syntax and semantics.	All CTM Chapter 2.1 dataflow.oz gpascal.oz length.oz map.oz
03/05	Single-assignment store, kernel language syntax	CTM Chapters 2.2 and 2.3 single-assignment.oz
03/09	Kernel language semantics: concepts, abstract machine	CTM Chapters 2.4.1-2.4.2 foldr.oz scope2.oz kernel.oz
03/12	Kernel language semantics: non-suspendable, suspendable statements, closures	CTM Chapters 2.4.3-2.4.5
03/16	Review for Exam I	gen_numbers.pl gen_numbers.oz
03/19	Exam I		20%
03/30	From kernel to practical language, exceptions	CTM Chapters 2.6-2.7 pdf pptx
04/02	Exam I analysis
04/06	Memory management, tail-form optimization, garbage collection	CTM Chapter 2.5 in pdf in ppt memleak.oz
04/09	Iterative computation, higher order programming, abstract data types	CTM Chapters 3.1-3.2,3.6-3.7 in pdf in ppt sqrt.oz stackADT.oz fold.oz
04/13	State, object-oriented programming, inheritance, polymorphism	All CTM Chapters 6.1-6.4,7.1-7.2 in pdf in ppt oop.oz c.java c1.java c2.java c3.java
04/16	Actors: a model of concurrent computation -- Programming Assignment 3 Due 05/01	PDCS Chapter 4A in pdf in ppt OOP Section 7.3.3 in pdf in ppt Programming Assignment #3 in pdf	20%
04/20	SALSA concurrency: actor creation, asynchronous message passing, state encapsulation, token-passing continuations, named tokens, join blocks, first-class continuations	All PDCS Chapter 9A in pdf in ppt HelloWorld.salsa Fibonacci.salsa TokenCellTester.salsa CellTester.salsa Cell.salsa Calculator.salsa
04/23	SALSA distribution and mobility: universal naming, location-transparent communication, actor migration	PDCS Chapter 9 Part B in pdf in ppt dist_examples.zip
04/27	Concurrent and distributed programming patterns	PDCS Chapter 9 Part C in pdf in ppt Fibonacci.salsa
04/30	Declarative concurrency	CTM Chapter 4 in pdf in ppt dconcurrency.oz
05/04	Dynamic and static typing, parameter passing mechanisms, lazy evaluation	CTM Chapters 2.8.3, 4.5, 6.1-6.4 in pdf in pptx lazy-eval.oz callbyneed.oz
05/07	Review for Exam II
05/11	Exam II		20%
	Class Participation Extra-Credit		10%

Reading Material

Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi. MIT Press 2004. Chs 1,2,3,4,6,7. (Required Textbook)

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

Programming Distributed Computing Systems: A Foundational Approach by Carlos A. Varela. MIT Press 2013. Chs 2,4,9. (Required Textbook)

URL: http://wcl.cs.rpi.edu/pdcs/

Programming Language Pragmatics by Michael L. Scott. Morgan Kaufmann Publishers 2009, 3rd Edition. Ch. 11. (Recommended Textbook)

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

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

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

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 26th, 2015.