Intellektual tizimlar

Funksiya	Argumentы
Rezultat
Cons	Atom X	( Atom . X )
Car	( Atom . X )	Atom
Cdr	( Atom . X )	X

Pri rabote s sistemoy sootvetstvuyuщiye vыrajeniya pokazanы nije:

Funksiya	Argumentы	Vid dlya sistemы
Cons	Atom X	(CONS 'ATOM ' X )
Car	( Atom . X )	(CAR '(ATOM . X )
Cdr	( Atom . X )	(CDR '(ATOM . X )

Tipichnaya forma zapisi simvolnыx vыrajeniy nazыvayetsya spisochnoy zapisyu (list-notation). Elementы spiska mogut bыt lyuboy prirodы.
Spisok – eto perechen proizvolnogo chisla elementov, razdelennыx probelami, zaklyuchennыy v kruglыye skobki.
Po soglasheniyu atom Nil vыpolnyayet rol pustogo spiska.
Binarnыy uzel, soderjaщiy paru atomov ATOM i Nil, rassmatrivayetsya kak odnoelementnыy spisok (ATOM ) :

ili dlya naglyadnosti:

Yesli vmesto atoma "ATOM" podstavlyat proizvolnыye atomы, a vmesto "Nil" - proizvolnыye spiski, zatem vmesto atomov - postroyennыye spiski i tak daleye, to mы poluchim mnojestvo vsex vozmojnыx spiskov. Mojno utochnit, chto spisok - eto zaklyuchennaya v skobki posledovatelnost iz razdelennыx probelami atomov ili spiskov.

(C )

(B C )

(C (A B))

Lyuboy spisok mojet bыt postroyen iz pustogo spiska i atomov s pomoщyu CONS i lyubaya yego chast mojet bыt vыdelena s pomoщyu podxodyaщyey kompozisii CAR-CDR.
CONS - Funksiya, kotoraya stroit spiski iz binarnыx uzlov, zapolnyaya ix parami obyektov, yavlyayuщixsya znacheniyami parы yeye argumentov. Pervыy argument proizvolnogo vida razmeщayetsya v levoy chasti binarnogo uzla, a vtoroy, yavlyayuщiysya spiskom, - v pravoy.
CAR – Funksiya, obespechivayuщaya dostup k pervomu elementu spiska - yego "golove".
CDR – Funksiya, ukorachivayuщaya spisok na odin element. Obespechivayet dostup k "xvostu" spiska, t.ye. k ostatku spiska posle udaleniya yego golovы.
ATOM - Funksiya, razlichayuщaya sostavnыye i atomarnыye obyektы. Na atomax yeye znacheniye "istina", a na boleye slojnыx strukturax dannыx – "loj".
EQ – Funksiya, kotoraya proveryayet atomarnыye obyektы na ravenstvo.
Razlichiye istinnostnыx znacheniy v Lispe prinyato otojdestvlyat s raznisey mejdu pustыm spiskom i ostalnыmi obyektami, kotorыm programmist mojet pridat v programme nekotorыy drugoy smыsl. Takim obrazom, znacheniye "loj" – eto vsegda Nil.
Yesli trebuyetsya yavno izobrazit znacheniye "istina", to ispolzuyetsya standartnaya konstanta – atom T (true), no rol znacheniya "istina" mojet vыpolnit lyuboy, otlichnыy ot pustogo spiska, obyekt.

1.2.3.3. Tochechnaya notasiya. Pri realizasii Lispa v kachestve yedinoy universalnoy bazovoy strukturы dlya konstruirovaniya simvolnыx vыrajeniy ispolzovalas tak nazыvayemaya "tochechnaya notasiya" (dot-notation), soglasno kotoroy levaya i pravaya chasti binarnogo uzla ravnopravnы i mogut xranit dannыye lyuboy prirodы.

Binarnыy uzel, soderjaщiy paru atomov ATOM1 i ATOM2,

mojno predstavit kak zapis vida:
( ATOM1 . ATOM2 )
Yesli vmesto atomov "ATOM1", "ATOM2" rekursivno podstavlyat proizvolnыye atomы, zatem postroyennыye iz nix parы i tak daleye, to mы poluchim mnojestvo vsex vozmojnыx sostavnыx simvolnыx vыrajeniy – S-vыrajeniy.
S-vыrajeniye - eto ili atom ili zaklyuchennaya v skobki para iz dvux S-vыrajeniy, razdelennыx tochkoy.
Vse slojnыye dannыye sozdayutsya iz odinakovo ustroyennыx blokov - binarnыx uzlov, soderjaщix parы obyektov proizvolnogo vida. Kajdыy binarnыy uzel sootvetstvuyet minimalnomu bloku pamyati.
Spiski – eto podmnojestvo S-vыrajeniy, dvijeniye vpravo po kotorыm zavershayetsya atomom Nil.
(A . B)

(C . (A . B))

Lyuboye S-vыrajeniye mojet bыt postroyeno iz atomov s pomoщyu CONS i lyubaya yego chast mojet bыt vыdelena s pomoщyu CAR-CDR.
Tochechnaya notasiya mojet tochno predstavlyat logiku xraneniya lyubыx struktur dannыx v pamyati i dostupa k komponentam struktur dannыx. V vide spiskov mojno predstavit lish te S-vыrajeniya, v kotorыx pri dvijenii vpravo v konse konsov obnarujivayetsya atom Nil, simvoliziruyuщiy zaversheniye spiska.
Atom Nil, rassmatrivayemыy kak predstavleniye pustogo spiska (), vыpolnyayet rol ogranichitelya v spiskax. Odnoelementnыy spisok (A) identichen S-vыrajeniyu (A . Nil). Spisok (A1 A2 … Ak) mojet bыt predstavlen kak S-vыrajeniye vida:
(A1 . (A2 . ( … . (Ak . Nil) … ))).
V pamyati eto fakticheski odna i ta je struktura dannыx.
1.2.4. Zapis Lisp-programm.
Teper rassmotrim pravila zapisi programm na Lispe. Takiye pravila razlichnы dlya obыchnыx i spesialnыx funksiy. Dlya Lispa xarakterno predpochteniye rekursivnыx funksiy. Funksii mogut imet nazvaniya ili bыt bezыmyannыmi, skonstruirovannыmi dlya razovogo ispolzovaniya.
Osnovnыye ponyatiya, voznikayuщiye pri napisanii programm – eto peremennыye, konstantы, vыrajeniya, vetvleniya, vыzovы funksiy i opredeleniya. Vse oni predstavimы s pomoщyu spiskov.
Samaya prostaya forma vыrajeniya - eto peremennaya. Imya peremennoy mojet bыt predstavleno kak atom. Peremennaya – eto atom, imeyuщiy znacheniye.
X
N
Variable1
Peremennaya2
LongSong
DolgayaPesnya
Nazvaniya funksiy, kak i imena peremennыx, izobrajayutsya s pomoщyu atomov, dlya naglyadnosti mojno predpochitat zaglavnыye bukvы.
CONS
CAR
CDR
ATOM
EQ
Vse boleye slojnыye formы v Lispe ponimayut kak primeneniye funksii k yeye argumentam (vыzov funksii). Argumentom funksii mojet bыt lyubaya forma. Spisok, pervыy element kotorogo – predstavleniye funksii, ostalnыye elementы - argumentы funksii, – eto osnovnaya konstruksiya v Lisp-programme.
Format:
(funksiya argument1 argument2 ... )
(CONS 1 2 )
Obыchno krome bazovыx sredstv v yazыk vklyuchayetsya i nabor naiboleye upotrebimыx bazovыx operasiy nad chislami i drugimi dannыmi. Yesli vvedenы chisla, to vvedenы i tradisionnыye arifmeticheskiye operasii, no forma ix primeneniya podchinena obщim pravilam:
(+ 1 2 3 4) ;; = 10
Kompozisii funksiy yestestvenno stroit s pomoщyu vlojennыx skobok.
Format:
(funksiya1 (funksiya2 argument21 argument22 ... ) argument2 ... )
(CAR (CONS 1 2 ) )
(CONS (CAR (CONS 1 2 ) ) (CDR (CONS 3 4 ) ))
Etix pravil dostatochno, chtobы boleye yasno vыpisat osnovnыye tojdestva Lispa, formalno xarakterizuyuщiye elementarnыye funksii CAR, CDR, CONS, ATOM, EQ nad S-vыrajeniyami:
(CAR (CONS x y)) = x
(CDR (CONS x y)) = y
(ATOM (CONS x y)) = Nil
(CONS (CAR x) (CDR x)) = x dlya neatomarnыx x.
(EQ x x) = T yesli x atom
(EQ x y) = Nil yesli x i y razlichimы
Lyubыye kompozisii zadannogo nabora funksiy nad konechnыm mnojestvom proizvolnыx obyektov mojno predstavit takim sposobom, no klass sootvetstvuyuщix im prosessov vesma ogranichen i malo interesen. Organizasiya boleye slojnogo klassa prosessov trebuyet boleye detalnogo predstavleniya v programmax sootvetstviya mejdu imenami i ix znacheniyami ili opredeleniyami, izobrajeniya vetvleniy i ob’yavleniya konstant.