Intellektual tizimlar

1.2.5. Opredeleniye yazыka programmirovaniya
Opredeleniye yazыka programmirovaniya obыchno nachinayut s sintaksicheskix formul, nazыvayemыx BNF (formulы Bekusa-Naura). Opredeleniye takix formul svoditsya k sleduyuщim polojeniyam:

• 
  Yazыk xarakterizuyetsya naborom opredelyayemыx ponyatiy.
  
• 
  Kajdomu ponyatiyu sootvetstvuyet nabor variantov sintaksicheskix formul.
  
• 
  Kajdыy variant – eto posledovatelnost elementov.
  
• 
  Element – eto ili terminalnыy simvol ili sintaksicheskoye ponyatiye – neterminalnыy simvol.
  

Sintaksis dannыx v Lispe svoditsya k pravilam predstavleniya atomov i S-vыrajeniy.
::=


::=

|
|
V Lispe atomы - eto melchayshiye chastisы. Ix razlojeniye po literam obыchno ne imeyet smыsla.
::=
| ( . ) ; para
| ( ... ) ; spisok
Po etomu pravilu S-vыrajeniya - eto ili atomы, ili uzlы iz parы S-vыrajeniy, ili spiski iz S-vыrajeniy.
Simvol ";" - nachalo kommentariya do konsa stroki.
T.o. "()" yest dopustimoye S-vыrajeniye. Ono v yazыke Lisp po soglasheniyu ekvivalentno atomu Nil.
Bazovaya sistema kodirovaniya dannыx - tochechnaya notasiya, xotya na urovne teksta zapis v vide spiskov udobneye. Lyuboy spisok mojno predstavit tochechnoy notasiyey:
() = Nil
(a . Nil) = (a)
- - -
(a1 . ( ... (aK . Nil) ... )) = (a1 ... aK)
Takaya yedinaya struktura dannыx okazalas vpolne dostatochnoy dlya predstavleniya skol ugodno slojnыx programm v vide dvoichnыx derevyev.
Sintaksis programm v Lispe vneshne ne otlichayetsya ot sintaksisa dannыx. Prosto vыdelyayem vыchislimыye vыrajeniya (formы), t.ye. dannыye, prisposoblennыye k vыchisleniyu. Vneshne eto vыglyadit kak ob’yavleniye obyektov, zaraneye izvestnыx v yazыke, i predstavleniye raznыx form, vыchisleniye kotorыx obladayet opredelennoy spesifikoy.
Vыpolneniye programmы na Lispe ustroyeno kak interpretasiya dannыx, predstavlyayuщix vыrajeniya, imeyuщiye znacheniye. Nije privedenы sintaksicheskiye pravila dlya obыchnыx konstruksiy, takix kak identifikatorы, peremennыye, konstantы, argumentы, formы i funksii.
::=
Identifikatorы - eto atomы, ispolzuyemыye pri imenovanii neodnokratno ispolzuyemыx obyektov programmы - funksiy i peremennыx. Predpolagayetsya, chto obyektы razmeщayutsya v pamyati tak, chto po identifikatoru ix mojno nayti.
::=
|

| (COND ( ) ( ) ... )

| ( ... >)


::= (QOUTE )
| '

::=

