CS450: Structure of Higher Level Languages

 Spring 2018

Mo We 5:30-6:45, W-1-063

 

Instructor

Course Description

Textbook

Evaluation

Homework assignments

Coursework (Summary notes and PDF slides are posted here)

Resources

Accommodations

Student Conduct

 


Instructor  

Nurit Haspel
Office: S-3-071
Office Hours: Monday, Wendesday 4:00-5:15pm or by appointment
Office Phone: 617-287-6414
e-mail: nurit.haspel@umb.edu
Homepage: http://www.cs.umb.edu/~nurith
TA:???


Course Description

The syntax and semantics of higher-level languages are treated. Formal specifications of syntax and models of semantics will be used. Important topics include mechanisms for parameter passing, scoping, dynamic storage allocation and systems interfacing. Both compiled and interpreted languages will be used as examples. The language of instruction is Scheme, a dialect of LISP, which is taught in the course.

See the course syllabus for a detailed list of topics.

Prerequisites are CS310 (Advanced Data Structures and Algorithms) and CS320 (Applied Discrete Mathematics) or permission from the instructor.


Required Textbook

Required:

Structure and Interpretation of Computer Programs, Harold Abelson and Gerald Sussman,
MIT Press, ISBN: 0262011530 ISBN-10: 032157351X


Grade Evaluation

There will be no exams. All the work in this course will be homework. There will be 10-ish 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 without permission (points will be taken off). The assignments are due in your account at 5PM on the due day.

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 http://www.cs.umb.edu/cs450/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:

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


Homework assignments

Assignment (PDF) Posted/Given on Due Date Handouts
HW1, part 1 Jan. 22, 2018 Jan. 29, 2018
HW1, part 2 Jan. 28, 2018 Feb. 5, 2018 R5RS
(Scheme language report)
HW2 Feb. 5, 2018 Feb. 12, 2018  
HW3 Feb. 12, 2018 Feb. 21, 2018 units.dat
HW4, part 1 Feb. 21, 2018 Feb. 28, 2018
(Q.2,5 should be submitted in class)
HW4, part 2 Feb. 21, 2018 Mar. 5, 2018 dist.dat
HW5, part 1 Mar. 5, 2018 Mar. 19, 2018
HW5, part 2 Mar. 5, 2018 Mar. 21, 2018 pi.pdf
pi_header.scm
HW6 Mar. 19, 2018 Apr. 2, 2018 (delayed) s450.scm
ps450.scm
load.s450
HW7 April 2, 2018 April 18, 2018 begin.scm
save_continuation.scm
sr.s450
sr_annot.s450
HW8 April 11, 2018 April 30, 2018
(Q1 to be discussed in class on April 18)
Q2 to be discussed on April 23.
regsim.scm

 


Syllabus

Week

Topic

Book Chapters

Session Dates

Session Info

Slides/notes

1

Introduction

1

Monday,
January 22

Introduction to Scheme

Introduction

Intro. Notes

1

Wednesday,
September 8

Syntax, Evaluation
Lexical scoping

Notes

Slides

2

Abstractions
Function Calls

1.2-1.3

Monday,
January 29

Tail Recursion vs. Iteration

2

Wednesday,
January 31

Data Abstractions
Pairs

Notes

Slides

3

Pairs and lists
More Data Structures

2.2-2.3

Monday,
February 5

Operations on Lists
Lists as Trees

lec03 Slides (updated)

New Slides

Notes

2.2-2.3

Wednesday,
February 7

Quote
Membership tests

4

Data Directed Programming
Message Passing

2.4, 3.1

Monday,
February 12

Representing Complex Numbers
Tagged Data

Slides

sec2.4.1.scm

sec2.4.2.scm

sec2.4.3_umb.scm

Wednesday,
February 14

Data Directed Programming
set!

Slides

Notes

5

The Environment Model

3.2

Monday,
February 19

No class
(Presidents day)

Wednesday,
February 21

The environment model

Slides

Notes

6

Tables
Streams

3.3, 3.5

Monday,
February 26

Tables, Mutable lists

Slides

Notes

Wednesday,
February 28

Finish tables
Start Streams

Slides

Notes

7

Streams

3.5

Monday,
March 5

Finite Streams

Slides
Notes
Notes (inf. streams)
Slides (inf. streams)

Wednesday,
March 7

Snow day

8

Meta-linguistic Abstraction

4.1

Monday,
March 19

The Metacircular Evaluator

Slides
s450.scm.pdf

Wednesday,
March 21

Snow day

9

Meta-linguistic Abstraction

4.1

Monday,
March 26

The Metacircular Evaluator

Same as last week

Wednesday,
March 28

10

Continuation
Variations on a Scheme

Monday,
April 2

Delayed, Dynamic, Reference variables

Slides

Wednesday,
April 4

Continuation passing

begin.scm.pdf
save_continuation.scm.pdf
sr.scm.pdf
sr_annot.scm.pdf

11

Continuation
Register Machines

5.1

Monday,
April 9

Continuation Passing
Start Register

Wednesday,
April 11

Register Machine

Slides

regsim.scm.pdf

12

Register Machine

5.1, 5.2

Monday,
April 16

Patriots day

Wednesday,
April 18

Register Machine

Slides (modified)

13

Register Machines

5.2, 5.4

Monday,
April 23

The Register Machine Code

Same

Wednesday,
April 25

The Explicit-control Evaluator

 

 


Resources

A Note About Written Work (Adapted from Prof. Carl Offner)

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. A spell checker cannot catch all possible mistakes (e.g. then vs. than, it's vs. its etc.), but I expect you to do your best. When in doubt, google is your friend.

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. I feel your pain, English is my second language as well, but I will do my best 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 almost always 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.


Accommodations:  Section 504 of the Americans with Disabilities Act of 1990 offers 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.


Student Conduct:  Students are required to adhere to the University Policy on Academic Standards and Cheating, to the University Statement on Plagiarism and the Documentation of Written Work, and to the Code of Student Conduct as delineated in the catalog of Undergraduate Programs. The Code is available online at: http://www.umb.edu/life_on_campus/policies/code/

In particular, see note about honesty