Chapter 1

evaluation rule is recursive. (* (+ 2 (* 4 6)) (+ 3 5 7)) = deeply nested 'combination'

as part of the evaluations execution, it must invoke itself again. each combination can be represented as a node, in a tree-like structure. the values of the lower (inner-most) operands perculating their values upwards until we get the final result. This form of evaluation is known as tree accumulation. Eventually you get to the point where you must evaluate on 'primitives' like numbers, not combinations. also built-in operators like + and * translate to machine instructions, depending on the environment. There are some special forms like define that dont take 2 arguments and produce a result.

Recursion is a powerful tool for dealing with tree-like structures.

Procedure Definition in Lisp

(define (⟨name⟩ ⟨formal parameters⟩) ⟨body⟩)

Substition model for procedure application (are there other types?? I can't imagine any other ways of doing it -- nevermind, it later says that this is the simplified model. real interpreters use slightly more complex models)

Substitute the parameters into the body

Applicative order vs Normal order evaluation

normal order is when you don't evaluate operands early, and instead replace them by parameters until you get down to an expression of only primitives, then you perform the evaluation.

Basically "fully expand and reduce" method. Sometimes you have to evaluate things twice. The interpreter uses the evaluation model from before called applicative-order evaluation where you eval operands as you go. -> this results in more efficiency because you don't need to re-evaluate the same expression more than once in cases where an expression gets reused later on but more importantly it results in less complexity when you move outside of functions that can be easily modelled with substitution.

Applicative evaluate operator and operands then apply procedure to resulting operands Normal form expand each substitution first then reduce whole expression

Conditional Expressions and Predicates

Uses keyword cond. e.g. evaluate absolute value of a number, it needs to do different things based on different cases (x < 0, x = 0, x > 0)

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

else can be used in the final clause of a conditional if no other predicates returned True. if is a special version of cond that is used when there are only 2 cases to analyse.

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

we can define our own predicate 'greater than or equal to'. equivalent to x is not less than y

Exercises

#lang sicp

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

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

(define (abs_if x)
  (if (< x 0)
      (- x)
      (x)
      ))

; Ex. 1.3
(define (sum-two-larger-squares a b c)
  (cond ((and (>= a b) (>= b c)) (sum-of-squares a b))
        ((and (>= a b) (> c b))  (sum-of-squares a c))
        (else (sum-of-squares b c))))

; Newton's method for calculating square roots
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

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

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

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

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

; Ex. 1.6
; infinite recursive loop because a functional call is applicative order so it evals all arguments first
; and operator and then applies the operator to the args. this will call sqrt-iter in the else-clase again
; causing infinite recursion

; Ex. 1.7
; good-enough? when squaring small numbers the squared number becomes smaller, so we very quickly
; hit 0.001 of precision because the difference might be big below that decimal place,
; but because the values are below 0.0001 e.g. 0.00003 vs 0.00008 we exit earlier
; they're both very different but within 0.001 of each other so the algorithm says its good enough
; For large numbers it won't terminate because the limited precision means that when we get to a very big
; large number, we cant represent a next number within 0.001 of the current guess (without using more
; bits to represent it), so our guess does not improve causing an infinite loop

(define (good-enough-delta? old-guess guess)
  (< (abs (- guess old-guess)) 0.001))

(define (sqrt-iter2 prev-guess guess x)
  (if (good-enough-delta? prev-guess guess)
      guess
      (sqrt-iter2 guess (improve guess x) x)))

; sqrt2 kick starts the recursive function with an old and a new guess
(define (sqrt2 x)
  (sqrt-iter2 1.0 (improve 1.0 x) x))

; sqrt  0.0003 -> 0.03438350032699598
; sqrt2 0.0003 -> 0.01732538223327823
; mr google    -> 0.01732050807

; Ex. 1.8
(define (cbrt x)
  (cbrt-iter 1.0 (improve-c 1.0 x) x))

(define (cbrt-iter prev-guess guess x)
  (if (good-enough-delta? prev-guess guess)
      guess
      (cbrt-iter guess (improve-c guess x) x)))

(define (improve-c guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))