e, 10k. , 123e10 1 23 * 1 0 1 0, -1 23 . 4 5 -1 - -1 23. 45 1 0 - 1 . Scheme :

18


and begin cond cons-stream define delay

else error if lambda let make-environment

or quote sequence set! the-environment unquote

, , . , . -: Q so up <=? a3 4 kT MN s lis t - >v ector +

t he -wo r d -rec u r si o n-ha s-ma ny-me a n i ngs
FOO.

Foo ,


- , . , . . «;» , . «» :
. * / < => ! ? : $ % _ & ~ ^

«.», «+» «-» . . «(» «) » . «'» . «" » . «\ » . «[ », «] », «{ » «} » . «# t » «# f » . «# \ » AS CII . «# (» . Scheme : , , , . , .


, , , . ->. .
486


-» 486

, (, + *) . . :
(+ ((* (/ (+ 137 34 9) 100 -3 34) 5 99) 10 5} 2.1 10 ) -> -> -> -> -> 486 43 4 49 5 2 12 .7

, , , . , - . , , , . , , . . , , . : (+ 11) -> 11
75 1200 (+ 21 35 12 7) -> (*25 4 12) ->

, .
(+ (* 3 5 )

, . ,
-> 19

(- 10 6) )

20


, , , .
(+ ( * 3 (+ ( * 2 4) (+3 5))) (+ (- 10 7) 6) )

57. (+ ( *
(+ (* 2 4) (+ 3 5) ) ( + (- 10 7) 6)))


. Scheme , (, , ..). define.
(define size 2)

, 2 size defi ne , , . , size 2, :
siz e (* 5 s i ze) -> 2 -> 10

define:
(define pi 3.14159)

(define radius 10)
(* pi (* radius radius)) (define circumference (* 2 pi radius)) circumference -> -> 314.159 62.8318

21


define . , , , . . , Scheme . , , . <, > ( ). Scheme , ( ) . (), . , , , , , . , () . Scheme . . , - Scheme. abc. abc. : 123, 78 -3 , # t . , , , . , , quote. (quote ) . Scheme. , , quote . qu o t e «' » (« ») . , (q u o te ) ' .
(quote a) (quote # (a b )) (quote (+ 1 2)) ->

-> #( )

-> ( + 1 2)

22


' '#( ) '(+ 1 2 ) '(quote a)

-> > -> >

# ( ) (+ 1 2) (quote a)

''



->

(quote a)

, . , "abc". , , ( quote «») .
'"abc" -> "abc"

"abc"
'145932 145932 '#t #t

>
-> -> -> ->

"abc"
145932 145932 #t #t

H o qu ot e : (define a 3) (define abc (+12)) (quote a) ' abc ' abc b 'b (+1 2) 2 ) -> -> 3 -> a -^ -> 3 -> abc -> - -> b -> 3 ·(+1 (+1 2)


, .

1. . 2. , , , .

23


(* (+ 2 (* 4 6 ) ) ( + 3 5 7 ) ) . . , ( 1 ) , , , , . : · (, , ); · , ; · , . , (de f i n e). (de f i n e x 3 ) define 3, 3. , define , . . ( ) . Scheme , , .


. , , . Scheme :
(define (square x) (* x x))

: . . :
(define ( ) )

, . < f o r m a l
24


para meters> , . , , . , . , , . square, .
(square 21) -> 441 (square ( + 2 5 ) ) -> 49 (square (square 3)) -> 81

. , 2 + 2
(+ (square x) (square ))

.
(def ine ( su m- o f- squa res ) (sum-of-squares 3 4 ) -> ( + (sq u are x) 25 ( squar e )) )

s u m - of - s qu a r es : (define (f a) (f 5 ) (sum-of-squares (+ a 1) -> 136 (* 2 ) ) )

, . , , .


, , , . , . . , , . (f 5 ) , f - , . f:
25


(sum-o f-sq uares (+ a 1 )

(* a 2))

, 5: (sum-of-squares ( + 5 1 ) (* 5 2})

, sum-o f-squares. . , , , , , . ( + 5 1 ) (* 5 2) 6 1 0 . sum-of-s q uares 6 10.
(+ (square 6) (square 10))

square
(+ (* 6 6) (* 10 10) )

(+ 36 100) 136. . , , . . , , . , , , , . (f 5).
(sum-of-squares ( + 5 1) (* 5 2))
(+ (square ( + 5 1 ) ) (square (* 5 2)))

(+ (* (+ 5 1) ( + 5 1 ) ) (* (* 5 2) (* 5 2) ))



26


{+ ( * 6 6) ( + 36 100) 1 36

( * 10 10) )

, (+ 5 1 ) (* 5 2 ) , (* ), (+ 5 1 ) (* 5 2 ) . « , », . « , », , , , . , . , . Scheme , , , , .


Scheme , , . cond. : (d ef i n e ( a bs x ) (cond ((> 0) ) (( = 0) 0)
( (< 0) ( - ))))


(cond (< p 1> ) (<2> <2>) ( ) )

cond , . , , . Scheme #f #t, . . . . , <2>. <2> ,


<>. , , . , , . abs >, <, =. « », . ab s : (def i n e (ab s x ) (cond ( (< x 0) (-x) ) (else x ) ) ) els e , cond. el se . el s e , (, #t). abs. (define (ab s x) ( i f (< x 0) (-x) x) )

if, , . if :
(if )

if . if , if . if cond , < i > co n d , . if .

28


, , <, >, = , . and, or not.
(and . . . )

and . , and , . , and .
(o r . . . <>)

or . , or , . , or .
(not )

not , <> . , and or , , not . 5 < < 10.
(an d (< 5) ( < 1 0) )

« »:
(define (>= ) (or (> ) (= ) ) )

(d efin e (>= ) (not (< ) ) ) 1 .

?

29


10 (+534) (- 91) ( / 2)

(+ (* 24) (-4 6))
(define a 3) (define b (+ a 1)) (+ a b (* a b) ) (= a b) (if (and (> b a) (< b (* a b) ) ) b a) (cond ((= a 4) 6) ((= b 4) (+ 6 7 a) ) (else 25)) (+ 2 (if (> b a) b a) ) (* (cond ((> a b) a) ( (< b a) b) (else -1) ) (+ a 1) )

2. -, .

3 : (define (a-plus-abs-b a b) (if (> b 0) + -) a b)) 4.

: (define (p) (p)) (define (test ) ( i f (= 0) 0 ) )

(t es t ( )) . : if . , .

.
: /**/k = , > = 0 2 = . , , , /. 2, , . , . = /. :

/
2/1=2 1.5/2=1.3333

1 1.5
30

/, )

