\input style \chapter{4 semanticheskaya harakteristika yazykov programmirovaniya} v PREDYDUSHCHEJ GLAVE MY VYDVINULI TEZIS, CHTO ZNAEM SEMANTIKU KONSTRUKCII $S$ DOSTATOCHNO HOROSHO, ESLI ZNAEM EE "PREOBRAZOVATELX PREDIKATOV", T. E. PRAVILO, UKAZYVAYUSHCHEE NAM, KAK VYVESTI PO LYUBOMU POSTUSLOVIYU $R$ SOOTVETSTVUYUSHCHEE SLABEJSHEE PREDUSLOVIE (KOTOROE MY OBOZNACHILI CHEREZ $\wp(S, R))$, HARAKTERIZUYUSHCHEE TE NACHALXNYE SOSTOYANIYA, PRI KOTORYH ZAPUSK PRIVEDET K SOBYTIYU PRAVILXNOGO ZAVERSHENIYA, PRICHEM SISTEMA OSTANETSYA V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM POSTUSLOVIYU $R$. vOPROS V TOM, KAK VYVODITX $\wp(S, R)$ DLYA ZADANNYH $S$ I $R$. oSTAVIM POKA VOPROS OB ODINOCHNOJ KONKRETNOJ KONSTRUKCII $S$. pROGRAMMA, NAPISANNAYA NA HOROSHO OPREDELENNOM YAZYKE PROGRAMMIROVANIYA, MOZHET RASSMATRIVATXSYA KAK NEKAYA KONSTRUKCIYA, TAKAYA KONSTRUKCIYA, KOTORUYU MY ZNAEM DOSTATOCHNO HOROSHO, ESLI ZNAEM SOOTVETSTVUYUSHCHIJ PREOBRAZOVATELX PREDIKATOV ODNAKO YAZYK PROGRAMMIROVANIYA POLEZEN TOLXKO PRI TOM USLOVII, CHTO EGO MOZHNO PRIMENYATX DLYA ZAPISI MNOGIH RAZLICHNYH PROGRAMM, I DLYA VSEH |TIH PROGRAMM NAM ZHELATELXNO ZNATX SOOTVETSTVUYUSHCHIE IM PREOBRAZOVATELI PREDIKATOV. kAZHDAYA TAKAYA PROGRAMMA ZADAETSYA SVOIM TEKSTOM NA HOROSHO OPREDELENNOM YAZYKE PROGRAMMIROVANIYA, I PO|TOMU EE TEKST DOLZHEN SLUZHITX DLYA NAS OTPRAVNOJ TOCHKOJ. nO TEPERX PERED NAMI NEOZHIDANNO OTKRYVAYUTSYA DVA SOVERSHENNO RAZLICHNYH NAZNACHENIYA TAKOGO TEKSTA PROGRAMMY. s ODNOJ STORONY, TEKST PROGRAMMY PREDNAZNACHEN DLYA \emph{MASHINNOJ} INTERPRETACII, ESLI MY HOTIM, CHTOBY ONA MOGLA VYPOLNYATXSYA AVTOMATICHESKI, ESLI MY HOTIM, CHTOBY PO NEJ DLYA NAS BYL PROIZVEDEN KAKOJ-LIBO KONKRETNYJ RASCHET. s DRUGOJ STORONY, ZHELATELXNO, CHTOBY TEKST PROGRAMMY GOVORIL \emph{NAM} O TOM, KAK STROITX SOOTVETSTVUYUSHCHIJ PREOBRAZOVATELX PREDIKATOV, KAK PROIZVODITX PREOBRAZOVANIE PREDIKATOV, CHTOBY VYVODITX PREDUSLOVIE $\wp(S, R)$ DLYA LYUBOGO DANNOGO POSTUSLOVIYA $R$, KOTOROE NAS POCHEMU-LIBO ZAINTERESOVALO. eTO ZAMECHANIE POZVOLYAET PONYATX, CHTO PODRAZUMEVAETSYA POD "HOROSHO OPREDELENNYM YAZYKOM PROGRAMMIROVANIYA" S \emph{NASHEJ} TOCHKI ZRENIYA. kOGDA SEMANTIKA KONKRETNOJ KONSTRUKCII (ILI PROGRAMMY) ZADAETSYA EE PREOBRAZOVATELEM PREDIKATOV, MY RASSMATRIVAEM SEMANTICHESKUYU HARAKTERISTIKU YAZYKA PROGRAMMIROVANIYA KAK NABOR PRAVIL, KOTORYE POZVOLYAYUT LYUBOJ PROGRAMME, NAPISANNOJ PA |TOM YAZYKE, POSTAVITX V SOOTVETSTVIE PREOBRAZOVATELX PREDIKATOV. s TAKOJ TOCHKI ZRENIYA MY MOZHEM RASSMATRIVATX PROGRAMMU KAK "KOD" DLYA SOOTVETSTVUYUSHCHEGO PREOBRAZOVATELYA PREDIKATOV. pRI ZHELANII MOZHNO PODOJTI K PROBLEME PROEKTIROVANIYA YAZYKA PROGRAMMIROVANIYA S TAKOJ POZICII. mOZHNO RUKOVODSTVOVATXSYA (DOVOLXNO FORMALXNO) TEM, CHTO PRAVILA POSTROENIYA PREOBRAZOVATELEJ PREDIKATOV DOLZHNY BYTX TAKIMI, CHTOBY, PRIMENYAYA IH, NELXZYA BYLO POSTROITX NICHEGO DRUGOGO, KROME KAK PREOBRAZOVATELYA PREDIKATOV, OBLADAYUSHCHEGO SVOJSTVAMI 1--4 IZ PREDYDUSHCHEJ GLAVY. v SAMOM DELE, ESLI PRAVILA NE DAYUT TAKOJ GARANTII, TO |TO OZNACHAET, CHTO VY DEFORMIRUETE PREDIKATY TAKIM OBRAZOM, CHTO ONI UZHE NE MOGUT INTERPRETIROVATXSYA KAK POSTUSLOVIYA I SOOTVETSTVUYUSHCHIE SLABEJSHNE PREDUSLOVIYA. sRAZU NAPRASHIVAYUTSYA DVA PRIMERA VESXMA PROSTYH PREOBRAZOVATELEJ PREDIKATOV, KOTORYE OBLADAYUT TREBUEMYMI SVOJSTVAMI. nACHNEM S TOZHDESTVENNOGO PREOBRAZOVANIYA, T. E, S KONSTRUKCII $S$, TAKOJ, CHTO DLYA LYUBOGO POSTUSLOVIYA $R$ MY IMEEM $\wp(S, R)=R$. eTU KONSTRUKCIYU ZNAYUT I LYUBYAT VSE PROGRAMMISTY: ONA IZVESTNA IM POD NAZVANIEM "PUSTOJ onepaTOR", I V SVOIH PROGRAMMAH ONI CHASTO ISPOLXZUYUT EE, OSTAVLYAYA PROPUSK V TOM MESTE TEKSTA, GDE SINTAKSICHESKI TREBUETSYA KAKOJ-TO OPERATOR. eTO NE SLISHKOM POHVALXNYJ PRIEM (KOMPILYATOR DOLZHEN ZNATX, CHTO ON "VIDIT" |TOT OPERATOR, NA TOM OSNOVANII, CHTO ON NICHEGO NE VIDIT, I PO|TOMU MY DADIM |TOJ KONSTRUKCII NAIMENOVANIE, SKAZHEM, "\var{PROPUSTITX}". iTAK, SEMANTIKA OPERATORA "\var{PROPUSTITX}" OPREDELYAETSYA SLEDUYUSHCHIM OBRAZOM: $$ \wp(\var{PROPUSTITX}, R)=R\qquad\hbox{ DLYA LYUBOGO POSTUSLOVIYA $R$ } $$ (kAK I VSE, YA BUDU POLXZOVATXSYA TERMINOM "OPERATOR", POSKOLXKU ON PROCHNO VOSHEL V ZHARGON. kOGDA LYUDI SOOBRAZILI, CHTO "KOMANDA" MOGLA BY OKAZATXSYA BOLEE PODHODYASHCHIM TERMINOM, BYLO UZHE SLISHKOM POZDNO% \note{ pO TRADICII MY PEREVODIM ANGLIJSKIJ TERMIN "statement" (UTVERZHDENIE, PREDLOZHENIE) TERMINOM "OPERATOR", VVEDENNYM V PROGRAMMIROVANIE a. a. lYAPUNOVYM, I TAKIM OBRAZOM, RUSSKIJ CHITATELX OKAZYVAETSYA V BOLEE VYGODNOM POLOZHENII, CHEM ANGLIJSKIJ.---{\it pRIM. RED.} }.) {\sl zAMECHANue.} tEM, KTO SCHITAET RASTOCHITELXSTVOM SIMVOLOV VVEDENIE YAVNOGO IMENI "\var{PROPUSTITX}" DLYA PUSTOGO OPERATORA, KOGDA "PUSTO" STOLX KRASNORECHIVO VYRAZHAET EGO SEMANTIKU, SLEDUET OSOZNATX, CHTO DESYATICHNAYA SISTEMA SCHISLENIYA OKAZALASX VOZMOZHNOJ TOLXKO BLAGODARYA VVEDENIYU SIMVOLA "0" DLYA PONYATIYA "NICHTO". {\sl (kONEC ZAMECHANIYA.)} pREZHDE CHEM PRODOLZHITX NASHI RASSUZHDENIYA, MNE HOTELOSX BY NE UPUSTITX VOZMOZHNOSTX OTMETITX, CHTO TEM VREMENEM MY UZHE OPREDELILI NEKIJ YAZYK PROGRAMMIROVANIYA. oSTAETSYA DOBAVITX TOLXKO ODNO: |TO ODNOOPERATORPYJ YAZYK, V KOTOROM MOZHNO OPISATX TOLXKO ODNU KONSTRUKCIYU, PRICHEM EDINSTVENNOE, CHTO SPOSOBNA SDELATX DLYA NAS DANNAYA KONSTRUKCIYA, |TO "OSTAVITX Vce, KAK ESTX" (ILI "NICHEGO NE DELATX", NO TAKOE NEGATIVNOE UPOTREBLENIE YAZYKA PREDSTAVLYAET OPASNOSTX, SM. SLEDUYUSHCHIJ ABZAC). dRUGOJ PROSTOJ PREOBRAZOVATELX PREDIKATOV PRIVODIT K POSTOYANNOMy SLABEJSHEMU PREDUSLOVIYU, KOTOROE VOVSE NE ZAVISIT OT POSTUSLOVIYA $R$. mY IMEEM DVA PREDIKATA-KONSTANTY, $T$ I $F$. kONSTRUKCIYA $S$, DLYA KOTOROJ $\wp(S, R)=T$ PRI VSEH $R$, NE MOZHET SUSHCHESTVOVATX, POTOMU CHTO ONA NARUSHILA BY ZAKON ISKLYUCHENNOGO CHUDA. oDNAKO KONSTRUKCIYA $S$, DLYA KOTOROJ $\wp(S,R)=F$ PRI VSEH $R$, OBLADAET PREOBRAZOVATELEM PREDIKATOV, UDOVLETVORYAYUSHCHIM VSEM NEOBHODIMYM SVOJSTVAM. eTOMU OPERATORU MY TOZHE PRISVOIM IMYA, NAZOVEM EGO "\var{OTKAZATX}". iTAK, SEMANTIKA OPERATORA "\var{OTKAZATX}" ZADAETSYA SLEDUYUSHCHIM OBRAZOM: $$ \wp (\var{OTKAZATX}, R) = F\qquad\hbox{ DLYA LYUBOGO POSTUSLOVIYA R} $$ eTOT OPERATOR NE MOZHET DAZHE "NICHEGO NE DELATX" V SMYSLE "OSTAVITX VSE, KAK ESTX"; ON VOOBSHCHE NI NA CHTO NE SPOSOBEN. eSLI MY POLAGAEM $R=T$, T. E. NE NAKLADYVAEM NA KONECHNOE SOSTOYANIE NIKAKIH DOPOLNITELXNYH TREBOVANIJ, KROME SAMOGO FAKTA EGO SUSHCHESTVOVANIYA, DAZHE TOGDA NE NAJDETSYA SOOTVETSTVUYUSHCHEGO NACHALXNOGO SOSTOYANIYA. eSLI ZAPUSTITX KONSTRUKCIYU PO IMENI "\var{OTKAZATX}", ONA NE SMOZHET DOSTICHX KONECHNOGO SOSTOYANIYA: SAMA POPYTKA EE ZAPUSKA YAVLYAETSYA GARANTIEJ NEUDACHI. (nAS NE DOLZHNO ZANIMATX TEPERX (A TAKZHE I VPOSLEDSTVII) TO, CHTO POZDNEE MY VVEDEM STRUKTURU OPERATOROV, V KOTOROJ SODERZHATSYA KAK CHASTNYE SLUCHAI SEMANTICHESKIE |KVIVALENTY DLYA "\var{PROPUSTITX}" I "\var{OTKAZATX}".) tEPERX MY RASPOLAGAEM NEKIM (VSE ESHCHE VESXMA ZACHATOCHNYM) DVUHOPERATORNYM YAZYKOM PROGRAMMIROVANIYA, V KOTOROM MOZHEM OPISATX DVE KONSTRUKCII; ODNA IZ NIH NICHEGO NE DELAET, A VTORAYA VSEGDA TERPIT NEUDACHU. sO VREMENI OPUBLIKOVANIYA ZNAMENITOGO "sOBSHCHENIYA OB ALGORITMICHESKOM YAZYKE algol 60" V 1960~G. NIKAKOJ UVAZHAYUSHCHIJ SEBYA UCHENYJ, ZANIMAYUSHCHIJSYA PROGRAMMIROVANIEM, NE POZVOLIT SEBE OBOJTISX NA |TOM |TAPE BEZ FORMALXNOGO OPREDELENIYA SINTAKSISA STOLX DALEKO PRODVINUTOGO YAZYKA PROGRAMMIROVANIYA V SISTEME OBOZNACHENIJ, NAZYVAEMOJ "nfb" (SOKRASHCHENIE OT "nORMALXNAYA FORMA b|KUSA"), A IMENNO: $$ \:: = \var{PROPUSTITX} | \var{OTKAZATX} $$ (chITAETSYA TAK: "eLEMENT SINTAKSICHESKOJ KATEGORII, IMENUEMOJ "OPERATOR" (IMENNO |TO OBOZNACHAYUT ZABAVNYE SKOBKI "$<$" I "$>$"), OPREDELYAETSYA KAK (|TO OBOZNACHAET ZNAK "$::=$") "\var{PROPUSTITX}" ILI (|TO OBOZNACHAET VERTIKALXNAYA CHERTA "$|$") "\var{OTKAZATX}". kOLOSSALXNO! nO NE BESPOKOJTESX; BOLEE VPECHATLYAYUSHCHIE PRIMENENIYA nfb V KACHESTVE SPOSOBA ZAPISI POSLEDUYUT V NADLEZHASHCHEE VREMYA.) oDIN KLASS BEZUSLOVNO BOLEE INTERESNYH PREOBRAZOVATELEJ PREDIKATOV OSNOVYVAETSYA NA PODSTANOVKE, T. E. NA ZAMENE VSEH VHOZHDENIJ NEKOEJ PEREMENNOJ V FORMALXNOM VYRAZHENII DLYA POSTUSLOVIYA $R$ NA (ODNO I TO ZHE) "CHTO-NIBUDX DRUGOE". eSLI V PREDIKATE $R$ VSE VHOZHDENIYA PEREMENNOJ $x$ ZAMENYAYUTSYA NEKOTORYM VYRAZHENIEM $(E)$, TO MY OBOZNACHAEM REZULXTAT |TOGO PREOBRAZOVANIYA CHEREZ $R_{E\to X}$. tEPERX MY MOZHEM RASSMOTRETX DLYA ZADANNYH $x$ I $E$ TAKUYU KONSTRUKCIYU, CHTOBY DLYA LYUBYH POSTUSLOVIJ $R$ POLUCHALOSX $\wp(S, R) =R_{E\to X}$; ZDESX $x$ --- "KOORDINATNAYA PEREMENNAYA" NASHEGO PROSTRANSTVA SOSTOYANIJ, A $E$ --- VYRAZHENIE SOOTVETSTVUYUSHCHEGO TIPA. {\sl zAMECHANIE.} tAKOE PREOBRAZOVANIE PUTEM PODSTANOVKI UDOVLETVORYAET SVOJSTVAM 1--4 IZ PREDYDUSHCHEJ GLAVY. mY NE STANEM PYTATXSYA DEMONSTRIROVATX |TO I PREDOSTAVIM SAMOMU CHITATELYU RESHATX V ZAVISIMOSTI OT SVOEGO VKUSA, BUDET LI ON OTNOSITXSYA K |TOMU KAK K TRIVIALXNOMU ILI ZHE KAK K GLUBOKOMU MATEMATICHESKOMU REZULXTATU. {\sl(kONEC ZAMECHANIYA.)} tAKIM SPOSOBOM VVODITSYA CELYJ KLASS PREOBRAZOVATELEJ PREDIKATOV, CELYJ KLASS KONSTRUKCIJ. oNI OBOZNACHAYUTSYA OPERATOROM, KOTORYJ NAZYVAETSYA "OPERATOR PRISVAIVANIYA"; TAKOJ OPERATOR DOLZHEN OPREDELYATX TRI VESHCHI: 1) NAIMENOVANIE PEREMENNOJ, PODLEZHASHCHEJ ZAMENE; 2) TOT FAKT, CHTO PRAVILO, SOOTVETSTVUYUSHCHEE PREOBRAZOVANIYU PREDIKATOV, ESTX PODSTANOVKA; 3) VYRAZHENIE, KOTORYM DOLZHNO ZAMENYATXSYA VSYAKOE VHOZHDENIE |TOJ PEREMENNOJ V POSTUSLOVII. eSLI PEREMENNAYA $x$ DOLZHNA BYTX ZAMENENA VYRAZHENIEM $(E)$ TO OBYCHNAYA ZAPISX TAKOGO OPERATORA VYGLYADIT SLEDUYUSHCHIM OBRAZOM: $$ x:=E $$ (GDE TAK NAZYVAEMYJ ZNAK PRISVAIVANIYA ":=" SLEDUET CHITATX KAK "STANOVITSYA"). sKAZANNOE MOZHNO SUMMIROVATX, OPREDELIV $$ \wp("x:=E", R) =R_{E\to X} \qquad\hbox{dLYA LYUBOGO POSTUSLOVIYA $R$} $$ pRI ZHELANII |TO MOZHNO RASSMATRIVATX KAK SEMANTICHESKOE OPREDELENIE OPERATORA PRISVAIVANIYA DLYA LYUBOJ KOORDINATNOJ PEREMENNOJ $x$ I LYUBOGO VYRAZHENIYA $E$ SOOTVETSTVUYUSHCHEGO TIPA. nASLAZHDAYASX, PO NASHEMU OBYKNOVENIYU, UPOTREBLENIEM nfb, MY MOZHEM RASSHIRITX NASH FORMALXNYJ SINTAKSIS, CHTOBY ON CHITALSYA TAK: $$ \eqalign{ &\ ::=\var{PROPUSTITX}|\var{OTKAZATX}|\ \cr &\ ::=\ := \ \cr } $$ PRICHEM POSLEDNYUYU STROCHKU SLEDUET CHITATX TAK: "eLEMENT SINTAKSICHESKOJ KATEGORII, IMENUEMOJ "OPERATOR PRISVAIVANIYA", OPREDELYAETSYA KAK |LEMENT SINTAKSICHESKOJ KATEGORII, IMENUEMOJ "PEREMENNAYA", ZA KOTORYM SLEDUYUT SNACHALA ZNAK PRISVAIVANIYA "$:=$", A ZATEM |LEMENT SINTAKSICHESKOJ KATEGORII, IMENUEMOJ "VYRAZHENIE". pERED TEM KAK PRODOLZHITX RASSUZHDENIE, PREDSTAVLYAETSYA RAZUMNYM UBEDITXSYA V TOM, CHTO |TIM FORMALXNYM OPISANIEM OPERATORA PRISVAIVANIYA V SAMOM DELE OHVATYVAETSYA NASHE INTUITIVNOE PONIMANIE OPERATORA PRISVAIVANIYA --- ESLI ONO U NAS ESTX! rASSMOTRIM PROSTRANSTVO SOSTOYANIJ S DVUMYA CELYMI KOORDINATNYMI PEREMENNYMI "$a$" I "$b$". tOGDA $$ \wp("a:=7", a=7)= \{7=7\} $$ I, POSKOLXKU LOGICHESKOE VYRAZHENIE V PRAVOJ CHASTI YAVLYAETSYA ISTINOJ DLYA VSEH ZNACHENIJ $a$ I $b$, T. E. DLYA VSEH TOCHEK PROSTRANSTVA SOSTOYANIJ, MY MOZHEM UPROSHCHENNO ZAPISATX |TO TAK: $$ \wp("a:=7", a=7)=T $$ iNACHE GOVORYA, VSYAKOE NACHALXNOE SOSTOYANIE GARANTIRUET, CHTO PRISVAIVANIE "$a:=7$" OBESPECHIT ISTINNOSTX "$a=7$". aNALOGICHNO $$ \wp("a:=7", a=6) = \{7=6\} $$ I, POSKOLXKU |TO LOGICHESKOE VYRAZHENIE YAVLYAETSYA LOZHXYU DLYA VSEH ZNACHENIJ $a$ I $b$, MY POLUCHAEM $$ \wp( "a:=7", a=6)=F $$ eTO OZNACHAET, CHTO NE SUSHCHESTVUET NIKAKOGO NACHALXNOGO SOSTOYANIYA, DLYA KOTOROGO MY MOGLI BY GARANTIROVATX, CHTO PRISVAIVANIE "$a:=7$" OBESPECHIT ISTINNOSTX "$a=6$". (eTO NAHODITSYA V SOOVETSTVII S NASHIM PREDYDUSHCHIM REZULXTATOM, CHTO VSE NACHALXNYE SOSTOYANIYA OBESPECHAT KONECHNUYU ISTINNOSTX "$a=7$", A SLEDOVATELXNO, KONECHNUYU LOZHNOSTX "$a\not=7$".) dALEE, $$ \wp ("a:=7", b=b0)=\{b=b0\} $$ T. E. ESLI MY HOTIM GARANTIROVATX, CHTO POSLE PRISVAIVANIYA "$a:=7$" PEREMENNAYA b IMEET NEKOTOROE ZNACHENIE $b0$, TO NUZHNO, CHTOBY $b$ IMELA |TO ZNACHENIE ESHCHE V NACHALXNOM SOSTOYANII. dRUGIMI SLOVAMI, VSE PEREMENNYE, ZA ISKLYUCHENIEM "$a$", NE IZMENYAYUTSYA, ONI SOHRANYAYUT TE ZNACHENIYA, KOTORYE IMELI RANXSHE; PRISVAIVANNE "$a:=7$" PEREMESHCHAET V PROSTRANSTVE SOSTOYANIJ TOCHKU, SOOTVETSTVUYUSHCHUYU TEKUSHCHEMU SOSTOYANIYU SISTEMY, PARALLELXNO OSI $a$ TAK, CHTO OBESPECHIVAETSYA KONECHNOE VYPOLNENIE RAVENSTVA "$a=7$". vMESTO TOGO CHTOBY BRATX V KACHESTVE VYRAZHENIYA $E$ KONSTANTU, MY MOGLI BY VZYATX KAKUYU-TO FUNKCIYU OT NACHALXNOGO SOSTOYANIYA. eTO ILLYUSTRIRUETSYA SLEDUYUSHCHIMI PRIMERAMI: $$ \eqalign{ &\wp("a:=2*b+1", a=13)=\{2*b+1=13\}=\{b=6\} \cr &\wp ("a: =a +1", a>10)=\{a+1>10\}=\{a>9\} \cr &\wp("a:=a-b", a>b) = \{a-b>b\}=\{a>2*b\} \cr } $$ vOZNIKAET NEBOLXSHOE OSLOZHNENIE, ESLI MY RAZRESHAEM VYRAZHENIYU $E$ BYTX CHASTICHNO OPREDELENNOJ FUNKCIEJ NACHACHALXNOGO SOSTOYANIYA, T. E. TAKOJ FUNKCIEJ, POPYTKA VYCHISLENIYA KOTOROJ DLYA NACHALXNOGO SOSTOYANIYA, NE VHODYASHCHEGO V OBLASTX OPREDELENIYA, NE PRIVEDET K PRAVILXNO ZAVERSHAEMOJ RABOTE. eSLI MY HOTIM PREDUSMOTRETX I |TU SITUACIYU, TO NAM NUZHNO UTOCHNITX NASHE OPREDELENIE SEMANTIKI OPERATORA PRISVAIVAIVANIYA I ZAPISATX $$ \wp ("x:=E", R) = \{D(E) \cand R_{E \to X}\} $$ zDESX PREDIKAT $D(E)$ OZNACHAET "V OBLASTI OPREDELENIYA $E$"; LOGICHESKOE VYRAZHENIE "$B1 \cand B2$" (TAK NAZYVAEMAYA "USLOVNAYA KON®YUNKCIYA") IMEET TO ZHE ZNACHENIE, CHTO I "$B1\and B2$", ESLI OBA OPERANDA OPREDELENY, NO POMIMO |TOGO PO OPREDELENIYU ONO IMEET ZNACHENIE "LOZHX", ESLI $B1$ YAVLYAETSYA "LOZHXYU"; POSLEDNEE SPRAVEDLIVO VNE ZAVISIMOSTI OT TOGO, OPREDELEN LI OPERAND $B2$. oBYCHNO USLOVIE $D(E)$ NE PODCHERKIVAETSYA YAVNO LIBO POTOMU, CHTO ONO=$T$, LIBO POTOMU, CHTO MY ISHODIM IZ PREDPOLOZHENIYA, CHTO OPERATOR PRISVAIVANIYA NIKOGDA NE BUDET ZAPUSHCHEN V NACHALXNYH SOSTOYANIYAH, NE PRINADLEZHASHCHIH OBLASTI OPREDELENIYA VYRAZHENIYA $E$. eSTESTVENNYM OBOBSHCHENIEM OPERATORA PRISVAIVANIYA YAVLYAETSYA IZLYUBLENNOE NEKOTORYMI PROGRAMMISTAMI TAK NAZYVAEMOE "ODNOVREMENNOE PRISVAIVANIE". v |TOM SLUCHAE VOZMOZHNA ODNOVREMENNAYA ZAMENA DLYA NESKOLXKIH \emph{RAZLICHNYH}PEREMENNYH. oPERATOR ODNOVREMENNOGO PRISVAIVANIYA OBOZNACHAETSYA SPISKOM RAZLICHNYH PEREMENNYH), PODLEZHASHCHIH ZAMENE (|TI PEREMENNYE RAZDELYAYUTSYA ZAPYATYMI), SLEVA OT ZNAKA PRISVAIVANIYA I STOLX ZHE PROTYAZHENNYM SPISKOM VYRAZHENIJ (TAKZHE RAZDELYAEMYH ZAPYATYMI) SPRAVA OT ZNAKA PRISVAIVANIYA. iTAK, RAZRESHAETSYA PISATX $$ x1,x2:=E1, E2 \qquad x1,x2, x3:=E1, E2, Ez $$ zAMETIM, CHTO $i$-YA PEREMENNAYA IZ SPISKA LEVOJ CHASTI DOLZHNA BYTX ZAMENENA NA $i$-e VYRAZHENIE IZ SPISKA PRAVOJ CHASTI, TAK CHTO, NAPRIMER, PRI ZADANNYH $x1$, $x2$, $E1$ I $E2$ OPERATOR $$ x1, x2:=E1,E2 $$ SEMANTICHESKI |KVIVALENTEN OPERATORU $$ x2,x1:=E2,E1 $$ oDNOVREMENNOE PRISVAIVANIE POZVOLYAET NAM PREDPISATX, CHTOBY DVE PEREMENNYE $x$ I $y$ OBMENYALISX SVOIMI ZNACHENIYAMI S POMOSHCHXYU OPERATORA $$ x, y:=y, x $$ v INOJ ZAPISI |TA OPERACIYA VYGLYADELA BY BOLEE GROMOZDKOJ. lEGKOSTX REALIZACII ODNOVREMENNOGO PRISVAIVANIYA I VOZMOZHNOSTX S EGO POMOSHCHXYU IZBEGATX NEKOTOROJ IZBYTOCHNOSTI ZAPISI YAVLYAYUTSYA PRICHINAMI POPULYARNOSTI TAKIH OPERATOROV. zAMETIM, CHTO ESLI SPISKI STANOVYATSYA SLISHKOM DLINNYMI, TO POLUCHAEMAYA PROGRAMMA STANOVITSYA VESXMA NEUDOBOCHITAEMOJ. iSTINNYJ LYUBITELX nfb RASSHIRIT SVOJ SINTAKSIS, OBESPECHIV DVE RAZLICHNYE FORMY DLYA OPERATORA PRISVAIVANIYA, SLEDUYUSHCHIM OBRAZOM: $$ \eqalign{ \::=&\:=\ | \cr &\, \, \ \cr } $$ eTO TAK NAZYVAEMOE "REKURSIVNOE OPREDELENIE", POSKOLXKU ODNA IZ ALXTERNATIVNYH FORM DLYA SINTAKSICHESKOJ EDINICY, IMENUEMOJ "OPERATOR PRISVAIVANIYA" (A IMENNO VTORAYA FORMA), SODERZHIT V KACHESTVE ODNOGO IZ SVOIH KOMPONENTOV SNOVA |TU ZHE SINTAKSICHESKUYU EDINICU, IMENUEMUYU "OPERATOR PRISVAIVANIYA", T. E. TU SAMUYU SINTAKSICHESKUYU EDINICU, KOTORUYU MY OPREDELYAEM! nA PERVYJ VZGLYAD TAKOE CIKLICHESKOE OPREDELENIE VYGLYADIT UZHASAYUSHCHE, NO POSLE BOLEE VNIMATELXNOGO IZUCHENIYA MY MOZHEM UBEDITXSYA V TOM, CHTO, PO KRAJNEJ MERE S SINTAKSICHESKOJ TOCHKI ZRENIYA, V |TOM NET NICHEGO NEPRAVILXNOGO. nAPRIMER, POSKOLXKU, SOGLASNO PERVOJ ALXTERNATIVE, $$ x2:=E1 $$ YAVLYAETSYA PRIMEROM OPERATORA PRISVAIVANIYA, TO FORMULA $$ x1,x2:=E1, E2 $$ DOPUSKAET RAZBOR VIDA $$ x1, \, E2 $$ A SLEDOVATELXNO, SOGLASNO VTOROJ ALXTERNATIVE, TAKZHE YAVLYAETSYA OPERATOROM PRISVAIVANIYA. oDNAKO S SEMANTICHESKOJ TOCHKI ZRENIYA |TO OTVRATITELXNO, POTOMU CHTO POLUCHAETSYA, CHTO $E2$ ASSOCIIRUETSYA S $x1$ VMESTO TOGO, CHTOBY ASSOCIIROVATXSYA S $x2$. v SRAVNENII S DVUHOPERATORNYM YAZYKOM, SODERZHASHCHIM TOLXKO "PROPUSTITX" I "OTKAZATX", NASH YAZYK S OPERATOROM PRISVAIVANIYA VYGLYADIT ZNACHITELXNO BOLEE BOGATYM: UZHE NET KAKOJ BY TO NI BYLO VERHNEJ GRANICY DLYA CHISLA RAZLICHNYH PRIMEROV SINTAKSICHESKOJ EDINICY "OPERATOR PRISVAIVANIYA". nO ON VSE ZHE YAVNO NEDOSTATOCHEN DLYA NASHIH CELEJ; NAM NUZHNA VOZMOZHNOSTX STROITX BOLEE IZOSHCHRENNYE PROGRAMMY, BOLEE SLOZHNYE KONSTRUKCII. dLYA POSTROENIYA POTENCIALXNO SLOZHNYH KONSTRUKCIJ MY POLXZUEMSYA SHEMOJ, KOTORUYU MOZHNO REKURSIVNO OPISATX TAK: $$ \displaylines{ \::=\| \hfill\cr \hfill\} >\cr } $$ dLYA TOGO CHTOBY |TA SHEMA MOGLA PRINESTI HOTX KAKUYU-NIBUDX POLXZU, NEOBHODIMO VYPOLNENIE DVUH USLOVIJ: V NASHEM RASPORYAZHENII DOLZHNY IMETXSYA "PROSTYE KONSTRUKCII", CHTOBY BYLO S CHEGO NACHATX, I, KROME TOGO, MY DOLZHNY ZNATX, KAK STROITX "PRAVILXNYE KOMPOZICII". vVEDENNYE RANXSHE OPERATORY MOZHNO VZYATX V KACHESTVE PROSTYH KONSTRUKCIJ; OSTAVSHAYASYA CHASTX |TOJ GLAVY POSVYASHCHENA IMENNO PROCESSU PRAVILXNOJ KOMPOZICII NEKOEJ NOVOJ KONSTRUKCII IZ ZADANNYH KONSTRUKCIJ. nOVAYA KONSTRUKCIYA V SVOYU OCHEREDX MOZHET VYSTUPATX V ROLI CHASTI ESHCHE BOLEE SLOZHNOGO SOSTAVNOGO OB®EKTA. pOSLE TOGO, KAK OB®EKT BYL OBRAZOVAN KOMPOZICIEJ CHASTEJ, MY MOZHEM RASSMATRIVATX EGO DVUMYA SPOSOBAMI. vO-PERVYH, MY MOZHEM SCHITATX EGO "NERAZDELXNYM CELYM", VOSPRINIMAYA EGO SVOJSTVA V BOLXSHEJ ILI MENXSHEJ STEPENI KAK MAGICHESKIE (ILI PRINIMAYA IH NA VERU ILI KAK POSTULATY). pRI TAKOM PODHODE SUSHCHESTVENNY TOLXKO SVOJSTVA KONSTRUKCII; NE IMEET NIKAKoro ZNACHENIYA, KAKIM OBRAZOM ONA OBRAZOVANA IZ SVOIH CHASTEJ. s TAKOJ TOCHKI ZRENIYA LYUBYE DVE KONSTRUKCII, OBLADAYUSHCHIE ODINAKOVYMI SVOJSTVAMI, |KVIVALENTNY. iLI ZHE MY RASSMATRIVAEM KONSTRUKCIYU KAK "SOSTAVNOJ OB®EKT", OBRAZOVANNYJ TAK, CHTO MY MOZHEM PONYATX, POCHEMU ONA OBLADAET OB®YAVLENNYMI SVOJSTVAMI. pRI |TOM MY VOSPRINIMAEM CHASTI KAK "MALYE" NERAZDELXNYE CELYE, DLYA KOTORYH PRINIMAYUTSYA V RASCHET TOLXKO IH OBSHCHIE SVOJSTVA. vTOROJ PODHOD VNOSIT YASNOSTX V TO, CHTO MY PONIMAEM POD "KOMPOZICIEJ". kOMPOZICIYA DOLZHNA OPREDELYATX, KAK SVOJSTVA CELOGO SLEDUYUT IZ SVOJSTV CHASTEJ. pOSLE |TIH OBSHCHIH ZAMECHANIJ VERNEMSYA K NASHIM KONKRETNYM KONSTRUKCIYAM, SVOJSTVA KOTORYH, KAK MY SCHITAEM, VYRAZHAYUTSYA IH PREOBRAZOVATELYAMI PREDIKATOV. tOCHNEE GOVORYA, ESLI ZADANY DVE KONSTRUKCII $S1$ I $S2$, CHXI PREOBRAZOVATELI PREDIKATOV IZVESTNY, MOZHEM LI MY PREDSTAVITX SEBE PRAVILO VYVODA NOVOGO PREOBRAZOVATELYA PREDIKATOV IZ DVUH ZADANNYH? eSLI DA, TO MY MOZHEM SCHITATX REZULXTIRUYUSHCHIJ PREOBRAZOVATELX PREDIKATOV OPISANIEM SVOJSTV SOSTAVNOGO OB®EKTA, POSTROENNOGO SPECIALXNYM OBRAZOM IZ CHASTEJ $S1$ I $S2$. oDNIM IZ PROSTEJSHIH SPOSOBOV POLUCHENIYA NOVOJ FUNKCII IZ DVUH ZADANNYH YAVLYAETSYA TAK NAZYVAEMAYA "FUNKCIONALXNAYA KOMPOZICIYA", T. E. PREDOSTAVLENIE ZNACHENIYA ODNOJ FUNKCII V KACHESTVE ARGUMENTA DLYA DRUGOJ. sOSTAVNOJ OB®EKT, SOOTVETSTVUYUSHCHIJ TAKOMU PREOBRAZOVATELYU PREDIKATOV, PRINYATO OBOZNACHATX CHEREZ "S1; S2", I MY OPREDELYAEM $$ \wp("S1; S2", R) =\wp(S1, \wp(S2, R)) $$ CHTO PRI ZHELANII MOZHNO RASSMATRIVATX KAK SEMANTICHESKOE OPREDELENIE TOCHKI S ZAPYATOJ. {\sl zAMECHANue.} iZ TOGO FAKTA, CHTO PREOBRAZOVATELI PREDIKATOV DLYA $S1$ I $S2$ OBLADAYUT SVOJSTVAMI 1--4 IZ PREDYDUSHCHEJ GLAVY, MOZHNO ZAKLYUCHITX, CHTO I OPREDELENNYJ VYSHE PREOBRAZOVATELX PREDIKATOV DLYA "$S1; S2$" TAKZHE OBLADAET |TIMI CHETYRXMYA SVOJSTVAMI. nAPRIMER, POSKOLXKU DLYA $S1$ I $S2$ SPRAVEDLIV ZAKON ISKLYUCHENNOGO CHUDA: $$ \wp(S1, F)=F\quad\hbox{ I }\quad\wp(S2, F)=F $$ MY ZAKLYUCHAEM, PODSTAVLYAYA $F$ VMESTO $R$ V VERHNEE OPREDELENIE CHTO $$ \eqalign{ \wp("S1; S2", F)&=\wp(S1, \wp(S2, F))\cr &=\wp(S1, F) \cr &=F \cr } $$ chITATELYU PREDOSTAVLYAETSYA V KACHESTVE UPRAZHNENIYA PROVERITX, CHTO OSTALXNYE TRI SVOJSTVA TOZHE SOHRANYAYUTSYA. {\sl (kONEC ZAMECHANIYA.)} pERED TEM KAK PRODOLZHITX NASHI RASSUZHDENIYA, UBEDIMSYA V TOM, CHTO |TIM FORMALXNYM OPISANIEM SEMANTIKI TOCHKI S ZAPYATOJ OHVATYVAETSYA NASHE INTUITIVNOE PREDSTAVLENIE O NEJ (ESLI ONO U NAS ESTX!), T. E. CHTO SOSTAVNAYA KONSTRUKCIYA "$S1;S2$" MOZHET BYTX REALIZOVANA NO PRAVILU "SNACHALA ZAPUSTITX KONSTRUKCIYU $S1$ I Po OKONCHANII EE RABOTY ZAPUSTITX $S2$". v SAMOM DELE, V NASHEM OPREDELENII $\wp ("S1; S2", R)$ MY PREDSTAVLYAEM $R$-POSTUSLOVIE DLYA SOSTAVNOJ KONSTRUKCII --- KAK POSTUSLOVIE K PREOBRAZOVATELYU PREDIKATOV DLYA $S2$, I |TIM OTRAZHAETSYA TO, CHTO OBSHCHAYA RABOTA KONSTRUKCII "$S1; S2$" MOZHET ZAKONCHITXSYA S OKONCHANIEM RABOTY $S2$. sOOTVETSTVUYUSHCHEE SLABEJSHEE PREDUSLOVIE DLYA $S2$, T. E. $\wp(S2, R)$, PREDSTAVLYAETSYA KAK POSTUSLOVIE K PREOBRAZOVATELYU PREDIKATOV DLYA $S1$; TEM SAMYM MY YAVNO OTOZHDESTVLYAEM NACHALXNOE SOSTOYANIE DLYA $S2$ S KONECHNYM SOSTOYANIEM DLYA $S1$. oDNAKO IMENNO TAK I BYVAET, ESLI RABOTA $S1$ NEPOSREDSTVENNO PREDSHESTVUET VO VREMENI ZAPUSKU $S2$. chTOBY UDOSTOVERITXSYA V |TOM, RASSMOTRIM PRIMER. pUSTX "$S1; S2$" PREDSTAVLYAET SOBOJ $$ "a:=a+b; b:=a*b" $$ I PUSTX NASHIM POSTUSLOVIEM YAVLYAETSYA NEKOTORYJ PREDIKAT $R(a, b)$; V TAKOM SLUCHAE $$ \eqalign{ \wp (S2, R (a, b) ) &=\wp ("b:= a * b", R (a, b))\cr &=R(a. c*b) \cr } $$ I $$ \eqalign{ \wp("S1; S2", R(a, b))&=\wp(S1,\wp(S2, R(a, b)))\cr &=\wp(S1,R(a, a*b))\cr &=\wp( "a:= a + b ", R ( a, a * b))\cr &=R(a+b, (a+b)*b)\cr } $$ T.E MY MOZHEM GARANTIROVATX VYPOLNENIE OTNOSHENIYA $R$ MEZHDU KONECHNYMI ZNACHENIYAMI $a$ I $b$ PRI USLOVII, CHTO PERVONACHALXNO TO ZHE OTNOSHENIE VYPOLNYAETSYA MEZHDU $a+b$ I $(a+b)*b$ SOOTVETSTVENNO. i NAKONEC, POSKOLXKU FUNKCIONALXNAYA KOMPOZICIYA OBLADAET SVOJSTVOM ASSOCIATIVNOSTI, TO NE IMEET ZNACHENIYA, BUDEM LI MY RAZBIRATX "S1; S2; S3" KAK "[S1; S2]; S3" ILI ZHE KAK "S1;[S2;S3]". iNACHE GOVORYA, MY IMEEM POLNOE PRAVO TRAKTOVATX TOCHKU S ZAPYATOJ KAK SIMVOL SOCHLENENIYA; PO|TOMU NE VOZNIKAET NIKAKOJ NEOPREDELENNOSTI, KOGDA MY VYPISYVAEM OPERATORNYJ SPISOK VIDA "$S_1$; $S_2$; $S_3$; \dots ; $S_n$", I MY BUDEM BEZ STESNENIYA POSTUPATX TAK, KOGDA DLYA |TOGO PREDSTAVYATSYA PODHODYASHCHIE SLUCHAI. {\bf uPRAZHNENIE.} pROVERXTE, CHTO KONSTRUKCII $$ "x1:=E1; x2:=E2"\hbox{ I }"x2:=E2; x1:=E1" $$ SEMANTICHESKI |KVIVALENTNY, ESLI PEREMENNAYA $x1$ NE VSTRECHAETSYA V VYRAZHENII $E2$, A PEREMENNAYA $x2$ NE VSTRECHAETSYA V VYRAZHENII $E1$. nA SAMOM DELE, V TAKOM SLUCHAE OBE |TI KONSTRUKCII SEMANTICHESKI |KVIVALENTNY ODNOVREMENNOMU PRISVAIVANIYU "$x1, x2:=E1, E2$". (eTA |KVIVALENTNOSTX YAVLYAETSYA ODNIM IZ ARGUMENTOV V POLXZU ODNOVREMENNOGO PRISVAIVANIYA; EE PRIMENENIE POZVOLYAET NAM IZBEZHATX IZBYTOCHNOSTI POSLEDOVATELXNOJ ZAPISI, BOLee TOGO, PRI ODNOVREMENNOM PRISVAIVANII STANOVITSYA OCHEVIDNYM, CHTO DVA VYRAZHENIYA $E1$ I $E2$ MOGUT VYCHISLYATXSYA ODNOVREMENNO, I |TO POSLEDNEE OBSTOYATELXSTVO PREDSTAVLYAET INTERES PRI NEKOTORYH METODIKAH REALIZACII. pOMIMO TOGO, BYTX MOZHET, BOLEE INTERESNAYA VOZMOZHNOSTX, CHTO KONSTRUKCIYA "$x1, x2:=E1, E2$" NE OKAZHETSYA SEMANTICHESKI |KVIVALENTNOJ NI KONSTRUKCII "$x1:=E1; x2:=E2$", NI KONSTRUKCII "$x2:=E2; x1:=E1$".) (kONEC UPRAZHNENIYA.) dO VVEDENIYA TOCHKI S ZAPYATOJ MY MOGLI PISATX TOLXKO ODNOOPERATORNYE PROGRAMMY; S POMOSHCHXYU TOCHKI S ZAPYATOJ MY OBRELI SPOSOBNOSTX PISATX PROGRAMMY V VIDE SOCHLENENIYA IZ $n$, $(n>0)$ OPERATOROV: "$S_1$; $S_2$; $S_3$; \dots; $S_n$". eSLI ISKLYUCHITX PROMEZHUTOCHNUYU NEZAVERSHENNOSTX, VYPOLNENIE KAZHDOJ PROGRAMMY VSEGDA OZNACHAET VREMENNUYU POSLEDOVATELXNOSTX VYPOLNENIJ $n$ OPERATOROV, SNACHALA $S_1$, POTOM $S_2$ I TAK DALEE DO $S_n$ VKLYUCHITELXNO. oDNAKO IZ NASHEGO PRIMERA IGRY NA LISTE KARTONA, REALIZUYUSHCHEJ ALGORITM eVKLIDA, MY ZNAEM, CHTO DOLZHNY UMETX OPISYVATX BOLEE SHIROKIJ KLASS "PRAVIL IGRY": VSYAKAYA IGRA BUDET SOSTOYATX IZ POSLEDOVATELXNOSTI PEREMESHCHENIJ, GDE KAZHDOE PEREMESHCHENIE IMEET VID LIBO "$x:=x-y$", LIBO "$y:=y-x$", NO SPOSOB CHEREDOVANIYA |TIH PEREMESHCHENIJ VO VREMENI I DAZHE IH OBSHCHEE CHISLO BUDUT IZMENYATXSYA OT IGRY K IGRE; ON ZAVISIT OT NACHALXNOGO POLOZHENIYA FISHKI, ON ZAVISIT OT NACHALXNOGO SOSTOYANIYA SISTEMY. eSLI TOCHKA S ZAPYATOJ YAVLYAETSYA EDINSTVENNYM NASHIM SREDSTVOM DLYA SOSTAVLENIYA NOVOGO CELOGO IZ ZADANNYH CHASTEJ, TO MY NE V SOSTOYANII |TOGO VYRAZITX, I PO|TOMU NAM NEOBHODIMO ISKATX NECHTO NOVOE. pOKA TOCHKA S ZAPYATOJ OSTAETSYA EDINSTVENNYM IMEYUSHCHIMSYA V NASHEM RASPORYAZHENII SREDSTVOM SOEDINENIYA, EDINSTVENNYM OBSTOYATELXSTVOM, PRI KOTOROM PROISHODIT ZAPUSK ODNOJ IZ SOSTAVLYAYUSHCHIH KONSTRUKCIJ $S_i\; (i>1)$, YAVLYAYUTSYA PRAVILXNOE ZAVERSHENIE RABOTY (LEKSIKOGRAFICHESKI) PREDSHESTVUYUSHCHEJ KONSTRUKCII. chTOBY DOBITXSYA NUZHNOJ NAM GIBKOSTI, NEOBHODIMO OBESPECHITX VOZMOZHNOSTX ZAPUSKA TOJ ILI INOJ (POD) KONSTRUKCII V ZAVISIMOSTI OT TEKUSHCHEGO SOSTOYANIYA SISTEMY. dLYA |TOGO MY VVEDEM --- V DVA |TAPA --- PONYATIE "OHRANYAEMOJ KOMANDY", SINTAKSIS KOTOROJ ZADAETSYA SLEDUYUSHCHIM OBRAZOM: $$ \eqalign{ \&::=\\to\cr &\\cr \&::=\ \{;\cr &\\}\cr } $$ GDE FIGURNYE SKOBKI "$\{$" I "$\}$" SLEDUET CHITATX TAK: "conpOVOZHDAETSYA LYUBYM CHISLOM (BYTX MOZHET, NULEM) |KZEMPLYAROV SODERZHIMOGO SKOBOK". (dRUGOJ VARIANT SINTAKSISA OHRANYAEMOJ KOMANDY MOZHET VYGLYADETX TAK: $$ \eqalign{ \&::=\ \{;\\}\cr \&::=\\to\cr &\\cr } $$ oDNAKO PO PRICHINAM, KOTORYE NE DOLZHNY NAS TEPERX INTERESOVATX, YA PREDPOCHITAYU SINTAKSIS, V KOTOROM VVODITSYA PONYATIE OHRANYAYUSHCHEGO ZAGOLOVKA). v |TOM SOCHETANII LOGICHESKOE VYRAZHENIE, PREDSHESTVUYUSHCHEE STRELKE, NAZYVAETSYA "PREDOHRANITELEM". iDEYA SOSTOIT V TOM, CHTO SLEDUYUSHCHIJ ZA STRELKOJ SPISOK OPERATOROV BUDET VYPOLNYATXSYA LISHX PRI TOM USLOVII, CHTO OBESPECHENA NACHALXNAYA ISTINNOSTX ZNACHENIYA SOOTVETSTVUYUSHCHEGO PREDOHRANITELYA. pREDOHRANITELX POZVOLYAET NAM IZBEZHATX VYPOLNENIYA SPISKA OPERATOROV PRI TEH PERVONACHALXNYH OBSTOYATELXSTVAH, KOGDA |TO POLNENIE OKAZALOSX BY NEZHELATELXNYM ILI (ESLI UPOTREBLYAYUTSYA CHASTICHNO OPREDELENNYE OPERACII) NEVOZMOZHNYM. iSTINNOSTX ZNACHENIYA PREDOHRANITELYA YAVLYAETSYA NEOBHODIMYM PREDVARITELXNYM USLOVIEM DLYA VYPOLNENIYA OHRANYAEMOJ KOMANDY KAK CELOGO; |TO USLOVIE, RAZUMEETSYA, NE YAVLYAETSYA DOSTATOCHNYM, POSKOLXKU TEM ILI INYM SPOSOBOM --- S DVUMYA TAKIMI SPOSOBAMI MY VSTRETIMSYA --- DO NEGO ESHCHE DOLZHNA DOJTI POTENCIALXNAYA "OCHEREDX". iMENNO PO|TOMU OHRANYAEMAYA KOMANDA NE RASSMATRIVAETSYA KAK OPERATOR: OPERATOR BEZOGOVOROCHNO VYPOLNYAETSYA, KOGDA NASTUPAET EGO OCHEREDX, A OHRANYAEMAYA KOMANDA MOZHET ISPOLXZOVATXSYA V KACHESTVE STROITELXNOGO BLOKA DLYA OPERATORA. eSLI GOVORITX TOCHNEE, MY PREDLOZHIM DVA RAZLICHNYH SPOSOBA SOSTAVLENIYA OPERATORA IZ NABORA OHRANYAEMYH KOMAND. pOSLE NEKOTOROGO OSMYSLIVANIYA RASSMOTRENIE NABORA OHRANYAEMYH KOMAND PREDSTAVLYAETSYA VPOLNE ESTESTVENNYM. pREDPOLOZHIM, CHTO NAM TREBUETSYA POSTROITX KONSTRUKCIYU, TAKUYU, CHTOBY PRI USLOVII, CHTO NACHALXNOE SOSTOYANIE UDOVLETVORYAET $Q$, KONECHNOE SOSTOYANIE UDOVLETVORYALO $R$. pREDPOLOZHIM DALEE, CHTO NAM NE UDAETSYA NAJTI EDINYJ SPISOK OPERATOROV, KOTORYJ VYPOLNYAL BY |TU RABOTU V LYUBYH SLUCHAYAH. (eSLI BY TAKOJ SPISOK OPERATOROV SUSHCHESTVOVAL, TO MY IMENNO EGO BY I ISPOLXZOVALI I NE VOZNIKLO BY POTREBNOSTI V OHRANYAEMYH KOMANDAH.) oDNAKO NAM MOZHET UDASTXSYA NAJTI NESKOLXKO SPISKOV OPERATOROV, KAZHDYJ IZ KOTORYH BUDET VYPOLNYATX NUZHNUYU RABOTU DLYA NEKoero PODMNOZHESTVA VOZMOZHNYH NACHALXNYH SOSTOYANIJ. k KAZHDOMU IZ |TIH SPISKOV OPERATOROV MY MOZHEM PRISOEDINITX V KACHESTVE PREDOHRANITELYA LOGICHESKOE VYRAZHENIE, HARAKTERIZUYUSHCHEE TO PODMNOZHESTVO, DLYA KOTOROGO |TOT SPISOK PODHODIT, I ESLI U NAS IMEETSYA VPOLNE DOSTATOCHNYJ NABOR PREDOHRANITELEJ, TAKOJ, CHTO IZ ISTINNOSTI $Q$ VSEGDA LOGICHESKI SLEDUET ISTINNOSTX ZNACHENIYA HOTYA BY ODNOGO PREDOHRANITELYA, TO DLYA KAZHDOGO NACHALXNOGO SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO $Q$, MY RASPOLAGAEM KONSTRUKCIEJ, KOTORAYA PEREVEDET SISTEMU V SOSTOYANIE, UDOVLETVORYAYUSHCHEE USLOVIYU $R$, PRICHEM |TOJ KONSTRUKCIEJ SLUZHIT ODNA IZ OHRANYAEMYH KOMAND, CHEJ PREDOHRANITELX IMEL NACHALXNOE ZNACHENIE "ISTINA". chTOBY VYRAZITX |TO, OPREDELIM SNACHALA $$ \::=\ \{\wbox \\} $$ %\ wbox --- white box vs black border: [] GDE SIMVOL "\wbox" VYSTUPAET V ROLI RAZDELITELYA VARIANTOV, V OSTALXNOM NE UPORYADOCHENNYH. oDIN IZ SPOSOBOV FORMIROVANIYA OPERATORA IZ NABORA OHRANYAEMYH KOMAND SOSTOIT V TOM, CHTOBY VKLYUCHITX TAKOJ NABOR V PARU SKOBOK "\kwd{if} \dots \kwd{fi}", PRI |TOM NASH SINTAKSIS DLYA SINTAKSICHESKOJ KATEGORII, IMENUEMOJ "OPERATOR", POPOLNYAETSYA SLEDUYUSHCHEJ FORMOJ: $$ \::=\kwd{if}\ \kwd{fi} $$ tAKIM OBRAZOM, MY POLUCHAEM VOZMOZHNOSTX OB®EDINITX NESKOLXKO OHRANYAEMYH KOMAND V NOVUYU KONSTRUKCIYU. mY MOZHEM PREDSTAVITX SEBE RABOTU, KOTORAYA PROIZOJDET POSLE ZAPUSKA |TOJ KONSTRUKCII, SLEDUYUSHCHIM OBRAZOM. vYBIRAETSYA ODNA IZ OHRANYAEMYH KOMAND, CHEJ PREDOHRANITELX YAVLYAETSYA ISTINNYM, I ZAPUSKAETSYA EE SPISOK OPERATOROV. pREZHDE CHEM MY PEREJDEM K IZLOZHENIYU FORMALXNOGO OPISANIYA SEMANTIKI NASHEJ NOVOJ KONSTRUKCII, UMESTNO SDELATX TRI ZAMECHANIYA. \medskip \item{1.} pREDPOLAGAETSYA, CHTO VSE PREDOHRANITELI OPREDELENY; ESLI |TO NE TAK, T. E. VYCHISLENIE KAKOGO-TO PREDOHRANITELYA MOZHET PRIIESTI K RABOTE BEZ PRAVILXNOGO ZAVERSHENIYA, TO DOPUSKAETSYA, CHTO I VSYA KONSTRUKCIYA NE SMOZHET PRAVILXNO ZAVERSHITX SVOYU RABOTU. \item{2.} vOOBSHCHE GOVORYA, NASHA KONSTRUKCIYA PRIVEDET K NEDETERMINIROVANNOSTI PRI TEH NACHALXNYH SOSTOYANIYAH, DLYA KOTORYH ISTINNY ZNACHENIYA BOLEE CHEM ODNOGO PREDOHRANITELYA, POSKOLXKU OSTAETSYA NEOPREDELENNYM, KAKOJ IZ SOOTVETSTVUYUSHCHIH SPISKOV OPERATOROV BUDET TOGDA VYBIRATXSYA DLYA ZAPUSKA. HIKAKOJ NEDETERMINIROVANNOSTI NE VOZNIKAET, ESLI VSE PREDOHRANITELI POPARNO ISKLYUCHAYUT DRUG DRUGA. \item{3.} eSLI NACHALXNOE SOSTOYANIE TAKOVO, CHTO NI ODIN IZ PREDOHRANITELEJ NE YAVLYAETSYA ISTINOJ, TO MY VSTRECHAEMSYA S NACHALXNYM SOSTOYANIEM, DLYA KOTOROGO NE PODHODIT NI ODIN IZ VARIANTOV, A SLEDOVATELXNO, I VSYA KONSTRUKCIYA V CELOM. zAPUSK PRI TAKOM NACHALXNOM SOSTOYANII PRIVEDET K OTKAZU. \medskip {\sl zAMECHANIE.} eSLI MY DOPUSKAEM TAKZHE I PUSTOJ NABOR OHRANYAEMYH KOMAND, TO OPERATOR "\kwd{if}-\kwd{fi}" SEMANTICHESKI |KVIVALENTEN NASHEMU PREZHNEMU OPERATORU "OTKAZATX". {\sl(kONEC ZAMECHANIYA.)} (v SLEDUYUSHCHEM FORMALXNOM OPREDELENII SLABEJSHEGO PREDUSLOVIYA DLYA KONSTRUKCII \kwd{if}-\kwd{fi} MY OGRANICHIMSYA SLUCHAEM, KOGDA VSE PREDOHRANITELI YAVLYAYUTSYA POLNOSTXYU OPREDELENNYMI FUNKCIYAMI. eSLI |TO NE TAK, TO NUZHNO PEREPISATX VYRAZHENIE S ISPOLXZOVANIEM SIMVOLA $\cand$ PRI DOPOLNITELXNOM TREBOVANII, CHTOBY NACHALXNOE SOSTOYANIE PRINADLEZHALO OBLASTI OPREDELENIYA VSEH PREDOHRANITELEJ.) oBOZNACHIM CHEREZ "\kwd{IF}" OPERATOR \footnote{1} {SL- ABBREVIATURA DLYA Statement List --- SPISOK OPERATOROV. ---{\sl pRIM. PEREV.} } $$ \kwd{if} B_1 \to SL_1 \wbox B_2\to SL_2 \wbox \dots \wbox B_n \to SL_n \kwd{fi} $$ tOGDA DLYA LYUBOGO POSTUSLOVIYA $R$ $$ \wp(IF, R) = (\exists j : 1\le j \le n: B_j) \and (\forall j : 1\le j \le n : B_j \Rightarrow wp(SL_j,R)) $$ % A I E --- |TO \forall I \exist? eTU FORMULU SLEDUET CHITATX TAK: $\wp(IF, R)$ YAVLYAETSYA ISTINOJ DLYA KAZHDOJ TAKOJ TOCHKI V PROSTRANSTVE SOSTOYANIJ, GDE HOTYA BY ODNO ZNACHENIE $j$ IZ OTREZKA $1\le j \le n$, TAKOE, CHTO $B_j$ YAVLYAETSYA ISTINOJ, I GDE, KROME TOGO, DLYA VSEH $j$ IZ OTREZKA $1\le j \le n$, TAKIH, CHTO $B_j$ --- ISTINA, ZNACHENIE $wp(SL_j, R)$ TAKZHE YAVLYAETSYA ISTINOJ. iSPOLXZUYA SIMVOL "\dots", KAK MY UZHE DELALI PRI OPISANII SAMOGO OPERATORA IF, MY MOZHEM PREDLOZHITX INUYU FORMU OPREDELENIYA: $$ \eqalign{ \wp (IF, R) =&(B_1 \or B_2 \or \ldots \or B_n) \and \cr &(B_1 \Rightarrow \wp(SL_1, R)) \and \cr &(B_2 \Rightarrow \wp(SL_2, R)) \and \ldots \and \cr &(B_n \Rightarrow \wp(SL_n, R) )\cr } $$ pONIMANIE |TIH FORMUL NE PREDSTAVLYAET OSOBOGO TRUDA. tREBOVANIEM, CHTOBY ZNACHENIE HOTYA BY ODNOGO PREDOHRANITELYA YAVLYALOSX ISTINOJ, OTRAZHAETSYA FAKT OTKAZA V SLUCHAE, KOGDA ZNACHENIYA DLYA VSEH PREDOHRANITELEJ LOZHNY. kROME TOGO, MY TREBUEM DLYA KAZHDOGO NACHALXNOGO SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO $\wp(IF,R)$, CHTOBY VYPOLNYALOSX $B_j \Rightarrow wp(SL_j, R)$ DLYA VSEH $j$. dLYA TEH ZNACHENIJ $j$, PRI KOTORYH $v_j$ --- LOZHX, |TO SLEDOVANIE ISTINNO NEZAVISIMO OT ZNACHENIYA $wp(SL_j, R)$, T. E. DLYA TAKIH ZNACHENIJ $j$, RAZUMEETSYA, BEZRAZLICHNO, CHTO BUDET DELATX $SL_j$. pRI NASHEJ REALIZACII |TO UCHITYVAETSYA V TOM, CHTO DLYA ZAPUSKA NE BERETSYA $SL_j$ S LOZHNYM NACHALXNYM ZNACHENIEM PREDOHRANITELYA $B_j$. pRI TEH ZNACHENIYAH $j$, DLYA KOTORYH $B_j$ --- ISTINA, DANNOE SLEDOVANIE MOZHET BYTX ISTINOJ TOLXKO V TOM SLUCHAE, KOGDA $wp(SL_j,R)$ TAKZHE YAVLYAETSYA ISTINOJ. pOSKOLXKU NASHE FORMALXNOE OPREDELENIE TREBUET ISTINNOSTI SLEDOVANIYA PRI VSEH ZNACHENIYAH $j$, TO REALIZACIYA NA SAMOM DELE IMEET SVOBODU VYBORA, KOGDA BOLEE CHEM ODIN PREDOHRANITELX YAVLYAETSYA ISTINOJ. kONSTRUKCIYA \kwd{if}-\kwd{fi} PREDSTAVLYAET SOBOJ TOLXKO ODIN IZ DVUH VOZMOZHNYH SPOSOBOV POSTROENIYA OPERATORA IZ NABORA OHRANYAEMYH KOMAND. v KONSTRUKCII \kwd{if}-\kwd{fi} SOSTOYANIE, PRI KOTOROM VSE PREDOHRANITELI IMEYUT LOZHNYE ZNACHENIYA, VEDET K OTKAZU. v NASHEJ VTOROJ FORME MY RAZRESHAEM, CHTOBY SOSTOYANIE, PRI KOTOROM NET NI ODNOGO PREDOHRANITELYA S ISTINNYM ZNACHENIEM, PRIVODILO K PRAVILXNOMU ZAVERSHENIYU; POSKOLXKU V |TOJ SITUACII NE ZAPUSKAETSYA NIKAKOJ SPISOK OPERATOROV, VPOLNE ESTESTVENNO, CHTO PRI |TOM VOZNIKAET SEMANTICHESKAYA |KVIVALENTNOSTX S PUSTYM OPERATOROM. oDNAKO |TO RAZRESHENIE NA PRAVILXNOE ZAVERSHENIE, KOGDA NET NI ODNOGO PREDOHRANITELYA S ISTINNYM ZNACHENIEM, DOPOLNYAETSYA TEM, CHTO RABOTE NE RAZRESHAETSYA ZAVERSHATXSYA, POKA HOTYA BY ODIN PREDOHRANITELX YAVLYAETSYA ISTINOJ. iTAK, POSLE ZAPUSKA PROVERYAYUTSYA VSE PREDOHRANITELI. eSLI NET NI ODNOGO ISTINNOGO ZNACHENIYA PREDOHRANITELYA, TO RABOTA ZAVERSHAETSYA; ESLI ZHE IMEYUTSYA PREDOHRANITELI S ISTINNYMI ZNACHENIYAMI, TO ODIN IZ SOOTVETSTVUYUSHCHIH SPISKOV OPERATOROV ZAPUSKAETSYA, A POSLE EGO ZAVERSHENIYA REALIZACIYA SNOVA NACHINAET OBSHCHUYU PROVERKU VSEH PREDOHRANITELEJ. eTA VTORAYA KONSTRUKCIYA OBOZNACHAETSYA PUTEM ZAKLYUCHENIYA SPISKA OHRANYAEMYH KOMAND V PARU SKOBOK "\kwd{do} .. \kwd{od}". fORMALXNOE OPREDELENIE SLABEJSHEGO PREDUSLOVIYA DLYA KONSTRUKCII \kwd{do}-\kwd{od} YAVLYAETSYA BOLEE SLOZHNYM, CHEM DLYA KONSTRUKCII \kwd{if}-\kwd{fi}; DELO V TOM, CHTO PERVOE VYRAZHAETSYA CHEREZ VTOROE. mY SNACHALA PRIVEDEM |TO FORMALXNOE OPREDELENIE, A ZATEM OB®YASNIM EGO. oBOZNACHIM CHEREZ "DO" OPERATOR $$ \kwd{do} B_1\to SL_1\wbox B_2\to SL_2 \wbox \ldots \wbox B_n \to SL_n \kwd{od} $$ I CHEREZ "IF" OPERATOR, POLUCHAEMYJ PUTEM ZAKLYUCHENIYA TOGO ZHE NABORA OHRANYAEMYH KOMAND V PARU SKOBOK "\kwd{if} ... \kwd{fi}". eSLI USLOVIYA $H_k(R)$ ZADAYUTSYA V VIDE $$ H_0(R)=R \and \non (\exists j: 1\le j \le n : B_j) $$ I PRI $k>0$ $$ H_k(R)=\wp(IF, H_{k-1} (R)) \or H_0(R) $$ TO $$ \wp(DO,R) = (\exists k: k\ge 0 : H_k(R)) $$ zDESX INTUITIVNO MY PONIMAEM $H_k(R)$ SLEDUYUSHCHIM OBRAZOM: |TO SLABEJSHEE PREDUSLOVIE, TAKOE, CHTO KONSTRUKCIYA \kwd{do}-\kwd{od} ZAVERSHIT SVOYU RABOTU POSLE NE BOLEE CHEM $k$ VYBOROK OHRANYAEMYH KOMAND, PRICHEM SISTEMA OSTANETSYA V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM POSTUSLOVIYU $R$. pRI $k=0$ TREBUETSYA, CHTOBY KONSTRUKCIYA \kwd{do}-\kwd{od} ZAVERSHILA RABOTU, NE PROIZVODYA VYBORKI KAKOJ-LIBO OHRANYAEMOJ KOMANDY, T. E. NE DOPUSKAETSYA SUSHCHESTVOVANIYA KAKOGO-LIBO PREDOHRANITELYA S ISTINNYM ZNACHENIEM, CHTO I VYRAZHENO VTORYM LOGICHESKIM SOMNOZHITELEM. pRI |TOM NACHALXNAYA ISTINNOSTX $R$ OCHEVIDNYM OBRAZOM YAVLYAETSYA NEOBHODIMYM USLOVIEM DLYA KONECHNOJ ISTINNOSTI $R$, CHTO I VYRAZHENO PERVYM LOGICHESKIM SOMNOZHITELEM. pRI $k>0$ NAM NUZHNO RAZLICHATX DVA SLUCHAYA: LIBO NI ODIN IZ PREDOHRANITELEJ NE IMEET ISTINNOGO ZNACHENIYA, NO TOGDA DOLZHNO VYPOLNYATXSYA USLOVIE $R$, I |TO PRIVODIT NAS KO VTOROMU LOGICHESKOMU SLAGAEMOMU; LIBO HOTYA BY ODIN PREDOHRANITELX YAVLYAETSYA ISTINOJ, I TOGDA SOBYTIYA RAZVIVAYUTSYA TAK, KAK PRI ODNOKRATNOM ZAPUSKE OPERATORA "IF" (V NACHALXNOM SOSTOYANII, KOTOROE NE MOZHET PRIVESTI K NEMEDLENNOMU OTKAZU VSLEDSTVIE OTSUTSTVIYA ISTINNYH ZNACHENIJ PREDOHRANITELEJ). oDNAKO POSLE TAKOGO VYPOLNENIYA, PRI KOTOROM PROIZVODILASX VYBORKA ODNOJ OHRANYAEMOJ KOMANDY, NAM NEOBHODIMA GARANTIYA POPADANIYA V SOSTOYANIE, TAKOE, CHTOBY POTREBOVALOSX NE BOLEE CHEM $(k-1)$ DALXNEJSHIH VYBOROK DLYA DOSTIZHENIYA ZAVERSHENIYA RABOTY V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM $R$. v SOOTVETSTVII S NASHIM OPREDELENIEM, TAKIM POSTUSLOVIEM DLYA |TOGO OPERATORA "IF" SLUZHIT $H_{k-1}(R)$. sOGLASNO POSLEDNEJ STROKE, OPREDELYAYUSHCHEJ $\wp(DO, R)$, DOLZHNO SUSHCHESTVOVATX TAKOE ZNACHENIE $k$, CHTOBY POTREBOVALOSX NE BOLEE CHEM $k$ VYBOROK DLYA OBESPECHENIYA ZAVERSHENIYA RABOTY V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM POSTUSLOVIYU $R$. {\sl zAMECHANIE.} eSLI MY DOPUSKAEM TAKZHE I PUSTOJ NABOR oxRANYAEMYH KOMAND, TO V SILU SKAZANNOGO OPERATOR "\kwd{do} \kwd{od}" SEMANTICHESKI |KVIVALENTEN NASHEMU PREZHNEMU OPERATORU "PROPUSTITX". {\sl (kONEC ZAMECHANIYA.)} \bye