SICP 1.12

SICP 1.12

 (define (pascal row col)  
  (cond ((= col 0) 1)  
     ((= col row) 1)  
     (else (+ (pascal (- row 1) (- col 1)) (pascal (- row 1) col)))))  

Summer semester...

...is over! Updates to follow.

Back from camping!

Stories soon to come!

Vacation!

I will not be working on SICP or school for the next week, as I will be in Yellowstone with my girlfriend. I am really looking forward to this trip and will hopefully have pictures and stories when I return.

SICP Exercise 1.11

SICP 1.11

 ; recursive version  
 (define (f-rec n)  
  (cond ((<= n 3) n)  
     (else (+ (f-rec (- n 1))   
          (* 2 (f-rec (- n 2)))   
          (* 3 (f-rec (- n 3)))))))  
   
 ; iterative version  
 (define (f n)  
  (cond ((<= n 3) n)  
     (else (f-iter 1 2 3 3 n))))  
   
 (define (f-iter fn-1 fn-2 fn-3 last-calc end)  
  (cond ((= last-calc end) fn-3)  
     (else (f-iter fn-2 fn-3 (+ fn-3 (* 2 fn-2) (* 3 fn-1)) (+ last-calc 1) end))))  
   

SICP Exercise 1.10

SICP 1.10

(A 1 10) = 1024
(A 2 4) = 65536
(A 3 3) = 65536

All of the following assume n =/= 0.
\[(f. n) = 2n\]

\[(g. n) = 2^n\]

\[(h. n) = 2^{(h (n-1))}\]

\[(k. n) = 5n^2\]

SICP Exercise 1.9

SICP 1.9

The first definition:
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

The second definition:
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

The first definition would be what the book calls a recursive process, and the second would be iterative.

SICP Exercise 1.8

SICP 1.8

 
 (define (square x)  
  (* x x))

(define (cube x)  
  (* x x x))  

 (define (improve guess x)  
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))
  
 (define (good-enough? old-guess new-guess)  
  (< (/ (abs (- new-guess old-guess)) new-guess) 0.001))  

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

 (define (cube-root x)  
  (cube-iter 0 1 x))  

SICP Exercise 1.7

Instead of spending the time to write out every SICP problem I am going to start linking to them via the html book.

The obvious problem with very small numbers and very large numbers resides in the precision of only using 0.001 as the difference validator between changes. When you get very small numbers you start getting off hundreds of percent errors, even for relatively simple squares, such as 0.0000001 and 0.0000000000001. For very large numbers you run into the same issue. In fact, the lack of appropriate precision gets so ridiculous at high numbers that often the program fails to end due to an inability to decipher the right amount of change between guesses.

 (define (square x) (* x x))  

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

 (define (improve guess x)  
  (average guess (/ x guess)))  

 (define (average x y)  
  (/ (+ x y) 2))  

 (define (good-enough? old-guess new-guess)  
  (< (/ (abs (- new-guess old-guess)) new-guess) 0.0000001))  

 (define (sqrt x)  
  (sqrt-iter 0 1.0 x))  

This alleviates the previous errors and gives expected results.

Another Endless Workout

Despite being relatively late I was still able to get an awesome workout at Endless today. My trainer had me perform a general preparedness procedure workout. I performed:

• lunges while holding an curled olympic bar back and forth the gym
• kettlebell swings
• box jumps (I need to ask how high these jumps were)
• band pull-aparts

Overall a great workout. More "cardio" than most of mine, but still really tough.

An update

I've had to set SICP aside to tackle some issues related to work and school. None the less I will return soon.

In the meantime I competed in an in-house jiu-jitsu tournament in my school this weekend. Normally I would not have done so given that I am injured, but two of our affiliation's black belts were there so I had hoped to show off. I did not give my best performance but I took 2nd, which is something I am proud of, tapping out people who are higher rank than myself all while my ribs were displaced.



Once work and school settles down I will return to SICP. I may even pick up a physical copy just for the incentive.

Update soon

I am running ragged but have many SICP exercises done as well as updates about jiu jitsu. I will be updating as soon as I can.

SICP Exercise 1.6

Alyssa P. Hacker doesn't see why if needs to be provided as a special form. "Why can't I just define it as an ordinary procedure in terms of cond?'' she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

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

Eva demonstrates the program for Alyssa:

 (new-if (= 2 3) 0 5)  
 5  
   
 (new-if (= 1 1) 0 5)  
 0  

Delighted, Alyssa 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 attempts to use this to compute square roots? Explain. 

