(vychádza z prednášky
Funkcionálne programovanie, Ivan Kalaš)
Petrovič Pavol, Ústav Informatiky, č.d. 15
e-mail: ppetrovi@dent.ii.fmph.uniba.sk
www k prednáške: http://www.ii.fmph.uniba.sk/vyuka/lisp
2.prednáška
Procedurálna dekompozícia:
sqrt |
|||
sqrt-iter |
|||
good-enough? |
improve |
||
square |
abs |
average |
|
dekompozícia na zmysluplné znovapoužiteľné úlohy, tzv. čierne skrinky
lokálne mená
[] (define x 5) x [] (square 7) 49 [] x 5
premenné v good-enough?
voľné (<, abs, -, square)
viazané (guess, x)
hodnota funkcie závisí len na voľných premenných (nie na viazaných)
interné definície
test prvočísel
Malá Fermatova veta: Ak n je prvočíslo a a je prirodzené číslo menšie ako n, potom a je kongruentné s a^n mod n.
Ak n nie je prvočíslo, pravdepodobnosť, že a je kongruentné s a^n mod n, je malá. Opakovaním testu times-krát sa pravdepodobnosť chyby zníži (ale nebude nulová).
funkcie sum-integer, sum-cube a pi8-sum využívajú rovnaký vzor:
(define (<name> a b)funkcia sum a jej využitie
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))
lambda
konštruktor vytvárajúci funkciu bez mena
formálna definícia
(lambda (<formal-parameters>) <body>)
(define (plus4 x) (+ x 4)) = (define plus4 (lambda (x) (+ x 4))) (define (<name> <par1> <par2> ...)
<body>)= (define <name>
(lambda (<par1> <par2> ...)
<body>))
vrátenie výsledku funkcie bez mena
[] ((lambda (x) (+ x 4)) 2) 6
[] ((lambda () 2)) 2
let
príklad:
f(x, y) = x (1 + xy)^2 + y (1 - y) + (1 + xy) (1 - y) = ?
zjednodušenie
a = 1 + xy
b = 1 - y
f(x, y) = x a^2 + y b + a b = ?
formálna definícia
(let (<equations>) <body>))
(let ((<var1> <exp1>)
(<var2> <exp2>)
...................................
(<varn> <expn>))
<body>)((lambda (<var1> ...<varn>)
<body>)
<exp1> ... <expn>)
výhody let oproti define
[] (define x 5) x
[] (* (let ((x 3)) (+ x x)) x) 30
[] (define x 2) x
[] (let ((x 3) (y (+ x 2))) (* x y)) 12
[] (define (id x) x) id
[] (id 2) 2
[] (id +) #<proc +>
[] (id (lambda () 2)) #<proc>
[] (define (x) (lambda () 2)) x
[] x #<proc x>
[] (x) #<proc>
[] ((x)) 2
[] (define (n+ n)
(lambda (x) (+ x n)))n+
[] (define 1+ (n+ 1)) 1+
[] (1+ 2) 3
Churchove čísla
prirodzené čísla
párne prirodzené čísla
mocniny 2
ľubovoľná iterácia - Churchove čísla
Churchove čísla = objekty (funkcie), ktoré ako argument vyžadujú iteračnú funkciu
Aby sa nemuselo definovať nekonečno čísel, vytvoria sa pomocou indukcie.
Kvôli nasledujúcim matematickým operáciám je výhodné okrem iterujúcej funkcie pridať ako argument aj nulovú hodnotu.
[] (define one (next zero)) one
[] (define two (next one)) two
[] (define three (next two)) three
[] ((three 1+) 0) 3
[] (((plus three two) 1+) 0) 5
[] (((krat three two) 1+) 0) 6
Last Updated on 28-Sep-2000
By Petrovic Pavol
E-mail: ppetrovi@dent.ii.fmph.uniba.sk