Schema lisp

server: 155.69.150.106

from: http://mitpress.mit.edu/sicp/full-text/book/book.html

The advantage of prefix operator:
i, it can accommodate procedures that may take an arbitrary number of arguments.
ii, it extends a straightforward way to allow combinations to be nested.

expressions:

- define

- (cond ( )
( )

( ))

- (if )

-(and ... ), (or ... ), (not )

Scheme is an *applicative-order* language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, *normal-order* languages delay evaluation of procedure arguments until the actual argument values are needed. Delaying evaluation of procedure arguments until the last possible moment (e.g., until they are required by a primitive operation) is called *lazy evaluation*. If the body of a procedure is entered before an argument has been evaluated we say that the procedure is *non-strict* in that argument. If the argument is evaluated before the body of the procedure is entered we say that the procedure is *strict* in that argument. In a purely applicative-order language, all procedures are strict in each argument. In a purely normal-order language, all compound procedures are non-strict in each argument, and primitive procedures may be either strict or non-strict.

Lexical scoping dictates that free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions; that is, they are looked up in the environment in which the procedure was defined.

The amount of information needed to keep track of it, grows linearly with n (is proportional to n), just like the number of steps. Such a process is called a *linear recursive process*.

By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an *iterative process*. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. Such a process is called a *linear iterative process*.

In contrasting iteration and recursion, we must be careful not to confuse the notion of a *recursive process* with the notion of a *recursive procedure*. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written.

Exercise 1.11:
Recursive:
(define (f n)
(if (< n 3) n
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

Iterator: ?

Exercise 1.12:
(define (pascal r c)
(if (or (= r 1) (= c 1) (= c r)) 1
(+ (pascal (- r 1) c) (pascal (- r 1) (- c 1)))))

Exercise 1.16:
(define (expt b n)
(fast-expt 1 b n))

(define (even? n)
(= (remainder n 2) 0))

(define (fast-expt a b n)
(cond ((= n 0) 1)
((= n 1) (* a b))
((not (even? n)) (fast-expt (* a b) b (- n 1)))
(else (fast-expt (* a (fast-expt 1 b (/ n 2))) b (/ n 2)))))


Exercise 1.17:
(define (even? n)
(= (remainder n 2) 0))

(define (double x) (* x 2))

(define (half x) (/ x 2))

(define (fast-mul a n)
(cond ((= n 0) 0)
((even? n) (fast-mul (double a) (half n)))
(else (+ a (fast-mul a (- n 1))))))

Exercise 1.19:
By calculating that: $T^2_{pq}(a, b) = a(P^2 + 2pq + 2q^2) + b(2pq +q^2), a(2pq + q^2) + b(p^2 + q ^ 2)$, you draw the conclusion that: $p'=p^2 + q^2, q'=2pq + q^2$.

(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* q q) (* p p)) ; compute p'
(+ (* 2 q p) (* q q)) ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))


Euclid's Algorithm:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))


Prime test by The Fermat test:
Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.
To implement the Fermat test, we need a procedure that computes the exponential of a number modulo another number:
(define (expmod base exp m)
(cond ((= exp 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)))

Exercise 1.27:
(define (fierce-fast-prime? n)
(define (try-it a)
(= (expmod a n n) a))
(define (try-from a)
(cond ((= a n) true)
((try-it a)
(try-from (+ a 1)))
(else false)))
(try-from 2))


A procedure that expresses the concept of summation itself rather than only procedures that compute particular sums:
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))

e.g., for integer addition:

(define (identity x) x)

(define (sum-integers a b)
(sum identity a inc b))

Exercise 1.29:
(define (Sum-Simpson f k a b n)
(define (inc i) (+ i 1))
(define h (/ (- b a) n))
(define (coefficient-i i)
(cond ((= i 0) 1)
((= i n) 1)
((even? i) 2)
(else 4)))
(define (term-i i)
(* (coefficient-i i) (f (+ a (* i h)))))
(* (/ h 3.0) (sum term-i k inc n)))

Exercise 1.30:
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))

Exercise 1.31:
(define (product term a next b)
(if (> a b)
1
(* (term a) (product term (next a) next b))))

(define (fac a)
(cond ((even? a) (/ (+ a 2) (+ a 1)))
(else (/ (+ a 1.0) (+ a 2)))))

(define (inc a) (+ a 1))

(define (factorial a b)
(* 4.0 (product fac a inc b)))

;another solution: iterative way
(define (product term a next b)
(define (product-iter a result)
(if (> a b)
result
(product-iter (next a) (* (term a) result))))
(product-iter a 1)
)

Exercise 1.32:
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) (accumulate combiner null-value term (next a) next b))))

; iterative
(define (accumulate combiner null-value term a next b)
(define (accumulate-iter a result)
(if (> a b)
result
(accumulate-iter (next a) (combiner (term a) result))))
(accumulate-iter a null-value)
)

;test:
(define (A-Sum a b)
(define (Identity x) x)
(define (Inc x) (+ x 1))
(define (Sum x y) (+ x y))
(accumulate Sum 0 Identity a Inc b))

Exercise 1.33:

(define (filter-accumulate combiner accept null-value term a next b)
(cond ((> a b) null-value)
((not (accept a)) (filter-accumulate combiner accept null-value term (next a) next b))
(else (combiner (term a) (filter-accumulate combiner accept null-value term (next a) next b)))))

test:
(define (sum-square-prime a b)
(define (sum x y) (+ x y))
(define (prime? n)
(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))
(= n (smallest-divisor n)))
(define (inc x) (+ x 1))
(filter-accumulate sum prime? 0 square a inc b))

;; relative prime's product
(define (product-relative-prime n)
(define (product x y) (* x y))
(define (inc x) (+ x 1))
(define (identity x) x)
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (relative-prime? i)
(if (and (= (gcd i n) 1) (< i n))
true
false))
(filter-accumulate product relative-prime? 1 identity 1 inc n))

Lambda function:
(lambda () )

The general form of a let expression is

(let (( )
( )

( ))
)

which can be thought of as saying

let have the value and
have the value and

have the value
in

The way this happens is that the let expression is interpreted as an alternate syntax for

((lambda ( ...)
)


)

Therefore no new mechanism is required in the interpreter in order to provide local variables. A let expression is simply syntactic sugar for the underlying lambda application.