The problem with the sqrt-iter is that new-if will evaluate forever. Functions use applicative-order evaluation, whereas conditionals use normal order (or something more similar to normal order). When new-if is called it will attempt to evaluate a version of sqrt-iter, which itself calls new-if, causing infinite evaluations.

Logic: a review

I recently picked up a copy of Introducing Logic: A Graphic Guide from Icon Books and decided to give it a spin given my love for the subject and its length when compared to the other book that I am reading (SICP).

I thought that this book provided a very entertaining outlook on the history of logic, with a very light description of how some of the major facets of the field work. One glaring omission that I found was the lack of George Boole and Claude Shannon. Given how this book seemed to try to present some useful applications of modern logic, one would assume that two of the greatest contributors to the development of computers as logical machines would have at least deserved a mention. This is especially warrented given that some of the concepts were not explained to their clearest, and that there were a few pages I felt did not deserve inclusion.

Otherwise I understand that such a text cannot get too mathy, but I was still disappointed that there were not enough examples. This text seems like it would be a good introduction for the history of logic were they versed in a small amount of Boolean Algebra and/or Set Theory, but otherwise I would not recommend it to anyone green.

Another workout down

Today I survived another workout at Endless Possibilities. Today I worked bench, pullups on a rope that required a good degree of concentration to keep from swining, band extension and band tricep extensions, and then rope pulls with a weighted sled followed by running the sled back down the room. Overall great workout.

No update as of yet.

School has been running me ragged. Hopefully I can update sometime tomorrow with a review and some solved problems from SICP.

SICP Exercise 1.5

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

 (define (p) (p))  
   
 (define (test x y)  
  (if (= x 0)  
    0  
    y))  

Then he evaluates the expression:

 (test 0 (p))  

Were this interpreter normal-order evaluation the function would return 0 as it would substitute the if statement in for test, evaluate the equality test, and then return.


Were the interpreter using applicative-order evaluation, it would substitute the two arguments in for test (0 and (p)) and then attempt to evaluate both. That (p) calls itself recursively forever an applicative-order evaluation of this function for the given input would loop forever.

SICP Exercise 1.4

Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

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

The operation follows on the if a then result, else b where a and b are the + and - operators. This is essentially the old conditional operator in C.

First day of personal training

I have been having a great deal of complications with my ribs in Brazilian Jiu-Jitsu, specifically - they keep popping out. This causes a considerable amount of pain and almost keeps my completely off the mats for several weeks. I have also found that I am not as athletic as I want to be. I mean, I lift a bit and run a great deal, and I feel I have great cardio jiu-jitsu-wise, but I don't feel as coordinated, explosive, or as resistant as I want to be.

At the suggestion of a few other teammates I enrolled in a personal training program with Brett Carter at Endless Possibilities. The first round of training was pretty good. It wasn't too intense overall, but Brett kept me at a constant pace that certainly taxed my abilities. I worked a box squats, lunges, back extensions, and pushes on a weight sled. Overall it was a great workout.

I will be at Endless twice a week and am certainly looking forward to further workouts and getting much more explosive.

SICP Exercise 1.3

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

(define (square x)  
  (* x x))  
   
 (define (sum-of-squares x y)  
  (+ (square x) (square y)))  
   
 (define (sum-square-two-largest x y z)  
  (cond [(and (> x z) (> y z)) (sum-of-squares x y)]  
     [(and (> x y) (> z y)) (sum-of-squares x z)]  
     [else (sum-of-squares y z)]))  

What I'm Reading: an interjection by Logic

I decided to give this a read through, and with school work I am a little behind on SICP. I should have a review of Introducing Logic sometime tomorrow, hopefully. Suffice to say, so far it's good but not great.

SICP Exercise 1.2

Translate the following into prefix form:

\[\frac{5 + 4 + (2 - (3 - (6 + \frac{4}{5})))}{3(6 - 2)(2-7)}\]

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



This one was pretty easy, just a parsing problem.

SICP Exercise 1.1

This one is basically just inputting values into the interpreter.

10
12
8
3
6
19
false
4
16
6
16

What I'm Reading: Structure Interpretation of Computer Programs

I decided to give Structure and Interpretation of Computer Programs another go. I read through about a third of this book about two years ago and somewhat trailed off, but I love the idea of it and absolutely adore Scheme, so I am giving it another go.

I'll be posting answers to my questions here, and I am currently using Racket as my Scheme of choice.

Hopefully I will be able to make it all the way through this book before the summer is over.