CS计算机代考程序代写 DrRacket scheme data structure compiler discrete mathematics assembly algorithm interpreter CS 450: The Structure of Higher Level Languages

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.