CS计算机代考程序代写 scheme algorithm interpreter CS 450 Homework 1

CS 450 Homework 1

Carl Offner

Fall 2021

(Taken from a similar assignment due to Prof. Bolker)

Part I. Due Friday, September 10.

1. Apply for a department Unix account in the usual way. (And talk to the

operators in the Unix lab if you are not familiar with this—they will

show you how to do this.)

Do that even if you already have a Unix account, so that you can tell

the system that you are enrolled in this course. Do not ever change the

protections on this account (or on any files or subdirectories in it).

When I send email to the class, I will send it to the cs450-1 email list.

This list consists of everyone who has signed up for the class in this

way, and the email will go to your email address at umb.edu. So be

sure to read your email there, or forward it to some place where you

will read it.

2. Read pages 1-21 of the text (Abelson and Sussman’s Structure and

Interpretation of Computer Programs) once over lightly, and try not to

worry about what doesn’t seem clear. Answer the following 4

exercises:

For this (Part I of homework 1) only, create a file with your

answers to the following problems, using emacs. (In particular, I

will not even try to read non-plain-text files, such as files

created using Microsoft Word.) Email that file to me at

.edu

I must receive that file by 6 PM on Friday, September 10. I will

not accept late files.

1. Problem 1.1 (page 20) Work this out with pencil and paper,

thinking it through by yourself before you run Scheme to see what

it really does. Then evaluate these expressions in Scheme to make

sure you got them right. And if you get something wrong, make

sure you understand the mistake you made. And explain that

mistake in your work. (And I won’t think badly of you if you do this

—I’ll be impressed, actually.)

2. (Call this Problem A on your paper, so I’ll know which one it is.)

Suppose we have this code:

(define (f x) (* x x))

1. What is this turned into internally when the Scheme

interpreter reads this definition?

2. Given this definition, and given the following expression

(f (+ 3 5))

1. Show how this expression is evaluated using applicative-

order evaluation.

2. Show how this expression is evaluated using normal-

order evaluation.

3. Problem 1.34 (page 66) The key point in this problem is the last

word. You should be able to do this in a way that I can understand

what you have written. If I can’t understand it, it’s wrong.

And just to reassure you: even though this problem occurs after

the pages I asked you to read for this, you should be able to do it

without any extra knowledge.

4. For extra credit: Problem 1.5 (page 21). And notice that the

problem asks for an explanation. If all you put is the answer but

not a clear and convincing explanation for it, I’m not even going to

read it. Please keep this in mind—it will apply to virtually

everything we do.

To test your answers and your understanding you will want to be able to

play with Scheme while you read the text. To run the UMB Scheme

interpreter simply type

% scheme

at the Unix prompt. Then enjoy.

To work with a file of Scheme code rather than simply typing at the

Scheme prompt you can redirect input (and output) with

% scheme < somefile.scm > somefile.out

or (load “somefile.scm”) while in Scheme.

Note: Your answers to the exercises should come along with (or be

incorporated in) a short essay in which you discuss what you discovered

about Scheme. How does it compare to other languages you know? Did

any of its responses surprise you? What is the largest integer Scheme will

handle? What message appears when you type ‘+’ at the Scheme prompt

(and what does the message mean)? What other experiments did you

perform? What do you like or dislike (so far) about Scheme?

This essay and the others I will regularly ask for are an important part of

how you learn, and an important part of your grade. I usually read them

before I read your code. So take them seriously.

Part II. Due Wednesday, September 15, 5:00 PM.

(Collected electronically.)

When your application for a Unix account for this course was processed, a

cs450 subdirectory of your home directory was created for you. You are to

do all your work for this course there. Do not ever change the protections

on this directory, or on any files or subdirectories in it. Sometimes I have

seen students who think that others can see what is there, and try to read-

protect it. Regardless of what it might look like to you, these directories

are actually set up so that only you and I and the grader can see what is

there. So don’t worry, and don’t change the permissions. If you do, lots of

stuff will break. You don’t want that to happen. (For one thing, it will make

it impossible for me to collect your homework, and you won’t get credit for

it.)

Create a hw1 subdirectory of your cs450 directory. Do your work for this

assignment there.

Emacs knows about Scheme. It edits files with the .scm extension in Scheme

mode. In that mode, the tab key will indent code correctly. If you are not an

emacs user you should definitely learn that editor now. It’s much more

powerful than vi; that power will save you lots of programming time.

One of the reasons I’m making a big point of this is that your code needs

to be indented properly so that it can be understood. I (and the grader as

well) have to be able to read your code and understand it. If the

indentation is messed up, I can’t do this, and I will definitely take off points.

I’m not trying to be mean about this. This is just an important thing that

you have to be able to do.

And by the way, I occasionally have students who try to do their work in

Microsoft Word and then somehow turn it back into plain text. They end up

wasting an incredible amount of time doing this, and their work looks like a

mess. Don’t fall into this trap. Use emacs, and if you need help, just ask

me, or send me email.

Rapidly read through the Scheme language report (“Revised5 Report on the

Algorithmic Language Scheme”; this is usually referred to as “R5RS”). Do

not try to learn everything that’s there. At this point you won’t really

understand very much of it. Skip all the hard parts. Use this reading to

learn the kinds of things that can be found there, so you can look things up

when you need to. And you will need to later.

Put the answers to the exercises listed below in a file named

ASanswers.txt in your hw1 directory. Your answers should be written out in

complete paragraphs. Your work should be sufficiently self contained so

that three months from now you will be able to look at them and

understand them without having to go back to the book to see what the

question was, or the point of the question.

This file should be a plain ASCII text file. You will have to rely on white

space for formatting. I am not going to deal with any files that contain

extra or hidden formatting characters, whether it is Microsoft Word or

HTML. And please make sure that all your lines in this file are 80

characters or less in length. If you put this line

(setq-default fill-column 80)

in your ~/.emacs file, this will help you. But you still have to make sure that

your lines haven’t run over. (And yes, I really mean this. I’m taking off

points if lines run over. If you don’t know what I mean, ask me or send me

email.)

Remember that unix file names are case sensitive. Here are three file

names that are incorrect:

asanswers.txt WRONG!

ASanswer.txt WRONG!

ASanswers.doc WRONG!

Do you see what is wrong with each of them? If you name your file even

slightly incorrectly, my collecting script will not find it, and I will never see

your homework. It is not my responsibility to go rummaging around in your

directory to try to figure out what you have named your files. So please be

careful with file names. It will save us both a lot of grief.

Here are the exercises you should do:

1. Problem 1.6 (page 25). Note that this exercise calls for an explanation,

not a program.

2. Problem 1.12 (page 42). To be precise, let us define the function p for

“Pascal” which takes two arguments:

r — the row number
e — the element number in the row

So (p r e) is the value of element e in row r. And we number the rows

starting from 0, and we also number the elements in each row starting

from 0. (That is the usual convention.) Thus for instance,

(p 0 0) evaluates to 1
(p 2 1) evaluates to 2
(p 4 2) evaluates to 6

and so on. The problem then is to write a recursive Scheme procedure

for the function p. And I really mean “recursive”. For this problem,

forget everything you ever learned about formulas for the elements of

Pascal’s triangle that involve factorials.

And I shouldn’t really have to say this, but you should make sure you

test your function, and indicate to me how you did this.

3. For extra credit: Exercise 8.1 in the Lecture 2 handout.

And when I say, “Be sure to discuss design and testing”, I really mean it.

You should be able to write something interesting and meaningful, and it

should be longer than just a few sentences. If you can’t think of anything

to write, then you probably haven’t thought enough about these problems.

In any case, please do feel free to contact me by email with any questions.