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 |
Handouts
- Mailing List Policies: Guidelines for writing better text
(in mailing list posts and in general).
- Style Guide: A collection of guidelines for writing better code.
- Tips: Some useful tips for PL work, DrScheme tips and
more.
- Scheme Evaluation Rules: Formal rules for evaluating Scheme Using
substitution.
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:
- Restart DrScheme (you should see a NEU icon on startup, and a
“PL Handin” in DrScheme’s toolbar).
- Menu: File > Manage PL Handin Account... (Your
computer will establish a secure connection to the handin server at
this point.)
- Make sure the “New User” tab is selected, and fill in the
form:
- ‘Username’ should be a lowercase alphanumeric string
- ‘Full Name’ should be your full name (as you want to be
known in class, not necessarily your ‘formal’ name: “Bob
Smith” is better than “Robert William Junior of the New
England Smiths”).
- ‘Email’ should be your active email — this address
will be used to contact you, so make sure you enter the email
address you use most frequently (for example, enter your Gmail
address if you use Gmail every day, even if you have a
@ccs.neu.edu address).
- ‘ID#’ is the last 4 digits of your NEU ID.
- Enter a password, twice. (Make sure you remember your
password.)
- Click the “Add User” button — if everything went fine,
you should see a “Success” message at the top of the dialog.
- If you had a mistake in the information for your account,
open up the “Manage...” dialog, and choose the “Change Info”
tab; enter your password in the “Old Password” field and
re-fill any fields you want to change and/or a new password.
(Once you fill your current password you can click the “Get
Current Info” button to retrieve the current values.) If you
forgot your password, mail us and we will re-set it.
- To submit a file, open it in DrScheme, and hit the “PL
Handin” button, choose the assignment you’re submitting to, enter
your password and hit the big Handin button.
- To verify the file you sent, you can click the “PL Handin”
button, choose the assignment, check the “Retrieve” checkbox,
enter your password and click the big button. You can even use
this method if you want to work on different machines: retrieve
your file, edit, and submit to save.
- Each time DrScheme starts, the plugin will check for updates,
and will ask you if it found that a newer version is available.
The plugin will be updated frequently, follow the web page and the
mailing list (see below) for announcements.
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.
- Choose your favorite CCIS Linux machine.
- SSH into this machine. Many Linux distributions have OpenSSH
installed by default, so just type
ssh 〈CCIS-username〉@〈machine〉.ccs.neu.edu |
Note that login is the preferred machine for such things
(specifically, it’s a machine that cannot be rebooted by random
students).
If you are using Windows or Mac, please look into a SSH client for
that OS. For Windows, putty is a popular free ssh client that works
well. Mac OS X comes with an ssh command that you can run in
the Terminal.
- Once presented with a prompt, similar to
[〈username〉@〈machine〉] ~ % use the command
The screen command allows you to run programs that will live on
this machine even after you log off — think of it as a kind of a
virtual text session manager. This is useful, since it makes it
possible to continuously run the IRC client so that you can
reconnect to it and see everything that was said while you were
away.
Important: You should use screen with no arguments
only once since this will create a new session. Later you will
use screen -rd to reconnect to an existing session.
- The screen should flash, possibly displaying a welcome message.
Press enter until you are given a prompt again. From here,execute
the command
This is a console based IRC client. This is good because you can
run it from screen, and as said, keep the program running even after
you leave.
- To connect to the CCIS IRC server (called “irc”), type in
the irssi prompt:
Text should scroll down the screen now.
- Once it stops, you should identify yourself with the server.
First, if you haven’t already, register by entering:
/msg nickserv register 〈some-password〉 |
This will secure the nickname you chose to you, and only you.
If you’re registered, then you need to identify yourself using your
password:
/msg nickserv identify 〈some-password〉 |
Please read up on google about how to use irssi.
Here’s a link
that seems useful.
(Note: while doing the above, a number may show up at the bottom of
your window. This means there is activity in a window that is not
currently shown. To show this window, press Esc and that
number.)
- Once you are identified, join the PL channels:
#pl-talk is the student-only channel (no instructor here), and
#pl is the main course channel and Eli is usually there too.
The content you post to these channels is up to you, but should
follow the common guidelines of the mailing list.
- Now that you are running irssi inside screen, press
Ctrl-A and then Ctrl-D (or just D). This will be caught
by screen and make it “detach” your session. This means
everything you are doing goes into a background process, waiting for
you you to return. You should be back at the original prompt that
you started with when you first connected into 〈machine〉. Feel
free to log out of this machine with Ctrl-D or by typing
exit.
- To get back to IRC later, ssh back into 〈machine〉 and
issue the following command:
You should be back where you left off, with irssi still running.
Repeat the Ctrl-A Ctrl-D to detach again.
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.