- 过程应用
- 代换模型
- 求值该组合式的各子表达式
- 将作为最左子表达式(运算符)的值的那个过程应用于相应的实际参数，所谓实际参数也就是其他子表达式(运算对象)的值
应用序求值(解释器实际使用)
解释器首先对运算符和各个运算对象求值，而后将得到的过程应用于得到的实际参数。 正则序求值
求值模型
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))应用序 会先计算(p) 这样 (p)调用(p)一直无限循环下去
如果是正则序
(define (square x)
(* x x))牛顿法求平方根 -- 逐步逼近方法
(define (square x)
(* x x))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (improve guess x)
(everage guess (/ x guess)))
(define (everage x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (my-sqrt x)
(sqrt-iter 1.0 x))
;;~~~~~~~~~~~~~~~~
(define (new-if predicate then-clause else-clause)
(cond
[predicate then-clause]
[else else-clause]))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))局部化
内部定义和快结构
(define (my-sqrt x)
(define (good-enough? prev guess)
(if (< (abs (- guess prev)) 0.00000000001)
#t
#f))
(define (sqrt-iter prev guess x)
(if (good-enough? prev guess)
guess
(sqrt-iter guess (improve guess x) x)))
(define (improve guess x)
(everage guess (/ x guess)))
(define (everage x y)
(/ (+ x y) 2))
(sqrt-iter 0 1.0 x))这种嵌套的定义称为块结构
简化：词法作用域
(define (my-sqrt x)
(define (good-enough? prev guess)
(if (< (abs (- guess prev)) 0.00000000001)
#t
#f))
(define (sqrt-iter prev guess)
(if (good-enough? prev guess)
guess
(sqrt-iter guess (improve guess))))
(define (improve guess)
(everage guess (/ x guess)))
(define (everage x y)
(/ (+ x y) 2))
(sqrt-iter 0 1.0))线性的递归 VS 迭代
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))迭代
1.计数器
2.维持一个变动的乘积
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(1+ counter)
max-count)))
(define (factorial n)
(fact-iter 1 1 n))
(factorial 6)tree-sum
(define tree-sum
(lambda (exp)
(match exp
[(? number? x) x]
[`(,e1 ,e2)
(let ([v1 (tree-sum e1)]
[v2 (tree-sum e2)])
(+ v1 v2))])))fib => n = (n - 1) + (n - 2)
(define (fib n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[else (+ (fib (- n 1))
(fib (- n 2)))]))
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))count change
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond
((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(count-change 100)
(define (my-expt b n)
(if (= n 0)
1
(* b (my-expt b (- n 1)))))
(define (expt2 b n)
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b (1- counter) (* b product))))
(expt-iter b n 1))Section 8.4 Examples
(define-syntax rec
(syntax-rules ()
[(_ x e) (letrec ([x e]) x)]))
(map (rec sum (lambda (x)
(if (= x 0)
0
(+ x (sum (- x 1))))))
'(0 1 2 3 4 5))
(define-syntax rec
(syntax-rules ()
[(_ x e) (letrec ([x e]) x)]))
(define-syntax let
(syntax-rules ()
[(_ ((x e) ...) b1 b2 ...)
((lambda (x ...) b1 b2 ...) e ...)]
[(_ f ((x e) ...) b1 b2 ...)
((rec f (lambda (x ...) b1 b2 ...)) e ...)]))e.g.
(let f ([ls '(1 2 3 4)] [sum 0])
(if (null? ls)
sum
(f (cdr ls) (+ sum (car ls)))))version 2.
(define-syntax let
(syntax-rules ()
[(_ ((x e) ...) b1 b2 ...)
((lambda (x ...) b1 b2 ...) e ...)]
[(_ f ((x e) ...) b1 b2 ...)
((letrec ([f (lambda (x ...) b1 b2 ...)]) f) e ...)]))log-fib
(define (fib n)
(define (fib-iter a b p q count)
(cond
[(= count 0) b]
[(even? count)
(fib-iter a
b
p
(+ q 1)
(/ count 2))]
[else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1))]))
(fib-iter 1 0 0 1 n))GCD [modified version]
(define (gcd a b)
(if (< a b)
(if (= a 0)
b
(gcd a (remainder b a)))
(if (= b 0)
a
(gcd b (remainder a b)))))
;; book
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))prime
(define (smallest-divisor n)
(find-divisor n 2))
(define (square n)
(* n n))
(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))
(define (prime? n)
(= n (smallest-divisor n)))fast-prime
(define (square n)
(* n n))
(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) #t]
[(fermat-test n) (fast-prime? n (- times 1))]
[else #f]))
(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 (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))ChezScheme Version
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (current-time)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (time-difference (current-time) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))if n is not prime it must have a divisor less than or equal to (sqrt n).
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.
In fact, Carmichael numbers are also called Fermat pseudoprimes