UMass logo
CMPSCI 630 (691F)
Programming Languages
Spring 2009

Programming Assignment 1

Big Picture

The purpose of this assignment is to bridge the gap between the formal syntax and semantics specifications that we have been studying thus far and the more practical concerns associated with parsing, type-checking and executing programs.

We give the name L{num str fun prod sum pat} or Lnsfpsp to the language defined by combining the grammar for L{num str} (p. 68 in Harper's book) with the extensions for L{num str fun} (p. 106), nullary and binary products (p. 134), binary and nullary sums (p. 139) and L{pat} (p. 148). Your assignment is to implement a parser, a type-checker and a simulator for Lnsfpsp, as detailed below.


Complete the following:

  1. Based on the combined grammar for Lnsfpsp, which you may need to disambiguate, and using the static semantics for the various components of Lnsfpsp, write a parser and type-checker for Lnsfpsp. The parser should take concrete syntax for a (purported) Lnsfpsp program as input and produce the corresponding abstract syntax as output, or report an error. The type-checker should take abstract syntax as input and determine what type can be assigned to it, or report an error. In effect, this is an automation of applying the inductive type derivation process.

    Your parser/type-checker should indicate the location and type of errors (syntax or type mismatch) found in a code sample.  After reporting an error, your parser/type-checker may stop processing the input; no error recovery is necessary.

    You are encouraged to write your parser and type-checker in Scala, preferably relying primarily (or better, entirely) on its functional programming features. (Documentation for the current version of Scala can be found on the Reading Assignments page of the course web site, and Scala is available on the EdLab machines -- although you may prefer to use your own copy installed on your own machine.) Ideally, you should write your parser in the "Combinator Parsing" style described in Chapter 16 of "Scala By Example (2008)" -- for some unknown reason this chapter isn't included in the current (2009) version of "Scala By Example (2009)". Exceptional programs will receive extra credit. Code written in other styles and/or other languages, such as Java, will be accepted but is discouraged and will receive somewhat less credit. Code written in a combination of Java and Scala will receive a better reception, although still not as good as a purely Scala version -- the higher the percentage of Scala the better.

  2. Based on the dynamic semantics for the various components of Lnsfpsp, write a simulator for Lnsfpsp. The simulator should take abstract syntax as input and produce a final value (or error) as output. In effect, this is an automation of applying the inductive judgements of the dynamic semantics. The same considerations regarding the choice of programming language and style, except for the encouragement to use the "Combinator Parsing" style, that applied to the other part of the assignment apply here.


You may find it helpful to complete this assignment incrementally, starting with some minimal subset of Lnsfpsp and then gradually adding additional features.

No later than a week before the due date, example Lnsfpsp programs will be made available for your use in testing your parser, type-checker and simulator. You are, of course, encouraged to create, and share, your own examples. (Note that successfully processing the examples does not necessarily mean that your parser, type-checker and/or simulator are correct.)

Submitting Your Assignment

The following materials should be submitted as a single ZIP file ( via email attachment to the instructor:

  1. Source files for parts 1 and 2. Include any special instructions for running your program. Do not include .class files.

E-mail the instructor

Last modified: Wed Mar 25 18:00 EDT 2009