Structure and interpretation of computer programs.

Images of Columbia’s Computational Design of Twisty Joints and Puzzles software in action. http://www.cs.columbia.edu/cg/twisty/

So I am still reading the SICP and following the last post I made on the substitution model, we were looking at how the break down compound procedures.

Initially we had f (a) defined to sum-of-squares( (+ a 10) (* a 20) )

So now what we would represent what the interpreter is doing with the substitution model to substitute the value of a and then evaluate the compound expression’s operands together with their relative operator. so f (5) substitutes in (+ 5 10) and (* 5 20) then reduces these with their relative operator, to get sum-of-squares( 15 100). Then because the operator is now a compound procedure [sum-of-squares] we can evaluate the substituent arguments by substituting the values in with x and y in the body of sum-of-squares to get

(+ (square 15) (square 100) )

once again we have to substitute the square’s arguments with x in squares body, resulting in (+ ( * 15 15) (* 100 100) ). At this point we can evaluate the subexpressions, and reduce it to.

(+ 225 10000)

and again to

10225

Now there is an alternative to this which is more like a series of expansions until everything is a primitive expression instead of evaluate the operators and then reducing .

f(5) would expand to

(sum-of-squares ( + 5 10) (* 5 20))

which would expand to

→(+ (square ( + 5 10)) ( square ( * 5 20) ) )

→(+ ( * (+ 5 10) (+ 5 10) ) (* (* 5 20 ) (* 5 20) ) )

→( + ( * 15 15 ) ( * 100 100 ) )

→( + 225 10000)

→10225

This idea of fully expanding the expression before reducing is known as normal order. The contrary idea is where the arguments are evaluated , and applied to their operators, this is called applicative-order evaluation. The interpreter uses the latter . Procedures can be shown through the substitution model that both applicative and normal order result int the same answer.

The lisp interpreter uses applicative-order evaluation this is because of the added efficiency of evaluating the expression then applying means that you avoid multiple evaluations of the same expression like (+ 5 10 ) and (* 5 20 ). But more significantly because normal order evaluation becomes too complicated in the future as you would have huge nests with particular compound procedures. However normal-order does have its merits which I will get on to fairly soon.

However we have met a turning point for our application as we cannot define explicit, turning points for our procedures to do particular things based on particular arguments given.

Take the function abs() which converts the number into an absolute value will return different values dependent on whether the number is positive , negative or zero. Using mathematical notation it looks like so:

Abs value of r

This structure is called case analysis. It is called cond which stands for conditional and it is used as follows [going to start using gists because I’m tired of not pretty-printing because I’m here on medium].

The general form of a cond is

The cond is followed by parenthesized pairs of expressions called clauses , in each expression is a predicate <px>. The way a cond is evaluated is like so

1. Predicate 1 is evaluated if it is false it goes onto the following clause’s predicate.
2. Predicate 2 is evaluated if it is false it goes onto the following clause’s predicate
3. Predicate 3 is evaluated if it is false it goes on .. until it finds the predicate that is right.
4. Once it finds the Predicate that is true it looks for the value of the corresponding consequent expression <cx>.

The word predicate is used for procedures that evaluate to true or false , the abs expression uses the primitive predicates < , > and = . These evaluate whether the 1st number is less than, greater than or equal to the 2nd number respectively.

The abs expression can also be written like so :

This can be expressed in english by saying if x is less than 0 then return the value -x , otherwise return the value x . Else is a special case where all predicates evaluate to false then the consequent expression after else will be returned. So use else when you want to have an alternative for when all other cases failing.

Here the familiar word if is used like

(if <predicate> <consequent> <alternative> )

So the interpreter looks at the predicate evaluates for true or false if it is true then the consequent expression value is returned, otherwise the alternative value is returned.

We can use the primitive predicates < , > , =. To evaluate to true or false for two primitive values, but we can also use and, or and not . to combine these predicates together.

Here is an example

and another one.

(and <e1>….<en> ) →If any expression e evaluates to false then the and expression will evaluate to false. If all of e’s values are true then and will evaluate to the value of the last e , <en>.

(or <e1>….<en> ) → if any expression e evaluates to true then that e’s expression’s value will be returned in or and the subsequent e expressions will not be evaluated , if any expression evaluates to false then or will evaluate to false.

(not <e> ) → if the expression e evaluates to true then not evaluates to false and vice versa.

An example of using the or logical expressions is to create a greater than or equal compound procedure

(define (>= x y ) ( or (> x y) (= x y) ) )

or alternatively , x is not less than y.

(define (>= x y ) (not (< x y) ) )