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




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