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.

• Lecture #1
  Wednesday, January 8th
Introduction to Programming Languages (CS4400/CS5400)
Introduction to Racket
• Lecture #2
  Friday, January 10th
Quick Introduction to Racket
Lists & Recursion
Some Style
• Lecture #3
  Wednesday, January 15th
Names are Important
Note on Types
BNF, Grammars, the Simple AE Language
Simple Parsing
The ‘match’ Form
Semantics (= Evaluation)
Implementing an Evaluator
Implementing The AE Language
• Lecture #4
  Friday, January 17th
Introduction to Typed Racket
Bindings & Substitution
Adding Bindings to AE: The WAE Language
• Lecture #5
  Wednesday, January 22nd
Implementing ‘with’ Evaluation
Formal Specs
Lazy vs Eager Evaluation
de Bruijn Indexes
• Lecture #6
  Friday, January 24th
Functions & First Class Function Values
Implementing First Class Function Values
The FLANG Language
Introducing Racket’s ‘lambda’
Using Functions as Objects
• Lecture #7
  Wednesday, January 29th
Using Higher-Order & Anonymous Functions: "Point-Free"/Combinators
Substitution Caches
Initial Implementation of Cache Functionality
Formal Rules for Cached Substitutions
Evaluating with Substitution Caches
• Lecture #8
  Friday, January 31st
Dynamic and Lexical Scopes
Dynamic versus Lexical Scope
Implementing Lexical Scope: Closures and Environments
Fixing an Overlooked Bug
Implementing Lexical Scope using Racket Closures and Environments
• Lecture #9
  Wednesday, February 5th
Snow emergency, no class
• Lecture #10
  Friday, February 7th
More Closures (on both levels)
Types of Evaluators
Feature Embedding
Recursion, Recursion, Recursion
Recursion without the Magic
• Lecture #11
  Wednesday, February 12th
The Core of ‘make-recursive’
A More Methodical Explanation of Recursion
The Y Combinator
Typing the Y Combinator
Lambda Calculus – Schlac
• Lecture #12
  Friday, February 14th
Church Numerals
More Encodings
• Lecture #13
  Wednesday, February 19th
Alternative Church Encoding
Recursive Environments
Recursion: Racket’s ‘letrec’
Implementing Recursion using ‘letrec’
• Lecture #14
  Friday, February 21st
Implementing ‘rec’ Using a Cyclic Structure
Boxes and Mutation
Types for Boxes
‘Boxof’s Lack of Subtyping
Implementing a Circular Environment
• Lecture #15
  Wednesday, February 26th
Variable Mutation
• Lecture #16
  Friday, February 28th
Midterm review
• Lecture #17
  Wednesday, March 12th
State and Environments
Implementing Objects with State
The Toy Language
• Lecture #18
  Friday, March 14th
"Compilation" and Partial Evaluation
Lazy Evaluation: Using a Lazy Racket
Lazy Evaluation: Some Issues
• Lecture #19
  Wednesday, March 19th
Lazy Evaluation: Some Issues (contd.)
Lazy Evaluation: Shell Examples
Lazy Evaluation: Programming Examples
Side Note: Similarity with Generators and Channels
Call by Need vs Call by Name
• Lecture #20
  Friday, March 21st
Example of Feature Embedding
Implementing Laziness (in plain Racket)
Sloth: A Lazy Evaluator
Implementing Call by Need
Side Effects in a Lazy Language
• Lecture #21
  Wednesday, March 26th
Designing Domain Specific Languages (DSLs)
Syntax Transformations: Macros
Macro Problems
• Lecture #22
  Friday, March 28th
Macro Problems (contd.)
Scheme (and Racket) Macros
Using Lazy Constructions in an Eager Language
Recursive Macros
• Lecture #23
  Wednesday, April 2nd
Problems of ‘syntax-rules’ Macros
Racket’s "Low-Level" Macros
Macro Conclusions
• Lecture #24
  Friday, April 4th
What is a Type?
What are Our Types – The Picky Language
Typing control
• Lecture #25
  Wednesday, April 9th
Implementing Picky
Typing Recursion
Typing Data
Type soundness
Explicit polymorphism
• Lecture #26
  Thursday, April 10th
Web Programming
Introduction to Continuations: Web Programming
• Lecture #27
  Friday, April 11th
More Web Transformations
Highlevel Overview on Continuations
Implementing an Automatic Continuation Converter
Continuations as a Language Feature
Continuations in Racket
Playing with Continuations
Continuation Conclusions




We will use the Racket environment extensively. DrRacket, the major component of Racket, will be used to develop code, debug, and submit homeworks. 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.


IRC, or “Internet Relay Chat” is a text-based chat protocol where people can join channels on IRC servers and communicate. IRC is sometimes refered to as “interactive notepad”. The major benefit of using IRC is real-time conversations with fellow class members as well as course staff.

If you have a CCIS account, you are almost ready to start using IRC. The following will describe a basic configuration, as described by jmendel (aka John Mendelewski). Feel free to set up your client as you wish.

Read up on these commands before you start experimenting. Google is your friend.

Finally, IRC is a valuable resource: don’t abuse it! Specifically, you should not post any source code, and you should try to read homework texts thoroughly before you ask questions. This applies for both channels.

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