Fundamentals of Computer Science I (CS151.02 2007S)
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
This lab is also available in PDF.
Summary: In this laboratory, you will ground your
understanding of the basic techniques for naming values and procedures
in Scheme, let
and let*
.
Contents:
let
let
What are the values of the following let
expressions?
You may use DrScheme to help you answer these questions, but be sure you
can explain how it arrived at its answers.
a.
(let ((tone "fa") (callme "al")) (list callme tone "l" tone))
b.
(let ((total (+ 8 3 4 2 7))) (let ((mean (/ total 5))) (* mean mean)))
c.
(let ((inchesperfoot 12) (feetpermile 5280)) (let ((inchespermile (* inchesperfoot feetpermile))) (* inchespermile inchespermile)))
Write a nested let
expression that binds a total of five
names, alpha
, beta
, gamma
,
delta
, and epsilon
, with alpha
bound to 9387 and each subsequent name bound to a value twice
as large as the one before it. That is, beta
should be
twice as large as alpha
, gamma
twice as
large as beta
, and so on. The body of the innermost
let
expression should then compute the sum of the values
of the five names.
Your result will look something like
(let ((...)) (let ((...)) (let ((...)) (let ((...)) (let ((...)) ...)))))
Write a let*
expression equivalent to the
let
expression in the previous exercise.
The file /home/rebelsky/Web/Courses/CS151/2007S/Examples/verbosebindings.ss
contains alternative versions of define
,
let
, and let*
(named verbosedefine
,
verboselet
, and verboselet*
).
a. Load this file with the following Scheme command.
(load "/home/rebelsky/Web/Courses/CS151/2007S/Examples/verbosebindings.ss")
b. Rewrite the examples from Exercise 1 to use verboselet
.
c. Rewrite your code from Exercise 2 to use verboselet
.
d. Rewrite your code from Exercise 3 to use verboselet*
.
In the reading, we noted that it
is possible to move bindings outside of the lambda in a procedure
definition. In particular, we noted that the first of the two
following versions of yearstoseconds
required
recomputation of secondsperyear
every time it was called
while the second required that computation only once.
(define yearstosecondsa (lambda (years) (let* ((daysperyear 365.24) (hoursperday 24) (minutesperhour 60) (secondsperminute 60) (secondsperyear (* daysperyear hoursperday minutesperhour secondsperminute))) (* years secondsperyear)))) (define yearstosecondsb (let* ((daysperyear 365.24) (hoursperday 24) (minutesperhour 60) (secondsperminute 60) (secondsperyear (* daysperyear hoursperday minutesperhour secondsperminute))) (lambda (years) (* years secondsperyear))))
a. Confirm that yearstosecondsa
does, in fact, recompute
the values each time it is called. (You might, for example, replace
let*
by verboselet*
.)
b. Confirm that yearstosecondsb
does not recompute the
values each time it is called. (Again, replace the let*
by verboselet*
.)
c. Given that yearstosecondsb
does not recompute each
time, when does it do the computation? (Consider when you see the
messages.)
You may recall that we defined a procedure to compute the roots of a quadratic polynomial as follows:
(define roots (lambda (a b c) (let ((negativeb ( b)) (squarerootof (sqrt ( (* b b) (* 4 a c)))) (twoa (* 2 a))) (list (/ (+ negativeb squarerootof) twoa) (/ ( negativeb squarerootof) twoa)))))
You might be tempted to move the let
clause outside the
lambda, just as we did in the previous exercise. However, as we noted
in this reading, this reordering will fail.
a. Verify that it will not work to move the let
before
the lambda, as in
(define roots (let ((negativeb ( b)) (squarerootof (sqrt ( (* b b) (* 4 a c)))) (twoa (* 2 a))) (lambda (a b c) (list (/ (+ negativeb squarerootof) twoa) (/ ( negativeb squarerootof) twoa)))))
b. Explain, in your own words, why this fails (and why it should fail).
In a recent laboratory, you wrote a procedure that took as parameters a list of real numbers and identified the number in that list that was closest to zero. Those of you who didn't want to use any sort of helper wrote something like the following:
(define closesttozero (lambda (lst) (cond ; If there's only one element in the list, it's closest to zero ((null? (cdr lst)) (car lst)) ; If the current element is closer to zero than the closest ; remaining thing, use that ((< (abs (car lst)) (abs (closesttozero (cdr lst)))) (car lst)) ; Otherwise, use the thing in the remainder closest to zero (else (closesttozero (cdr lst))))))
There is a hidden difficulty here: In some cases, we do two recursive calls, rather than one recursive call. From one perspective, that doesn't seem like a lot. However, it can be quite costly.
a. Add the following lines to closesttozero
, right before
the cond
statement.
(display (list 'closesttozero lst)) (newline)
b. Find the number closest to zero in the list (1 2 5 11 23 45). How many recursive calls are there?
c. Suppose we wanted to find the number closest to zero in the list (45 23 11 5 2 1). How many recursive calls would you expect to see?
d. Check your answer to the previous subproblem experimentally. If the result does not match your expectation, explain the difference. (In fact, if the number of recursive calls is different than the number for b, explain the difference.)
e. Here's a slightly different version of the program, using
let
to name the recursive call.
(define closesttozero (lambda (lst) (if (null? (cdr lst)) (car lst) (let ((closestremaining (closesttozero (cdr lst)))) (if (< (abs (car lst)) (abs closestremaining)) (car lst) closestremaining)))))
Check to make sure that it works.
f. Insert lines to print out a list similar to that in step a.
g. Suppose we want to find the number closest to zero in the list (1 2 5 11 23 45). How many recursive calls do you expect? Try the command. How many recursive calls are there?
h. Suppose we wanted to find the number closest to zero in the list (45 23 11 5 2 1). How many recursive calls would you expect to see? Try the command. How many recursive calls are there.
i. Explain the differences between c&d and g&h.
Consider the following procedure that squares all the values in a list.
;;; Procedure: ;;; squarevalues ;;; Parameters: ;;; lst, a list of numbers of the form (num_1 num_2 ... num_n) ;;; Purpose: ;;; Squares all the values in lst. ;;; Produces: ;;; listofsquares, a list of numbers ;;; Preconditions: ;;; [Standard] ;;; Postconditions: ;;; listofsquares has the form (square_1 square_2 ... square_n) ;;; For all i, square_i is the square of num_i (that is num_i * num_i). (define squarevalues (lambda (lst) (let ((square (lambda (val) (* val val)))) (if (null? lst) null (cons (square (car lst)) (squarevalues (cdr lst)))))))
a. Verify that squarevalues
works correctly.
b. Try to execute square
outside of squarevalues
.
Explain what happens.
c. Replace the let
with a verboselet
. Then
square a list of five values. How many times does square
get bound?
Here's a slightly different version of squarevalues
.
(define squarevalues (let ((square (lambda (val) (* val val)))) (lambda (lst) (if (null? lst) null (cons (square (car lst)) (squarevalues (cdr lst)))))))
a. Verify that squarevalues
works correctly.
b. Try to execute square
outside of squarevalues
.
Explain what happens.
c. Replace the let
with a verboselet
. Then
square a list of five values. How many times does square
get bound? When does it get called?
Here is a procedure that takes a nonempty list of lists as an argument and returns the longest list in the list (or one of the longest lists, if there is a tie).
;;; Procedure: ;;; longestlistinlist ;;; Parameters: ;;; los, a list of lists ;;; Purpose: ;;; Finds one of the longest lists in los. ;;; Produces: ;;; longest, a list ;;; Preconditions: ;;; los is a nonempty list. ;;; every element of los is a list. ;;; Postconditions: ;;; Does not affect los. ;;; Returns an element of los. ;;; No element of los is longer than longest. That is, ;;; For each lst in los, (length los) >= (length lst). (define longestlistinlist (lambda (los) ; If there is only one list, that list must be the longest. (if (null? (cdr los)) (car los) ; Otherwise, take the longer of the first list and the ; longest remaining list. (longerlist (car los) (longestlistinlist (cdr los))))))
This definition of the longestlistinlist
procedure
includes a call to the longerlist
procedure, which returns
the longer of two given lists:
;;; Procedure: ;;; longerlist ;;; Parameters: ;;; left, a list ;;; right, a list ;;; Purpose: ;;; Find the longer of left and right. ;;; Produces: ;;; longer, a list ;;; Preconditions: ;;; Both left and right are lists. ;;; Postconditions: ;;; longer is a list. ;;; longer is either equal to left or to right. ;;; (>= (length longer) (length left)) ;;; (>= (length longer) (length right)) (define longerlist (lambda (left right) (if (<= (length right) (length left)) left right)))
Revise the definition of longestlistinlist
so that the
name longerlist
is bound to the procedure that it denotes
only locally, in a let
expression.
Note that there are at least two possible ways to do the previous exercise:
The definiens of
longestlistinlist
can be a lambda
expression
with a let
expression as its body, or it can be a
let
expression with a lambda
expression as its
body. That is, it can take the form
(define longestlistinlist (let (...) (lambda (los) ...)))
or the form
(define longestlistinlist (lambda (los) (let (...) ...)))
a. Define longestlistinlist
in whichever way that you did not
define it for the previous exercise.
b. Does the order of nesting affect what happens when the procedure is
invoked? You may want to use verboselet
to help you answer
this question.
c. If there is a difference, which arrangement is better? Why?
The two definitions of longestoflist
you came up with in the previous exercises
are not the only alternatives you have in placing the let
.
Since longerlist
is only needed in the recursive case,
you can place the let
there.
(define longestlistinlist (lambda (los) ; If there is only one list, that list must be the longest. (if (null? (cdr los)) (car los) ; Otherwise, take the longer of the first list and the ; longest remaining list. (let ((longerlist (lambda (left right) (if (<= (length right) (length left)) left right)))) (longerlist (car los) (longestlist inlist (cdr los))))))
Including the original definition (in which longerlist
is
bound with define
), you've now seen or written four
variants of longestlistinlist
. Which do you prefer?
Why?
Extend your favorite version of longestlistinlist
so
that it verifies its preconditions (i.e., that los
only
contains lists and that los
is nonempty). If the
preconditions are not met, your procedure should return #f
.
It is perfectly acceptable for you to check each list element in turn to determine whether or not it is a list, rather than to check them all at once, in advance.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/let.html
.
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Thu Sep 13 20:54:20 2007.
The source to the document was last modified on Thu Feb 15 21:02:13 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007S/Labs/let.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.