(2+1)/2=1.5 (1.3333+ 1.5J/2-1. 4167


1.4167 1.4142

2/1.4167=1.4118

(1.4168+1.4118)/2=1.414 2

sqrt-iter, guess () (, ). , guess, guess.
(define {s qr t-iter gues s x) ( i f (good-enough? guess x) guess ( sqrt iter (i mprove guess x) x))}

x/guess guess.
(d e f in e (def ine ( a ve rage x y) ( / ( + x y ) 2) ) ( i m p ro v e gu e s s x) (a v e ra g e gu e ss ( / x gue s s ) ) )

, good-enough?. , , , «?». \guess2 - \ < eps.
( d e f i n e ( g o o d - e n o ugh? gue ss x) (< (abs (- (square guess) x)) 0 . 0 0 1 ))

guess . . , sqrt. , 1.
(define (sqrt x) (sqrt-iter 1.0 x))

sqrt, .
(sqrt 9) (sqrt (+100 37)) -> -> 3.00009155413138 11.704699917758145


(sqrt (+ (sqrt 2)(sqrt 3))) (square (sqrt 1000))

-> 1.7739279023207S92 -> 1000.000369924366

, , , (, ). sq rt -iter . sqrt. , : , . . . . , . , good-enough? square. « ». , . , , , . square .


5. if ? cor.d?
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) ( e l s e e l s e cl ause)) )


(new-if (= 2 3) 0 5} (new-if (= 1 1) 0 5) -> -> 5 0

. , ne w- i f sq rt- ite r ? .
(define (sqrt-iter guess x! (new-if (good-enough? guess x) guess (sqrtiter (improve guess x) x))) 32


6. good-eno ugh? . 7. , , , ( /2 + 2 ) / 3. , cub e-root, . . , square . . , sqrt.

(define (average ) (/ ( + ) 2 ) ) (define ( s qrt x ) (define (good-enough? guess x) (< (abs (- square guess) x)) 0.00 1 )) (define (impro ve guess x) ( a ve r a ge g u e s s ( / x gu e s s) ) ) (defi n e ( s qr t - i t e r guess x) (if (good-enough? guess x) guess (sqrt - i t er ( i mp ro v e guess x ) x)) ) (sq r t- iter 1 . 0 x) )
. . () sq rt , go o d -eno ugh? , i mp ro v e sq uare-iter , . () . .
(define (sqrt x)

(define (good-enough? guess) (< (abs (- square guess) x)) 0.001)) (define (improve guess)
(average guess (/ x guess))) (define (sqrt-iter guess)


(if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))

Algol-60. .

,
. , . , Scheme.


n! = ( 1) ( - 2) ... 3 2 1. . , ! ( - 1 )!. , , 1! = 1, :

(de f in e ( f ac to ri al n) (if (= n 1) 1 (* n (factorial (- n 1 ) ) ) ) ) , ( f a ctor i a l 6) , . ,
(factorial 6) (* 6 (factorial 5)) (* (* 5 (factorial 4))) (* 6 (* 5 (* 4( factorial 3)))) (* 6 (* 5 (* 4 (* 3 (factorial 2))))) (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1)))))) (* 6 (* 5 (* 4 {* 3 (* 2 1))))) ) (* 6 (* 5 (* 4 (* 3 2))))) (* 6 (* 5 (* 4 6)))) (* 6 (* 5 24» (* 6 120) 720

1 2 3 . . .
34


1 . : <- * <- + 1

n! - , , .
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter I ) ) ) ) (iter l 1 ))

