- When modeling complex problems, we create “languages” to express those problems.
- Mechanisms languages use to create complex ideas:
- Primitive expressions
- Means of Combination
- Means of abstraction
- See Chapter 2 Picture Language and Chapter 3 Simulator Language as examples
- 2 kinds of elements in programming:
- Procedures
- Data
- Both of these are not so different
- Will be discussed later how the interpreter substitutes the body of a procedure to an argument
- Additional Resource: https://sookocheff.com/post/fp/evaluating-lambda-expressions/
- Lisp interpreter uses Applicative order substitution
The interpreter first evaluates the operator and operands and then applies the resulting procedure to the resulting arguments.
(double (average 2 4))
(double (/ (+ 2 4) 2))
; Then start reducingFirst substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation.
Expression is fully expanded then reduced
(double average(2 4))
(+ (average 2 4) (average 2 4))
(+ (/ (+ 2 4) 2) (/ (+ 2 4) 2))
; Then start reducing- There are cases when evaluation order does not return the same result
- Lisp uses application order as it provides better efficiency
- See Exercise 1.26
- Predicate: name given to procedures which return either true or false
- If keyword is a special form in Lisp
- A special form is does not follow the normal rules of evaluation
- Logic composition operations (and, or and not) construct compound predicates
- And and Or are special forms
- Not is a procedure
10 12 3 6
- 3 (+ 3 1) (* 3 (+ 3 1)) = + 3 4 (* 3 4) = + 3 4 12 = 19
false …
#lang racket
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7))); Procedure to print the square of the highest two numbers
#lang racket
(define (square x) (* x x))
(define (sum-squares x y) (+ (square x) (square y)))
(define (sum-greatest-two-squares a b c) (cond
[(and (< a b) (< a c)) (sum-squares b c)]; print b and c
; else
[(and (< b a) (< b c)) (sum-squares a c)]; print a and c
; else
[(and (< c a) (< c b)) (sum-squares a b)] )); print a and b
(sum-greatest-two-squares 1 2 3)
(sum-greatest-two-squares 4 2 3)
(sum-greatest-two-squares 4 5 3)
- Recursive Procedure: Specifically a procedure which directly/indirectly refers to itself
- Recursive process: Specifically how the process evolves. Process builds a chain of deferred operations
- Is not the same as a recursive procedure
- Linear iterative process: Has a complete description of the state of the process at any point (i.e. fixed number of state variables)
Example of a iterative process with recursive procedure:
#lang racket
(define (fact-iter product i max-count)
(if (> i max-count)
product
(fact-iter (* i product) (+ i 1) max-count )))
(define (factorial n) (fact-iter 1 1 n))
(factorial 5)- Recursion with multiple branches
- In general number of steps is proportional to nodes in the tree
- Space is proportional to depth of the tree
- Not really efficient but can be improved with tabulation (i.e. a table of already computed values which the intepreter can fist try look up before computing)
- See Example with Fibonacci series
#lang racket
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))#lang racket
(require racket/trace)
(define (f-tree n)
(if (< n 3)
n
(+ (f-tree (- n 1))
(* 2 (f-tree (- n 2)))
(* 3 (f-tree (- n 3))))))
(trace f-tree)
;; (define (f-iter n)
;; (define (iter i)))
(f-tree 2)
(f-tree 4)
#lang racket
(require racket/trace)
;; (define (pascal-row level)
;; (define (pascal-iter i)
;; (if (> i level)
;; 0
;; ((display (pascal level i))
;; (pascal-iter (+ i 1)))))
;; (pascal-iter 1))
;; ^^^^ need to find a way to execute multiple lines in if statement for this
(define (pascal level coeff)
(cond ((= coeff 1) 1)
((= coeff level) 1)
(else (+ (pascal (- level 1) (- coeff 1))
(pascal (- level 1) coeff)))))
; (trace pascal)
(pascal 5 1)
(pascal 5 2)
(pascal 5 3)
(pascal 5 4)
(pascal 5 5)- Interested in algorithm where if the problem size doubles; the resource requirement remains constant
n * n * n * …
#lang racket
; computing b^n
(define (iter b i product)
(if (= i 0) product (iter b (- i 1) (* b product)) ))
; computing b^n
(define (even? n) (= (remainder n 2) 0))
(define (square n) (* n n))
(define (fast-iter b n)
(cond ((= n 0) 1)
((even? n) (square (fast-iter b (/ n 2) )))
(else (* b (fast-iter b (- n 1)))) ))
(define (expt b n) (iter b n 1))
(define (fast-expt b n) (fast-iter b n))
(expt 2 4)
(fast-expt 2 4)#lang racket
(define (even? n) (= (remainder n 2) 0))
(define (expo b n a)
(cond ((= n 0) 1)
((= n 1) a)
(else )))
(square 2 4 1)#lang racket
(define (even? n) (= (remainder n 2) 0))
(define (double x) (+ x x))
(define (half x)
(if (even? x)
(/ x 2)
x))
; multiplication with addition in log steps
(define (mult a b)
(cond ((= b 1) a)
((even? b) (mult (double a) (half b)))
(else (+ a (mult a (- b 1))))))
(mult 4 4)
(mult 3 5)#lang racket
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(gcd 4 5)- Iteratively increase a test-divisor starting at two (ignoring 1 as a factor)
- If test-divisor^2 is greater than n and no divisor is found; number is prime
#lang racket
(define (square x) (* x x))
(define (divides? a b) (= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (smallest-divisor n) (find-divisor n 2))
(define (prime? n) (= n (smallest-divisor n)))
(prime? 5)
(prime? 4)$θ(log n)$ - Congruences: Arithmetic of remainders
- Consider 40 % 3 and 16 % 3 both produce 1
- Therefore 40 and 16 with respect to 3 are congurent
- Properties of congruence worth noting:
- Remainder of sum is equal to sum of the remainders
- Remainder of the product is equal to product of the remainder
- Useful when dealing with powers
- a^n congurent b^n (mod m)
- Fermat’s theorem: if p is prime; a^p congruent a (mod p)
- Fermat’s Little Theorem: a^(p-1) congurent 1 (mod p)
#lang sicp
(define (square x) (* x x))
; define a modulo procedure
; returns base^exp mod m
(define (expmod base exp m)
(cond ((= exp 0) 1) ; n^0 = 1
; [(base^(n/2) mod m)^2] mod m
((even? exp) (remainder (square (expmod base (/ exp 2)) m) m))
; product of the remainder
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))- Dealing with procedures whose answer is only “probably” correct
- An example is the Fermat test where Carmichael numbers can fool the test
#lang racket
(define (square x) (* x x))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)#lang sicp
; see testing for primality
(define (square x) (* x x))
(define (divides? a b) (= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (smallest-divisor n) (find-divisor n 2))
(define (prime? n) (= n (smallest-divisor n)))
; modified to not print every number
(define (timed-prime-test n)
; (newline)
; (display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))))
(define (report-prime prime elapsed-time)
(newline)
(display prime)
(display " *** ")
(display elapsed-time))
(define (search-for-primes lbound hbound)
(cond ((even? lbound) (search-for-primes (+ lbound 1) hbound))
((> lbound hbound) nil)
(else (search-for-primes (+ lbound 2) hbound)))
(timed-prime-test lbound))
(search-for-primes 1000 1100)
(newline)
(search-for-primes 10000 10100)
(newline)
(search-for-primes 100000 100100)
(newline)
(search-for-primes 1000000 1000100)
#lang sicp
(define (next n)
(if (= n 2)
3
(+ n 2)))
(define (square x) (* x x))
(define (divides? a b) (= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor))))) ; modified
(define (smallest-divisor n) (find-divisor n 2))
(define (prime? n) (= n (smallest-divisor n)))
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))))
(define (report-prime prime elapsed-time)
(newline)
(display prime)
(display " *** ")
(display elapsed-time))
(define (search-for-primes lbound hbound)
(cond ((even? lbound) (search-for-primes (+ lbound 1) hbound))
((> lbound hbound) nil)
(else (search-for-primes (+ lbound 2) hbound)))
(timed-prime-test lbound))
(search-for-primes 1000 1100)
(newline)
(search-for-primes 10000 10100)
(newline)
(search-for-primes 100000 100100)
(newline)
(search-for-primes 1000000 1000100)
Yes. The compute time has been halved
#lang sicp
(define (square x) (* x x))
(define (expmod base exp m)
(cond ((= exp 0) 1) ; n^0 = 1
((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (fast-prime? n 100) ; choosing 100
(report-prime n (- (runtime) start-time))))
(define (report-prime prime elapsed-time)
(newline)
(display prime)
(display " *** ")
(display elapsed-time))
(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)
- Although computation is growing by an order of magnitude; the time is increasing by a factor of 10 (i.e. follows logarithmic growth)
- No.
- The Lisp interpreter by explicitly defining the multiplication the arguements separately and then multiplied together. Instead the the argument should be evaluated once and then using that result, squared.
- Explicitly calling the multiplication causes normal order evaluation versus applicative evaluation.
- Carmichael numbers are numbers which pass the Fermat test however not prime numbers
- Very few
- 561, 1105, 1729, 2465, 2821, 6601 are examples
#lang sicp
(define (square x) (* x x))
(define (expmod base exp m)
(cond ((= exp 0) 1) ; n^0 = 1
((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(fermat-test 561)
(fermat-test 1105)
(fermat-test 1729)
(fermat-test 2465)
(fermat-test 2821)
(fermat-test 6601)- First abstraction is to name procedures, and work in terms of the abstraction
- Useful abstraction to pass procedures as arguments
- Conversely procedures can return other procedures
- Examples and exercises using this abstraction is shown below
#lang racket
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result)) ))
(iter a 0))
(define (inc a) (+ a 1))
(define (sum-basic a) (+ a 1))
(sum sum-basic 1 inc 5)#lang racket
(require racket/trace)
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result)) ))
(iter a 1))
; factorial
(define (inc a) (+ a 1))
(define (product-basic a) a)
(product product-basic 1 inc 5)
; pi approximation
(define (pi-approx-inc a)
(+ a 2))
(define (pi-approx-product a)
(if (= a 2)
2
(* a a)))
; (trace pi-approx-product)
(define pi-approx-num
(product pi-approx-product 2 pi-approx-inc 10))
(define pi-approx-den
(product pi-approx-product 3 pi-approx-inc 9))
(/ pi-approx-num pi-approx-den)
; product rewritten as recursive
;; (define (product-recur term a next b)
;; (if (> a b)
;; 1
;; (product-recur )))#lang racket
(define (accumulate combinator null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combinator (term a) result))))
(iter a null-value))
(define (inc a) (+ a 1))
(define (basic-term a) a)
(accumulate + 0 basic-term 1 inc 5)
(accumulate * 1 basic-term 1 inc 5)
#lang sicp
(define (filter-accumulate combinator null-value term a next b filtr)
(define (iter a result)
(cond ((> a b) result)
((not (filtr a)) result)
(else (iter (next a) (combinator (term a) result)))))
(iter a null-value))
; get prime test
(define (square x) (* x x))
(define (divides? a b) (= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (prime-next test-divisor))))) ; modified
(define (smallest-divisor n) (find-divisor n 2))
(define (prime? n) (= n (smallest-divisor n)))
(define (prime-next n)
(cond ((= n 1) 2)
((= n 2) 3)
(else (+ n 2))))
(define (basic-term a) a)
(define (relatively-prime? n)
(define (iter a)
(cond ((= a n) true)
)))
(filter-accumulate * 1 basic-term 1 prime-next 10 prime?) ; expecting 210- Lambda keyword used to create anonomous functions
- Let keyword provides easy way to bind local variables of lambda functions (syntactic sugar for lambda)
- Need to be aware if defining a variable with let and global variable share the same name; the value assigned by let only applies to the body of the let “function”
#lang racket
(define (square x) (* x x))
(define (f x y)
(define (f-helper a b)
(+ (* x (square a))
(* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y)))
; no need for intermediate helper function name
(define (f-lambda x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y)) ; define x
(- 1 y) )) ; define y
; notice locations of definitions of x and y
(define (f-let x y)
(let ((a (+ 1 (* x y))) ; define x
(b (- 1 y))) ; define y
; body
(+ (* x (square a))
(* y b)
(* a b))))
(f 2 3)
(f-lambda 2 3)
(f-let 2 3)- Section builds on Procedures as Arguments section (how to use abstraction to build more general procedures)
- Sections gives two more examples; finding zeros and finding fixed points of functions
#lang sicp ; half-interval theorem (Reminds me of squeeze theorem) ; f(a) [negative] < 0 < f(b) [postive] ; as long as ^this is true we can keep halving the distance between a and b to approximate a zero (define (search f neg-point pos-point) (let ((midpoint (average neg-point pos-point))) (if (close-enough? neg-point pos-point) midpoint (let ((test-value (f midpoint))) (cond ((positive? test-value) (search f neg-point midpoint)) ((negative? test-value) (search f midpoint pos-point)) (else midpoint) ))))) (define (close-enough? x y) (< (abs (- x y)) 0.0001)) (define (average a b) (/ (+ a b) 2)) ; consider the case we don't provide negative and positive numbers (define (half-interval-method f a b) (let ((a-value (f a)) (b-value (f b))) (cond ((and (negative? a-value) (positive? b-value)) (search f a b)) ((and (negative? b-value) (positive? a-value)) (search f b a)) (else (error "Try different values which produce opposite sign" a b)) ))) (half-interval-method sin 2.0 4.0) ; approx pi
- In mathematics we have procedures which transform functions. Eg. The derivative of f(x) = x^3 produces f’(x) = 3x^2
#lang racket
; Takes function g to produce derivative function
; g'(x) = [g(x + dx) - g(x)]/dx for a small number of x
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
(define dx 0.00001)
; define a function f(x) = x^3
; and find derivative at x = 5
(define (cube x) (* x x x))
((deriv cube) 5)- It is useful to apply higher orders of abstraction when applicable
#lang racket
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
(define dx 0.00001)
; Define newton's transform which is
; f(x) = x - g(x)/g'(x)
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x) ))))
(define (newton-method g guess)
(fixed-point (newton-transform g) guess))
(define (sqrt x)
(newton-transform (lambda (y) (- (square y) x)) 1.0))- Rights of first class elements are:
- Named by variables
- Passed as arguments to procedures
- return as results by procedures
- included in data structures
#lang racket
; Find roots of x^3 + ax^2 + bx + c
(define (cubic a b c)
(lambda (x) (+ (* x x x) (* x x a) (* x b) c) ))#lang racket
(define (double f) ; takes procedure f
(lambda (x) (f (f x)) )) ; applies function twice to x
(define (inc a) (+ a 1))
((double inc) 5) ; expected 5 + 2
(((double (double double)) inc) 5)#lang racket
(define (composition f g)
(lambda (x) (f (g x)))) ; first apply g on x then f on the result
(define (square x) (* x x))
(define (inc x) (+ x 1))
((composition square inc) 6) ; expected (6+1)^2 = 49#lang racket
(define (composition f g)
(lambda (x) (f (g x)))) ; first apply g on x then f on the result
; first attempt but doesn't use procedure as return value
;; (define (repeated f n)
;; (define (iter i result)
;; (if (> i n)
;; result
;; (iter (+ i 1) (f result)) ))
;; (lambda (x) (iter 1 x)))
(define (repeated f n)
(if (= n 1)
(lambda (x) (f x)) ; return procedure
(composition f (repeated f (- n 1)) ))) ; compose with recursive next procedure
(define (square x) (* x x))
((repeated square 2) 5); expected (5^2)^2#lang racket
(define dx 0.001)
(define (smooth f)
(lambda (x) ((/ ((+ (f (- x dx)) (f x) (f (+ x dx)) )) 3))))
(define (composition f g)
(lambda (x) (f (g x)))) ; first apply g on x then f on the result
(define (repeated f n)
(if (= n 1)
(lambda (x) (f x)) ; return procedure
(composition f (repeated f (- n 1)) )))
(define (test-function x) (+ (* x x) 1))
((repeated (smooth test-function) 2) 3)