Symbolické programovanie a LISP, zima 2000/2001

(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

3.prednáška

Abstrakcia dát

znamená oddeliť

Napríklad funkcia linear-combination fungujúca pre ľubovoľné (číselné) objekty nepozná a nepoužíva vnútorné informácie o reprezentácii týchto objektov.

racionálne čísla

n1/d2 + n2/d2 = (n1 d2 + d1 n2)/(d1 d2)
n1/d2 - n2/d2 = (n1 d2 - d1 n2)/(d1 d2)
n1/d1 * n2/d2 = (n1 n2)/(d1 d2)
n1/d1 / n2/d2 = (n1 d2)/(d1 n2)
n1/d1 = n2/d2 <=> n1 d2 = d1 n2

Funkcie nemajú žiadne predpoklady o dátach (zlomkoch), používajú "interface" pozostávajúci z konštruktorov (make-rat) a selektorov (numer, denom).

páry - cons, car, cdr

[] (define p (cons 1 2)) p
[] (car p) 1
[] (cdr p) 2
zlomky ako páry
[] (define one-half (make-rat 1 2)) one-half
[] (print-rat one-half) 1/2
[] (define one-third (make-rat 1 3)) one-third
[] (print-rat (rat+ one-half one-third)) 5/6
[] (print-rat (rat* one-half one-third)) 1/6
[] (print-rat (rat+ one-third one-third)) 6/9

Úrovne abstrakcie

Ak je nutné modifikovať program (napríklad aby vytváral zlomky v základnom tvare), stačí opraviť "interface" = vymeniť zásuvku - tzv. zásuvková metóda. Vyššie úrovne zostávajú nezmenené.

program s racionálnymi číslami
rat
rat+, rat-, rat*, rat/, rat=?
aritmetika nad racionálnymi číslami
make-rat, numer, denom
racionálne čísla ako páry
cons, car, cdr
ľubovoľná implementácia párov

zlomky v základnom tvare

Implementácia každej "zásuvky" môže byť rôzna (závisí od špecifikácie programu). Musí ale spĺňať podmienky pre ňu dané. Napríklad:

x = (make-rat n d) ---> (numer x)/(denom x) = n/d
z = (cons x y) ---> (car z) = x; (cdr z) = y

(cons 1 2)

[] (define z1 (cons (cons 1 2) 3)) z1
[] (define z2 (cons 1 (cons 2 3))) z2
[] (cdr z1) 3
[] (car (car z1)) 1
[] (cdr (car z1)) 2
[] z1 ((1 . 2) . 3)

vlastné zoznamy

obsahujú zakončenie - "nil" - ()

(list <o1> <o2> ... <on>) = (cons <o1> (cons <o2> ... (cons <on> ()) ... ))

[] (define 1az4 (list 1 2 3 4)) 1az4
[] 1az4 (1 2 3 4)
[] (car 1az4) 1
[] (cdr 1az4) (2 3 4)
[] (cons 10 1az4) (10 1 2 3 4)
[] (cons 1 (cons 2 (cons 3 4))) (1 2 3 . 4)
funkcie nth a length
[] (null? (list 1 2)) ()
[] (null? (cdr (list 1 2))) ()
[] (null? (cddr (list 1 2))) #T

stromy

(cons (list 1 2) (list 1 2)) ((1 2) 1 2)

(list (list 1 2) (list 1 2)) ((1 2) (1 2))

funkcia countatoms

atom? je predikát, ktorý zistí, či jeho argument je zložený S-výraz (zoznam, dvojica) alebo jednoduchý (číslo, symbol)

quote '

[] (define a 1) a
[] (define b 2) b
[] (list a b) (1 2)
[] (list 'a 'b) (a b)
[] (list a 'b) (1 b)
[] '(a b) (a b)

'<x> = (quote <x>)

quote zastaví vyhodnocovanie argumentu

eval

(eval <S-exp>)
eval vynúti vyhodnotenie <S-exp>

Kedže prvýkrát sa vstupný S-výraz vyhodnotí ako argument funkcie (pozri vyhodnocovanie S-výrazov), výsledkom je S-výraz vyhodnotený dvakrát - druhýkrát funkciou eval.

[] + #<proc +>
[] '+ +
[] ''+ (quote +)
[] (eval +) #<proc +>
[] (eval '+) #<proc +>
[] (eval ''+) +
[] (eval '(+ 2 3)) 5

porovnávanie - eq?, equal?

(eq? <o1> <o2>)
(equal? <o1> <o2>)

[] (eq? 1 1) ???
[] (eq? 'ahoj 'ahoj) #T
[] (eq? (cons 1 2) (cons 1 2) ()
[] (define x (cons 1 2)) x
[] (eq? x x) #T
[] (equal? 1 1) #T
[] (equal? 'fero 'fero) #T
[] (equal? (cons 1 2) (cons 1 2)) #T
[] (eq? x 'ahoj) ()
[] (equal? 'a 'ahoj) ()

 

Last Updated on 19-Oct-2000
By Petrovic Pavol
E-mail: ppetrovi@dent.ii.fmph.uniba.sk