Note: Before working this assignment, please read through Section 1.1.5 of Structure and Interpretation of Computer Programs (also known as SICP).
Numbers in bold at the start of problems (e.g. [10]) are a crude estimate of the time (in minutes) the problem should take. If it seems like a problem is taking you disproportionately long to complete (e.g. if you are spending hours on a problem rated [10]), that is a hint that you might want to talk to a TA. These numbers assume that you have read the book and done the portions of the assignment that precede it.
One thing you should do immediately is to make sure you have an account on the CS cluster and begin to become familiar with the computers in the lab. This series of exercises is intended to guide you through this process.
The computers we are using for CS1 are in the CS lab (Jorgensen 154). TAs staff the lab Sunday through Wednesday to answer your questions and help you through difficulties (the first week they will be there from Tuesday to Friday).
[10] Sign up for a computer account using the Account Request Form.
If you have not already done so, do this immediately as it will take a bit of time to process your account.
[30] Review the Unix handout. You may also want to go to the Tutorial session on Thursday, September 30 (10:00pm in Jorgensen 74).
[15] Go to the lab and log in to a CS computer with your new account and password.
[5] Make sure that you can start up a terminal window, which is a window into which you can type commands to be executed immediately. If you can't figure out how to do this, ask your TA.
[5] If you do not plan to log in to the CS cluster and check your mail there regularly, make sure your mail is forwarded to wherever you do read mail regularly (e.g. your ITS account). Ask your TA to help you set this up (it's very easy). This is very very important! If you don't do this, you will not receive any of the emails that CS1man sends you!
[30] The Scheme interpreter we will be using for CS1 is
called DrScheme (pronounced "doctor
Scheme"). DrScheme also provides a full development environment for your
Scheme programs. Start up DrScheme by typing "drscheme &" at
the terminal prompt; the DrScheme environment will come up in a new window.
The first thing you need to do is to set the DrScheme "language level", which
means which version of the programming language Scheme to use. DrScheme
supports many different dialects of Scheme, and we will be using several of
these in this course. Go into the "Language" menu and select the "Choose
Language" option. Select Teaching languages/How To Design
Programs/Intermediate Student with lambda and click OK. Then click the
Run button in the main DrScheme window and you are ready to go.
WARNING: if you select the wrong language level, things WILL
NOT work the way they're supposed do, so be careful. You can always
change the language level later using the menus if this happens. We will let
you know which language level to use for any given assignment, but this one
will suffice for now. When you exit DrScheme, the language level you were
last using is stored, so you won't have to set it again when you start
DrScheme up again unless you want to change it to something different.
The main DrScheme window is divided into two parts. The upper half is where you enter most of your code (the stuff your TA will be grading). This is called the "definitions" window. The lower half is called the "interactions" window; in it you can type single expressions to be evaluated. This allows you to easily test the definitions you have entered in the definitions window.
Click on "help desk" in the "help" menu. This will bring up a web browser window where all the documentation for DrScheme is found. Much of this documentation is highly technical, but one thing you should check out is the documentation on DrScheme itself under the "Tools" heading. Don't feel like you need to read this in detail, but it's worth skimming so that you're familiar with what DrScheme can do.
Note that the files you turn in for your CS1 assignments must be plain-text (also known as ASCII) files (so, for example, Word documents are not acceptable --- your TA will return any such submissions unmarked and ask you to rewrite or convert your work to ASCII text). DrScheme will store your Scheme code as plain text files.
CS1 will rely on email to contact students. After each assignment has been graded your TA will send you email commenting on your answers and code. If you did not master all the concepts on the lab, your TA will tell you what you need to rework in order to complete the lab.
There is no part B this week. Please make sure you have read the assigned sections of SICP. There will be problems from the book assigned in part B in subsequent weeks.
In this section, make sure that you are using the Intermediate Student with lambda language level as described above.
In this course, we want you to write functions in a particular stylized way.
Let's illustrate this with a trivial function which doubles its input. We'll
call the function double. Here's how we want you to write this
function:
;; double: number -> number
;; This function returns twice the input value.
(define (double n)
(* n 2))
;; Tests:
(check-expect (double 0) 0)
(check-expect (double 42) 84)
The first line (;; double: number -> number) is a special kind
of comment called the contract of the function. After the semicolons,
this line contains the name of the function, followed by a colon, followed by
the type of the function argument n (which is supposed to
be a number), followed by an arrow, followed by the type of the result (also a
number). If there are more than one arguments to the function, they will be
listed before the arrow (e.g. a sum of squares function would have the
contract ;; sum-of-squares: number number -> number). Since the
contract is a comment, the Scheme interpreter will ignore it altogether, but it
is extremely good documentation for anyone trying to read (and understand) your
code (for instance, your TA). Contracts make the purpose of the function
clearer by specifying what kinds of data are consumed and produced by the
function. We expect you to put proper contracts before every function you
write. For now, the only type of data you will be working with are numbers, but
we will be introducing other types of data as we go along.
As an aside, the name of the function in a contract is important too! You
should give functions meaningful names and avoid the temptation to write
abbreviated names (like dbl in this case). Sure, they're quicker
to type, but they're also harder for people to read. We will take marks off for
bad function names. If you're unsure of whether your function names are good
enough, ask your TA.
The second line (;; This function returns twice the input
value.) is the function comment. It is a very brief verbal description
of what the function does. If possible, don't just restate what the code
already says but give a higher-level description of what the purpose of the
function is (in this case, there is no such higher-level description, but there
usually will be). Writing good function comments is an extremely important
skill; not only does it let the TA know whether or not you understand what the
function is supposed to be doing, it will serve the same purpose if you need to
look at the function in a few months or a few years (say, to modify it).
Beginning programmers usually don't like to write comments because they think
that they're useless; experienced programmers know better.
The next two lines constitute the actual code (also sometimes called the "body") of the function. This is the part that is actually executed by the computer when the function is called.
After the code we have the tests of the function. DrScheme provides an
extremely useful function called check-expect which you can use to
test your functions. check-expect takes two operands: the first is
a function call, and the second is the correct result of the function call. If
the function gives the correct result for all of the tests, DrScheme will
report "All tests passed!" when you run this code. If not, it will report an
error. Checking your functions right after you write them is an extremely
effective way to ensure that your programs will work as expected. However, it's
important to know what to test, since you can't usually test every possible
input to a function. We will be giving you hints about how to write good tests
as we proceed.
At this point, you should do the following:
[3] Type the above code into the top window of DrScheme (the definitions window) and hit the Run button. What happens?
[1] Comment out the tests by putting a semicolon in front of the
lines with check-expect in them and re-run the code. Now what
happens?
[1] Uncomment the lines you just commented out, and now change
the body of the function so that instead of (* n 2) you have
(+ n 2). Re-run the code again. Now what happens?
You don't need to hand in the answers to the questions above. Just make sure you understand how testing works in DrScheme.
[15] Type the following expressions into the DrScheme interactions window (the lower window) one at a time, then hit return. Make sure you understand why each expression gives the result it does. Then type all of the expressions into the definitions window (the upper window) and click on the Run button. Note that the results appear in the lower window in the order in which the expressions were encountered. (The computer will, not surprisingly, print out a message to the effect that "This program should be tested." Don't worry about it.)
(* 6 9)
(* (+ 2 3) (+ 3 4))
(define b 9) b
Note! This particular example will not work as intended in the "Intermediate Student with Lambda" language level of DrScheme (a student pointed this out to us). If you want to see what it would do in full Scheme, you can switch to the "Legacy Languages/R5RS" language level and try it out there. Just be sure to switch back to the "Intermediate Student with Lambda" language level before continuing with the rest of the lab.
(define (answer) 42) answer (answer)
(define (f x) (+ 4 (* x 5) (* x x))) (f 2) (f 5)
[60] Write a series of Scheme functions for temperature conversion. In each case, make sure that
each of your functions has a contract, a function comment, the body of the function (of course), and some tests
using check-expect. Write all these functions in the definitions window of DrScheme (the upper
window). Make sure you run your tests!
Write a Scheme procedure to take a Celsius temperature and return the corresponding Kelvin temperature. Test it for Celsius temperatures -273. -100, 0 and 100.
Write a routine to take in a Fahrenheit temperature and convert it to Celsius. Test it on Fahrenheit temperatures 212 (which is 100 Celsius), 32 (which is 0 Celsius) and -40 (which is -40 Celsius).
Compose (i.e. combine) your previous two functions to create a Fahrenheit to Kelvin conversion function. Test that 32 Fahrenheit equals 273 Kelvin and 212 Fahrenheit equals 373 Kelvin.
[20] Learn how to use DrScheme "teachpacks". A "teachpack" is a set of pre-written definitions
that are useful for solving particular problems. Often, a teachpack will provide an interface which will help
you run your functions in an interesting way, often involving graphics. The teachpacks themselves are written
in Scheme, but they use more advanced features of the language than we will be covering in this course.
Fortunately, you don't need to know how they work to use them. This exercise will show you how to use a
teachpack to test your fahrenheit-to-celsius function.
Go to the Language menu and select "Add Teachpack". Select "convert.ss" from the list and hit OK. Then hit Run. In the definitions window, add the line:
(convert-repl fahrenheit->celsius)
after the definition of fahrenheit->celsius. Then hit Run. This will bring up an
interactive program which you can use to test your function on various values. (The name "repl" stands for
"read-eval-print-loop" and has a long history. It basically just means an interactive program that reads
in some input, evaluates it, prints it, and starts over.) Enter some values, press the return key, and see
what happens. Type x followed by a return to exit the test.
Using the same teachpack and the same code in the definitions window, change
convert-repl to convert-gui and hit Run. This will bring up a separate window
which you can use to test your function graphically. Scroll the Fahrenheit slider and hit the "Convert"
button to see its Celsius equivalent. Try entering the same numbers you used in the
check-expect tests and seeing what results they give. You might want to widen the window
slightly to allow you to enter all the numbers exactly.
[20] Become familiar with how to save and load definitions into DrScheme.
Save the temperature conversion functions you wrote into a file called
temp_conversions.ss by hitting the Save button on top of the definitions window and
specifying the file name. Alternatively, you can go into the File menu and select Save
Definitions As....
Exit and restart DrScheme so that you are starting with a fresh environment.
Now load the file using the File/Open menu command.
Exit DrScheme and restart it with the filename as a command-line argument as follows:
% drscheme temp_conversion.ss &
where % is the terminal prompt (yours may look different).
In the future, you will often find it convenient to write your code in files and load them into the Scheme interpreter as you need them.
These exercises will test your understanding of Scheme syntax and of the substitution model. They can be done offline (without using the Scheme interpreter). If you like, you can also use the DrScheme stepper (that's the button marked like a big foot) to help you with the evaluations, but be aware that the stepper uses a slightly different evaluation sequence than the one we discussed in class. Specifically, it skips a lot of steps and it evaluates the operator before the operands. Nevertheless, it will give you the same results. Go to the DrScheme Help Desk to learn more about using the stepper, or ask your TA.
You will need to type up your results to submit them with your answers to the rest of the assignment. We recommend that you type them up as part of your Scheme file, but that you comment them out by putting a semicolon in front of each line. Alternatively, you can write them in a separate (plain text) file.
Translate the following expressions into Scheme syntax:
[5] 2 * 9 + 62 - 8
[5] (42 * (6 + 7 + (5 - 2)))2
Walk through the substitutions involved in the evaluation of the following expressions. Show every step. Really. Every single step, no matter how trivial.
[5]
(+ 1 (/ (- 2 3) (* 4 5)))
[15]
(define (f x) (+ (- 2 x) (* x (+ x 5)))) (f 3)
NOTE: Don't forget to evaluate the define as
well as the function call!
[20] What is wrong with these expressions?
(+ + 3)
(+ 3 4
(3 + 4)
(2)
((+ 2 3))
(define b 3 4)
(define c + 3 4)
(define b (x) (+ x 1))
Type the buggy expressions above into the interactions window of DrScheme. See how the interpreter responds to these "bugs". (You don't need to write up the error messages.)
Finally, read the instructions on how to use the cs1man submission program to turn in your assignment, and then do so.
Here is what you need to turn in for this lab:
Part A: There is nothing to turn in for this section.
Part B: There is no need to turn in your reading. In fact, we're not even sure it's possible.
Part C: Turn in the answers to section C.2 only.
Part D: Turn in the results for all exercises except for section D.3.i.