You are currently browsing the tag archive for the ‘exercises’ tag.

A few more exercises – one that looks at the way Scheme interprets expressions and a brief glance at special forms, and a couple of numerical ones.

Exercise 1.6

Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. Can’t we just define it in terms of cond? Alyssa defines a new version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

This seems to work:

> (new-if (= 0 1) 0 5)
5

> (new-if (= 1 1) 0 5)
0

Alyssa now uses new-if to rewrite the square root program:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

What happens when Alyssa tries to use this program to compute square roots? Explain.

The program will enter into an infinite loop. When you call new-if the interpreter attempts to evaluate all the inputs, and then passes them into cond. In the square root program, the third input to new-if calls sqrt-iter, which involves another call to new-if, which calls sqrt-iter again, and so on.

In contrast, the special form if evaluates its first argument, and then evaluates only one of the remaining two arguments depending on whether the first argument is true or false — therefore the problem of entering into an infinite loop never arises, as eventually the first argument returns true, which means that the second argument (rather than the third) is the one that gets evaluated.

Exercise 1.7

The good-enough? test used to compute square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inaccurate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and stop when the change is a very small fraction of the guess. Design a square root procedure that uses this kind of test. Does it work better for small and large numbers?

The procedure fails for very small numbers because it is not accurate enough. For example, say we want to compute the square root of 0.000001 (which is 0.001) using this procedure. If our initial guess was 0.02 (too big by a factor of 20) then our test squares it to get 0.0004, which is certainly within 0.001 of the input — so this guess passes the test, and is reported as the true number. Here’s an example, using 1.0 as an initial guess:

> (sqrt 0.000001)
0.031260655525445276

It fails for large numbers because the computer only stores floating point numbers to a limited precision — it uses a fixed number of bits to store a number of significant digits, and the rest of the bits to store an exponent. The limit of precision is often called machine epsilon. For significantly large numbers, machine epsilon is bigger than 0.001, and thus the difference between any two different, sufficiently large numbers will be greater than 0.001, and the process will not terminate. For example, trying to computer

> (sqrt 1000000000000000)

(that’s 1 followed by 15 zeros) causes the interpreter to hang.

To get around this, we can redefine good-enough?. We supply it with the previous guess and the new guess, and it returns true when the difference in guesses is smaller than the new guess by some fixed ratio (let’s say 0.000001, or 10^{-6}). Our sqrt-iter process becomes:

(define (sqrt-iter old-guess new-guess)
  (if (good-enough? old-guess new-guess)
      guess
      (sqrt-iter new-guess (improve new-guess))))

with good-enough? now given by:

(define (good-enough? old-guess new-guess)
  (< (abs (- old-guess new-guess)) (* 0.000001 new-guess)))

We can now try computing the square roots of very small and large numbers:

> (sqrt 0.000001)
0.0010000000000000117

> (sqrt 1000000000000000)
31622776.601683907

and see that everything works as we would expect it to.

Exercise 1.8

Netwon’s method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value

\dfrac{x/y^2 + 2y}{3}.

Use this formula to implement a cube root procedure analogous to the square root procedure.

We only need to change a few of our procedures. Our newly improved good-enough? procedure is already fine. If we implement a procedure improve-cbrt as

