Com S 342 --- Principles of Programming Languages
HOMEWORK 1: SCHEME BASICS
(File $Date: 2001/09/18 07:57:38 $)
Due: problems 1, 3, at beginning of class on Thursday September 13, 2001;
problem 5 at beginning of class on Tuesday September 18, 2001.
In this homework, you will learn some of the basics of Scheme and
functional programming (in particular, a bit about flat recursion).
All code is to be written in Scheme, using the exact procedure names
specified in the problem descriptions. For code hand in *both* your
printout of the code and a transcript of testing (see homework 0 for
instructions on how to make transcripts). This applies even if you
aren't using the department machines. (If you're not, see the
directions in course "running Scheme" web page.)
*No* credit will be given for Scheme programming problems unless you
also hand in a printout of your code and a transcript of its testing.
You may not email us to turn in your homework, we only accept it in
printed form. This is to allow the TAs to comment on your coding style.
You should use the course interpreter, scheme342, for these problems.
A few of the problems required to use the interpreter, scheme342typed,
which provides type checking.
The section headings below give the readings related to the problems.
Doing the readings listed now will save you time in the long run.
STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS
(Sections 1.1.1-1.1.6, 2.2.1-2.2.2, and 2.3.1)
THE LITTLE SCHEMER (p. xiii, chapter 1)
REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME
(Sections 1 [Overview], and 6.1-6.3 [Standard Procedures])
1. (105 points total)
The following is to help you learn Scheme.
Note: don't use the typed interpreters for this problem, as several
parts will cause type errors. Instead use the untyped interpreters.
a. (5 points)
Translate the following algebraic formulas into Scheme's notation.
Your answer may be handwritten, however you may want to check it
with the Scheme interpreter.
(8 * 7) - (10 + 5)
(5 * (4 + (-5 - -3)))
(3 / (5 - (1 / 7)))
For example, translating (7 - (4 - 5)) into Scheme's notation
yields (- 7 (- 4 5)).
b. (5 points)
Describe in words how to translate an algebraic formula into Scheme's
notation. (This can be handwritten.)
IMPORTANT: Make a transcript for parts c, e, f, g, i, k, l. *No
credit* will be given without a printed transcript. These may be
combined into one transcript, but each problem should be clearly
labeled and they should be in order. The TA will deduct points (up to
30%) if there is any difficulty in finding and reading your solutions.
(Some of these problems also require you to give English answers; you
can do this by writing a comment (a semicolon (;) up to a newline is a
Scheme comment) in your transcript, or by giving some
handwriting on your printout.)
c. (5 points)
Give definitions of the variables e and pi in Scheme,
so that they approximate to the usual values (2.73... and 3.14...).
d. (5 points)
Write an if-expression in Scheme that uses both variables e and pi,
and that has as its value the larger of the two variables.
e. (5 points)
Write a similar if-expression that has as its value the smaller of e and pi.
f. (5 points)
Without using an if (or cond) expression, write an expression
that uses both variables e and pi, and that has as its value #t if the
values of e and pi are equal, and #f otherwise.
g. (5 points)
Experiment with ' (quote) in the Scheme interpreter.
Try, for example 'e, '+, '(+ 3 4), and unquoted versions of expressions.
In English, answer the following question: what does ' do?
h. (5 points)
What can you do with a string in Scheme that you can't do with a symbol?
Why is there a distinction between strings and symbols in Scheme?
(You may want to look at the Revised^5 Report on Scheme, see the
course resource web page, for some hints on this.)
i. (5 points)
Using *only* the Scheme procedure 'list', and numbers and quoted symbols
(such as '+, 'sentence, and 'np), write Scheme expressions to make
the following lists. Check them with the Scheme interpreter.
(3 4 2)
(+ 1 (- 2 3))
(sentence
(np (noun fred))
(vp (verb sells)
(object it)))
For example, to make the list (3 (5)), one can use the expression
(list 3 (list 5)).
Note: don't use the typed interpreters for this problem.
j. (5 points)
Draw box and pointer diagrams, as shown in class or in Figure 2.3
of Abelson and Sussman's book (Structure and Interpretation of
Computer Programs), for the above lists.
k. (10 points)
Using *only* the Scheme procedure cons, numbers, quoted symbols
(such as '+, 'sentence, and 'np), and the empty list ('()),
write Scheme expressions to make the lists in part i above.
For example, to make the list (3 (5)), one can use the expression
(cons 3
(cons (cons 5 '())
'()))
Note: don't use the typed interpreters for this problem.
l. (5 points)
Suppose we are writing code for a procedure in which the variable "lst"
is bound to a list of numbers. Suppose further that lst
has the value (3 4 2). For each of the following,
write an expression that uses lst and makes the given list:
(5 3 4 2)
(6 5 3 4 2)
(4 2)
(2)
You can check your answer on the computer by first typing
(define lst (list 3 4 2))
m. (5 points)
Make a transcript showing that Scheme's car and cdr procedures
do not change their arguments. (Hint: you may want to use define.)
n. (5 points)
What are the differences between a vector and a list in Scheme?
What is a vector like in C or C++? How is a Scheme vector different
than the corresponding feature in C or C++?
o. (10 points) [car, cdr, cons transcript]
What do each of the following return in Scheme? (I.e., fill in the
blanks in the following transcript.
Note: assume that you are using the untyped interpreters for this problem.
> (define capitals '((iowa (des moines)) (michigan (lansing))
(florida (talahassee)) (wisconsin (madison))))
> (car (cdr capitals))
> (cadr capitals)
> (cdar capitals)
> (cadar capitals)
> (caadar capitals)
> (cdadar capitals)
> (car (cdadar capitals))
> (cons 'st (cons 'paul '()))
> (cons (cons 'st (cons 'paul '())) '())
> (cons 'minnesota (cons (cons 'st (cons 'paul '())) '()))
> (cons (cons 'minnesota (cons (cons 'st (cons 'paul '())) '()))
capitals)
Use the computer to check your work, but don't do this on the
computer at first. Be sure not to use the typed interpreter,
instead use the untyped interpreter. What you hand in should be
handwritten for this problem.
p. (10 points) [eq? and sharing transcript]
Fill in the blank lines of the following transcript.
> (define x '(a b))
> (define y '(a))
> (define z (cons x y))
> z
> (eq? z (cons x y))
> (equal? z (cons x y))
> (eq? (car z) x)
> (equal? (car z) x)
> (set-car! x 'q)
> x
> z
> (eq? (cdr z) y)
> (set-car! y 'hmm)
> y
> (cdr z)
> (eq? (cdr z) y)
Use the computer to check your work, but don't do this on the computer
at first. What you hand in should be handwritten for this problem.
q. (10 points) [vector transcript]
Fill in the blank lines of the following transcript.
> (define vec1 (vector 3 4 2))
> (define vec2 (vector 3 4 2))
> vec1
> (equal? vec1 vec2)
> (eq? vec1 vec2)
> (vector-set! vec1 0 5)
> vec1
> vec2
> (equal? vec1 vec2)
> (eq? vec1 vec2)
> (define vec3 vec2)
> (equal? vec3 vec2)
> (eq? vec3 vec2)
> (vector-set! vec2 0 6)
> vec2
> vec3
> (equal? vec3 vec2)
Use the computer to check your work, but don't do this on the computer
at first. What you hand in should be handwritten for this problem.
2. (10 points; extra credit)
Considering problems 1(p) and (q) above, summarize the differences
between the Scheme procedures eq? and equal?
THE LITTLE SCHEMER (Chapter 2)
3. (10 points) [all-numbers]
Write a procedure, all-numbers?, which takes a list, l,
and returns #t just when each element in the l is a number, and #f
otherwise. That is, all-numbers? has the following type:
(forall (T) (-> ((list-of T)) boolean))
(See $PUB/docs/typedscm_toc.html for a discussion of the above
notation for types.)
For example:
(all-numbers? '()) ==> #t
(all-numbers? '(3)) ==> #t
(all-numbers? '(2 3)) ==> #t
(all-numbers? '(1 2 3)) ==> #t
(all-numbers? '(not this either?)) ==> #f
Note that, because we stated that the argument is a list, your code
may assume, without checking, that the argument is a list.
(Problem 4 below, however, does not make this assumption.)
Put your code in a file `all-numbers.scm' (we omit the question
marks in file names because they cause problems on some operating
systems). At the top of your code put a version of the following
lines, as in homework 0:
(displayln "Name: ")
(displayln "Section: , ")
To save yourself time, we recommend that you get in the habit of
first testing your procedures yourself. This is better than just
running our automatic test cases first (see below), because you can
control what parts of your code get executed first. It won't make
much of a difference for this problem, but latter you'll be happy
to have this habit.
After doing your own testing, you must provide us a transcript of
our test cases for your code. You can do this as follows.
First, make sure you cd to a directory you own (not $PUB, for example).
If you are using the Com S machines, start a transcript by typing at
the Unix shell's prompt
script all-numbers.out
Then, assuming you have the directory $PUB/bin in your PATH,
start the typed interpreter, scheme342, by typing at the shell prompt
scheme342
(You can, however, use the typed interpreter, scheme342typed, if you wish.)
Now load your code
(load "all-numbers.scm")
Then execute our test by typing:
(test-hw1 "all-numbers")
(If you get errors that appear to be in our files, they are actually
problems in your code... Really!)
You can also add your own test cases to the output by running them
now if you want. When you are satisfied, you can stop by typing
the following lines
(exit)
exit
The first stops the Scheme interpreter, the second stops the Unix script.
Print the file `all-numbers.out' and hand that in with your printout
of the code in `all-numbers.scm'. Be sure your name appears at the top
of your code (as described above).
(See homework 0 for other ways to make transcripts.)
If you aren't on the Com S machines, see the directions in the
course "running scheme" web page. You can also edit and print at
home but test on ISU's machines if you want.
IMPORTANT: No credit will be given unless you hand in a printout of
both your code and a transcript that includes our tests.
4. (10 points; extra credit) [list-of-number]
Generalize all-numbers? to a procedure list-of-number?
that takes any kind of data in Scheme and returns #t just when
the argument is a list of numbers.
For example:
(list-of-number? '()) ==> #t
(list-of-number? '(3)) ==> #t
(list-of-number? '(2 3)) ==> #t
(list-of-number? '(1 2 3)) ==> #t
(list-of-number? '(not this either?)) ==> #f
(list-of-number? 342) ==> #f
(list-of-number? 'all-numbers) ==> #f
(list-of-number? '(3 . 4)) ==> #f
(list-of-number? (cons 3 (cons 4 '()))) ==> #t
Hint: I needed to use has-type-trusted to get my version of this to
type check with the desired type: (-> (datum) boolean). So don't
use the type checker on this problem.
Normally we won't provide test cases for extra credit problems, but
there is one available for this. So hand in a printout of your
code and testing with our test cases, as described in the previous problem.
5. (20 points) [occurs-twice]
Write a procedure, occurs-twice?, which takes a symbol, sym,
and a list of symbols, los, and returns #t just when
sym appears (at least) twice in los, and #f otherwise.
That is, occurs-twice? has the following type:
(-> (symbol (list-of symbol)) boolean)
For example:
(occurs-twice? 'hmm '()) ==> #f
(occurs-twice? 'hmm '(hmm)) ==> #f
(occurs-twice? 'hmm '(hmm hmm)) ==> #t
(occurs-twice? 'other '(hmm hmm)) ==> #f
(occurs-twice? 'ah '(ah ha oh but ah)) ==> #t
(occurs-twice? 'ah '(uh ah ha oh but ah)) ==> #t
(occurs-twice? 'ah '(ah ah ah)) ==> #t
(occurs-twice? 'ah '(ha oh but ah oh)) ==> #f
(occurs-twice? 'not '(not this either?)) ==> #f
Hint: this is easy if you use an appropriate helping procedure.
If you write the helping procedure yourself, you should test it
separately.
As always, put your code in a file `occurs-twice.scm', and include
your identification at the top of your code. (See problem 3.)
Hand in a printout of your code and a transcript of testing that
includes our test cases, which you can execute using:
(test-hw1 "occurs-twice")