Languages and compilers
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
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.
- GNU Prolog
- Use gcc for C code. Turn on all warnings.
- Haskell. I recommend using Hugs for learning Haskell.
- Ocaml. Note that ocaml 3.04 is
installed on the CAS servers (in /usr/local/bin); this is fine for
getting the assignments done. The latest version of ocaml is 3.07+2,
but it is not necessary to use this.
- Java. Java 1.4 is already
installed on all CAS machines.
- You can use either free pascal
or use one of the undergraduates machine with Pascal installed on it.
This is now installed on birkohff (a Sun) and penguin (linux). To
run this properly you should
- add /usr/local/mercury-0.11.0/bin to your PATH,
This can be done (if you use a csh-based shell) via
set path = ($path /usr/local/mercury-0.11.0/bin)
in your .cshrc (in your home directory). Something similar can
be put in your configuration
if you use a sh-based shell.
- add /usr/local/mercury-0.11.0/man to your MANPATH,
- and add /usr/local/mercury-0.11.0/info to your INFOPATH.
- You may also want to add the following lines to the `.emacs' file in your home directory (if you are an emacs user):
(setq load-path (cons (expand-file-name
(autoload 'mdb "gud" "Invoke the Mercury debugger" t)
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
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!!
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: