Computer Science 3MI3 - Principles of Programming Languages
2019 Course Homepage
Table of Contents
- 1. Deprecation notice
- 2. Lecture and tutorial notes
- 3. Course texts
- 4. Course outline
- 5. Assorted resources
1 Deprecation notice
As of August 2020, this page has been deprecated. Class communications and course work have been removed.
Notes and other information are left for reference.
Future iterations of this course have their homepage hosted at https://armkeh.github.io/principles-of-programming-languages.
2 Lecture and tutorial notes
Lecture notes are provided as reveal.js
slides,
handout-style (printer-friendly) PDFs, and
the original Org mode document
from which the other formats are generated.
Make use of the format(s) that work best for you.
2.1 Lecture notes
- 1 – Introduction
- 2 – Formal descriptions
- 3 – Two Language Kernels
- 4 - Introduction to types
- 5 - Semantics of While
- Other lecture content
- Sept. 9th Oz notes
- Sept. 12th Ruby and F# notes
- Sept. 19th lecture sample code for custom lists
- Sept. 30th, Oct. 2nd testing out memory models
- Nov. 11th, written notes on attribute grammars
- Nov. 13th, written notes for midterm 2 review
- Nov. 18th and 20th, written notes on types
- Nov. 21st, sample Prolog code
- Nov. 25th, written notes on tail recursion
- Nov. 25th & Nov. 27th, written notes on formal semantics of SA-Decl
- Nov. 28th, Prolog interpreter
- Dec. 4th, final exam notes and draft practice
- Partial slides
- These versions of the slides were partial versions
uploaded before the full versions were complete.
- 3a – Two Language Kernels (Expressions and Memory Models)
- 3b – Two Language Kernels (The Kernels)
2.2 Tutorial notes
- Sept. 19th tutorial notes by Musa
- Sept. 24th tutorial notes by Musa
- Oct. 1st tutorial notes by Musa
- Oct. 8th, 10th, 22nd and 24th tutorial Agda demo
- Oct. 29th tutorial notes by Musa
- Oct. 31st tutorial notes by Musa
- Nov. 5th tutorial notes by Musa
- Nov. 7th tutorial notes by Musa
- Nov. 12th tutorial notes by Musa
- Nov. 21st tutorial notes by Musa
- Nov. 26th tutorial notes by Musa
3 Course texts
This iteration of the course has two recommended (not required) texts.
- “Van Roy & Haridi”
- Concepts, Techniques, and Models of Computer Programming
- By Peter Van Roy and Seif Haridi
pdf
available through CiteSeerX.
“Dowek”
- Principles of Programming Languages
- By Gilles Dowek
pdf
available through the McMaster library.
Highly-accessible and an excellent read ♥‿♥
See 4.5 in the course outline for additional details and other useful texts.
4 Course outline
The course outline is available as a PDF. Its contents are also repeated here.
4.1 The purpose of this outline
A course outline sets the expectations for students and what they can expect in terms of the course experience they will receive, the format in which the course will be delivered and the knowledge and skills that can be gained. The outline introduces the course and the instructor and sets out the expectations of the instructor so that students are aware of how they will learn, what level of participation will be expected and how they will be assessed.
4.2 Course staff
4.2.1 Instructor: Mark Armstrong
- Email: armstmp “at” mcmaster.ca
- Website: http://www.cas.mcmaster.ca/~armstmp/
- Office: ITB-229
4.2.2 Teaching assistant: Musa Alhassy
- Email: alhassm “at” mcmaster.ca
- Website: https://alhassy.github.io
- Office: ITB-229
4.2.3 Teaching assistant: Maryam Kord
- Email: kordm “at” mcmaster.ca
4.3 Schedule
Mon | Tues | Wed | Thu | Fri | |
9:30 |
|
|
|
Tutorial 2 ABB 270 |
|
10:30 |
Lecture PC 155 |
Tutorial 1 BSB B155 |
Lecture PC 155 |
Lecture PC 155 |
|
4.4 Administration tools
This course will be administered via a combination of
- the course homepage,
- a repository for each student on the McMaster CAS GitLab server, and
- communications via McMaster email addresses.
It is the student's responsibility
- to ensure they have an account on the McMaster CAS GitLab server,
- to be aware of the information on the course's homepage and
- to check the homepage, their GitLab repo, and their email regularly for announcements and changes.
To communicate with course staff, you should use the emails listed under 4.2. Other means of communication may not be monitored (in particular, Avenue to Learn email addresses will not be monitored).
4.4.1 Disclosure of information
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 the McMaster email 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 instructor.
4.5 Resources
The course notes are intended to be self contained, but the recommended texts and several of the available resources are available free of charge, so you are encouraged to investigate them.
4.5.1 Recommended texts
These textbooks should be available at the Campus Bookstore. They are additionally available online at the included links.
- “Van Roy & Haridi”
ACM Digital Library citation:
Peter Van Roy and Seif Haridi. 2004. Concepts, Techniques, and Models of Computer Programming (1st ed.). The MIT Press.
From its abstract:
The book presents all major programming paradigms in a uniform framework that shows their deep relationships and how and where to use them together.
pdf
available through CiteSeerX. - “Dowek”
ACM Digital Library citation:
Gilles Dowek. 2009. Principles of Programming Languages. Springer Publishing Company, Incorporated.
From its abstract:
This book is an introduction to the principles around which these languages are organised: imperative constructions, functional constructions, reference, dynamic data types, objects and more.
pdf
available through the McMaster library.
4.5.2 Additional resources
These texts may be of interest, or assist if something is unclear in the notes and recommended texts.
- “SICP”; “The Wizard Book”
ACM Digital Library citation:
Harold Abelson and Gerald J. Sussman. 1996. Structure and Interpretation of Computer Programs (2nd ed.). MIT Press, Cambridge, MA, USA.
From its abstract:
With an analytical and rigorous approach to problem solving and programming techniques,this book is oriented toward engineering. Structure and Interpretation of Computer Programs emphasizes the central role played by different approaches to dealing with time in computational models. Its unique approach makes it appropriate for an introduction to computer science courses, as well as programming languages and program design.
html
available through the MIT press andpdf
available through GitHub. - “Sebesta”
ACM Digital Library citation:
Robert W. Sebesta. 2012. Concepts of Programming Languages (10th ed.). Pearson.
An encyclopedic text on the construction of programming languages.
- “Fernández”
ACM Digital Library citation:
- Fernandez. 2004.
Programming Languages and Operational Semantics: An Introduction. King's College Publications.
An introductory text covering primarily operational semantics of a simple imperative and a simple functional language.
pdf
available through the McMaster library.
4.6 Purpose and goals of this course
The undergraduate calendar description of this course is
Design space of programming languages; abstraction and modularization concepts and mechanisms; programming in non-procedural (functional and logic) paradigms; introduction to programming language semantics.
But we should be more specific.
4.6.1 Informal objectives
- Expose you to several programming languages.
- A relatively shallow but comprehensive survey.
- Focussing on general-purpose languages.
- Formally describe programming language syntax and semantics.
- An application of theory you have learned previously.
- Analyse the building blocks of languages.
- Programs can be massive entities, but they are composed of relatively few small pieces.
- Provide you with criteria by which to judge languages.
- So you can identify what languages fit what tasks.
- Examine the origins of certain languages/groups of languages.
- Historical context provides insight into why languages are designed the way they are.
4.6.2 Course preconditions
Before beginning this course:
- Students should know and understand:
- Basic concepts about integers, sets, functions, & relations.
- Induction and recursion.
- First order logic, axiomatic theories & simple proof techniques.
- Regular expressions & context-free grammars.
- Programming in imperative language
- Basic concepts of functional programming languages.
- Students should be able to:
- Produce proofs involving quantifiers and/or induction.
- Understand the meaning of a given axiomatic theory.
- Construct regular sets & context-free languages.
- Produce small to medium scale programs in imperative languages.
- Produce small scale programs in functional languages.
4.6.3 Course postconditions
After completion of this course:
- Students should know and understand:
- The basics of several programming languages.
- Formal definitions of syntax & semantics for various simple programming languages.
- Various abstraction & modularisation techniques employed in programming languages.
- Students should be able to:
- Reason about the design space of programming languages, in particular tradeoffs & design issues.
- Produce formal descriptions of syntax & semantics from informal descriptions, identifying ambiguities.
- Select appropriate abstraction & modularisation techniques for a given problem.
- Produce (relatively simple) programs in various languages, including languages from non-procedural paradigms.
4.6.4 Formal rubric for the course
Topic | Below | Marginal | Meets | Exceeds |
Familiarity with various programming languages (PLs) |
Shows some competence in procedural languages, but not languages from other paradigms |
Shows competence in procedural languages and limited competence in languages from other paradigms |
Achieves competence with the basic usage of various languages |
Achieves competence with intermediate usage of various languages |
Ability to identify and make use of abstraction, modularisation constructs |
Cannot consistently identify such constructs |
Identifies such constructs, but does not consistently make use of them when programming |
Identifies such constructs and shows some ability to make use of them when programming |
Identifies sucj constructs and shows mastery of them when programming |
Ability to comprehend and produce formal descriptions of PL syntax |
Unable or rarely able to comprehend given grammars; does not identify ambiguity or precedence rules |
Comprehends given grammars, but produces grammars which are ambiguous or which do not correctly specify precedence |
Makes only minor errors regarding precedence or ambiguity when reading or producing grammars |
Consistently fully understands given grammars and produces correct grammars. |
Ability to comprehend and produce operational semantics for simple PLs |
Rarely or never comprehends such semantic descriptions |
Usually comprehends such semantic descriptions, but cannot consistently produce them |
Comprehends such semantic descriptions and produces them with only minor errors |
Comprehends such semantic descriptions and produces them without errors |
Ability to comprehend denotational and axiomatic semantics for simple PLs |
Rarely or never comprehends such semantic descriptions |
Inconsistently comprehends such semantic descriptions |
Consistently comprehends such semantic descriptions |
Consistently comprehends and can produce some simple semantic descriptions |
4.7 Grading
The graded work for this course is:
- Weekly short homeworks, marked for completion,
- (each student is permitted to miss 2 homeworks without penalty)
fourprogramming/written answer assignments,- (Updated as of October 15th, 2019)
- two midterm examinations, and
- the final examination.
Each student's final grade will be the maximum grade among three grading schemes.
Scheme 1 | Scheme 2 | Scheme 3 | |
Homework | 10% | 10% | 10% |
Assignments | 3 * 10% = 30% | 3 * 10% = 30% | 3 * 10% = 30% |
Midterm 1 | 10% | 20% | 10% |
Midterm 2 | 20% | 10% | 10% |
Final Exam | 30% | 30% | 40% |
In this way, your best examination is weighted more heavily.
4.8 Additional statements/information
4.8.1 Missed work
A student who would like to receive accommodation
for missed academic work due to an absence
needs to complete a McMaster Student Absence Form (MSAF) on-line at
http://www.mcmaster.ca/msaf/.
When the MSAF tool asks you for the party
who should receive your request for accommodation,
enter armstmp@mcmaster.ca
.
MSAFs sent to any other email address will be ignored.
Students are reminded that they are expected to contact the instructor after filling out an MSAF.
For this course, the accomodation
- for a missed assignment will be a 4 day extension, and
- for a missed midterm will be a reallocation of
the midterm/final examination weights to
- 20% for the remaining midterm examination and
- 40% for the final examination.
No accomodation will be given for missed homework, as each student is already permitted to miss 2 homeworks without penalty.
In the case that further accomodations are required, the instructor reserves the right to conduct make-up oral examinations.
4.8.2 Academic integrity
You are expected to exhibit honesty and use ethical behavior 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 behavior 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 university.
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, located at http://www.mcmaster.ca/academicintegrity/.
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.
Your work must be your own. Plagiarism and copying will not be tolerated! If it is discovered that you plagiarized or copied, it will be considered as academic dishonesty.
Students may be asked to defend their written work orally.
4.8.3 Discrimination
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 Department Chair and the Human Rights and Equity Services (HRES) office as soon as possible.
4.8.4 Academic accomodation
Students who require academic accommodation must contact Student Accessibility Services (SAS) to make arrangements with a Program Coordinator. Academic accommodations must be arranged for each term of study. Student Accessibility Services can be contacted by phone 905-525-9140 ext.~28652 or email mailto:sas@mcmaster.ca. For further information, consult McMaster University's Policy for Academic Accommodation of Students with Disabilities.
Students requiring academic accommodation based on religious, indigenous on spiritual observances should follow the procedures set out in the RISO policy. Students requiring a RISO accommodation should submit their request to their Faculty Office normally within 10 working days of the beginning of term in which they anticipate a need for accommodation or to the Registrar's Office prior to their examinations. Students should also contact their instructors as soon as possible to make alternative arrangements for classes, assignments, and tests.
4.8.5 Course modifications
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 web sites
weekly during the term and to note any changes.
Your McMaster email is the one
with the address ending in @mcmaster.ca
.
This is a separate email address from your Avenue address.
5 Assorted resources
Suggestions for additional resources are always appreciated!
5.1 Software installation instructions
Reminder: it is generally recommended you use Ubuntu, specifically Ubuntu 18.04, for the purposes of this course. It is the system we test software installation on, and so it is the system for which we provide installation instructions.
If you do install software for any of these languages on another OS, consider compiling a short list of instructions and sending them to me; I will post them for others to make use of.
5.1.1 Oz
We will use the Mozart2 programming system for Oz. (Note that Van Roy & Haridi use the older Mozart 1.3.0 system; for our purposes, this should not matter). Releases of Mozart2 are available for Linux, macOS and Windows via the Mozart2 GitHub page. You may use whichever operating system you like for Oz.
The installation necessarily provides you with an (Aqua)Emacs program —which the instructional staff love and will use throughout.
- For a quick guide to using Emacs
(especially for basic keybindings),
I recommend using the builtin tutorial
by pressing
Ctrl-h
followed byt
. - You may also find the beginning section of Org mode beginning at the basics, “The absolute minimum you need to know about Emacs”, insightful.
- Also, consider using
Spacemacs
ordoom-emacs
, which provide default settings more inline with modern text editors.- Installation instructions and tutorials can be found online.
◆ Fyi: Oz is a multi-paradigm programming language whose programming systems is named Mozart. ◆
Read Tutorial of Oz (•̀ᴗ•́)و |
- Ubuntu
- Download the prebuilt
.deb
binary from the Mozart2 GitHub page. Alternatively, executewget https://github.com/mozart/mozart2/releases/download/v2.0.1/mozart2-2.0.1-x86_64-linux.deb
in your terminal to download it. - In your terminal, navigate to the directory you downloaded it to
(unnecessary if you used
wget
). - Install Mozart2 via
sudo apt install ./mozart2-2.0.1-x86_64-linux.deb
. This step will also install prerequisite software. - If you do not have it installed,
install Emacs via
sudo apt install emacs
. - Start Mozart2 (which is a wrapper for Emacs) via the command
oz
.
- Download the prebuilt
- Mac OS
- Open a terminal by pressing
cmd+spc
then enteringterminal
then pressingenter
. Copy and paste each of the following lines, one at a time.
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" brew tap dskecse/tap brew cask install mozart2
The first line install a package manager for macOs.
The next two lines use compiled binaries to install mozart.
(If a line overflows, just double-click it and copy it into your terminal.)
- Open
Applications
, right-click onMozart2
and selectopen
, then confirm theopen
.- You need to do this once to identify the program as ‘safe’.
- In the future, you can quickly
cmd+spc
then entermozart2
thenenter
to open it.
- Open a terminal by pressing
5.1.2 Ruby
The course staff will be using Ruby 2.3.0 or greater. It is very likely that the specific version you use will not matter, so long as it is 1.9 or greater. You should not use features which are version dependent. If you have some reason to do so, please inform us.
If you are using macOS, an suitable version of Ruby should be preinstalled.
Ubuntu installation instructions
Simply run sudo apt install ruby
to install
a suitable version.
5.1.3 F#
We will use the Mono framework for F#.
See the F# homepage for general installation instructions.
I recommend using either Emacs or VSCode, not Visual Studio.
Recommended:
Follow the instructions below to obtain an F# compiler,
then install fsharp-mode
in Emacs
(M-x package-refresh-contents
, M-x package-install fsharp-mode
)
or follow the instructions on the
F# homepage
to set up VSCode.
- Ubuntu
Simply run
sudo apt install mono-complete fsharp
. - Mac OS
- Open a terminal by pressing
cmd+spc
then enteringterminal
then pressingenter
. Copy and paste each of the following lines, one at a time.
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" brew install mono
The first line install a package manager for macOs.
The next line installs mono, an F# command-line compiler.
(If a line overflows, just double-click it and copy it into your terminal.)
- In the terminal, enter
mono --version
to ensure things worked.
- Open a terminal by pressing
- Windows
Note: these instructions are not tested.
Install
mono
following the instructions here.
5.1.4 Agda
- Installing Agda itself
Installation instructions are available on the Agda “Read the docs”. Some may be out of date, though!
Pre-built binaries are available on many Linux distros as well as for MacOS.
On Ubuntu,
sudo apt install elpa-agda2-mode
- To install both Agda and
agda-mode
for Emacs.
- To install both Agda and
sudo apt install agda-stdlib
- To install the standard library for Agda.
You may also consider building from source or installing GHC and then installing via the
cabal
package manager. - Setting up Emacs for Agda
However you install, you will have to ensure Emacs is set up to work with Agda.
If you install the
elpa-agda2-mode
package, the.el
files for Agda should be automatically in the load path for Emacs, so no configuration is necessary.Otherwise, setup should be as simple as adding this to your init file:
(load-file (let ((coding-system-for-read 'utf-8)) (shell-command-to-string "agda-mode locate"))) (require 'agda-input) (require 'agda2-highlight)
or, alternatively, run
agda-mode setup
in your terminal; it will modify your
.emacs
for you. - Installing the standard library
Depending upon how you installed, you may already have the standard library for Agda on your system.
Try typechecking an Agda file with
open import Data.Nat
to confirm Agda can find the standard library.
If you do not have it, follow the installation instructions for the standard library.
5.1.5 Prolog
For Prolog, we recommend SWI-Prolog, a free implementation commonly used for teaching. Installers are available for all major operating systems.
See the instructions regarding getting started quickly.
For Emacs users, you may need to set .pl
files to open in prolog-mode
(instead of perl-mode
); this setting in your init will do that.
(add-to-list 'auto-mode-alist '("\\.pl\\'" . prolog-mode))
5.2 Programming language tutorials
5.2.1 Cheatsheets produced by course staff
- Oz cheatsheet, produced by Musa
- Ruby cheatsheet, produced by Musa
- F# cheatsheet, produced by Musa
- Agda cheatsheet, produced by Musa
- Prolog cheatsheet,
produced by Musa
- Posted very late; apologies.
5.2.2 Learn X
in Y
minutes
https://learnxinyminutes.com/ provides community driven “whirlwind tour[s] of your next favorite language”.
5.3 Emacs and Org mode
5.3.1 Sample initialisation files
5.3.2 organice
organice is “An implementation of Org mode without the dependency of Emacs - built for mobile and desktop browsers”.
You can use it to manage Org documents without Emacs (or Atom/VSCode). It is simply a front end; you may store your documents in Dropbox or Google Drive.
Try out a sample document.
5.4 Literate programming
In this course, we encourage use of Org mode to enable literate programming.
Of course, literate programming can be accomplished via many other tools.
5.4.1 About literate programming
Let us change our traditional attitude to the construction of programs: Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do.
The practitioner of literate programming can be regarded as an essayist, whose main concern is with exposition and excellence of style. Such an author, with thesaurus in hand, chooses the names of variables carefully and explains what each variable means. He or she strives for a program that is comprehensible because its concepts have been introduced in an order that is best for human understanding, using a mixture of formal and informal methods that reinforce each other.
— Donald Knuth, Literate Programming (1984)
5.4.2 An example of literate programming using LaTeX
* An example of literate programming The amount of documentation we use will depend upon the problem being considered. For simple functions from math, we might choose to repeat the definition of the function. For instance, recall that given n elements, the number of possible combinations of r of them is given by #+begin_src latex $\comb{n}{r} = \frac{n!}{r! × (n-r)!}$ #+end_src We easily implement this definition in F#, first implementing factorial. #+begin_src fsharp :results none // factorial let rec fact n = match n with | 0 -> 1 | n when n > 0 -> n * fact (n - 1) | _ -> printfn "Can't calculate factorial of a negative!" -1 // combinations let comb n r = fact(n) / (fact(r) * fact(n-r)) #+end_src If we choose to implement it in an iterative way, perhaps it would merit more documentation. Here we iterate from i = 0 to n. At each stage, r is the factorial of i, so the result is n!. #+Name: ruby-fact #+begin_src ruby :results none def fact n return -1 if n < 0 i , r = 0 , 1 i , r = i+1 , (i+1)*r until i == n # Note that multiple assignment is carried out simultaneously # So r is being multiplied by the new value of i return r end #+end_src Of course, the combinations function follows simply. #+begin_src ruby :noweb yes :results none <<ruby-fact>> def comb (n,r); fact(n) / (fact(r) * fact(n - r)) end #+end_src
5.4.3 An example of literate programming using LaTeX
\section{An example of literate programming} The amount of documentation we use will depend upon the problem being considered. For simple functions from math, we might choose to repeat the definition of the function. For instance, recall that given /n/ elements, the number of possible combinations of /r/ of them is given by $\comb{n}{r} = \frac{n!}{r! × (n-r)!}$. We easily implement this definition in F#, first implementing factorial. \begin{lstlisting} % no listings support for f# // factorial let rec fact n = match n with | 0 -> 1 | n when n > 0 -> n * fact (n - 1) | _ -> printfn "Can't calculate factorial of a negative!" -1 // combinations let comb n r = fact(n) / (fact(r) * fact(n-r)) \end{lstlisting} If we choose to implement it in an iterative way, perhaps it would merit more documentation. Here we iterate from ~i = 0~ to ~n~. At each stage, ~r~ is the factorial of ~i~, so the result is ~n!~. \begin[language=Ruby]{lstlisting} def fact n return -1 if n < 0 i , r = 0 , 1 i , r = i+1 , (i+1)*r until i == n # Note that multiple assignment is carried out simultaneously # So r is being multiplied by the new value of i return r end \end{lstlisting} Of course, the combinations function follows simply. \begin{lstlisting} def comb (n,r); fact(n) / (fact(r) * fact(n - r)) end \end{lstlisting}
5.4.4 The listings
package for LaTeX.
The listings
for LaTeX should come installed
in whatever LaTeX distribution you are using.
listings
allows you to easily embed source code
into your LaTeX-produced documents.
You can copy your code into your .tex
file,
include a whole file at any in the document,
or include only certain lines at any point.
Documentation for listings
can be found
here.