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



Handouts



Interpreters



Software

We will use the PLT Scheme environment extensively. DrScheme, the major component of PLT Scheme, 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 PLT website. Binary installers exist for all major operating systems, and the course work will be platform independent.

PLT Scheme 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 PLT Scheme 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.



Mailing List

There is a mailing list for this course at http://groups.google.com/group/neu-pl/ (send mail to neu-pl@googlegroups.com). It is hosted on Google Groups, but you don’t need a Google account to use it. The mailing list is the main medium for discussions, questions, announcements etc. You should try to use if you have questions, so others can benefit from the discussion as well. Do not to post any assignment code on the mailing list. You should also consult the Mailing List Policies handout for mailing list posts.

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

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

Many Scheme books etc are available on-line, a few good ones are:

In addition, there are lots of good Scheme-related references at Schemers.org.