You should read through the end of Section 2.1 in order to be fully prepared for this lab.
For this lab, and for the rest of the class, we will be using the "module" language level of DrScheme, which is its most advanced level. There are several things to note about this level:
Most important: before you write any code in the top (definitions) window, you need to include the magic line:
#lang scheme
at the top of the file.
In order to use the check-expect function for testing, you need to put this line after the #lang scheme line:
(require htdp/testing)
and you need to put this line after your definitions and tests (i.e. at the bottom of the definitions window):
(generate-report)
This will run the tests and tell you the results. If you leave out this line, it's not an error, but the tests won't be run.
Speaking of testing, there is a handy testing function called check-within that can be used to check functions that return floating point numbers (i.e. approximate real numbers with some maximum number of decimal points). It's automatically loaded when you have the (require htdp/testing) line in your code. It works like this:
(define (my-sqrt x) ...) ; some function to compute square roots (check-within (my-sqrt 2.0) 1.414 0.001)
This checks that (my-sqrt 2.0) produces a value that is within 0.001 of 1.414. Functions that return floating-point numbers (approximate real numbers) should always use check-within rather than check-expect for testing, because floating-point numbers are difficult to specify exactly in decimal form (due to technical considerations we don't want to go into here).
In this language level, you can use either style of internal definitions (the style that SICP uses, or the one using local that is available in the DrScheme teaching language levels).
The stepper is not available in this language level. Sorry.
As you answer the problems below, make a note on how long you spent on each of the sections.
If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.
Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.
Consider:
(define (make-add-constant constant) (lambda (x) (+ constant x)))
[5] Show how this procedure can be used to define a function which adds 5 to its argument.
[5] Define an analogous,
make-multiply-constant function.
[15] Define the higher-order function
make-op2-constant which takes both the two argument
function (e.g. + or * shown here) and the constant as arguments
and returns a single argument function just as
make-add-constant and make-multiply-constant
do.
[5] Show how to use make-op2-constant to
define the same procedure you defined in part a.
Determine the value of the following by working through the substitution model evaluation of each expression. Use the DrScheme editor to help with the parenthesis matching. Include your full substitution evaluation in your solution. (Remember that the stepper is not available in the module language level, but if you go back to a previous language level and use it, it's OK with us. However, it probably won't be very illuminating.)
You may use the evaluation shortcuts that were allowed in previous labs, i.e.:
+ ==> + instead of
+ ==> [primitive procedure +](lambda (x) ...) ==> itself
instead of copying the entire lambda expression(= 2 0) ==> #f
and (- 2 1) ==> 1.
(+ 2 x) then you have to evaluate it
explicitly.[10]
(((lambda (y) (lambda (x) (/ x y))) 2) 4)
[20]
((((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3) 4) 5)
[10] What's wrong with these expressions?
(car 1)
(cdr 2)
(+ (cons 1 2) 2)
After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".
[10] Consider the following functions:
(define (square x) (display (* x x))) (define (sum-of-squares a b) (+ (square a) (square b)))
Presumably, the writer of the square function intended it to be used to find the square of an input number. If you type this into DrScheme and try it out, it will indeed display the correct square of a given input number. Nevertheless, sum-of-squares will not work. Why not? [This mistake is seen all the time in CS 1 exams.]
[10] Given:
(define (order a b)
(if (< a b)
(cons b a)
(cons a b)))
Define max and min in terms of
order.
Please work the following exercises from the textbook. Make sure that your functions all have proper comments and contracts (unless specified otherwise). You don't need to put in explicit tests for these problems.
Note that in a contract, if a function (used as an argument or returned from another function) has arguments and/or return types which are unknown, just use lower-case letters like a, b, c, etc. An unknown function of one argument will thus have the type (a -> b), since we don't know what the argument or return types are (or if they're the same). Make sure that all the types match up correctly.
[20] Exercise 1.42 (compose -- operations of functions on functions)
[20] Exercise 1.43 (repeated application of functions)
Note that the first argument of the repeated function is a
function f that takes one argument only. This is implied by
the problem statement but isn't specified as clearly as it might be.
We definitely suggest that you use your compose function
from the previous problem in this problem; it'll make the solution much
simpler.
[30] Exercise 2.4 (cons, car, and cdr in terms of lambda)
You don't have to rigorously prove that (car (cons x y)) =
x for any x and y and the new versions
of car and cons. Just give a brief
explanation.
(Don't write contracts for the functions in this problem. They do exist, but they are quite complex. You can also skip the function comments because we already know what cons, car and cdr do.)
Then verify that (cdr (cons x y)) = y for any
x and y in detail by determining the value
of (cdr (cons 1 2)) using the new versions
of cons and cdr and using the substitution
model.
N.B.: You probably want to use a clean Scheme interpreter session for this problem only, so that you can return to the normal definition of cons/car/cdr for the other parts of the lab.
lambdaNumerical differentiation in one argument:
[30] Define the function numerical-derivative which takes a Scheme
function of one argument representing a mathematical function and returns a new procedure which
calculates the derivative of the specified function. (For this problem you may define dx in a
let statement inside your function; set it to 0.001.) Give a contract and comment, but no tests
(we'll do those below).
[15] Use your numerical-derivative to define derivative functions for the
following functions. Test that your derivatives produce correct results within a reasonable
amount of error, using the check-within procedure as described above.
(define f1 (lambda (x) (+ (* 12.0 x x) (* 3.0 x) 1.0)))
Evaluate the derivative at x = 3.0, within an error tolerance of 0.02.
(define f2 (lambda (x) (* x (exp (* 3.0 x)))))
Evaluate the derivative at x = 3.0, within an error tolerance of 200.0.
(define f3 (lambda (x) (log x)))
Evaluate the derivative at x = 3.0, within an error tolerance of 0.001
[20] Define a function that returns the function that takes the nth-derivative of a function. (You should use your numerical-derivative procedure defined in the previous problem.) Be sure to check that (nth-derivative 1) gives a function that is equivalent to the numerical-derivative function defined above. You can also use the fact that the zeroth derivative of a function is the function itself. Write a contract and comment, as usual. Assume that all functions involved are functions from numbers to numbers. You don't have to write explicit tests. Use this function to define functions computing the first, second, and third derivatives of functions from numbers to numbers. (You can omit the contract, comments, and tests from these derived functions).
Numerical integration in one argument:
[60] Define a function make-integrator that
takes two arguments:
and returns another function, which we'll call F2 for short. F2 takes
one argument, which is a function to be integrated; we'll call that
function F3 for short. The output of F2 is yet another function, which
we'll call F4. In other words, F2 takes in function F3 and returns
function F4. This function F4 takes two arguments (an upper and lower
limit) and returns the value of the integral of F3 between those limits.
This value is computed using the expansion rule and the integration
interval that were used to create F2 by make-integrator.
That is, we should be able to do the following:
(define simpsons-integrator (make-integrator
(lambda (f x dx)
(* (/ dx 6.0)
(+ (f (- x (/ dx 2.0)))
(* 4.0 (f x))
(f (+ x (/ dx 2.0))))))
0.001))
(define integral-logx (simpsons-integrator (lambda (x) (log x))))
(integral-logx 2.0 4.0) ; returns the integral of log(x) between 2 and 4
In this case:
simpsons-integrator function, returned from
make-integrator(lambda (x) (log x))integral-logx function[N.B. We have posted a short explanation of expansion functions for integration on this page.]
As usual, write a contract and a comment for your function, but you can omit tests. You can assume that all function arguments which aren't themselves functions are numbers. Note that the expansion rules themselves each have the contract (number -> number) number number -> number. These contracts are quite complicated, so take your time. You don't need to restate the function contract in the comment.
[5] Define a Simpson's rule integrator function for dx = 0.00001. (You can skip the contract, comment, and tests.)
[15] Using your make-integrator show how you would make an integrator
based on the simple expansion rule (shown in Section 1.3.1, just before exercise 1.29) for dx =
0.00001. (You can skip the contract, comment, and tests.)
[20] For the three functions below and each of the two integration functions defined above [in (b) and (c)], evaluate the integrals from x=1.0 to x=3.0. Make a table of your results (you will have 3 x 2 = 6 results).
(define f1 (lambda (x) (+ (* 3.0 x) 1.0)))(define f2 (lambda (x) (sin x)))(define f3 (lambda (x) (- 10.0 (exp x))))[10] Consider this procedure to compute one solution of the quadratic equation a*x2 + b*x + c = 0:
(define (solve-quadratic-equation a b c) (define disc (sqrt (- (* b b) (* 4.0 a c)))) (/ (+ (- b) disc) (* 2.0 a)))
What makes this procedure hard to understand?
Write a cleaned up version of this procedure.
What makes the new version easy to understand?