PL: Resources

Class Notes

These are the class notes files. In some places they are in pretty raw form, intended mainly for reference, code examples etc. They are not a substitute for taking notes in class, and they certainly cannot compensate for not coming in. Also, they are not guaranteed to cover all of the material that was presented in class. What they do get you is avoiding the hassle of trying to copy this stuff that you see it in class.

Lecture #1
  ? Tuesday, September 13th
Intro to CS4400/CS5400
Intro to Programming Languages
Intro to Racket
Side-note: “Goto Statement Considered Harmful”
Quick Intro to Racket
Lecture #2
  ? Tuesday, September 13th
Lists & Recursion
Some Style
Lecture #3
  ? Tuesday, September 20th
Tail calls
Note on Types
Side-note: Names are important
BNF, Grammars, the AE Language
Lecture #4
  ? Tuesday, September 20th
Simple Parsing
The match Form
Lecture #5
  ? Tuesday, September 27th
Semantics (= Evaluation)
Side-note: Compositionality
Implementing an Evaluator
Implementing The AE Language
Intro to Typed Racket
Lecture #6
  ? Tuesday, September 27th
Bindings & Substitution
WAE: Adding Bindings to AE
Evaluation of with
Lecture #7
  ? Tuesday, October 4th
Evaluation of with (contd.)
Formal Specs
Lazy vs Eager Evaluation
Lecture #8
  ? Tuesday, October 4th
de Bruijn Indexes
Functions & Function Values
Implementing First Class Functions
The FLANG Language
Lecture #9
  ? Tuesday, October 11th
The FLANG Language (contd.)
Introducing Racket’s lambda
Using Functions as Objects
Using Higher-Order & Anonymous Functions
Lecture #10
  ? Tuesday, October 11th
Side-note: “Point-Free” combinators
Substitution Caches
Implementation of Cache Functionality
Formal Rules for Cached Substitutions
Evaluating with Substitution Caches
Dynamic and Lexical Scopes
Lecture #11
  ? Tuesday, October 18th
Dynamic and Lexical Scopes (contd.)
Dynamic versus Lexical Scope
Implementing Lexical Scope: Closures and Environments
Fixing an Overlooked Bug
Lexical Scope using Racket Closures
Lecture #12
  ? Tuesday, October 18th
More Closures (on both levels)
Types of Evaluators
Feature Embedding
Recursion, Recursion, Recursion
Recursion without the Magic
Lecture #13
  ? Tuesday, October 25th
The Core of make-recursive
Denotational Explanation of Recursion
The Y Combinator
The main property of Y
Lecture #14
  ? Tuesday, October 25th
Typing the Y Combinator
Lambda Calculus — Schlac
Church Numerals
Lecture #15
  ? Tuesday, November 1st
More Encodings
Lecture #16
  ? Tuesday, November 1st
Alternative Church Encoding
Recursive Environments
Lecture #17
  ? Wednesday, November 2nd
Recursion: Racket’s letrec
Implementing Recursion using letrec
Implementing rec Using Cyclic Structures
Boxes and Mutation
Types for Boxes
Boxof’s Lack of Subtyping
Lecture #18
  ? Tuesday, November 8th
Implementing a Circular Environment
Variable Mutation
State and Environments
Implementing Objects with State
The Toy Language
Lecture #19
  ? Tuesday, November 8th
Compilation and Partial Evaluation
Lecture #20
  ? Tuesday, November 15th
Lazy Evaluation: Using a Lazy Racket
Lazy Evaluation: Some Issues
Lazy Evaluation: Shell Examples
Lazy Evaluation: Programming Examples
Side Note: Similarity to Generators and Channels
Lecture #21
  ? Tuesday, November 15th
Call by Need vs Call by Name
Example of Feature Embedding
Implementing Laziness (in plain Racket)
Sloth: A Lazy Evaluator
Lecture #22
  ? Tuesday, November 22nd
Sloth: A Lazy Evaluator (contd.)
Getting more from Sloth
Implementing Call by Need
Side Effects in a Lazy Language
Lecture #23
  ? Tuesday, November 22nd
Designing Domain Specific Languages (DSLs)
Side-note: WSJ on the proliferation of PLs
Syntax Transformations: Macros
Lecture #24
  ? Tuesday, November 29th
Macro Problems
Complexity of S-expression transformations
Scoping problems
Scheme (and Racket) Macros
Meta Macros
Lazy Constructions in an Eager Language
Recursive Macros
Another example: a simple loop.
Problems of syntax-rules Macros
Lecture #25
  ? Tuesday, November 29th
(Extra stuff we didn’t get to)
Racket’s “Low-Level” Macros
Solving the syntax-rules problems
Breaking Hygiene, How Bad is it?
Macros in Racket’s Module System
Defining Languages in Racket
Macro Conclusions
Side-note: macros in mainstream languages
Lecture #26
  ? Tuesday, November 29th
What is a Type?
Our Types — The Picky Language
Typing control
Lecture #27
  ? Tuesday, December 6th
Extending Picky
Implementing Picky
Typing Recursion
Extending Picky with recursion
Lecture Notes, single file
  ? Tuesday, December 6th
If you find a single file format more convenient.
(Also, as a plain text file.)




We will use the Racket environment extensively. DrRacket, the major component of Racket, will be used to develop code, debug, and submit homework. CCS computers have an updated version installed (available on both Unix and Windows). To use it on your own machine, get it from the Racket website. Binary installers exist for all major operating systems, and the course work will be platform independent.

Racket has a system for distributing software bundles that will be used to get a course-specific plugin. This packages both specific functionality for each homework, and an integrated tool for homework submissions. Once you have Racket installed, download the plugin package, and use the “Setup PLT” application to install it. You can also use “Install .plt File” in the File menu, and enter the URL for the plugin.

Note: The handin server uses a dedicated port for communication. You need to work from a network that does not restrict this port — for example, if you use Northeastern’s ‘NUwave-guest’ network, then you will not be able to connect to the server. ‘NUwave’ (which requires you to authenticate through myNEU) does not have this restriction.

To set-up your account:

Additional software may be used later in the course.

Piazza Group

There is a piazza group for this course at The piazza group is the main medium for discussions, questions, announcements etc. You should use it if you have any questions, so others can benefit from the discussion as well. If you want to ask a question that involves showing your solution code, make sure that you choose the “private” option. Do not to post any homework code on the piazza group without using the “private” option. Direct emails to the course staff should be your last resort. Consult the Email and Piazza Group Policies handout for further details about piazza group posts and emails.

Note that you do not need to request to be subscribed to the mailing list — you will get added after you register with the submission server.

On-line books and other materials

There are lots of Racket and Scheme books on-line, a few good ones are:

You can also find some good on-line courses: In addition, there are lots of additional Scheme-related references at