, , .
(factorial (iter 1 (iter 1 (iter 2 (iter 6 6) 1) 2) 3) 4)

(iter 24 5) (iter 120 6) (iter 720 7) 720

. . . , . . . ( ). , . , , . , , . / , , , . .

35


, . . , , , . n! . . , . , . «» , , , « » . , . , . , , . , , , , . (, iter) . , , Ada, Pascal , , , , , . , . Scheme , .


8. , inc dec. (define (+ a b) (if (= 0) b (inc (+ (dec ) b) ) } ) (define (+ a b) (if (= 0) b (+ (dec a) (inc b) ) ) )
36


, npo (+ 4 5). - ?


. .
(JOHN SMITH 33 YEARS) ((DAVE 17) (MARY 24) (ELIZABETH 6 ) )

((my house) has (large (light windows)))

, , . , . . . . - . 1. . 2. , , .

.
, , ( ) ().

car ( ) . , . .
( ( ( ( ' ' ' ' ( b ) ) ( () b d) ) ) () ) -> -> () -> ->

cdr , . cdr
37


. , cdr ni 1, .
(cdr ' ( () b d) ) d) (cdr ' ( )) (cdr ' () ) -> -> -> (b c nil

cdr , .

(car (cdr (cdr x)))
(A B D). (cdr x ) (B C D ) , a (cdr (cdr )) (C D). , (car (cdr (cdr x ) ) ) c, . Scheme cdr. T o , , :
(caar ) (cadr ) (cdddar ) (cddddr )

, caddr
(define (caddr x) (car (cdr (cdr x)))))

Scheme :
(first ) (second ) (eighth )

, , ..., .
(first ' ( (a b) d) ) (second ' ( (a b) d) ) (eighth ' (a b d e f g h) ) -> (a b) -> -> h

38


cons . ( cons) cdr. co ns nil, cons , . (cons ) + 1. nil , . , , .
( d ef i n e x ( c o n s 1 2) ) (car x) (c dr x) ( d e f ine (d ef in e ( car ( car (c ar (c dr y (c ons z (cons z) ) z) ) 3 x -> -> 1 2

4) ) y) ) -> 1 -> 3 -> -> -> (a) ( ( a ) b d) ("a" b c)

(cons 'a ' ( ) ) (cons ' ( a ) ' (b d) ) (cons "a" ' ( b e ) )

cons:
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) -> ( 1 2 3 4)

Scheme
(list < 3 > ... < >)


(cons (cons (cons . . . , (list 1 2 3 4 ) (l i s t 'a ( + 3 4) ' c ) (list ) -» -» -> (1 2 3 4) (a 7 c) () (cons n i l) ... )))

, , , . .
39


(atom? ) , ( ) .
(atom? (atom? (atom? (atom? (atom? (atom?

3)

-> -> car) -> '(a 3 -> -> ' nil) ->

'

#t #t #t #f #t #t

, , (list? ) , . ( ( ( ( list? list? list? list? ' ' ' ' a) ()) ( b) ) ( . b)) -> -> -> -> #f #t #t #f

: (null? ) , . eq?, , equal?, . , . (equal? ' ( b) ' (a b)) (equal? 3 3 ) (equal? ' ') (eq? ' (a b) ' (a b ) ) (eq? 3 3 ) -> -> -> -> -> #t #t #t #f #t


, lis t - ref , ite m s , - .
40


, 1 . = 1 list-ref , . list-ref (n-l) - , cdr .
(d efi n e (li st-r ef ite m s n) (i f (= n 1) (car items) (list-ref (cdr items) (- n 1 ) ) ) ) (define squares (list 1 4 9 16 25)) (list-ref s q ua re s 4) -> 16

( ) .
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items))))) (length squares) -> 5

:
(define (length items) (define (length-iter a count) (if (null? a) count (length-iteg (cdr a) (+ 1 count)))) (length-iter items 0))

append , :
(define (append list1 Iist2) (if (null? listl) list2 (cons (car listl) (append (cdr listl) list2))))


9. last-element , , .

( l ast-p a ir ( list 1 2 3 4 ) )

->

4

10. reverse, , .
41


(reverse (list 1234))->

( 4 321)

, co ns , . .
(cons 'a 3) (cons ' ( ) ') (cons ' (b) ) -> ( . 3) -> (( ) . ) -> ( )

, nil.
(pair? )

, < obj > . , , - . (pai (pai (pai (pai r? r? r? r? ' ' ' ' ( . b) ) (a b ) ) ()) \ # ( a b)) -> -> -> -> #t #t #f #f

(co n s e 1 e 2 ) (v1.v2), v1 v2 e1 2, , . : · , , , :
Vk.vk+1)

