CS 450: The Structure of Higher Level Languages
Carl Offner
Fall 2021
office: M-3-201-31
email: offner “at” cs.umb.edu
Aside from this web page, and pages it points to, I will be providing other
course material as files (not web pages!) under ~offner/cs450. This is the
“course directory”. Feel free to poke around there. Anything there is for
you to take.
Please read this course home page carefully for information about
the course. You are responsible for understanding everything on
this page.
In addition, you will also need to read the file (again, not a web
page!) ~offner/cs450/honesty.pdf, which you should print out and
keep. And take it seriously.
Assignments:
hw1: Scheme syntax; recursion and iteration; applicative-order and
normal-order evaluation.
hw2: List manipulation and recursion.
hw3 Transforming units.
Prerequisites:
CS 220: Applied Discrete Mathematics
CS 310: Advanced Data Structures and Algorithms
These prerequisites are important. If you have not had both of them (and I
hope you have done well in both of them), you should not be enrolled in
this course.
http://www.cs.umb.edu/~offner/cs450/hw1/hw1.html
http://www.cs.umb.edu/~offner/cs450/hw2/hw2.html
http://www.cs.umb.edu/~offner/cs450/hw3/hw3.html
I really mean this. This course is intensive. You will spend many hours and
many days each week doing the work. And that’s if you are well prepared.
It’s a great course if you’re ready for it—you’ll learn a lot, and you’ll be
amazed at the remarkable things you will find yourself able to do.
But this only happens if you’re really prepared for the course. If you’re not,
don’t fool yourself into thinking you can just “work really hard” and get
through it. I have had students who were not prepared for the course tell
me they were “self-starters” and would “work really hard”. They did work
really hard. And they all failed. (Well, either that or they realized about
halfway through the course that they were really in over their head and
rather than dropping the course, plagiarized. This always leads to very
unpleasant meetings, failure in the course, and referrals to the Dean.
Please don’t put yourself in that position.)
Class meetings: M/W 5:30-6:45 PM in room W-1-005. (That’s in the
Wheatley building.)
Office hours: Before class: M/W 4:30-5:15 PM
Text:
Structure and Interpretation of Computer Programs, Second Edition
(paperback)
by Harold Abelson and Gerald Jay Sussman with Julie Sussman
MIT Press, 1996
ISBN: 978-0-262-51087-5
A word about our textbook: Computer science is still a rapidly growing
field, and you may be used to having books that are very recent. So why do
we use this book? Here is the answer: This is one of the great books of
computer science. Arguably, it’s one of the great books of the last century,
in any field. Every serious computer scientist knows and loves this book.
You will too.
One thing you have to watch out for is that in a few very minor respects
the book is slightly out-of-date. It was written just as the Scheme
language was being put in its modern form, and there are a very few
constructions in the book that are not in Scheme today. In particular, there
is no symbol named “nil”. You won’t have to worry about that in the
beginning (or much at all, for that matter).
Lectures
I will place PDF versions of my lectures before each class in the course
directory. You should either print each lecture out or have it available on a
laptop in class.
Syllabus:
We will cover Chapters 1 and 2 of the text very quickly. Then we will spend
a major amount of time on Chapters 3, 4, and 5.
Chapters 1 and 2 cover functional programming, data abstraction, and the
duality between data and operations on data.
Chapter 3 covers imperative programming, programs with mutable state,
delayed operations, and some remarkable programs that can be built with
these capabilities.
Chapter 4 describes a Scheme interpreter written in Scheme. We will
modify that interpreter in order to study different ways in which languages
behave and how they can be implemented so as to behave in those ways.
Chapter 5 discusses three programs:
1. An abstract register machine simulator. This simulator reads programs
written in an assembly language. Each such program describes a
special-purpose register machine. The simulator “assembles” such a
program into a model of the machine and then runs the machine.
2. An explicit-control evaluator that is similar to the Scheme interpreter
from Chapter 4, except that it is itself a register machine, rather than
a Scheme program, and so is executed by the register machine
simulator.
3. A Scheme compiler, which like the interpreter of Chapter 4 is itself a
Scheme program that takes as input a Scheme expression or program,
but instead of interpreting the Scheme source code, it generates
register machine code out of Scheme input. This code can then itself
be executed by the register machine simulator.
Course Work:
There will be no exams. All the work in this course will be homework. There
will be 10 assignments, each involving some written work and also some
programming. Each assignment will involve an extensive amount of work.
Assignments 1 and 2 however, will be considerably easier than the others
(and will count for somewhat less when I calculate grades). The
assignments will be handed out with ample time allowed to finish them. I
will not accept late assignments.
All Scheme code that you write in this course must work under UMB
Scheme as installed here at UMB. The sources for UMB Scheme are
publicly available, and so you may install this also on your own machine at
home or elsewhere if you wish. (If you are on a Linux system and you are
trying to compile from the sources and you are having problems, try using
the modified sources in ~offner/tools/src/scheme-3.2-for-Linux.tar.) Even
if you do install UMB Scheme on your own machine, make sure to double-
check by running your code here at UMB before it is due.
UMB Scheme has very minimal support for debugging. There is one other
Scheme interpreter that is more useful in that respect. I have very
occasionally used it; you may want to do that yourself:
Racket (or “DrRacket”, and formerly called “DrScheme”): Available for
Linux, MacOS, and Microsoft Windows.
If you use Racket, set the language to “R5RS”. (Ask me if you can’t
figure out how to do this.) This will probably be pretty close to what
UMB Scheme supports. But be careful: you still have to test this on
UMB Scheme as installed here.
In any case, I should also say that I have found that just inserting “print
statements” in the code is a quite effective way of debugging, and is
very simple to do. That’s the main way I actually debug my own code.
Once again: if you use Racket (or any other Scheme interpreter) make sure
your code continues to work here under UMB Scheme. Please be careful
about this.
http://www.racket-lang.org/
What You Need To Know About Asking Me Questions
Many students shy away from asking questions. Sometimes they
think it will make them look stupid. Often they think I will have a
low opinion of them.
Exactly the opposite is true. I expect you to ask me questions.
Asking me questions does not lower your grade. It does not
indicate to me that you are ignorant. What it does tell me is that
you are taking this work seriously. That’s a very good thing.
When I first started learning about this field, I had a lot of
questions. Each time I teach this course, I have a few more
questions. Questions are good. If you don’t ask questions, I worry
that you are not really understanding this material.
Even if you think your question is “stupid”, please ask it anyway. In
the first place, I’ve never really been asked a stupid question. In the
second place, my job is to answer your questions. You are paying
good money for this course. You are entitled to get your questions
answered, and I’m happy to do this. I really mean it.
Finally, I guarantee you that if you ask a question in class, there will
be several other students with the same question, and they will be
so grateful to you for asking it. So don’t be afraid. In fact, I have
found that it is usually the very best students in the class who ask
the most questions.
A Note About Written Work
An important part of this course is for you to begin to learn how seasoned
engineers design and implement projects. To do this, they have to
communicate clearly with each other. In almost every assignment, I will ask
you to write down some explanations, some thoughts on design, or
something similar. I expect these essays to be written clearly, so that I can
understand what you are saying. Remember—it is not my job to guess
what you mean, any more than it is the computer’s job to guess what your
programs mean. A significant part of your grade in this class will be
determined by this written work.
In particular, you should always run a spell-checker on your written work,
and you should look it over for proper grammar and usage. I am going to
be pretty serious about this. Spelling errors are easy to catch with a spell
checker, and I expect you to use one.
Also, this is written work, not text messaging to your buddies. “u” is not
how you spell “you”. “2” is not how you spell “to”. “thanx” or “tx” or “tks” is
not how you spell “thanks”. You want to be a professional; here is the time
to start writing like one.
I understand that there will be students in this class whose first language is
not English. Whether or not this is true in your case, I am quite willing to
help each of you in any problems you may have expressing yourself clearly
—just come to my office hours or send me email, and I’ll be glad to help as
much as I can.
The work you hand in must be in plain text. It can’t be in Microsoft Word
format or anything else with embedded control characters. And it can’t
have any lines longer than 80 characters. I really mean this. It won’t print
out right if it has long lines. Unfortunately some students don’t tend to
take this seriously, so let me just say that I plan to take points off for lines
that are over 80 characters in length.
Here are some suggestions for how to produce acceptable text files:
1. If you prepare plain text on a Microsoft platform, then when you
transfer it to the Unix system at UMB the line endings will most likely
be all wrong. You many not notice this, since many editors and text
viewers are forgiving about this. But it will definitely screw up my
printing scripts.
Fortunately, it’s quite easy to fix. On Unix at UMB, just run
dos2unix your_original_file
and it will fix up your file.
2. You can configure emacs so that it will help you keep your lines to a
maximum of 80 characters by creating (if you don’t already have) a file
named .emacs (note the initial dot) in your home directory, and putting
the line
(setq-default fill-column 80)
in it. (setq is the emacs lisp version of set! in Scheme, and setq-
default is a variant which seems to be needed here.)
Then if you place the point (i.e., the cursor) anywhere in a paragraph
and type M-q (i.e., “meta q”, which you can always do by typing the
escape key and then q, although often the “alt” is bound to “meta”,
and it acts as a shift key—you hold it down while typing the q), then
the paragraph will get adjusted so that none of its lines is more than
80 characters long.
3. Another useful thing to put in your .emacs file is this line:
(setq ispell-check-comments t)
This will cause the built-in spell checker in emacs (which is called
“ispell”) to check spelling of words inside comments as well as
everything else. This is probably what you want.
4. And here is a third line for your .emacs file:
(setq-default indent-tabs-mode nil)
This stops emacs from using TAB characters when performing
automatic indentation. This is definitely what you want—TAB
characters tend to screw things up, and you want to avoid them.
A Note About Emacs
Learn it. If you haven’t learned it yet, learn it now. It will be very useful to
you in your whole career. In this course you can’t use any sort of WYSIWIG
editor like Microsoft Word, and simple-minded editors like notepad and vi
and such are going to cause you all sorts of problems. Believe me, I’ve
seen this again and again. I know that students are under all sorts of time
pressure, and I have seen too many students who just figured they didn’t
have time to learn emacs and so would just struggle through using vi or
notepad or some other brain-dead editor. They invariably ended up making
a lot more work for themselves than if they had just spent some time and
learned emacs. And in almost all cases, the work they handed in was
extremely sloppy and caused a lot of headaches for both me and the
grader.
So learn emacs. You’ll thank me for this some day.
Some Useful References:
Structure and Interpretation of Computer Programs—2nd Edition . This
is the home page for the textbook. Here you can find supporting
material for the text, some errata, and other information.
I often am asked for information on Unix and the basic Unix utilities. I
highly recommend the following book:
Unix for the Impatient (Second Edition)
by Paul W. Abrahams and Bruce R. Larson
Addison-Wesley, 1997
The book comes with a CD that you might find useful as well. It covers
the basics of the typical Unix environments, and also gives a nice short
introduction to the Emacs editor, which you should absolutely learn
now if you haven’t yet—see the note above. To find the best price for
this book, go to http://www.addall.com and search for it.
Some University Policies:
Student Conduct, Instructional Setting Conduct, Plagiarism, etc.:
Students are required to adhere to the polices expressed at the
University web site Academic Policies and Rights.
Accommodations: Section 504 of the Rehabilitation Act of 1973 offers
guidelines and support for curriculum modifications and adaptations
for students with documented disabilities. If applicable, students may
obtain adaptation recommendations from the Ross Center for
Disability Services, Campus Center, Upper Level, Room 0211, 617-287-
7430. The student must present these recommendations and discuss
http://mitpress.mit.edu/sicp/
http://www.addall.com/
http://www.umb.edu/life_on_campus/policies/academics/
them with each professor within a reasonable period, preferably by the
end of Drop/Add period.