Category Archives: SICP

Hacker School Day 9: SICP review, Sinatra solutions, JS productivity

I dabbled in too much today! But I think it’s okay. Just for today.

First up, I want to write about SICP*, and what I reviewed today. Hopefully that will help cement these complex thoughts a little more firmly into my malleable medium of brain. I started working through SICP again with another (SLOWER) group. This is more to my liking, as I merely want this to be an enlightening side-project.

SICP Exercise 1.5

(define (p) (p))

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

Evaluate (test 0 (p))
This exercise tries to demonstrate the difference between Applicative-Order Evaluation and Normal-Order Evaluation. Let me try to explain: in Applicative-Order Evaluation (which is similar to how the Scheme interpreter actually evaluates code), you evaluate the parameters of the function or expression FIRST, then plug your results into the outer function(s). In Normal-Order Evaluation, you leave your parameters as junk-words and expand out the outer functions as much as possible. In fact, you expand everything down to simple operations as much as possible, THEN you go through and evaluate it all back up and simplify. So, in the case of the code above, approaching it Applicatively, we would FIRST evaluate 0 and (p) (since these are our parameters to the test function). When we try to evaluate (p), we are returned the function (p), which then returns the function (p), which then returns the function (p), etc. The program runs forever, just trying to get some real stuff to put into the parameters of test. Yikes! When we approach this Normally (ha! except not really — please note my use of capital “N”), we first expand out our function: (if (= 0 0) 0 [STOP!]. With if, since it’s a special form and not a normal procedure, we don’t plug everything in everywhere up front; we instead plug in our first test case and evaluate it, then either evaluate the success expression or evaluate the else expression. In this case, we get to (= 0 0) (does 0 equal 0? why, yes, it does!) and we return 0. Done. Easy. No infinite loop.

SICP Exercise 1.6

In this exercise, Alyssa P. Hacker and her friend Eva Lu Ator (author’s names, not mine) decide that if is just a sub-set of cond (conditional), where there is only one test case, so they decide to write their own if function based on cond:

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

This works fine if you’re just evaluating a few simple numbers, but if you use it for a process involving iteration, it may cause an endless loop. Here’s why: (SICP example slightly simplified)
Let’s write a function called improve guess where we say “if (guess is good enough) (return guess) else (improve guess),” and improve guess calls itself. If we use the normal special form if as defined by Scheme (or any language, really), the interpreter knows to only look at the else clause IF the first clause is false. Fine. Great. What’s the big deal? If we instead use our homemade function new-if, we have to plug in: (new-if: (good enough?) (guess) (improve guess)) into our function. As I talked about above, if we were to evaluate this Applicatively, similar to the way the Scheme interpreter does, we would FIRST evaluate our parameters before doing the outer function stuff, which means we would FIRST evaluate the parameter “improve guess” which means we would call our function all over, plug in the same parameters, evaluate them (which would mean evaluating “improve guess”, which would mean calling our function yet again, plugging in the parameters, evaluating them (which would mean …)). And if you run this code in the Dr Racket interpreter (in which I declare the language to be Scheme), it only quits when it’s run out of its allotted memory. Ha! SO. THAT is why some functions are built-in to languages with SPECIAL instructions, such as IF, AND, OR. Take that, Alyssa P. Hacker and Eva Lu Ator! I guess that’s whatcha get for tryin’ tah be clever.

Sinatra!

Not Frank. The other one. Less dancy, unfortunately. This one is a light-weight Ruby web server (I think). Anyway, I used it for my tiny gmail filter maker about a month ago, so when a classmate was struggling with it I offered to lend an eye. While we didn’t make leaps and bounds of progress, it challenged us both to think about harder about GETs and POSTs and how to see what of our parameters were getting properly delivered. Ultimately, I think she’ll need to switch to session variables, which I would love to learn how to do with Ruby and Sinatra, but I also had to get back to work on:

Nefario Teaches Typing

… my typing game. Progress so far: added the beginnings of a keyboard, changed the frame rate of the character’s animation, added scoring, added pause and resume. Next up: do more with the keyboard, pull some of the html-building out of the JavaScript and let it just be already in the html the way I want (will try to do this as a new “branch” so that I can go back to it… that will be an experiment/learning opportunity with git). I also need to refine the “rules” so that the level can be won or lost and is somewhat tailored to the player’s typing speed and accuracy. So much to do!

*SICP = Structure and Interpretation of Computer Programs, a fundamental work about what it means to write programs, used at MIT, “changed my life,” blah, blah, blah. It’s actually pretty cool, though quite dense.