Quirksand

SICP

SICP 1.1.6 Solutions

July 12, 2012 13:02

Ex 1.1.

Nothing really to do here but enter the lines and see what happens. I’ll mention here that I’m using Dr Racket as my interpreter. Racket is a language based on Scheme, although not a strict superset. At this point the differences will not be noticed, but it will come into play later in the book. The Dr Racket software includes an implementation of Scheme in Racket, although I don’t normally use it. I use the ‘legacy language’ Pretty Big.

It uses ‘#f’ and ‘#t’ as returned values for false and true, which might be the only remarkable part of this problem.

For the most part I’m trying to keep the code portable, but there may be a few minor differences that need to be worked out on other interpreters. I don’t really want to make any recommendations or suggestions as to what interpreter to use. Going with whatever you find comfortable is the best.

Ex 1.2.

The best way to test your result in writing this out in prefix form is to simply type it into an interpreter. The value of the expression is -74/100, or -37/150 in reduced terms, or -0.24666… as a decimal fraction.

Ex 1.3.

Our first function definition. We need to sum the squares of the biggest two of any three numbers.

(define (bigger-sum-of-squares  a b c)
                              (cond
                              ((and (<= a b) (<= a c)) (+ (* b b) (* c c)))
                              ((and (<= b a) (<= b c)) (+ (* a a) (* c c)))
                              (else              (+ (* a a) (* b b)))
                              )
)

There are probably several ways to write the comparisons. The basic idea here is to figure out which element is no bigger than the others, and then square the other two. Once a and b are ruled out, c can’t be bigger, so the last result is in the else clause without further comparing.

The values included for testing are initially a few different positive values, not necessarily in order. Then some negative values, fractions, and a set that crosses 0 in its span. Finally a few runs with numbers that don’t have a strictly smallest value. Any simple procedure in Scheme should have no problem dealing with these. There aren’t really any tricky sets for this function.

Ex 1.4.

We have to explain what this procedure does:

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

At first glance it seems a bit strange to read an if statement like that. Taking a very straightforward, computer-like look at the function, we can interpret exactly what it does. Each expression in parentheses can be evaluated on its own without thinking about what’s going on outside it.

To start from the inside, (> b 0) will return either true or false, depending on b. Suppose it to be true. The if statement then looks like this: (if #t + -). The if will evaluate to the third element if true, or the fourth if false. It evaluates to + in the case considered. Now we have the expression (+ a b). That’s easily enough a mathematical statement, a + b. If b was less than zero, it would have been ab since the if would evaluate to - then.

In a more mathematical sense, the procedure does what its name implies; it returns a + |b|. When b is negative, it adds -b, and when b is postive it adds b. Both cases yield the same answer.

The best way to check the behavior of the procedure is to test it out. A few runs with some positive and negative numbers will verify that it works as expected.

Ex 1.5.

We’re examining the difference between what happens when evaluating an expression with an unusual procedure in it, based on whether applicative or normal order is used.

(define (p) (p))
(define (test x y) (if (= x 0)
                       0
                       y))
;Then he evaluates the expression
(test 0 (p))

The procedure test takes two arguments and uses a conditional statement. If the first argument is 0, then it simply evaluates to 0. If not, the second argument is the result.

We passed in 0 and (p) as our arguments (Note the distinction between (test 0 (p)) and (test 0 p)). Using normal order, there’s no need to do anything other than check if our first argument is 0. Since it is, 0 is the result. In applicative order, each argument must be evaluated to a primitive in order to proceed. Unfortunately our second argument (procedure p) doesn’t resolve to a primitive — it resolves to itself. That leads to an infinite loop of attempting to resolve the expression (p), even though there was no need to use it in this particular call to test.

It’s easy enough to find out what the interpreter uses by simply entering these statements. The definition of p above doesn’t cause any problems when you enter it. Certainly defining a procedure doesn’t mean ‘executing’ it, and no problems are going to appear until something attempts to evaluate it down the line. Be prepared to kill it if it goes into an infinite loop.

Solution file : Solutions 1.1.6