CS 4536, Programming Languages
C Term, 2012
Prof. Joshua D. Guttman

Email: last name@wpi.edu
Office: FL 137

Class meetings: Lower Perrault Hall, T F, 1-2:50


 

Course Description
Personnel
Textbook
Recommended Background
Grading
Projects
Language







 

The two scheme programs illustrating call/cc, or more specifically prompt and fcontrol are available here (fringe.scm) and here (ds_threads.scm.scm) .

The extra credit problems, are due noon Thursday, 1 March, are here now.

Project 4, due midnight (end of) Wednesday, 29 Feb, is here.

Three refcards for the OCaml language, compilers and tools, and standard library were created by the OCamlPro consulting company.

 

Project 3, due midnight (end of) Tuesday, 21 Feb, is here.

 

Project 3, due midnight (end of) Tuesday, 21 Feb, is here.

 

Exercise 2, due midnight Sunday, 12 Feb, is here.

 

Reading assignment for Tuesday, 7 Feb: Read Sections 1-3.3 of A Theory of Type Polymorphism in Programming Languages. Then read the very short Principal type-schemes for functional programs. Finally read Section 5 of A Theory of Type Polymorphism....

 

Code for the compiler and VM, including support for functions, recursion, and tail-recursive call, is here. A gzipped tar file is here. Remember to use dofile on the init.lua init file.

 

Project 2, due Monday 6 Feb., is here.

 

Project 1, due Friday 27 Jan, is here.

 

Code for the simplest compiler and VM are here. Remember to use dofile on the init.lua init file.

 

Exercise 1, due midnight Saturday 21 Jan, is here.

 

Warning: This syllabus is subject to change.

 

Course Description

CS 4536. PROGRAMMING LANGUAGES. Cat. II This course covers the design and implementation of programming languages. Topics include data structures for representing programming languages, implementing control structures (such as functions, recursion, and exceptions), garbage collection, and type systems. Students will be expected to implement several small languages using a functional programming language.

Recommended background: CS 2303, CS 3133, and experience programming in a functional language (as provided by CS 1101 or CS 1102).

Undergraduate credit may not be earned for both this course and CS 536.

Meeting jointly with CS 536,

graduate Programming Language Design. CS 536 will also include 4 seminar-style meetings in March-April, and an additional substantial project.


 

Main topics

  1. Architecture of byte coded implementations, especially representing procedures and environments
  2. Control structures such as conditionals, procedure call and return, and tail recursion; method dispatch; lazy evaluation
  3. Static type systems
  4. Data types, abstractions, and modules.
  5. Memory management and garbage collection
  6. Domain-specific languages and support for special data types; Logic programming
  7. Advanced control structures via continuations: backtracking and multi-threading. Message-passing and distributed programming.

 

Personnel

  • Professor Joshua D. Guttman
    C term Office hours in FL 137:
    • Tuesday 4:00 -- 5:00
    • Thursday 10:00 -- 11:00
    • Thursday 1:00 -- 2:00
    • Friday 10:00 -- 10:45 as needed (check ahead)
    D term office hours for cs 536
    • Tuesday 3:00 -- 4:30
    • Thursday 1:30 -- 2:30
    • Friday 10:00 -- 10:45 as needed (check ahead)
    I am also available at other times; please set things up by email.
    last name @ wpi.edu
  • cs 4536 Teaching Assistant Will Coon
    C term Office Hours: Fuller Labs B16
    • Monday 10:30 -- 12:00
    • Wednesday 4:30 -- 6:00
    Check by email for other times.
    First name last name @ wpi.edu, no punctuation.
  • cs 4536 Teaching Assistant Theo Giannakopoulos
    C term Office Hours: Fuller Labs Alas Lab B17
    • Monday 3:00 -- 4:00
    Check by email for other times.
    First initial, giannak @ wpi.edu, no punctuation.

Class Mailing Lists: To reach the members of the cs4536 staff, please send mail to the staff mailing list. It's cs4536, followed by a hyphen, and the word "staff". It's a mailing list at cs.wpi.edu. The circumlocution is to avoid spam.

