Of late I’ve been studying light, and thought it would be fun to write a program to model light striking a planar mirror. I have now got a working version out which happily traces the rays using some simple vector math and a slightly buggy ray tracing algorithm. Pictures are necessary :D

## Archive for the ‘**abstraction**’ Tag

## Simple 2D Ray Tracer Leave a comment

## SICP Section 2.3.4 Leave a comment

## SICP Section 2.3.3 Leave a comment

## SICP – Section 2.3.1-2.3.2 Leave a comment

This section introduces the idea of “symbolic data”, and demonstrates how we can abstract our code with it. I found it to be really enjoyable, the questions were very challenging at the end. I notice I seem to say that I find each section enjoyable, and I do! I cannot recommend this book enough, not only for the knowledge and ideas you gain from it, but for the fun you’ll have solving the problems.

**;;Exercise 2.53**

As usual, just a check to make sure we understand how to manipulate symbolic data.

`>(list '(a b c))`

(a b c)

>(list (list 'george))

*((george))*

>(cdr '((x1 x2) (y1 y2)))

*(y1 y2)*

>(cadr '((x1 x2) (y1 y2)))

*y1*

>(pair? (car '(a short list)))

*#f*

>(memq 'red '((red shoes) (blue socks)))

*#f*

>(memq 'red '(red shoes blue socks))

*(red shoes blue socks) *

**;;Exercise 2.54**

A fairly straightforward implementation of the recursive description they gave.

```
(define (my-equal? a b)
(cond ((and (eq? a '()) (eq? b '())) true)
((and (symbol? a) (symbol? b))
(eq? a b))
((and (pair? a) (pair? b))
(and (my-equal? (car a) (car b))
(my-equal? (cdr a) (cdr b))))
(else false)))
```

**;;Exercise 2.55**

The first challenging question. Had me stumped for a while, even when I typed the code in at my interpreter I didn’t get it, however, if you notice the footnote no. 34, it explains that the interpreter replaces each use of `'`

with a `quote`

. So `''abracadabra`

is `'(quote abracadabra)`

, and the car of that list is the symbol `quote`

!

**;;Exercise 2.56**

We’ve been introduced to the differentiation program, a very nice example of abstraction. The key to this exercise is pretty much to copy what happens for the other rules, just supplying different selectors and constructors, and a bit more code in the deriv function. I’m a bit of a rebel ;) I chose to use the ‘^ symbol instead of ‘**, as ‘^ seems more intuitive to me :)

Here are the selectors, predicate, and constructors:

```
;;'(^ b a)
(define (exponentiation? x)
(and (pair? x) (eq? (car x) '^)))
(define (base x)
(cadr x))
(define (exponent x)
(caddr x))
(define (make-exponentiation base exponent)
(cond ((and (number? base) (number? exponent))
(expt base exponent))
((=number? exponent 0) 1)
((=number? exponent 1) base)
(else (list '^ base exponent))))
```

And here is the modified deriv function:

```
(define (deriv expr var)
(cond ((number? expr) 0)
((variable? expr)
(if (same-variable? expr var) 1 0))
((exponentiation? expr) ;;EXPONENTIATION RULE
(make-product
(make-product (exponent expr)
(make-exponentiation (base expr)
(- (exponent expr) 1)))
(deriv (base expr) var)))
((sum? expr)
(make-sum (deriv (addend expr) var)
(deriv (augend expr) var)))
((product? expr)
(make-sum
(make-product (multiplier expr)
(deriv (multiplicand expr) var))
(make-product (deriv (multiplier expr) var)
(multiplicand expr))))
(else
(error "unknown expression type -- DERIV" expr))))
```

And a test,

`>(deriv '(^ x 4) 'x)`

*(* 4 (^ x 3))*

**;;Exercise 2.57**

I had some initial difficulties with this question, I understood what I was attempting to do in the selectors, but the constructors were a little trickier. With the selectors, the only interesting bit is in the augend selector. When we get the augend, we must remember if there is a list, we need to return it as the sum of the rest of the items in the list, not a a list of two or more numbers. eg. (augend ‘(+ 1 2 3)) is (+ 2 3) not (2 3).

```
(define (addend s) (cadr s))
(define (augend s)
(let ((aug (cddr s)))
(if (eq? (cdr aug) '())
(car aug)
(make-sum (car aug)
(cdr aug)))))
```

The constructor also held me up for a little while, as I had a bit of a hiccup in my code.

I was not combining the augend a2 into the list (‘+ a1 a2) correctly. This is best shown with some code…

`>(make-sum x (2 (* 5 y)))`

*(+ x (2 (* 5 y)))*

As you can see, instead of combining the 2 at the same level as x, it is a separate list, (2 (* 5 y)) which the program does not know how to parse. It should of course be (+ x 2 (* 5 y)). How do we combine the lists? Using append! Here is the constructor then:

```
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (append (list '+ a1) a2))))
```

Note that we can leave all the simplification code in, it will still work even in the new format. The changes to product are almost exactly the same as the changes to sum, I feel as though there’s an underlying abstraction somewhere ;)

Here’s the full code, including the product as well as sum, remember that this is all available on my sicp github repo.

```
;;(+ x y z)
(define (addend s) (cadr s))
(define (augend s)
(let ((aug (cddr s)))
(if (eq? (cdr aug) '())
(car aug)
(make-sum (car aug)
(cdr aug)))))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (append (list '+ a1) a2))))
;;'(* x y z)
(define (multiplier p) (cadr p))
(define (multiplicand p)
(let ((mult (cddr p)))
(if (eq? (cdr mult) '())
(car mult)
(make-product (car mult)
(cdr mult)))))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (append (list '* m1) m2))))
```

**;;Exercise 2.58**

**;;Part A**

Things are getting interesting, we are now getting out of the safe world of polish notation, and into the rather complex one of parsing infix expressions. However, part a is very easy to implement, it simply requires swapping the parsing of* *the operator and the first operand, the change is exactly the same for multiplication.

```
(define (sum? x)
(and (pair? x) (eq? (cadr x) '+)))
(define (addend s) (car s))
(define (augend s) (caddr s))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list a1 '+ a2))))
```

**;;Part B**

Part b is simply put, a beast of a question. It most certainly is quite a difficult problem, but it’s definitely possible! In fact, I suggest you stop reading now, so that you can have the same exhiliration that I got upon solving it! We are now required to parse infix expressions with any or no parenthization. I mulled over this one for a couple days, and spent more than a few nights writing attempts to solve it in my note book. I finally hit epiphany at badminton on Thursday (6/5/10) night.

Before we do anything, we should state what we are attempting to accomplish with our code. This is a bit trickier than it sounds, so let’s go through a couple examples and see if we can find anything interesting.

`(x * (6 + y) + 5)`

is equivalent to

`((x * (6 + y)) + 5)`

(note the extra parenthesis before *x*)

So one thing we need to do is replace parentheses to make it easier to parse.

`(x * (6 + y) + 5)`

can be reduced like so:

```
addend: x * (6 + y)
multiplier: x
multiplicand: (6 + y)
addend: 6
augend: y
augend:
```

This looks like a job for recursion to me, and it also looks like we’ll need to worry about putting sums in the right place before the products. For example, if we tried to grab the multiplicand of (3 * 6 + 5) we would obtain 6 + 5 instead of 6.

We can come up with a simple recursive definition for this:

If the augend of *expr* is a *sum*, then the augend of *expr* is the *sum* of everything after the *sum* operator in *expr* (y + 3* z). If the augend of *expr* is a *product*, then the augend of *expr* is the *product* of everything after the *product* operator in *expr*. If the augend of *expr* is a single *variable* then the augend of *expr* is the first item after the *sum* operator. Finally if the augend of *expr* is a single *number*, then the augend of *expr* is the first item after the *sum* operator.

So we can see that there are four rules to apply here which will eventually filter down to the base case of the single variable or number. So, the first thing we will implement is the definition of a sum and product. An expression is a sum if it has the ‘+ operator in it, and an expression is a product if it has only the ‘* operator in it. This gives us the proper operator precedence. The in? predicate here tells whether a given symbol is in a list.

```
(define (sum? x)
(and (pair? x) (in? '+ x)))
(define (product? x)
(and (pair? x) (not (in? '+ x)) (in? '* x)))
```

Now that we have our definitions of what constitutes a sum, we need to give the definitions of addend and augend. The addend is everything before the first ‘+ operator, but we also need to process the addend (remember the recursive definition) to correctly resolve operator precedence in it. We will do this with the recursive process stated above as a procedure named *process-expr* which I will leave unspecified. Remember that black box abstraction, and wishful thinking are very important. Anyway, here’s the definition of addend and augend, *split-on* is a function which gives a cons where the car is everything before the symbol, and the cdr is everything after the symbol.

`>(split-on '+ (1* x + 2 * y))`

*((1 * x) 2 y)*

```
(define (addend s)
(process-expr (car (split-on '+ s))))
(define (augend s)
(process-expr (cdr (split-on '+ s))))
```

Now it’s almost all in place, there’s one more definition left, how do we construct a sum? This is very easy, and stays the same as what we implemented for part A, `(list a1 '+ a2).`

Now, to implement the *process-expr* procedure. Since we have already defined all the selectors and constructors, this will be very easy.

```
(define (process-expr expr)
(cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
((if (= (length expr) 1) (number? (car expr)) false) (car expr))
((sum? expr) (make-sum (addend expr)
(augend expr)))
((product? expr) (make-product (multiplier expr)
(multiplicand expr))))))
```

This is a beautiful example of mutual recursion, and the great thing is, that it works! I first wrote this while waiting to play at badminton, and when I tranferred it from paper, it worked first try, with just a couple hiccups. One of those hiccups was the parsing of a parenthized expression such as `(3 * (5 + 4))`

. The augend of this expression is ((5 + 4)), which is (list (list 5 + 4)). When process-expr encounters this, it checks if it is a variable, but while the length of (list (list 5 ‘+ 4)) is 1, it will not satisfy either the variable? or the number? predicate. It will then check if it is a sum, but there is no ‘+ in (list (list 5 + 4)), and it will also check if it is a product, but it won’t satisfy that either, so the cond expression will return #void! This is a bit of a bug, but it is fairly easy to fix. Let’s think of a parenthized-expression as another type of expression. It must satisfy these requirements to be considered parethized:

- Must have a length of 1
- Must not be a variable
- Must not be a number
- It’s car must be either a sum or a product

This is readily expressed as a procedure.

```
(define (parenthized-expression? expr)
(and (not (variable? expr))
(not (number? expr))
(= (length expr) 1)
(or (sum? (car expr))
(product? (car expr)))))
;;Selector
(define (deparenthize expr) (car expr))
```

Now, we just need to add a rule for handling parenthized-expressions to *process-expr*. This is accomplished by adding a *let* expression, which will bind *expr* correctly:

```
(define (process-expr expr)
(let ((expr (if (parenthized-expression? expr) (deparenthize expr) expr)))
(cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
((if (= (length expr) 1) (number? (car expr)) false) (car expr))
((sum? expr) (make-sum (addend expr)
(augend expr)))
((product? expr) (make-product (multiplier expr)
(multiplicand expr))))))
```

We’re done! We have now created a fairly useful symbolic differentiator, which can handle (almost) arbitrary expressions. There is nothing as exhilirating as solving a really tough problem, and this can definitely be ranked as one of them! Here is all the code, and remember, this code is on my sicp github repo.

*Happy Hacking!*
;;Split an expr on symb
(define (split-on symb expr)
(define (iter r l)
(cond ((eq? l '()) r)
((eq? symb (car l)) (cons r (cdr l)))
(else (iter (append r (list (car l))) (cdr l)))))
(iter '() expr))
;;Is symb in expr?
(define (in? symb expr)
(cond ((eq? expr '()) false)
((eq? symb (car expr)) true)
(else (in? symb (cdr expr)))))
;; representing algebraic expressions
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (=number? exp num)
(and (number? exp) (= exp num)))
;;Is expr a parenthized expression? eg. ((1 + 2))
(define (parenthized-expression? expr)
(and (not (variable? expr))
(not (number? expr))
(= (length expr) 1)
(or (sum? (car expr))
(product? (car expr)))))
(define (process-expr expr)
(let ((expr (if (parenthized-expression? expr) (deparenthize expr) expr)))
(cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
((if (= (length expr) 1) (number? (car expr)) false) (car expr))
((sum? expr) (make-sum (addend expr)
(augend expr)))
((product? expr) (make-product (multiplier expr)
(multiplicand expr))))))
(define (deparenthize expr) (car expr))
;;'(+ x y)
(define (sum? x)
(and (pair? x) (in? '+ x)))
(define (addend s)
(process-expr (car (split-on '+ s))))
(define (augend s)
(process-expr (cdr (split-on '+ s))))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list a1 '+ a2))))
;;'(* x y)
(define (product? x)
(and (pair? x) (not (in? '+ x)) (in? '* x)))
(define (multiplier p)
(process-expr (car (split-on '* p))))
(define (multiplicand p)
(process-expr (cdr (split-on '* p))))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list m1 '* m2))))
(define (deriv expr var)
(cond ((number? expr) 0)
((variable? expr)
(if (same-variable? expr var) 1 0))
((sum? expr)
(make-sum (deriv (addend expr) var)
(deriv (augend expr) var)))
((product? expr)
(make-sum
(make-product (multiplier expr)
(deriv (multiplicand expr) var))
(make-product (deriv (multiplier expr) var)
(multiplicand expr))))
(else
(error "unknown expression type -- DERIV" expr))))

`>(deriv '(x + 3 * (x + y + 2)) 'x)`

*4*

## SICP – Section 2.1.4 Leave a comment

I’ve been silent for the past couple days, but not without good reason :)

I decided to finish all my solutions to the interval arithmetic exercise

before posting, because I can share as much insight as I have gained, in one

hit. ;)

In this extended exercise, we are helping Alyssa P. Hacker

(note the pun :) to develop an interval arithmetic system for

her fellow electrical engineering compatriots.

The answers to exercises 2.7 to 2.10 are fairly clear, so here they are:

**Exercise 2.7**

(define (make-interval a b) (cons a b))

(define (lower-bound i) (car i))

(define (upper-bound i) (cdr i))

**Exercise 2.8**

(define (sub-interval x y)

(make-interval (- (lower-bound x) (lower-bound y))

(- (upper-bound x) (upper-bound y))))

**Exercise 2.9**

Let’s add some intervals and note the relation between the width of the

operands and the width of the result.

(define a (make-center-width 5 1))

(define b (make-center-width 10 2))

(define x (mul-interval a b))

(width x) = 3

From this it is fairly obvious that the width of the result of addition can

be described like so:

w(x*y) = w(x)+w(y)

The inverse holds true of division:

w(x/y) = w(x)-w(y)

Hmm… anyone else see the relation to logarithms?

**Exercise 2.10**

This one is also fairly simple.

(define (zero-span? i)

(if (and (<= (lower-bound i) 0) (>= (upper-bound i) 0))

true

false))

(define (div-interval x y)

(if (zero-span? y)

(error "Attempt to divide by an interval that spans 0")

(mul-interval x

(make-interval (/ 1.0 (upper-bound y))

(/ 1.0 (lower-bound y))))))

Exercise 2.11

To be honest, I didn’t get Ben’s cryptic comment. After reading

Eli Bendersky’s post on the topic I understood, but previously I had

gone off on a wrong tangent.

Regarding this, let me state my policy regarding my completion of these exercises. I firmly believe that cheating cheats the cheater, and while it is not necessarily cheating to check an answer to get hints, this is usually not necessary. There have been a few exercises where I have encountered a mindblock, but my advice to others is to go do something else, completely unrelated to computing or using your brain. Hop on your bike, go for a run or eat a pie, whatever works for you :) Usually when you get a mindblock it shows that you’ve been working your brain too long, too hard, and you just need to let it relax. This also happens a bit in programming, at least when you’re starting out, and in “How To Think Like A Computer Scientist” the author also suggests taking a break when you get frustrated, as this can be a source of unpleasant code and bugs.

I tend to read Eli’s posts after completing a section, because they are quite enlightening and informative. There is nothing quite like a veteran hackers view of the topic :)

This leads me to a shout out to Eli. Thanks for writing such detailed, interesting, and informative posts! I believe that, along with watching the lectures, doing the exercises and reading the book, your posts are a very complementary aid in understanding the material.

Exercise 2.12

(define (make-center-percent c p)

(make-interval (- c (* c p))

(+ c (* c p))))

(define (percent i)

(/ (- (upper-bound i)

(center i))

(center i)))

Again, this is fairly simple. The percent selector may have caused

some trouble, but it’s not too hard to figure out.

**Exercise 2.13**

;;Let's try:

(define a (make-center-percent 1 .1))

(define b (make-center-percent 1 .2))

(define x (* a b))

(percent x)

*.294*

So we can indeed see that (percent x) ~= (percent a) + (percent b)

This follows from exercise 2.9, except here we see that the percentage

is only approximate.

Exercise 2.14

To show why, we will use:

(define A (make-center-percent 8 .01))

(define B (make-center-percent 9 .05))

We will process A/A by hand, in order to see what’s going on.

`(mul-interval A (make-interval (/ 1 8.08) (/ 1 7.92)))`

;;p1 = .980

;;p2 = 1

;;p3 = 1

;;p4 = 1.02

The result is: (make-interval .980 1.02)

Instead of (make-interval 1 1) which you might have expected.

Let’s also do (/ A B) as suggested

;;(mul-interval A (make-interval (/ 1 9.45) (/ 1 (8.55))))

;;p1 = .838

;;p2 = .926

;;p3 = .855

;;p4 = .945

So the result is: (make-interval .838 .945) instead of the more accurate

(make-interval .855 .926)

Here’s my explanation.

Interval A/A is not an interval spanning 1 <-> 1 as we would expect in normal arithmetic, but an interval spanning .980 <-> 1.02. The width of this interval is a factor of the initial uncertainty .01, where the new uncertainty is .04. Interval A/B is also not the .855 <-> .926 that we might expect, but instead .838 <-> .945. We can see from these examples that arithmetic operations increase the innacuracy/uncertainty of the answer. The error in the answer is therefore directly related to the uncertainty in the intervals given.

**Exercise 2.15**

She is correct. As stated above, the amount of error in the answer is directly related to the uncertainty in the intervals given. Because there are more intervals in par1, there is a higher error in the answer. That is why par2 is a better method.

Reading Eli’s solutions to this extended exercise also gives a different view on the matter, he talks about it in terms of the fact that interval arithmetic is not a one-to-one mapping of simple numerical arithmetic.