(v1. (v2. (v

3

.. .

(v

k

.v

k+1

)

... )

(v

1

v

2

...

· , nil, , nil: (v 1 v 2 ... V k . n il) (v 1 v
2

... v k )

42


, (cons a (cons b (cons nil))) (a. (b. (. nil))),
( b . ( . nil)) ( b . nil) ( b )

, , , . (x1 2 . ) X1 , 2 - , - . . . ( ) - . ( ), (cdr ). . , cons. ,

43


. - , , , . . count-l e ave s, . le n gt h co u nt-leaves - .
(define x (cons (list 1 2) (length x)
(count-leaves x) (list x x ) 4)) (length (list x x)) (count-leaves (list x x))

(list 3 4 ) ) ) -> 2
-4 > -> ( ( (1 2) 3 4) ((1 2) 3 -2 > -> 8

count-leaves .
1. . 2. , , . 3. () (cdr) .
(define (count-leaves x) (cond ((null? x) 0) ((atom? x) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))


11 . (l is t l (l ist 2 (l is t 3 4 ) ) ) . , . 12. cdr,
7.

( 1 3 (5 7) 9) (( 7 ) ) (1 (2 (3 (4 (5 ( 6 7 ) ) ) } ) )
44


13. .
(define x (list 1 2 3 ) ) (defin e (list 4 5 6 ) )

:
(append x ) (cons ) (list x ) 14. rever se, de ep- r ev e r s e , , , , . , . :
(d e f in e x ( l i s t ( l is t 1 -> (reverse x) -> ( de ep - rev e rs e x) -> 2) ( (1 ( (3 ((4 (list 3 4 ) ) ) 2) (3 4)) 4) (1 2 ) ) 3) (2 1 ))

15. fringe, , , , , .
(d e fin e x ( lis t (l is t 1 2) ( lis t 3 4 ) ) ) (fringe x) -> (1 2 3 4) (fringe (list x x) ) -> ( 1 2 3 4 1 2 3 4 )


, , . , , , . , , , , .

. b:


(define (sum-integers a b) (if (> a b) 0 (+ a (sum-integers (+ a 1) b) ) ) )

:

(def i n e ( s um -s q u are s a b) ( i f (> a b) 0 ( + (square a) (sum-squares (+ 1) b) )) )

: 1/1*3+1/5*7+1/9*11+ .. .
(d ef in e (p i-s u m a b ) (if (> a b ) ( + ( / 1 . 0 (* ( + 2 ) ) ) (pi-sum (+ 4) ) ) ) ) . , . :

(defin e ( a b) (if (> a b ) 0 ( + ( a)

( ( a) b))))

/* */E. .
(de f i n e ( s um t e r m a n e xt b) (if (> a b) 0 ( + (term a) (sum (next a) b) ) ) )

su m 4 : (, b) term next. sum , . , .
(define (inc n) (+ n 1)) (define (sum-squares a b) (sum square a inc b)) (define (identity x) x) (define (sum-integers a b) (sum identity a inc b)) (define (pi-sum a b) (define (pi-term x) (/ 1.0 (* x (+ x 2))))) (define (pi-next x) (+ x 4)) (sum pi-term a pi-next b))

46


, , .
(d e f in e ( i n c 1 -lis t x ) (if (eq? x nil) nil (cons (+ (car x) 1)

(incl-list (cdr x)))))

mod2-list 2.
( de fi ne (m od 2- li st x) (if (eq? x nil) nil (cons (mod (car x) 2)

(mod2-list (cdr x)))))

, , , .
(define (map x f) (if (eq? x nil) nil (cons (f (car x) 2)

(map (cdr x)))))

inc-list mod2-list map :
(define ( de fi ne ( de fi ne (define (inc1 x) (+ x 1) (mod2 x) (mod x ( incl-lis t x ) (m (mod2-list x) (m ) 2)) ap x incl )) ap x mod2))

, , . . reduce - , g - , - . (x1 x2 ... xk) g(x1, g(x2 .. . g(xk, a) ...)). , (reduce x + 0) .
(define (reduce x g a) (if (eq? x nil) a (g (car x) (reduce (cdr x) g a ))))

47


, :
{define (sum x) (reduce x + 0)) (define (mult x) (reduce x * 1)

filter , , .
(define (filter predicate sequence) (cond ((null? sequence) nil) ((predicate (car sequence)) (cons (car sequence)

(filter predicate (car sequence)))) (else (filter predicate (cdr sequence)))))

: (filter odd? (list 1 2 3 4 5 ) ) -> (135)

- accumulate.
(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence)))))

:
(accumulate + 0 (list 1 2 3 4 5 ) ) (accumulate * 1 (list 1 2 3 4 5 ) ) (accumulate cons nil (list 1 2 3 4 5 ) ) -> 15 -> 120 -> ( 1234 5)