To reach all students in the class, as well as the staff, please substitute "all" for "staff". Send email to the whole class very sparingly.

Email subject line: cs4536. In all email messages connected with the class, please include the string cs4536. This allows my email filters to put your message in the right place, so that I can see it and respond fast.


 

Textbook

Required Textbook:

There is no required textbook for this class.


Additional materials:

A very useful text on

Programming Languages: Application and Interpretation,
by Shriram Krishnamurthi, is available free on line.

Also free and on line, and focused on type systems and semantics, is

Practical Foundations for Programming Languages,
by Robert Harper, is available here.

Not free, but excellent, are

The Formal Semantics of Programming Languages: An Introduction,
by Glynn Winskel, MIT Press, 1993, on semantics; and

Types and Programming Languages,
by Benjamin Pierce, MIT Press, 2002, on type systems.

Recommended Background


 

Grading

There will be no exams in this class. There will be five programming projects/homeworks, of which the last will be the largest. There are also two "exercises," meant to introduce you to the programming languages we'll be using in the class.
Exercise 1 5%
Project 1 15%
Project 2 15%
Exercise 2 5%
Project 3 15%
Project 4 15%
Project 5 25%
Participation     5%

Your final grade will reflect your own work and achievements during the course. Any type of cheating will be penalized in accordance with the Academic Honesty Policy.

Students are expected to study code and examples in advance of each class, and to participate in class. Class participation will be taken into account when deciding students' final grades.


 

Programming Projects

There will be five programming projects. They are intended to give you a practical mastery of the course material. There will also be two introductory "exercises" to give you some initial familiarity with the languages we'll be using for implementation here.

Programming projects are individual work. You may not share code; you may not ask someone to look at your code and help you correct it (except the TAs and professor); you may not assist a student. Any type of cheating will be penalized in accordance with the Academic Honesty Policy.

Late policy for projects: You can hand in projects late. But there's a cost associated. Each 24 hours (or part thereof) late will cost you 10%.

Thus, if you hand something in that would have been worth 93 on time, but it's 36 hours late, that means that you only get 93(.9)(.9)=75.

So, yes, you can hand things in late, but it's expensive, and very expensive if you do it often.

Exercise 1: Due Saturday, 21 January at midnight. Use turnin. Let me know if you didn't get your account and turnin password. Description is at exercise 1 writeup. Starter code is in this lua file. Examples etc are zipped together in this zip file. Be sure to look through a few examples, and test your code against them.

 

Project 1: Due Friday, 27 January at midnight. Use turnin. Description is at project 1 writeup. Starter code is in this directory of Lua code. Starter code, examples, etc are zipped together in this zip file.

 

Project 2: Due Monday, 6 Feb at midnight. Use turnin. The full description is now at project 2 writeup. Use the code for the system in this gzipped tar file of Lua code. The individual files are also available here.

 

Exercise 2: Introduction to OCaml. Due Sunday, 12 Feb. at midnight, end of the day. Use turnin. Let me know if you didn't get your account and turnin password. Description is at exercise 2 writeup. Starter code is in this directory. Examples and source etc are tarred and gzipped together in this tar file. Be sure to look through a few examples, and test your code against them.

 

Project 3: Due Tuesday, 21 Feb at midnight. Use turnin. The full description is now at project 3 writeup. Use the code for the system in this gzipped tar file of OCaml code. The individual files are also available here.

 

Project 4: Due Wednesday, 29 Feb at midnight. Use turnin. The full description is now at project 4 writeup. Use the code for the system in this gzipped tar file of OCaml code. The individual files are also available here.

 

Extra credit problems: Due Thursday, 1 Mar at noon. Use turnin. The description of the four problems is now at the extra credit writeup. Use previously distributed program code.


 

Programming Languages: Lua and OCaml

The programming projects will be done using Lua and OCaml. Lua is a very simple programming language, designed to allow the maximum computational content to be expressed with a minimum of syntactic clutter and verbosity. It is a procedural language like C and Java, but has excellent support for recursion and higher-order functions. In this regard it is as good as Scheme.

