[SOLVED] schemeCS 450 The Structure of Higher Level Languages

office: 130

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. Feel free to poke around there. Anything there is for you to take.

Assignments:

hw1: Scheme syntax; recursion and iteration; applicative-order and normal-order evaluation.

hw2: List manipulation and recursion.

hw3Transforming units.

Prerequisites:

• CS 310: Advanced Data Structures and Algorithms
• CS L320: Applied Discrete Mathematics

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.

I really mean this. This course is intensive. You will spend many hours and many days each week doing the work. And thats if you are well prepared. Its a great course if youre ready for ityoull learn a lot, and youll be amazed at the remarkable things you will find yourself able to do.

But this only happens if youre really prepared for the course. If youre not, dont 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.

Class meetings:Tu/Th 5:30-6:45 PM in room M-3-430. (Thats in the McCormack building.)

Office hours:Before class: Tu/Th 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, its 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 Scheme 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 wont have to worry about that in the beginning (or much at all, for that matter).

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 will be somewhat 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, please be 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 much more useful in that respect and that you may want to make use of:

• • DrRacket (formerly called DrScheme): Available for Linux, Mac OSX, and Microsoft Windows.

If you use DrRacket, set the language to R5RS. (Ask me if you cant 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.

Once again: if you use DrRacket (or any other Scheme interpreter) make sure your code continues to work here under UMB Scheme.

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. Rememberit is not my job to guess what you mean, any more than it is the computers 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 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 clearlyjust come to my office hours or send me email, and Ill be glad to help as much as I can.

The work you hand in must be in plain text. It cant be in Microsoft Word format or anything else with embedded control characters. And it cant have any lines longer than 80 characters. I really mean this. It wont print out right if it has long lines. Unfortunately some students dont 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, its 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 dont 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. ( setqis the emacs lisp version of set!in Scheme, and setq-defaultis 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 keyyou 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 almost always what you wantTAB characters tend to screw things up, and you want to avoid them.

A Note About Emacs

Learn it. If you havent learned it yet, learn it now. It will be very useful to you in your whole career. In this course you cant 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, Ive 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 didnt 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. Youll thank me for this some day.

Some Useful References:

• Structure and Interpretation of Computer Programs2nd 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 utilites. I highly recommend the following book:

  Unix for the Impatient (Second Edition)by Paul W. Abrahams and Bruce R. LarsonAddison-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 havent yetsee the note above. To find the best price for this book, go to http://www.addall.comand search for it.

Some University Policies:

• Student Conduct and Plagiarism Students are required to adhere to the polices expressed at University web site Academic Policies and Rights.
• Accomodations for Students with Disabilities Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990 offer guidelines 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, UL, Room 211, (617-287-7430). The student must present these recommendations and discuss them with each professor within a reasonable period, preferably by the end of Drop/Add period.