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:

  1. Understanding of a broad range of programming language concepts, including those found in most popular programming languages, in a single mathematical framework.
  2. 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.
  3. Ability to give a mathematically precise definition of the statics (type system) and dynamics (execution behavior) of a programming language.
  4. 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.
  5. Ability to implement an interpreter for a broad range of programming languages that is derived directly from its defined syntax, statics, and semantics.
  6. 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 language design.

Pre-requisites
(15150) and (15251 or 21228)

Credits
This is a 12 unit course.

Place and time

Mondays and Wednesdays 10:00 to 11:15 Room 2147 lectures
Thursdays 10:00 to 10:50 Room 2147 recitations

Schedule

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.

Staff

Giselle Reis (Instructor)

E-mail: giselle@cmu.edu


Assessment

Grading

Getting the Assignments

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 template. 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:

Type your solutions for the written part in the file hwX.tex.

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 material.

The zip file needs to be submitted to the programming part of the assignment on Gradescope.

The pdf file needs to be submitted to the written part of the assignment on Gradescope. Submissions that are in another format or badly typed will be penalized.

Tools

Textbook
Robert Harper, Practical Principles for Programming Languages (Second Edition). Cambridge University Press, 2016.
Please see the PFPL Home page for corrections and commentary on the text.

Software
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) version 110.97.

LaTeX
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 math.

Policy

You are expected to comply with the university policy on academic integrity (see also The Word and Understanding Academic Integrity).

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 student-counselling@qatar.cmu.edu. Consider reaching out to a friend, faculty or family member you trust for help.

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.