OCaml is not a simple language. It is sophisticated and syntactically a bit tricky. But it is an outstanding implementation of many of the central programming languages ideas of the last thirty years. In particular, its treatment of types, pattern-matching, and modules are excellent. I use it as an exploratory programming language because the type system helps me clarify ideas, and the type checking in the compiler helps me get them consistent.

Three refcards for the OCaml language, compilers and tools, and standard library were created by the OCamlPro consulting company.

I will schedule Lua Labs early in the term, and I will write up a small guide to Lua. One of the advantages of Lua is that it has fairly few gotchas. Three main gotchas are:

  • Forgetting the return statement. If a function finishes without encountering a return statement, it returns nil. This is the most annoying single thing about the language, I think.
    When your code is behaving buggily, always check that you haven't left out a return statement.
    return doesn't make the function return, it only tells it what value it should return if in fact it is returning.
  • Forgetting local when declaring a local variable. Inside a function,
    local varname = initval 
    declares a local variable named varname. Nothing of the same name in any other scope (or recursive call) can be affected. Leave out the word local, and things will go haywire.
  • You must use the word then to start the then-clause of a conditional. Unlike C and Java, a conditional takes the form

    if condition then statement1 else statement2 end

    The else part is optional.
Also, remember that x == e is the boolean expression that's true in case the value of e is the same as the value of x.

OCaml labs will come later in the term.

You can download Lua for the main types of system here, and Windows users often like Lua for Windows.

I will put three copies of the Lua Reference Manual on reserve in the library, but I mainly use the online version. They have a very nice book on Programming in Lua. The version that's free on line is not 100% up-to-date, but it is totally adequate for the parts of the language we'll use in this course.

A recent survey of the popularity of programming languages from TIOBE reports for October 2011 that Lua has surged in popularity during the past year. It has risen eight positions, and is now 16th in popularity.

We have gathered some instructions, and Lua Lab times, and pointers to some code, at

Page for CS 4536 Lua code


Some of the programming projects will be done using Lua. Lua is a very simple programming language, designed to allow the maximum computational content to be expressed with a minimum of syntactic clutter and verbosity. It is a procedural language like C and Java, but has excellent support for recursion and higher-order functions. In this regard it is as good as Scheme.

A recent survey of the popularity of programming languages from TIOBE reports this month (October 2011) that Lua has surged in popularity during the past year. It has risen eight positions, and is now 16th in popularity.

How to get Lua

You can download Lua for the main types of system here, and Windows users often like Lua for Windows. You may use either Lua version 5.1.4, the current stable version, or the newly released version 5.2.

Windows users often like to use the Scite editor, and Macintosh users often like TextWrangler. Both are freely available, and easy to find by googling. I like Emacs, using the lua-mode available on the web. It gives excellent support for running Lua interactively as a subordinate process under Emacs.

I will put three copies of the Lua Reference Manual on reserve in the library, but I mainly use the online version. They have a very nice book on Programming in Lua. The version that's free on line is not 100% up-to-date, but it is totally adequate for the parts of the language we'll use in this course.

Learning Lua

We will use only the core of Lua. That should make it easier to master the part that matters to us now. If you find Lua useful, you may want to learn more later. And in fact it can be very useful, since it has good, platform-independent access to system resources; since it is easy to embed into programs written primarily in other languages such as C, and vice versa; and since it's convenient for user configuration.

I will schedule Lua Labs early in the term, and I will write up a small guide to Lua.

Lua Labs:
Before coming to a Lua Lab, please download and install Lua on your system. It's available here. Please also retrieve and save the files init.lua and programs/sorting.lua. That will give you a starting point. If possible, try to run those files, and add a few examples. Lua labs are currently scheduled in FL 137 for:
  • 17 Jan, 3:00 -- 4:00
  • 19 Jan, 10:00 -- 11:00
  • 19 Jan, 1:00 -- 2:00