McMaster University
CAS 706

Lectures  Extra material  Languages and compilers  Assignements Presentations

Lectures and Tutorials

Tuesday, Wednesday and/or Friday 3:30-5:00 in ITB/222. Normally the class will be Tuesday/Wednesday, except for 1 week in 4, where the class will be on Friday because I have a meeting those Wednesdays that I have to go to.

Textbooks and web materials

Textbook section to be filled in later.
There is some very useful material at the following pages: When in the mood to look at weird languages, I definitely recommend For specific languages, I recommend: All the sites above contain executables and lots of documentation.


Assignment 2

Lambda-calculus interpreter. To be done in Pascal, ocaml, java and mercury.
Use the following term language:
	var :== any sequence of lower case letters
	int :== any integer
	op1 :== - | not
	op2 :== + | * | and | or
	term :== var | int | bool | Apply term term | Abs var term |
	    let var = term in term | op1 term | op2 term term |
		if term then term else term fi

You should first write down the evaluation rules for your language. Since the language is untyped, your evaluator can get *stuck* - make sure to handle this properly! You should also be providing some test cases for your interpreter - make sure to test higher-order functions as well as cases that get stuck and cases that work but would be rejected in a typed language. I want you to implement the (abstract) language above - you may ''rearrange'' the grammar in any equivalent way you want if it eases the implementation.

Assignment 3

Typed lambda-calculus interpreter. To be done in C, ocaml, Java and your choice of prolog or mercury.
Use the same term language as for assignment 2, but add a type system to the language. All your terms should be typed, and your need to modify your interpreter to work on the typed terms. You should verify that all terms that are properly typed evaluate (to a value of the right type), and that all terms that cannot be typed also get stuck if ealuated with the untyped interpreter. The main part of this assignment is the type inference engine. This is not difficult, but does require implementation of unification; look at lesson 13 at this page. Do not worry about polymorphism!!

Additional resources

Lectures 0-5 (see bottom of page for links) are very useful and topical. The slides from this course on programming languages are also topical.

Googling for "introduction to lambda calculus" and "lambda calculus interpreter" yield a lot of useful resources


These are in presentation order:

Jan 2003