Languages and compilers
Monday and Thursday 14:00-15:20 in ITB/222. First lecture will be
Monday Spetember 12th.
Design, definition and implementation of programming languages. Programming
language paradigms; syntax, attribute grammars, typing; axiomatic, operational
and denotational semantics; correctness proofs; implementation techniques,
virtual machines; design and implementation of Domain-Specific Languages. code
generation and optimization
Course Pages: http://www.cas.mcmaster.ca/~carette/CAS706/W2011.
This is where you will find further information, announcements and useful
Electronic versions of the
assignment sheets will also be kept there.
It is the student's responsibility to be aware of the information in the course Web pages, and to check
regularly for announcements.
40% assignments, 35% in-class presentation, 25% final exam.
All examinations in this course will be Closed Book. That is, no
written or printed material nor a calculator may be used during the
The instructor reserves the right to conduct any deferred exams orally
The major topics are most likely to be presented in an interleaved manner
that allows applying theory in practice with less delay. The course material
will be chosen from a selection of the topics below
Definite attention will be paid to all language paradigms, with an emphasis on
the appropriateness of each language to particular tasks.
Students can expect assignments in up to a dozen languages, from the likes
of C, Fortran, Java, C++, Ocaml, Haskell, Prolog, Scheme, Mercury, Perl,
Python and Ruby. Additional languages will be used for illustration purposes.
Knowledge of logic (ex: CAS 701, taken concurrently is ok) is required.
The assignments below are not final, but instead a copy of those
for the version of the course I last offered. This year's assignment
will be similar.
- Programming language paradigms
- Structuring methodology
- Programming language design goals and description tools
- Syntax description beyond context-free grammars
- Typing systems
- Attribute grammars
- Lambda Calculus as unifying paradigm
- Axiomatic semantics
Principles, use, and limitations of Hoare logic
- Operational semantics
- Denotational semantics
concentrating on functional and imperative languages
- Programming languages and correctness
- Proving consistency of axiomatic, operational and denotational
semantics of the same language
- Program correctness proofs using different semantics
- Additional (advanced) topics, student selected
- ex: continuations, aspect-oriented programming, dependent types
Required: Types and Programming Languages Benjamin C. Pierce
- Parametrized quicksort.
Languages: D, Ruby, Clojure, Prolog.
- Lambda calculus interpreter.
Languages: Lua, Scala, Haskell, lambda-Prolog.
- Typed Lambda calculus interpreter.
Languages: Go, Groovy, F#, Mozart-oz.
- Fun with scripting languages. Perl, python.
Topics to choose from (* items need to be covered). Further
topics will be added in the first 2 weeks of lectures.
- * TAPL Ch 9,11 (typed lambda calculus + extensions)
- * TAPL Ch 12,13 (normalization, references)
- * TAPL Ch 15,16 (subtyping)
- * TAPL Ch 19 (featherweight Java)
- * TAPL Ch 22 (type reconstruction - needed for assignment 3).
Examples from class.
- TAPL Ch 23 (Universal types)
- TAPL Ch 24 (Existential types, modules)
- * OO: objects, classes, inheritance, subtyping, prototypes
- * OO: overloading, overriding and method dispatch
- Domain Theory (CPOs, least and greatest fixed points, etc)
- Compiling statically typed functional languages
- Compiling dynamically typed languages
- Continuations and the semantics of goto
- Partial evaluation
- Operational semantics of Prolog
- The design of Scala's containers library
- Typeclassopedia and category-extras
- suggest a topic!
Googling for "introduction to lambda calculus" and
"lambda calculus interpreter" yield a lot of useful resources
"The Faculty of Engineering is concerned with ensuring an
environment that is free of all adverse discrimination. If there is a
problem that cannot be resolved by discussion among the persons
concerned individuals are reminded that they should contact their
Chair, the Sexual Harassment Office or the Human Rights Consultant,
as soon as possible."
The instructor and university reserve the right to modify elements of the
course during the term. The university may change the dates and deadlines
for any or all courses in extreme circumstances. If either type of
modification becomes necessary, reasonable notice and communication with the
students will be given with explanation and the opportunity to comment on
changes. It is the responsibility of the student to check their McMaster
email and course websites weekly during the term and to note any changes.
You are expected to exhibit honesty and use ethical behaviour in all aspects
of the learning process. Academic credentials you earn are rooted in principles
of honesty and academic integrity.
Academic dishonesty is to knowingly act or fail to act in a way that results
or could result in unearned academic credit or advantage. This behaviour can
result in serious consequences, e.g. the grade of zero on an assignment, loss
of credit with a notation on the transcript (notation reads: Grade of F
assigned for academic dishonesty), and/or suspension or expulsion from the
It is your responsibility to understand what constitutes academic
dishonesty. For information on the various types of academic dishonesty please
refer to the
Academic Integrity Policy
The following illustrates only three forms of academic dishonesty:
- Plagiarism, e.g. the submission of work that is not one's own or for which other credit has been obtained.
- Improper collaboration in group work.
- Copying or using unauthorized aids in tests and examinations.
Individual assignments have to be solved by one person only,
any outside source, this includes asking other people,
or using any books or information found on the web has to
be documented. In complience with the senate regulations
on academic integrity I remind you that:
People who let other people copy are as guilty as the ones who copy.
You are allowed to consult outside sources, meaning textbooks
or the web, but any use of an outside source
must be documented. Similarly, group assignments must
be solved by members of that group only, and the above policies
apply as well.
In the case the instructor or a TA
has the impression that an assignment is copied, the instructor can
ask the corresponding students to explain exactly how the assignment
was prepared and take appropriate actions.
In this course we will be using Avenue. Students should be aware that, when
they access the electronic components of this course, private information such
as first and last names, user names for McMaster e-mail accounts, and
program affiliation may become apparent to all other students in the same
course. The available information is dependent on the technology used.
Continuation in this course will be deemed consent to this disclosure. If you
have any questions or concerns about such disclosure please discuss this with
the course instructor.
Last revised: Aug 20011