16. map, append, length, count-leaves accumulate. (define (map p sequence)
(accumulate (lambda (x y) ) nil sequence) (define (append seql seq2)

(accumulate cons ))
(define (length sequence) (accumulate 0 sequence))

48


(define (count-leaves t)
(accumulate (map )))

17. sum . sum , , , . .
(define (sum term a next b) (define (iter a result) (if < ? ?> (i t e r < ??> < ??> ))) ( ite r < ??> ))

lambda
, , , p i-next, pi - s um . «, , 4» . , , lambda :
(lambda () (+ 4) )

, pi-sum :
(define (pi-sum a b)

(sum (lambda () (/ 1.0 (* (+ 2) ) ) ) (lambda () (+ 4 ) ) ) , lambda :
(lambda )

< formals > , . lambda , . , (de f i n e (pl u s 4 ) (+ 4 ) ) (de f i n e p l us 4 (la m bda (x ) (+ 4 )) ).
49


, , lambda .
(lambd a () (+ )) ((lambda ( z) (+ (square z) ) ) 1 2 3) - > - > 12

lambda : · (variable1 ... variablen) - . ; · variable - . ; · (variable1 . . . variablen-1 . variablen) - -1 . -1 , .
((lambda ) 3 4 5 6) ((lambda ( . z) z) 3 4 5 6) -> (3 4 5 6) -> (5 6)


lambda .

f(x, y)=x(l+ ) 2 + (1 - ) + (1 + ) (1 -) = 1 + b = 1- f(x,y)=-xa 2 + yb + ab
, f , , b. f-helper :
(define (f ) (define (f-helper a b) (+ (* (square a)) (* b) (* a b) } ) (f-helper (+ 1 {* x )}(- 1 ) )


lambda . f :
(d ef i n e ( f x ((lam b d a (* () ( b ) ( + (* x (s q u a r e a ) ) b ) ( * b )) ) ( + 1 (* )) 1 )))

, let, . let f :
(d ef in e (f x ) (let ( ( a ( + 1 (* ) ) ) (b (- 1 ))) ( + ( * (sq u a re a) ) ( * b) (* b) ) ) )

let :
(let )


( ( ) ( ) ... ( ) )

let , , - <2>, ... - < >. le t ( ). let , , let . , let ((l ambda (... ) ) ...< n >) . let , , let let. : · le t . , ( + (l e t (( 3)) (+ (* 1 0) )) let , let 5, , 5, ) 38 . 33. let
51


· le t . , , , , . , 2, (l et (( 3) ( (+ 2 ) ) ) (* )) 12, let 3, - 4 ( , 2). , lambda , . . :
(let ((n 1 )) (let (( f (( lam b da z) (+ z n ) ) ) (let ( ( n 2 ) ) (f 3 ) ) ) )

n 1, lambda , f (z + 1), n f . f (+ z 1), 4.


18. (define (f g) (g 2 ) ) . :
(f s q u a re) (f (lambda (z) (* z (+ z 1) ) ) ) -> -> 4 6

(f f). .
Scheme ( ), . :
(de fi ne ( i n c n n) ( ( l a m b d a x) ( + x n) ) ) .

incn , . , n , (incn 3) , , . ,
( (incn 3 ) 2 ) -> 5


incl-list (define (incl-list x) (map x (incn 1))

, , . compose. , .
(de fi ne (c ompo se f g) ((l a m bda x) (f (g x))))

, f g. , , . , . . « » , : · · · · ; , ; .

Scheme , . , , .


, , . . .

53


, . , . . . . , . , . . , , . Scheme . , , . , () , .
(set! variable expression)

se t! . ( define) . set! . (de fi (+ (s et ! (+ n e x 2} 1) 4) 1) -> -> -> -> 3 5

. :


(define (factorial n) (let ((product 1) (counter 1) (define (iter) (if (> counter n) product (begin (set! product (* counter product)) (set! counter (+ counter 1)) (iter)))) (iter)))

.


, .
(set-car! )

. , . set-car! .
(set-cdr! )

. , . set-cdr! .


, , if , sequence begin. (sequence expressionl expression2 . . . ) (begin expressionl expression2 ...) ( ) . .

(begin (set! 5) (+ 1) ) -> 6 (sequence (print "4 plus 1 equals ") (print ( + 4 1 ) ) ) ->
55


«4 plus 1 equals 5». , print .

56


3
( , , ), , ( ). : , , . «» : , . , , . , , . : « X , (), , X ». , , , . , , . , . , ( ) ( ). , . , . , , , . - , *- ,
57


, , , [8].
(, , ) . , , , . , . , - , , , . , ( ). , . , . , . , . , , . , , , , . , , , , NP- . , , , , , , ..


( ) ,
58


( , , , ). : 1. - (, 0 1). 2. - (, 0 1), . 3 - , , , . - , . 4. - - ; ; -; . 5. - ; , . 6. - , . 7. - , . 8. - « » . , , . , , , . . , , , , . - . ( ). - , (, , G), .
59


. , , , . , . , , . , , . , , , . , «», , . () . . , . , . , , . , , . (0 1, , ). , . « » - . ( ) . , . - «». , . - . , . , . , , , , ,
60


. , , . , . « » . , , . , « » «», . « », . . , . . . . , . . , , . , . , ( . . ). , , . . - , : · ; · ; · ; · . 61


, -. - «» . «» .
. . , () . , , , . , , . , , . () . , , .

. 11. , ( , , ). . , , .
62


(, ) ( ). , (. 11 ). , . ( ) . - . , . . . , , ( , , - , , ..). , , .. . , , . , , . G(V, E). , , (V) (E), . --> V * V ( - ) : , , . , . . , .
63


, . . , . , .


[5]. , , . . . , , . . , . , . , - . , . , . , « » . : . , . , , . (, ) . , . , , . , ( ).
64


, , (backtracking). , . . . , , , . , . nodes . paths . init-le ng th , , slow-path-length distbetw een-po ints. find-co nnected-no des , . depth , .
(d e f in e (d ef in e ( y-co ord x) (x -co o r d x ) (t ru n c a t e ( c a d r x ) )) (tru n cate (car x )))

( d ef i n e nod es ' ( (nl (n2 (n3 (n4 (n5 ( (n7 (n8 (n9 (n l 0 (nil

( 60 402 ) ) ( 50 3 1 0) ) (110 60) ) ( 220 375) ) ( 1 92 220 ) ) (260 4 4 ) ) ( 305 300 ) ) (347 404)) ( 3 5 1 262 )) (4 0 0 11 0)) ( 4 1 5 404) ) ) )

