PL: Resources

Class Notes

These are the class notes files. They are not a substitute for taking your own notes in class, and they certainly cannot compensate for not coming in.

Lecture #1 (text)
    Tuesday, January 19th
Intro to CS4400/CS5400
Intro to Programming Languages
Lecture #2 (text)
    Tuesday, January 19th
Intro to Racket
Side-note: “Goto Statement Considered Harmful”
Quick Intro to Racket
Lists & Recursion
Some Style
Tail calls
Lecture #3 (text)
    Tuesday, January 26th
Note on Types
Side-note: Names are important
BNF, Grammars, the AE Language
Simple Parsing
The match Form
The define-type Form
The cases Form
Lecture #4 (text)
    Tuesday, January 26th
Semantics (= Evaluation)
Side-note: Compositionality
Implementing an Evaluator
Implementing The AE Language
Intro to Typed Racket
Lecture #5 (text)
    Tuesday, February 2nd
Bindings & Substitution
WAE: Adding Bindings to AE
Evaluation of with
Lecture #6 (text)
    Tuesday, February 2nd
Evaluation of with (contd.)
Formal Specs
Lazy vs Eager Evaluation
de Bruijn Indexes
Lecture #7 (text)
    Tuesday, February 9th
Functions & Function Values
Implementing First Class Functions
Side-note: how important is it to have anonymous functions?
The FLANG Language
Lecture #8 (text)
    Tuesday, February 9th
Introducing Racket’s lambda
Using Functions as Objects
Using define-type for new “type aliases”
Currying
Using Higher-Order & Anonymous Functions
Side-note: “Point-Free” combinators
This is not Runtime Code Generation
Lecture #9 (text)
    Tuesday, February 16th
Substitution Caches
Implementation of Cache Functionality
Formal Rules for Cached Substitutions
Evaluating with Substitution Caches
Dynamic and Lexical Scopes
Dynamic versus Lexical Scope
Implementing Lexical Scope: Closures and Environments
Fixing an Overlooked Bug
Lecture #10 (text)
    Tuesday, February 16th
Lexical Scope using Racket Closures
More Closures (on both levels)
Types of Evaluators
Feature Embedding
Lecture #11 (text)
    Tuesday, February 23rd
Recursion, Recursion, Recursion
Recursion without the Magic
The Core of make-recursive
Denotational Explanation of Recursion
Lecture #12 (text)
    Tuesday, February 23rd
The Y Combinator
The main property of Y
Yet another explanation for Y
Typing the Y Combinator
Lambda Calculus — Schlac
Church Numerals
Lecture #13 (text)
    Tuesday, March 2nd
More Encodings
Alternative Church Encoding
Lecture #14 (text)
    Tuesday, March 2nd
Implementing define-type + cases in Schlac
Recursive Environments
Recursion: Racket’s letrec
Implementing Recursion using letrec
Lecture #15 (text)
    Tuesday, March 9th
Implementing rec Using Cyclic Structures
Boxes and Mutation
Types for Boxes
Boxof’s Lack of Subtyping
Implementing a Circular Environment
Lecture #16 (text)
    Tuesday, March 9th
Variable Mutation
State and Environments
Implementing Objects with State
The Toy Language
Lecture #17 (text)
    Tuesday, March 16th
Compilation and Partial Evaluation
Lecture #18 (text)
    Tuesday, March 16th
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
Call by Need vs Call by Name
Example of Feature Embedding
Lecture #19 (text)
    Tuesday, March 23rd
Implementing Laziness (in plain Racket)
Sloth: A Lazy Evaluator
Getting more from Sloth
Implementing Call by Need
Lecture #20 (text)
    Tuesday, March 23rd
Side Effects in a Lazy Language
Designing Domain Specific Languages (DSLs)
Syntax Transformations: Macros
Lecture #21 (text)
    Tuesday, March 30th
Macro Problems
Complexity of S-expression transformations
Scoping problems
Scheme (and Racket) Macros
Lecture #22 (text)
    Tuesday, March 30th
Scheme (and Racket) Macros (contd.)
Meta Macros
Lazy Constructions in an Eager Language
Recursive Macros
Another example: a simple loop
Yet Another: List Comprehension
Lecture #23 (text)
    Tuesday, April 6th
Problems of syntax-rules Macros
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 #24 (text)
    Tuesday, April 6th
Types
What is a Type?
Our Types — The Picky Language
Typing control
Extending Picky
Implementing Picky
Lecture #25 (text)
    Tuesday, April 13th
Improving Picky
Even better…
Typing Recursion
Extending Picky with recursion
Lecture #26 (text)
    Tuesday, April 13th
Typing Data
Judgments for recursive types
“Runaway” instances
Type soundness
Explicit polymorphism
Polymorphism in the type description language
Type judgments for explicit polymorphism and execution
Explicit polymorphism conclusions
Lecture #27 (text)
    Tuesday, April 13th
Web Programming
Basic web programming
Continuations: Web Programming
Simulating web reading
Lecture #28 (text)
    Tuesday, April 20th
More Web Transformations
Transforming a recursive function
Using sum/k
Converting stateful code
Converting higher order functions
Highlevel Overview on Continuations
An Automatic Continuation Converter
Lecture #29 (text)
    Tuesday, April 20th
Continuations as a Language Feature
Continuations in Racket
Playing with Continuations
The Ambiguous Operator: amb
Generators
Delimited Continuations
Continuation Conclusions
Lecture Notes, single file (text)
    Tuesday, April 20th
If you find a single file format more convenient.

Handouts

Interpreters

Software

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, start DrRacket, use the “Install .plt File” in the File menu and enter http://pl.barzilay.org/pl.plt — and restart DrRacket after it is installed. You can also use the “Setup PLT” application to install it if you want to do an off-line installation.

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

There is a piazza page for this course at Piazza.com. Piazza 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 piazza without using the “private” option. Direct emails to the course staff should be your last resort. Consult the Email and Piazza Policies handout for further details about piazza posts and emails.

Feel free to post questions privately if you have any concerns about them, and if your question is useful for the rest of the class and we think that it is fine to do so, we will make it public.

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 Schemers.org.