15-312: Foundations of Programming Languages (Fall 2021)
This course introduces the fundamental principles of programming
language design, semantics, and implementation. For more information
on the course philosophy, read Why
Study Programming Languages?.
After completing this course you will have acquired the
following knowledge and skills:
Understanding of a broad range of programming
language concepts, including those found in most popular
programming languages, in a single mathematical framework.
Understanding of the concepts of abstract syntax, and the
binding and scope of identifiers in a program. Be able to
prove properties of languages by structural induction,
respecting renaming of bound identifiers.
Ability to give a mathematically precise definition
of the statics (type system) and dynamics (execution behavior)
of a programming language.
Mastery of the concept of safety for a programming
language, be able to prove that a language is safe, or
derive a counterexample to its safety.
Ability to implement an interpreter for a broad range of
programming languages that is derived directly from its
defined syntax, statics, and semantics.
Understanding of how to integrate multiple features in a
language and ensure that the combination is sensible.
It is not a goal of this course to provide a survey of
popular languages, as doing so has no enduring educational
value, and would only reinforce oft-repeated mistakes in
(15150) and (15251 or 21228)
This is a 12 unit course.
Place and time
Mondays and Wednesdays
10:00 to 11:15
10:00 to 10:50
In the table below, recitations and homework due days are in blue, exams are in red and the upcoming activity is green.
Gray days are in the past or have no lectures.
The writeup and starter files for each assignment are in a
zip file linked on the schedule above.
Uncompressing this file will create the directory
assnX with the starter code and a LaTeX
If you need to download these files again, be
careful not to overwrite your work!
To see the instructions, go to the written
directory and type make. This compiles the files:
assnX.pdf: the instructions for the
hwX.pdf: your solutions for the written
part of the assignment
Type your solutions for the written part in the file
Submitting the Assignments
The handout contains Makefiles to help you organize your
files for submission. Typing make in the
top-level directory will create the file
handin.zip with the programming part.
Typing make in the written directory will
compile the LaTeX into a pdf.
If you need help using this Makefile, ask the course staff.
The zip file must contain the solutions for the coding
part. The pdf must contain the solutions for the
written part. It is your responsibility to
ensure that the generated files contain the correct
The zip file needs to be submitted to the
programming part of the assignment on
The pdf file needs to be submitted to the written part of
the assignment on
Submissions that are in another
format or badly typed will be penalized.
The programming language we will use for this course is SML (Standard ML). There
are different compilers (i.e. implementations) for SML, but your code
will be tested with
Standard ML of New Jersey (or SML/NJ)
Your written assignments must be written in LaTeX. If you have never used
LaTeX before, contact the course staff.
There are various tools for editing and compiling LaTeX. If you do not
want to install anything locally, you can use one of the web-based ones,
such as Overleaf. If
you use one of those tools, upload all files in the latex
directory of the handout.
If you want to know what is the LaTeX name for a symbol, you can use Detexify.
If you have not memorized all symbols yet, Mathcha can help you type
Collaboration is regulated by the whiteboard policy: you can bounce
ideas about a homework with other students, but when it comes to typing
it down for submission, you are on your own. You are not allowed to use
notes, files, pictures, etc, from any previous discussion nor previous
versions of this course.
And remember not to ignore your inner voice when it says “That’s
probably not the best decision...”.
An Invitation to Students with Learning Disabilities:
Carnegie Mellon University is committed to providing reasonable
accommodations for all persons with disabilities. To access
accommodation services you are expected to initiate the request and
submit a Voluntary Disclosure of Disability Form to the office of Health
& Wellness or CaPS-Q. In order to receive services/accommodations,
verification of a disability is required as recommended in writing by a
doctor, licensed psychologist or psycho-educational specialist. The
office of Health & Wellness, CaPS-Q and Office of Disability Resources
in Pittsburgh will review the information you provide. All information
will be considered confidential and only released to appropriate persons
on a need to know basis.
Once the accommodations have been approved, you will be issued a Summary
of Accommodations Memorandum documenting the disability and describing
the accommodation. You are responsible for providing the Memorandum to
your professors at the beginning of each semester.
Take Care of Yourself:
Do your best to maintain a healthy lifestyle this semester by eating
well, exercising, getting enough sleep and taking some time to relax.
This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. You are not
alone. There are many helpful resources available on campus and an
important part of the college experience is learning how to ask for
help. Asking for support sooner rather than later is often helpful.
If you or anyone you know experiences any academic stress, difficult
life events, or feelings like anxiety or depression, we strongly
encourage you to seek support. Counseling and Psychological Services
(CaPS-Q) is here to help: call 4454 8525 or make an appointment to see
the counselor by emailing
Consider reaching out to a friend, faculty or family member you trust
If you or someone you know is feeling suicidal or in danger of
self-harm, call someone immediately, day or night at 5554 7913. If the
situation is life threatening, call 999.