Working out SICP exercises on an Ubuntu-18. I found the most convenient way to get started is installing racket. This also installs DrRacket an IDE that makes working with scheme painless, rather it makes it fun.

$ sudo apt install racket

Once the installation is out of the way, DrRacket is ready to use via the application-search feature or running drracket in a terminal shell.

Having a reference to the book should help while logging my lessons. I plan on posting covered exercises within the titles, hopefully across editions of the books those don't change. In case they do, the book is here.

The book talks about these topics before the first set of exercises:

1. Building Abstractions with Procedures

   1. The elements of programming

      1. Expressions
      2. Naming and the Environment
      3. Evaluating Combinations
      4. Compound Procedures

      5. The Substitution Model for Procedure Application

         • Applicative order vs normal order
      6. Conditional Expressions and Predicates

Applicative order vs Normal order

Going through the topics, I found myself familiar to most topics albeit a different name or no name at all, but Applicative order vs normal order (1.1.5) seemed to be something that I had taken for granted. I had assumed programming languages would obviously implement the applicative order. The difference in working is covered by these examples:

;; applicative order:-
(sum-of-squares (+ 5 1) (* 5 2))

;; Evaluate operateor and arguments first
;; (sum-of-squares 6 10)
;; (+ (square 6) (square 10))

on the contrary, the normal order works this way:

;; normal order
(sum-of-squares (+ 5 1) (* 5 2))

;; Expand the expressions first
;; (sum-of-squares (+ 5 1) (* 5 2))
;; (+ (square (+ 5 1)) (square (* 5 2)))
;; (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

I don't understand why is the normal order considered normal, it returns the same result but slower (The need to compute terms like (+ 5 1) and so on twice!).

Conditional Expressions and Predicates

Cond

Using this snippet for reference.

(define (abs x)          ;; Cond contains clauses, the first expression in each clause is a predictate
  (cond ((x > 0) x)      ;; p1 (predicate = (x > 0))
        ((x < 0) (- x))  ;; p2
        ((= x 0) 0)))    ;; p3

The expression is evaluated as follows:

p1 is evaluated first, if the value is false:

1. p2 is evaluated, else.
2. Since p1 returned true, the consequent expression is evaluated and returned.
3. If pN happens to be false, the other predicates get tested until one that returns true.
4. If none of the predicates evaluate to true, the value evaluated by cond is undefined.
5. You can have else as the last predicate instead of managing the behaviour in [4].

If

The same function above could be re-written as:

(define (abs x) 
  (if (< x 0) 
      (- x) 
      x))
      
;; (if <predicate> <consequent> <alternative>)

if is a restricted conditional (at least for scheme) used when there are precisely two cases. The evaluation works like:

1. The interpreter starts by evaluating the predicate, if true.
2. The interpreter evaluates the consequent.
3. Otherwise evaluates the alternative.
4. Return's either [2] or [3] as applicable.
5. Logical predicates like and, or, not are available for use in if.

Note: and and or are special forms, they are not procedures so they don't follow the general _applicative order

Skipped exercises: 1.1, 1.2

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

Answer:

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

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

Answer: The if conditional will supply the operator, either + or -. Since the predicate is evaluated first.

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))

and then he evaluates the expression.

(test 0 (p))

1. What behavior will Ben observe with an interpreter that uses applicative-order evaluation?
2. What behavior will he observe with an interpreter that uses normal-order evaluation?

Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Answer: The procedure is a recursive call with no stopping criteria, so the evaluation should halt the execution if the procedure is invoked.

1. Normal order:

   1. (test 0 (p)) will be expanded first to (if (= 0 0) 0 (p))
   2. The if special-form will evaluate the predicate, and return the consequent which is 0. The alternative will not be evaluated.
2. Applicative order: Since the procedure (test 0 (p)) requires (p) to be evaluated, the test will never complete.