(define (improve-cbrt guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

and the iterative cube root as essentially identical to the iterative cube root:

(define (cbrt-iter old-guess new-guess x)
  (if (good-enough? old-guess new-guess)
      guess
      (cbrt-iter new-guess (improve-cbrt new-guess) x)))

and finally

(define (cbrt x)
  (cbrt-iter 0.0 1.0  x))

then we can use our new cube root procedure as we’d expect:

> (cbrt 8)
2.0

> (cbrt 100)
4.64158883361313

Next we’ll look at a way to hide our abstractions from the end user, by defining procedures inside other procedures.

Advertisements

Now we get onto some more interesting exercises, that explore the way that the Lisp interpreter works.

Exercise 1.4

Our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behaviour of the following procedure:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

This is cool! We want the function to return a + |b|, which we can do by making it return a + b if b>0 and a - b otherwise. Because procedures are like any other data type in the language, they can be the return value of an expression. We use that to our advantage here, by using an if procedure that returns the procedure + in the case that b > 0 and - otherwise. Try doing that in Java!

Exercise 1.5

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order or normal-order evaluation. He defines the following two procedures:

> (define (p) (p))

> (define (text x y)
    (if (= x 0)
        0
        y))

Then he evaluates the expression

> (test 0 (p))

What behaviour will Ben observe with an interpreter that uses applicative-order evaluation> What about normal-order?

The procedure p is defined in terms of itself, so if we ever try to evaluate p we will end up in an infinite loop. If we use applicative order application, then both arguments to test are evaluated before we call test with those arguments. Since this involves evaluating p, the interpreter will hang.

On the other hand, if we use normal-order application then we expand out the arguments without evaluating them, to get

(if (= 0 0)
    0
    (p))

now when we evaluate this, we first test if (= 0 0), which returns true, so we execute the first statement after the predicate: the second statement, which is p, is never evaluated, and the program happily returns 0.

The first exercise is merely to evaluate some Lisp expressions manually, and then check them in the interpreter. Easy and not too interesting, but I did say that I’d do every exercise, so I guess I’ll plough ahead.

This is good time to talk about the interpreter I’m using. I initially toyed with downloading the MIT Scheme interpreter, which is a minimalist product that’s designed to be used alongside this course. I also thought about downloading Emacs – you can get implementations with a built-in Lisp interpreter. But I’ve been getting along quite happily with a combination of Vim and TextMate (for Mac OS X) for the past few months, and I’m not sure that learning a new text editor is necessary right now. I also wanted to do some more advanced coding in Lisp (what’s the point of learning a new language if I’m not going to use it?) so I wanted something a bit meatier than MIT Scheme.

DrRacket

DrRacket

I eventually settled on Racket, a bells-and-whistles implementation of Scheme that includes a lot of extra features out of the box – lots of nice data structures, the ability to create GUIs and manipulate graphics, and lots more. It comes with its own interpreter, DrRacket, which is functional and pretty easy to use. A nice touch is that you can load any definitions file into the interpreter to give you a whole load of pre-defined functions – and if the first line of the definitions file is #lang <language-name> then you will only use the features of that language. For example, the first line of the definitions file I’m using for this project is #lang scheme so I don’t have access to all the funky procedures defined in Racket – just the core Scheme language.

On with the exercises.

Exercise 1.1

What is the result printed by the interpreter in response to each of the following expressions?

> 10 
10

Numerals have a value equal to the number they represent.

> (+ 5 3 4)
12

This is equivalent to 5 + 3 + 4. Note that the + procedure can take multiple arguments. I haven’t learned how to define a function with a variable number of arguments yet, but hopefully I will soon!

> (- 9 1)
8

This is equivalent to 9 – 1.

> (/ 6 2)
3

Equivalent to 6 / 2. Note that we get an integer result.

> (+ (* 2 4) (- 4 6))
6

Equivalent to (2 * 4) + (4 – 6) = 8 + (-2). Note that there is no need for operator precedence in Scheme, because we always include the parentheses! I wonder if a syntax for Scheme could be defined that allowed you to leave out parentheses when the meaning was clear, and had rules of operator precedence instead. For example, the K programming language that I use at work has simple right-to-left order of evaluation. This can lead to very code and lets you easily write one-line expressions that are very powerful, but has many gotchas: for example, 2*4+5 evaluates to 18 in K, rather than 13.

> (define a 3)

Whether or not define statements return a value is implementation-dependent. My interpreter doesn’t give a return value. However, we have now bound the value 3 to the variable a.

> (define b (+ a 1))

Again, there is no return value, but we have bound the value of (+ a 1) to the variable b, so that b now has the value 4.

> (+ a b (* a b))
19

This is equivalent to a + b + (a * b) where a = 3 and b = 4.

> (if (and (> b a) (< b (* a b)))
      b
      a)
4

This procedure says “if (b > a) and (b < a * b) then return b, else return a”, which becomes “if (4 > 3) and (4 < 12) then return 4, else return 3” so it returns 4.

> (+ 2 (if (> b a) b a))
6

First evaluate the if statement. It says “if (b > a) return b, else return a” which becomes (by substitution) “if 4 > 3 then return 4, else return 3”, so it returns 4. We then evaluate (+ 2 4), which returns 6.

> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

We first evaluate the cond statement. It evaluate to 4, since the first predicate is false but the second one is true. The second argument (+ a 1) evaluates to 4 also, and finally (* 4 4) evaluates to 16.

Exercise 1.2

Translate the following expression into prefix form:

\dfrac{5 + 4 + (2 - (3 - (6 + 4/5)))}{3(6 - 2)(2 - 7)}

I reckon we have:

> (/ (+ 5
        4
        (- 2
           (- 3
              (+ 6
                 (/ 4 5)))))
     (* 3
        (- 6 2)
        (- 2 7)))
-37/150

That return value was a surprise to me! I had assumed that when applying the division operator to two integers, Scheme would either perform integer division (like Java) or return a floating point number (like Python). Apparently it has a built-in rational data type. Which is nice.

Exercise 1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

Here’s a pretty ugly answer, using the built-in min function:

> (define (f a b c)
    (- (+ (* a a) (* b b) (* c c))
       (* (min a b c) (min a b c))))

Why is it ugly? Well, it needlessly applies min twice, and it does four multiplications, two additions and a subtraction, when all that’s needed is one addition and two multiplications. How about:

> (define (g a b c)
    (cond ((and (<= a b)
                (<= a c)) (+ (* b b) (* c c)))
          ((<= b c) (+ (* a a) (* c c)))
          (else (+ (* a a) (* b b)))))

This looks uglier, but it’s more efficient: it never performs more than two multiplications and one addition, and never more than three comparisons (the minimum possible, since you have to sort the arguments so that you know which is the smallest, and this takes three comparisons in the worst case. If anyone has a prettier and efficient solution (perhaps one that works for arbitrary lists of arguments?) then I’d like to see it.