Honors Programming Languages

G22.3110 .01
Fall 2002

Monday-Wednesday 3:30 pm - 4:45 pm
Room 102, Warren Weaver Hall


Professor Edmond Schonberg


Instructor: Edmond Schonberg (schonberg@cs.nyu.edu) Room 410, Warren Weaver Hall.

Office hours: Monday-Wednesday 5:00 to 6:30 pm, and by appointment.

Teaching Assistants: TBA

Objectives

The study of programming languages has two main components: on the pragmatic side it relates to Software Engineering (what is the best programming tool for this particular task?), on the theoretical side to models of computation, formal semantics and the theory of types. In this course we will try to balance these concerns by examining in depth several widely-used contemporary languages, and studying as well some of the more formal methods used to describe their structure and semantics.

We will address the pragmatic component by discussing imperative languages such as Ada95, C++, Java, and some of their ancestors. We will examine their type systems, the tools they provide for Programming-in-the-large, their support for concurrency, and mechanisms for object-oriented programming. We will also examine functional languages, particularly Scheme and ML, in a similar light.

We will examine more formal methods through the Lambda Calculus, an introduction to Denotational Semantics, and a glimpse of Type Theory, in particular in connection with Object-Oriented programming and information hiding.

Finally, we will examine some less-widespread languages that have intriguing useful features and a dedicated user-community, such as APL and its successors, and PYTHON.

Course Work

There will be programming assignments in several languages, as well as paper assignments and a final examination.

Textbooks

required:

John Barnes: Programming in Ada95

Bjarnes Stroustrup: The Design and Evolution of C++

Paulson: ML for the working Programmer

There is abundant material on the web on the other languages we will discuss. We will also distribute readings from Computing Surveys and other journals.

Class list

All students should register themselves with the class list, which is used for all technical discussions concerning the course. To register, go to the following web page, and follow the instructions:

cs.nyu.edu/mailman/listinfo/g22_3110_001_fa02

You can also subscribe by sending an e-mail message to majordomo@cs.nyu.edu. The contents of the message should be the single line:
     subscribe g22_3110_001_fa02
you will be notified in return that you are a list participant. Please send all your questions to this list (not to the instructor) so that everyone can participate.
Lecture 1. The variety of programming languages. Imperative, functional, and declarative languages. A brief history.

class notes (powerpoint)
Lecture 2 Introduction to Ada.

class notes
Lecture 3 Introduction to Ada (cont.).
Readings : in addition to the corresponding chapters in Barnes, you will find the "Ada 95 Rationale" a useful overview of the design principles of the language. It can be accessed at Adapower under Reference materials.
Lecture 4 Composite types. discriminated types. Variants vs. object-oriented programming.
class notes
Lecture 5 Variants and storage allocation. Access types, pointers and their problems, controlling allocation and deallocation in Ada and C++.
Readings : Ada RM, secs. 3.10.2, 13.11. Stroustrup chapter 10.
Lecture 6 Generic programming in Ada and C++. Type and class parameters, visibility and name capture, instantiation.
Readings : Ada RM ch. 12, Barnes ch. 17, Stroustrup ch. 15.
class notes
Lecture 7 The highlights of C++ : overloading.
Lecture 8 Inheritance, polymorphism and dynamic dispatching in C++ and Ada.
class notes
Lecture 9 Exceptions: defining, throwing, handling.
class notes
Readings : Ada RM ch. 11, Barnes ch. 14, Stroustrup ch. 16.
Lecture 10 Concurrency: tasks and threads. Creation, activation, synchronization. Rendez-vous, conditional communication. Data-driven synchronization, Java threads.
Readings Barnes ch.18, and the Super-Sieve example.
class notes
Lecture 11 functional languages (1): pure LISP.
class notes
Lecture 12 the LISP interpreter. Meta-circular definition, binding disciplines.
Lecture 13 ML : the basics.
class notes
Lecture 14 ML : type type model, type inference and unification. Datatypes.
Lecture 15 The untyped lambda calculus.
class notes
Readings: Hudak (ACM Computing Surveys, 21,3 1989). Scott: Programming Language Pragmatics, section 11.2.4.
The online ML tutorial
Lecture 16 ML: programming in the large, imperative constructs.
class notes
Readings: Paulson chapters 7 and 8.
Lecture 17 Reasoning about functional programs.
Readings: Paulson chapter 9.
Lecture 18 Introduction to denotational semantics: simple functional constructs.
class notes
Lecture 19 Denotational semantics: state, local variables, continuations.
Lecture 20 Continuations in functional languages. Call/cc and its uses.
Lecture 21 APL and J : functional programming in an algebraic framework.
class notes
Lecture 22 inner product, outer product, explicit definitions in J. Formal proofs of equivalence in APL and J.
Lecture 23 Logic programming and Prolog
class notes
Extra lecture (Robotics) Java and Mindstorms
slides

Assignments

Assignment 1: read, compile and test the Sylvan sorter program in Barnes (program P2). Translate it into your other favorite language.

Assignment II
Assignment III (C++, parsing ambiguous languages)
Assignment IV (Scheme, symbolic differentiation)
Assignment V (ML, satisfiability solver)

Using Ada

You can use the GNAT compiler on all servers at NYU. All the needed files are in /usr/local/pkg/gnat/bin/, so you should place this directory in front on your path. If your test program is called numbers.adb, you create an executable for it simply by writing:

gnatmake numbers.adb

which you can execute by writing: ./numbers

If you want to compile a single file, you can write:

gcc -c numbers.adb

You can also install gnat on your personal computer, by downloading the appropriate version from the NYU ftp site, ftp cs.nyu.edu, directory pub/gnat.
Finally, you can install and use the ObjectAda compiler that comes with the Barnes text.
Copious information on Ada, including programming environments, software, and tools, can be found at Adapower