(def ine paths ' ( ( n l n2) ( n 2 n3) ( n3 n 5 ) ( n n 6 ) ( n 6 nl 0) ( n9 nl 0) ( n 7 n9) ( n l n 4 ) ( n 4 n 2 ) ( n 5 n8) (n 8 n 4 ) (n 7 n i l )))
(define (init-l engths pat hlist) (let ((new-path -list '()) (pathlength 0) (path-with-leng th '())) (do ((path pathlist (cdr path))) 65


((null? path)) (set! pathlength (slow-path-length (car path))) (set! path-with-length (append (car path) (list pathlength))) (set! new-path-list (cons path-with-length new-path-list))) new-path-list)) ; "As the crow flies" distance between ; the starting and ending nodes on a path: (define (slow-path-length path) (let ((nodel (car path)) (node2 (cadr path))) (let ((nl (assoc nodel nodes)) (n2 (assoc node2 nodes))) (dist-betweenpoints (cadr nl) (cadr n2))))) ; Calculate the Cartesian distance between points: (define (dist-between-points pointl point2) (let ((x-dif (- (X-coord point2) (X-coord pointl))) (y-dif (- (Y-coord point2) (Y-coord pointl)))) (sqrt (+ (* x-dif x-dif) (* y-dif y-dif))))) ; Change the global path list to include distance between ; adjacent nodes: (set! paths (init-lengths paths)) ; (pp paths) (define (find-connected-nodes a-node) (let ((ret-list '())) (do ((1 paths (cdr 1))) ((null? 1)) (let ((path (car 1))) ; (nodel node2 distance)=path (if (equal? a-node (car path)) (set! ret-list (cons (cadr path) ret-list))) (if (equal? a-node (cadr path)) (set! ret-list (cons (car path) ret-list))))) ret-list)) ; (find-connected-nodes 'n2) (define (depth path goal) (if (equal? (car (last-pair path)) goal) path ; done with search (let ((new-nodes (find-connectednodes (car (last-pair path)))) (keepsearching #t) (ret-val '())) (do ((nn newnodes (cdr nn)))

66


( (or
(null? nn) (equal? keep-searching #f))) (if (not (member (car nn) path))

(let ((temp (depth (append path (list (car nn))) goal)))
(if (not (null? temp)) (begin

( se t! r et- v al te m p) (set! keep-searching #f) ) ) ) ) ) ret-val)))

testl test2 depth. testl , test2 .
; T e st c o d e w i t h gr ap hi c s su p port :

(load "Graph .ss") ( d e f i n e ( t e s t l) (open-gr) (pen-width 1) (do ((p paths (cdr p))) ((null? p ) )

(display "(car p)=") (display (car p)) (newline) (let ((from (cadr (assoc (caar p) nodes))) (to (cadr (assoc (cadar p) nodes)))) (plot-line (x-coord from) (y-coord from) (x-coord to) (y-coord to) "black"))) (do ((n nodes (cdr n))) ((null? n)) (let ((n-val (cadar n))) (plot-string (+ 2 (x-coord n-val)) (y-coord n-val) (symbol->string (caar n)))))) (define (test2) (define (draw-path pi) (pen-width 3) (let ((nodel (cadr (assoc (car (set! pi {cdr pi)) (do ((p pi ((null? p)) (plot-line (x-coord nodel) (y-coord nodel) (x-coord (cadr (y-coord (cadr

pi) nodes)))) (cdr p)))

(assoc (car p) nodes))) (assoc (car p) nodes))) 67


"red") (set! nodel (cadr (assoc (car p) nodes)))))) (draw-path (depth ' (n1) 'nil)))

(testl) (test2)

depth, Scheme trace. depth . , . , . . , . , , «» . . , , , depth breadth. , .
(define (breadth start-node goal-node) ( l e t ((visited-list (list st art-node)) ( s ea rch- li st ( list (list start-node start-node 0 . 0 ) ) ) ) (define (next s-list) (let ((new-s-list ' ())) (do ((1 s-list (cdr 1))) . ((null? 1)) (let ((path (car 1))) (let ((last-node (car
(last-pair (except-last-pair path))))) (let ((connected-nodes (find-connected-nodes last-node))) (do ((n connected-nodes (cdr n))) ((null? n)) (if (not (member (car n) visited-list)) (begin (set! new-s-list (cons (append 68


(except-last-pair path) (list (car n)) (list (+ (c ar (last-pair path)) ; old distance (slow-path-length (list (car (last-pair (except-last-pair path))) (car n)) ) ))) new-s-list)) (set! visitedlist (cons (earn) visited-list))))))))) new-s-list)) (define (f ound-go al-node? ) (let ((good-path '())) (do ((1 search-list (cdr 1))) ((null ? 1 ) (not (null ? good- path))) ( if (member goal-node (car 1)) (begin (set! good-path (car 1)) (display "Found a good path:") (display good-path) (newline)))) good-path)) (l et ((a -good -path ·()) ) (do ((iter 0 (+ iter 1) ) ) ((or
(equal? iter (length nodes)) (not (null? a-good-path) ) ) ) (set! se ar c h -li s t (next search-l i st )) (newline) (display "search level=") (display iter) (newline) (displ ay "current vi sited list:" ) (n ewlin e) (displ ay visit ed-list ) (newline) (display "current search list:") (newline) (display search-list) (newline) (set! a-good-path (found-goal-node?))) (cdr a-goodpath))))

breadth, , depth - . breadth, , .
69


, , , test2 .
» (breadth 'n1 'nil) search level=0 current visited list: (n4 n2 n1) current search list: ((n1 n1 n4 162.2621335986927) (n1 n1 n2 92.5418824100742)) search level=1 current visited list: (n3 n8 n4 n2 n1) current search list: ((n1 n1 n2 n3 349.64108505372303) (n1 n1 n4 n8 292.53108615454926)) search level=2 current visited list: (n6 n5 n3 n8 n4 n2 n1)

current search list:
((n1 n1 n2 n3 n6 500.49200483878764) (n1 n1 n2 n3 n5 529.4298499974759)) search level=3 current visited list: (n10 n6 n5 n3 n8 n4 n2 n1) current search list: ((n1 n1 n2 n3 n6 n10 655.2692641503545)) search level=4 current visited list: (n9 nl0 n6 n5 n3 n8 n4 n2 nl) current search list: ((n1 n1 n2 n3 n6 nl0 n9 814.9721132169882)) search level=5 current visited list: (n7 n9 nl0 n6 n5 n3 n8 n4 n2 n1) current search list: ((n1 n1 n2 n3 n6 nl0 n9 n7 874.6378487776934)) search level=6 current visited list: (n11 n7 n9 nl0 n6 n5 n3 n8 n4 n2 nl) current search list: ((n1 n1 n2 n3 n6 nl0 n9 n7 n11 1026.0181645390235)) Found a good path:(nl nl n2 n3 n6 nl0 n9 n7 n11 1026.0181645390235)


4


: ( ) . . , () . , , . , ( ) , ( , ). - , , . «» , () . , . . - () . . 0 1 . . . . . , .
71


«» . (.. «» ). ( , ). , . , , .


1. . . 1 - : :f(x) = + |sin (32 )|,

[0, pi).

2- : .

2. . , . 1- : , . 2- : ( ). 3. . N. n (, > 1), N = *n? 1 - : , n, N . 2- : , , N. ( ). 4. . , . , a -x + 1 ? 1- : , .

72


2- : , ( ). 5. . U , s(u) Z+ U, , B 1 , ..., B k - . U U1, U2,... , Uk, , Bj? 1- : (Bi - Bj i,j) .

2- : .

6. .

U , s(u) Z+ v(u) Z+ U , . N U' U, ¸ ,, ¸ s(u) < ¸ ,, v(u)>Kl 1- : . 2- : N .

7. . , ;, ..., ,,. ,, ..,, ,, a,j, ,2, ..., aik (0 <= < (2 < ... < ik < ), + ... - & = . 1- : . 2- : N . 8. k . G = (V, ). G k ? , / -> { 1 , 2 , . . . , k }, , f (u ) ?f (v ), {, v} ? 1 - : k = 2. 2- : k > 4. 9. . , 1 ,..., n. , . 1- : = 2. 2- : > 2.


10. .

G = (V, E) , < |V|. V' V, |V| v V \ V' V'? 1- : . 2- : N .
11. ().

G = (V, ). G ()? 1- : ( ). 2- : ( ). G = (V, ) s, t V, 1() Z+ B K. G s t, ? 1- : , . 2- : G s t, . G = (V, ), l(e) Z+ , ' Z* . G , E' ? 1- : , E'. 2- : , ' .
13. .

12. .


- , . , . . :
74


Graph ::= Start GraphNodes GraphEdges Finish Start : : = [ORIENTED] [COLORED] [WEIGHTED] [WITH CONDITIONS]
#GRAPH DESCRIPTION OptName OptName ::= Name | GraphNodes ::= iNODES StartNode [Node}* StartNode ::= #START NODE Name [COLOR ColorName] Node ::= Name [COLOR ColorName] GraphEdges ::= #EDGES {Edge}*

Edge :=
EdgeName ':' Name Name [WEIGHT NaturalNumber] [CONDITION Input] [COLOR ColorName] EdgeName := OptName Input ::= Name Finish ::= #END GRAPH DESCRIPTION OptName, Name - NaturalNumber - ColorName - 16-

:
ORIENTED COLORED WITH CONDITIONS #GRAPH DESCRIPTION ExampleGraph #NODES
#START NODE A COLOR RED

7 5


COLOR WHITE COLOR MAGENTA D E QQ COLOR BLACK #EDGES El : CONDITION si

E2 : D E CONDITION s2 : D QQ CONDITION si
#END GRAPH DESCRIPTION

. : E 1 2. : . , (WHITE). . , - , - . , s1. ( ). , . , , . . , ( ) . , . : · · · · ·
76

; ; , , ; ;


.. . , , , , . , . , , .


1. .

: . , ( )? 1- , .
. 2- : . : , , , . 2. . : . . . , , ( ). 1- : ,

, . 2- , . , , , , .
3. «» . N : i- j- , 1<=i, j <= N,

77

.


. ? 1- : . 2- : « » . : , , . 4. «» . N . ( i j-, 1 <= i, j <= N, ). , ? 1 - : , , . 2- : « » , . : , , . 5. . . ( , , .) 1- : . 2- : , , . : , , . 6. . , . - . ( ) , . , : ( ), , , , - .
78


, . 1- : - , , . 2- : . : , . 7. . , . , , , - VI 8, V2 . . ( : VI ), . 1- : . 2- : , . : , , . 8. . , - . , , . 1- : , . 2- : , . : , , . 9. . , . - . ( ) , . , : ( ), , , ,
79


-. , . . 1 - : . . 2- : . : , .

80



1. Haasan Gomaa. The Impact of prototyping on software system engineering in lEEEComputer Society press tutorial 1990, 543-552. 2. Barry W Boehm. A Spiral Model of Software Development and Enhancement in Software Engineering Project Management, 1987, 120-142. 3. Ala n M. Da vis , Ed w a rd H. Bers o f f , Ed w a rd R . C o m e r A S t rate gy f o r Comparising Alternative Software Development Life Cycle Models in IEEE Transactions on Software Eng. Vol. SE-14, 10, Oct.1988,1453-1461. 4. Harold Abelson, Gerald J. Sussman, Julie Sussman. Structure and Interpretation of Computer Programs. MIT Press. 1996. 5. Mark Watson. Programming in Scheme. Springer-Verlag. 1996. 6. . , . . , ., , 1982. 7. ., ., ., , ., , 1979.

8. ., ., ., : , ., , 1980. 9. ., , ., , 1988. 10. ., , ., , 1981.



............................................................................................................ 3 ............................. 5 ................................................................... 5 ................................................................................. 6 ...................................................................................... 6 ....................................................................... 7 , ............................................... 8 ................................................................... 9 ....................................................... 11 , ......................... 12

............................................... 15 ...................................................... 15

.................................................................................... Scheme ..................................................................... Scheme ............................................ ...................................................................................................... ................................................................................... .................................................. ......................................... .............................................................................................

............................................................... 21 ....................................................................22 ........................................23

16 18 18 18 18 19 19 19

.............................................................................. 24 ................................ 25 ............................................. 26 ..................................................... 27 . .............30 ....................................33 , ..............................34 ............................................................................37 . .....................................................37 ....................................................................................... ............................... .................................................................... .................................................................... .................................................................... lambda ................................................................................. ........................................................ ............................................. .............................................................................................
82

.............................................................. 40
42 43 44 45 45 49 50 52 53


....................................................................... 54 ............................................................. 55 ......................................................... 55 ..........................................................57 .......................................................................... 58 ..........................................................................................................63 ............................................................................ 64 .................................................. 71 ............................................................................. 71 .............................................................................................. 72 ...................................................................................... 74 .............................................................................................. 77 ....................................................................................................... 81

83