Peremennaya - eto identifikator, imeyuщiy mnogokratno ispolzuyemoye znacheniye, raneye vыchislennoye v podxodyaщyem kontekste. Podrazumevayetsya, chto odna i ta je peremennaya v raznыx kontekstax mojet imet raznыye znacheniya.
Forma - eto vыrajeniye, kotoroye mojet bыt vыchisleno. Formami yavlyayutsya peremennыye i spiski, nachinayuщiyesya s QUOTE, COND ili s predstavleniya nekotoroy funksii.
::=
Yesli forma predstavlyayet soboy konstantu, to net neobxodimosti v vыchisleniyax, nezavisimo ot vida konstantы. Konstantnыye znacheniya, mogut bыt lyuboy slojnosti, vklyuchaya vыchislimыye vыrajeniya, no v dannыy moment oni ne vыchislyayutsya. Konstantы izobrajayutsya s pomoщyu spesialnoy funksii QUOTE, blokiruyuщyey vыchisleniye. Predstavleniye konstant s pomoщyu QOUTE ustanavlivayet granisu, daleye kotoroy vыchisleniye ne idet. Ispolzovaniye apostrofa (') - prosto sokraщyennoye oboznacheniye dlya udobstva nabora teksta. Konstantnыye znacheniya argumentov xarakternы pri testirovanii i demonstrasii programm.
Yesli forma predstavlyayet soboy peremennuyu, to yeye znacheniyem doljno bыt S-vыrajeniye, svyazannoye s etoy peremennoy do momenta vыchisleniya formы. Sledovatelno gde-to xranitsya nekaya tablisa, po kotoroy, znaya imya peremennoy, mojno nayti yeye znacheniye.
Tretya pravilo glasit, chto mojno napisat funksiyu, zatem perechislit yeye argumentы i vse eto kak obщiy spisok zaklyuchit v skobki.
Argumentы predstavlyayutsya formami. Eto oznachayet, chto dopustimы kompozisii funksiy. Obыchno argumentы vыchislyayutsya v poryadke vxojdeniya v spisok argumentov.
Posledneye pravilo zadayet format uslovnogo vыrajeniya. Soglasno etomu formatu uslovnoye vыrajeniye stroitsya iz razmeщyennыx v dvuxelementnom spiske sintaksicheski razlichimыx pozisiy dlya usloviy i obыchnыx form. Dvuxelementnыye spiski iz opredeleniya uslovnogo vыrajeniya rassmatrivayutsya kak predstavleniye predikata i sootvetstvuyuщyego yemu S-vыrajeniya. Znacheniye uslovnogo vыrajeniya opredelyayetsya pereborom predikatov po poryadku, poka ne naydetsya forma, znacheniye kotoroy otlichno ot Nil, chto oznachayet logicheskoye znacheniye "istina". Strogo govorya, takaya forma doljna naytis nepremenno. Togda vыchislyayetsya S-vыrajeniye, razmeщyennoye vtorыm elementom etogo je dvuxelementnogo spiska. Ostalnыye predikatы i formы uslovnogo vыrajeniya ne vыchislyayut (logika Mak-Karti), ix formalnaya korrektnost ili opredelennost ne vliyayut na suщyestvovaniye rezultata.
Raznisa mejdu predikatami i obыchnыmi formami zaklyuchayetsya lish v traktovke ix rezultatov. Lyubaya forma mojet vыpolnit rol predikata.
::=
| (LAMBDA )
| (DEFUN )


::= (
... )


=
Nazvaniye funksii - eto identifikator, opredeleniye kotorogo xranitsya v pamyati, no ono mojet ne podvergatsya vliyaniyu konteksta vыchisleniy.
Takim obrazom, funksiya - eto ili nazvaniye, ili spisok, nachinayuщiysya s LAMBDA ili DEFUN.
Funksiya mojet bыt predstavlena prosto imenem. V takom sluchaye yeye smыsl doljen bыt zaraneye izvesten. Naprimer, vstroyennыye funksii CAR, CDR i t.d.
Funksiya mojet bыt vvedena s pomoщyu lyambda-konstruktora, ustanavlivayuщyego sootvetstviye mejdu argumentami funksii i svyazannыmi peremennыmi, vxodyaщimi v telo yeye opredeleniya (v opredelyayuщyey yeye forme). Forma iz opredeleniya funksii mojet vklyuchat peremennыye, ne vklyuchennыye v lyambda-spisok, - tak nazыvayemыye svobodnыye peremennыye. Ix znacheniya doljnы ustanavlivatsya na boleye vneshnem urovne. Yesli funksiya rekursivna, to sleduyet ob’yavit yeye imya s pomoщyu spesialnoy funksii DEFUN.
Obщiy mexanizm vыchisleniya form budet pozdneye opredelen kak universalnaya funksiya EVAL, a seychas zaprogrammiruyem ryad vspomogatelnыx funksiy, poleznыx pri obrabotke S-vыrajeniy. Nekotorыye iz nix prigodyatsya pri opredelenii interpretatora.
AMONG – proverka vxodit li zadannыy atom v dannoye S-vыrajeniye.
(DEFUN among (x y) (COND
((ATOM y) (EQ x y))
((among x (CAR y)) (QUOTE T))
((QUOTE T) (among x (CDR y) ))
)
)

(among 'A '( B . A ) )

EQUAL - predikat, proveryayuщiy ravenstvo dvux S-vыrajeniy. Yego znacheniye "istina" dlya identichnыx argumentov i "loj" dlya razlichnыx. (Elementarnыy predikat EQ strogo opredelen tolko dlya atomov.) Opredeleniye EQUAL illyustriruyet uslovnoye vыrajeniye vnutri uslovnogo vыrajeniya (dvuxurovnevoye uslovnoye vыrajeniye i dvunapravlennaya rekursiya)
(DEFUN equal (x y) (COND
((ATOM x) (COND
((ATOM y) (EQ x y))
((QUOTE T) (QUOTE NIL))
)
)
((equal (CAR x)(CAR y)) (equal (CDR x)(CDR y)))
((QUOTE T) (QUOTE NIL))
)
)

(equal '( A B ) '( A . B))

(equal '( A B ) '( A . (B . Nil)) )
SUBST - funksiya trex argumentov x, y, z, stroyaщaya rezultat zamenы S-vыrajeniyem x vsex vxojdeniy atoma y v S-vыrajeniye z.
(DEFUN subst (x y z) (COND
((equal y z) x)
((ATOM z) z)
((QUOTE T)(CONS
(subst x y (CAR z))
(subst x y (CDR z))
)
)
)
)

(subst '(x . A) 'B '((A . B) . C)) ;= ((A . (x . A)) . C)

(subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) ;= ((A . x)(E . x)(F . x))
NULL - predikat, otlichayuщiy pustoy spisok ot vsex ostalnыx S-vыrajeniy. Ispolzuyetsya, chtobы vыyasnyat, kogda spisok ischerpan. Prinimayet znacheniye "istina" togda i tolko togda, kogda yego argument - Nil.
(DEFUN null (x) (COND
((EQ x (QUOTE Nil)) (QUOTE T))
((QUOTE T) (QUOTE Nil))
)
)
( null '(()) )
Sleduyuщiye funksii ispolzuyutsya, kogda rassmatrivayutsya lish spiski.
APPEND - funksiya dvux argumentov x i y, sseplyayuщaya dva spiska v odin.
(DEFUN append (x y) (COND
((null x) y)
((QUOTE T) (CONS
(CAR x)
(append (CDR x) y)
)
)
)
)
(append '(A B) '(C D E)) ;= (A B C D E)
MEMBER - funksiya dvux argumentov x i y, vыyasnyayuщaya vstrechayetsya li S-vыrajeniye x sredi elementov spiska y.
(DEFUN member (x y) (COND
((null y) (QUOTE Nil))
((equal x (CAR y)) (QUOTE T))
((QUOTE T) (member x (CDR y))
)
)
(member ' A '( B (A) C)
PAIRLIS - funksiya trex argumentov x, y, al, stroit spisok par sootvetstvuyuщix elementov iz spiskov x i y - svyazыvayet i prisoyedinyayet ix k spisku al. Poluchennыy spisok par, poxojiy na tablisu s dvumya stolbsami, nazыvayetsya assosiativnыm spiskom ili assosiativnoy tablisey. Takoy spisok mojet ispolzovatsya dlya svyazыvaniya imen peremennыx i funksiy pri organizasii vыchisleniy interpretatorom.
(DEFUN pairlis (x y al) (COND
((null x) al)
((QUOTE T) (CONS (CONS (CAR x)
(CAR Y) )
(pairlis (CDR x)
(CDR y)
al)
) ) )
)

(pairlis '(A B C) '(u t v) '((D . y)(E . y))) ;= ((A . u)(B . t)(C . v)(D . y)(E . y))

ASSOC - funksiya dvux argumentov x i al. Yesli al - assosiativnыy spisok, podobnыy tomu, chto formiruyet funksiya pairlis, to assoc vыbirayet iz nego pervuyu paru, nachinayuщuyusya s x. Takim obrazom, eto funksiya poiska opredeleniya ili znacheniya po tablise, realizovannoy v forme assosiativnogo spiska.
(DEFUN assoc (x al) (COND
((equal x (CAAR al)) (CAR al))
((QUOTE T) (assoc x (CDR al))
) )
)
(assoc 'B '((A . (m n)) (B . (CAR x)) (C . w) (B . (QUOTE T)))) ;= (B . (CAR x))
SUBLIS - funksiya dvux argumentov al i y, predpolagayetsya, chto pervыy iz argumentov AL ustroyen kak assosiativnыy spisok vida ((u1 . v1) ... (uK . vK)), gde u yest atomы, a vtoroy argument Y - lyuboye S-vыrajeniye. Deystviye sublis zaklyuchayetsya v obrabotke Y, takoy chto vxojdeniya peremennыx Ui, svyazannыye v assosiativnom spiske so znacheniyami Vi, zamenyayutsya na eti znacheniya. Drugimi slovami v S-vыrajenii Y vxojdeniya peremennыx U zamenyayutsya na sootvetstvuyuщiye im V iz spiska par AL. Vvodim vspomogatelnuyu funksiyu SUB2, obrabatыvayuщuyu atomarnыye S-vыrajeniya, a zatem - polnoye opredeleniye SUBLIS:
(DEFUN sub2 (al z) (COND
((null al) z)
((equal (CAAR al) z) (CDAR al))
((QUOTE T) (sub2 (CDR al) z))
) )

(DEFUN sublis (al y) (COND

((ATOM y) (sub2 al y))
((QUOTE T)(CONS
(sublis al (CAR y))
(sublis al (CDR y))
) )))

(sublis '((x . Shekspir)(y . (Romeo i Djulyetta))) '(x napisal tragediyu y))

;= (Shekspir napisal tragediyu (Romeo i Djulyetta))
INSERT – vstavka z pered vxojdeniyem klyucha x v spisok al.
(DEFUN insert (al x z) (COND
((null al) Nil)
((equal (CAR al) x) (CONS z al))
((QUOTE T) (CONS (CAR al) (insert (CDR al) x z)))
)
)

(insert '(a b c) 'b 's) ; = (a s b c)

ASSIGN – model prisvaivaniya peremennыm, xranyaщim znacheniya v assosiativnom spiske. Proisxodit zamena znacheniya, svyazannogo s dannoy peremennoy v pervoy naydennoy pare, na novoye zadannoye znacheniye. Yesli ne bыlo parы voobщye, to novuyu paru iz peremennoy i yeye znacheniya razmeщayem v kones a-spiska, chtobы ona mogla rabotat kak globalnaya.
(DEFUN assign (x v al) (COND
((Null al) (CONS (CONS x v) Nil ))
((equal x (CAAR al))(CONS (CONS x v) (CDR al)))
((QUOTE T) (CONS (CAR al) (assign x v (CDR al))))
)
)
(assign 'a 111 '((a . 1)(b . 2)(a . 3))) ;= ((a . 111)(b . 2)(a . 3))
(assign 'a 111 '((c . 1)(b . 2)(a . 3))) ;= ((c . 1)(b . 2)(a . 111))
(assign 'a 111 '((c . 1)(d . 3))) ;= ((c . 1)(d . 3) (a . 111))