Haaroitus (ohjelmointi)

Haaroittuminen ohjelmoinnissa on toiminto, jota käytetään tapauksissa, joissa tietyn komentosarjan suorittamisen tai suorittamatta jättämisen täytyy riippua tietyn ehdon täyttymisestä tai täyttymättä jättämisestä. Haaroitus on yksi kolmesta strukturoidun ohjelmoinnin perusrakenteesta (komentojen ja silmukan peräkkäisen suorittamisen ohella) .

Haaroittamisen tärkeimmät toteutusmuodot imperatiivisissa ohjelmointikielissä ovat ehdollinen operaattori (operaattori if) ja moniarvoinen valintaoperaattori (kytkin, case, switch). Varhaisissa matalan tason kielissä haarautuminen toteutetaan ehdollisen haaraoperaattorin kautta .

Ehdollinen operaattori

Ehdollinen operaattori toteuttaa tiettyjen komentojen suorittamisen edellyttäen, että jokin looginen lauseke (ehto) saa arvon "true" true. Useimmissa ohjelmointikielissä ehdollinen lause alkaa avainsanalla if(käännetty  englannista  -  "jos"). On olemassa seuraavat ehdollisen operaattorin muodot - yksi haara ja kaksi.

Kun ehtolausetta suoritetaan yhdellä haaralla if <условие> then <команды> end, ehto arvioidaan ja jos se on tosi, suoritetaan komennot avainsanaan asti end, muuten ohjelman suoritus jatkuu ehdollista lausetta seuraavalla komennolla. Matalilla kielillä ( asentajat ) tämä on ehdollisen operaattorin ainoa käytettävissä oleva muoto. Joillakin kielillä käytetään erityistä avainsanaa ehdolliseen operaattoriin, jolla on yksi haara (yleensä tämä then, käännetty  englannista  -  "that").

Kun suoritetaan kaksihaaraista ehdollista operaattoria if <условие> then <команды1> else <команды2> end , jos ehto on tosi, avainsanan jälkeiset komennot suoritetaan ; jos ehto on thenepätosi, avainsanan jälkeiset komennot suoritetaan else. Jos on tarpeen tarkistaa useita ehtoja peräkkäin, on mahdollista peräkkäin ehdolliset lauseet:

jos ehto 1 komentaa 1 else if ehto 2 sitten komentaa 2 else jos ehto 3 sitten komentaa 3 ... else jos ehto N + 1 sitten komento N + 1 else komennot loppuvat ; _

Tässä tapauksessa ehdot tarkistetaan peräkkäin, ja heti kun tosi täyttyy, vastaava komentosarja suoritetaan ja suoritus siirtyy ehdollista käskyä seuraavaan komentoon. Jos mikään ehdoista ei täyty, haaran komennot suoritetaan else.

Useat ohjelmointikielet sisältävät erityisen rakenteen ehdollisten lausekkeiden peräkkäin, jonka avulla voit kirjoittaa useita haaroja hieman kompaktimmin ja vähemmän alttiita kirjoitusvirheille:

if ehto1 sitten komennot1 elsif ehto2 sitten komennot2 elsif ehto3 sitten komennot3 ... else komennot loppuvat ; tämän käskyn suoritusjärjestys vastaa täsmälleen yllä olevaa yksinkertaisten jos-niin-else-lauseiden sarjaa, ja ero on puhtaasti formaalinen: useiden ehdollisten lausekkeiden sijasta tämä konstruktio on yksi kokonaisuus ja sisältää ylimääräisen avainsanan elsif, joka vaatii toisen lauseen. kunto itsensä jälkeen.

Toteutukset

Pascal peri Algol -60:stä syntaksin , jonka mukaan ehdollisen operaattorin haaroihin voidaan sijoittaa vain yksi komento. beginSiksi, jotta sinne mahtuisi enemmän komentoja, ne ryhmitellään yhdistetyksi lauseeksi käyttämällä ja avainsanaparia end. Muu haara on valinnainen. beginja endne ovat välttämättömiä vain, jos operaattoreita on useita (esimerkiksi koodin yhtenäisyyden vuoksi ). Esimerkissä Pascalin valintaoperaattori:

Jos ehto aloita lausekkeet ; _ end else begin -lauseet ; loppu ;

Ehdollisen operaattorin tarvetta Algolissa ja Pascalissa on kritisoitu sen alusta lähtien. Kriitikot sanoivat, että lukuisat yhdistelmäkäskyt sotkevat ohjelmaa, häiritsevät normaalia sisennystä ja aiheuttavat virheitä (jos unohdat yhdistetyn lauseen sinne, missä sitä tarvitaan if-lauseen viimeiseen haaraan, kääntäjä ei huomaa mitään, mutta ohjelmaa suoritettaessa lauseryhmästä, joka tulee suorittaa tässä haarassa, ehdon mukaan vain ensimmäinen suoritetaan, kaikki loput - aina). Seuraavat kielten sukupolvet - Algolin jälkeläiset yrittivät päästä eroon tästä puutteesta. Niiden joukossa on kolme laajalti tunnettua kieltä: Algol-68 , Modula-2 ja Ada . If-lauseen rakenne niissä on lähes sama, yksittäisiin avainsanoihin asti:

  • Algol-68:
jos kunto ... fi ;
  • Moduuli-2
JOS ehto 1 NIIN komento 1 ELSE JOS ehto 2 NIIN komento 2 ... MUUTA komento N LOPPU ;
  • Ada
if ehto1 sitten komennot1 else if ehto2 sitten komennot2 ... else commandsN end if ;

Kaikissa tapauksissa "komentoX" on mikä tahansa määrä puolipisteillä erotettuja lauseita. Kaikissa tapauksissa kaikki ehdollisen lauseen haarat ensimmäistä lukuun ottamatta ("sitten" haarat) ovat valinnaisia ​​ja ne voidaan ohittaa. Jos "muu"-haaraa ei ole eikä mikään ehdoista täyty, ohjaus siirretään ehdollisen täydennysavainsanan (END, FI tai END IF) jälkeiseen komentoon.

C :llä ja C++ :lla (ja niiden jälkeen Java , C# , PHP ja monet muut kielet) on ehdollinen operaattori, joka on rakenteeltaan samanlainen kuin Pascal. beginErona on, että ehto on kirjoitettava sulkeisiin ja avainsanojen sijasta endkäytetään kiharoita {}:

jos ( < ehto > ) { < operaattorit > } muu { < operaattorit > }

Nemerlessä , toisin kuin useimmissa kielissä , joissa operaattorilla ifvoi olla joko yksi tai kaksi haaraa, operaattorilla if(syntaksi on täysin samanlainen kuin C-kielellä) on oltava kaksi haaraa. Yksihaarainen ehdollinen operaattori alkaa avainsanalla when, lisäksi kielellä on toinen ehdollinen operaattori - unless, joka on "käänteinen kun" - siinä ehdollisen haaran komennot suoritetaan, jos ehto on epätosi.

when ( ehto ){ lausekkeet } paitsi jos ( ehto ) { lauseet }

Forthissa ehdollisen operaattorin muoto on erilainen kuin muilla kielillä jälkiliitteen merkintätavasta ja pinojärjestelystä johtuen. Ehdollinen operaattori koostuu kolmesta sanasta IF ELSE THEN[1] .

< ehto > JOS < lauseke _1_ jos _ ehto _ on tosi > MUU < lauseke _2_ jos _ ehto _ on epätosi > NIIN

Tässä <условие>se vain työntää arvon pinon päälle, IFjäsentää lipun ja jos:

  • se ei ole yhtä suuri kuin nolla, silloin lausekkeet suoritetaan ELSEtai asti THEN;
  • jos se on yhtä suuri kuin nolla, lausekkeet välillä ELSEja suoritetaan THEN.

Jos puuttuu ELSE, saadaan yksihaarainen valitsin: lausekkeet välillä IFja THENsuoritetaan vain, jos lippu on nollasta poikkeava.

Fortranilla oli aluksi vain aritmeettinen IF , jossa lausekkeen etumerkistä riippuen siirryttiin johonkin kolmesta etiketistä. Esimerkiksi osa toisen asteen yhtälön ratkaisijarutiinin koodista:

DN = B * B - 4 * A * C IF ( DN ) 90 , 10 , 10 10 D = SQRT ( DN ) X1 = ( - B + D ) / ( 2 * A ) X2 = ( - B - D ) / ( 2 * A )

Sitten lisättiin loogiset (loogiset) lausekkeet ja looginen IF yhdellä lauseella, jonka arvioi GOTO, myöhemmin - rakenteellinen IF (useita ehtoja), esimerkiksi:

DN = B * B - 4 * A * C _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 * A ) ELSE ! (ei koodia negatiiviselle erottajalle) END IF

Perl tukee moniehtoista if-rakennetta sekä lauseen muokkaajia, jotka kirjoitetaan suoritettavan käskyn osan jälkeen. Esimerkiksi seuraavat kaksi esimerkkiä ovat toiminnaltaan identtisiä:

if ( $a == 0 ) { ++ $nolla_luku ; } ++ $nolla_luku , jos $a == 0 ;

Jos sijaan, voit kirjoittaa ellei, mikä saa aikaan ehdollisen lausekkeen arvon käänteisen ennen tarkistamista. Sama toimenpide, ellei:

++ $nolla_luku, ellei $a != 0 ;

Yhdistetyssä lauseessa (lohkossa) vain rakennemuoto on sallittu, ei muuntaja. Esimerkiksi:

if ( $a == 0 ) { ... } else if ( $a > 0 ) { ... } else { ... }

Lopullista avainsanaa ei tarvita, koska ehtojen mukaiset lauseet on muotoiltava lohkoiksi {…}.

Elsif-haaroihin ei ole vastaavaa ellei.

Erlang käyttää kahta ehdollista lausetta - if ja case. Molemmilla on tulosarvo, joka on sama kuin suoritetun haaran viimeisen käskyn arvo ja niitä voidaan käyttää (määritetty nimeen, välitetty funktiolle...), joten siinä ei ole erillistä kolmiosaista ehtolauseketta . Case-lauseessa suoritetaan Pattern Matching , jossa on mahdollisuus lisätä ehtoja vertailuarvoihin ja if-lauseessa vain ehtotestaus. Suojatestit mahdollistavat rajoitetun joukon toimintoja ja sisäänrakennettuja toimintoja.

Tapausesimerkki (tapahtumamerkinnän poistaminen aikapuusta):

{ NewEBW , NewEBN } = case dict : etsi ( EBN , Node ) of error -> { EBW , EBN }; { ok , Expiry } -> { gb_trees : delete_any ({ Expiry , Node }, EBW ), dict : erase ( Node , EBN )} end ,

Esimerkkejä jos:

if NeedLater -> erlang : send_after ( trunc ( 1000 * ( 1 + Kulunut )), self (), i_apply_nodes_portion ); totta -> nop end , After2 = jos %% Jos se oli liian kauan sitten, ajoita aikakatkaisu välittömästi. After1 =< ? EXPIRY_STEP_MIN -> ? EXPIRY_STEP_MIN ; After1 >= ? EXPIRY_STEP_MAX -> ? EXPIRY_STEP_MAX ; tosi -> After1 end ,

Monivalintaoperaattori

Kytkimen suunnittelussa on useita (kaksi tai useampia) haaroja. Kytkin suorittaa yhden tietyn haaran riippuen arvioidun avainlausekkeen arvosta. Perimmäinen ero tämän käskyn ja ehdollisen operaattorin välillä on, että lauseke, joka määrittää suoritettavan haaran valinnan, ei palauta loogista, vaan kokonaislukuarvoa tai arvon, jonka tyyppi voidaan heittää kokonaisluvuksi. Jotkut kielet sallivat joidenkin ei-kokonaislukutyyppisten lausekkeiden (esimerkiksi tekstimerkkijonojen) käytön kytkimessä.

Nykyaikaisen syntaktisen rakenteen prototyyppi oli vanhoissa ohjelmointikielissä käytetty hyppykäsky. Tämä komento määritti valitsinlausekkeen, joka palautti kokonaisluvun arvon ja joukon tunnisteita. Kun komento suoritettiin, lauseke arvioitiin ja sen arvoa käytettiin sen etiketin numerona (komentoluettelossa), johon siirryttiin. Tällaisia ​​rakenteita oli esimerkiksi ohjelmointikielissä Fortran ("laskettu GOTO") ja BASIC . Suunnittelun houkutteleva puoli on sen melko korkea tehokkuus: halutun haaran (hyppymarkkerin) määrittämiseksi ei ole tarpeen verrata valitsinlausekkeen tulosta peräkkäin moniin arvoihin, riittää, että tallennetaan joukko ehdottomia hyppykäskyjä. tarvittavat osoitteet muistissa niin, että komentoa suoritettaessa haluttu elementti lasketaan suoraan lausekearvoista. Tässä tapauksessa komennon suorittamisen nopeus ei riipu tarrojen määrästä. Nykykielissä kytkinkäskyn toteutus toteutetaan usein myös hyppytaulukona, joka koostuu ehdottomista hyppykäskyistä vastaaviin koodinpätkiin. Arvioitava lauseke muunnetaan hyppytaulukon siirtoarvoksi, joka määrittää suoritettavan komennon. Kielessä, jossa valitsinlausekkeella voi olla ei-kokonaislukuarvo, ei läheskään aina ole mahdollista suoraan arvioida haluttua kytkinrakenteen haaraa, joten niissä käytetään muita menetelmiä suoritusten optimointiin.

Nykyaikaisissa korkean tason ohjelmointikielissä kytkinkomennolla on yleensä nimi switch(käännetty  englannista  -  "kytkin") tai case(käännetty  englannista  -  "tapaus"). Laskennallinen tarravalinta voidaan kuitenkin säilyttää nykyaikaisissa matalan tason ohjelmointikielissä, kuten Siemensin valmistamien ohjelmoitavien S7-300- ja S7-400 - logiikkaohjaimien STL-ohjelmointikielen JL-käsky.

Esimerkiksi C:ssä komennon syntaksi on:

kytkin ( i ) { tapaus 0 : tapaus 1 : // lauseiden sarja break ; case 2 : // lauseiden sekvenssi break ; oletus : ; }

Tässä i on valitsinlauseke, jonka on oltava tyypiltään castable-tyyppinen kokonaisluku. Jokainen suorituksen haara alkaa avainsanalla case, jota seuraa sen lausekkeen arvo, jolla tämä haara suoritetaan. Mielenkiintoinen C-kielen ominaisuus on, että siinä kytkin tulkitaan täsmälleen komennona hypätä lasketun nimiön päälle, ja haaraotsikot ( case значение :) toimivat nimikkeinä. Switch-käskystä poistumiseen haarakoodin valmistumisen jälkeen käytetään erityistä komentoa break. Jos haarassa ei ole tällaista komentoa, valitun haaran koodin suorittamisen jälkeen alkaa sitä seuraavan koodin suoritus. Tätä ominaisuutta voidaan käyttää optimointiin, vaikka se voi aiheuttaa vaikeasti löydettäviä virheitä (jos ohjelmoija vahingossa jättää väliin, kääntäjä ei anna virhettä, mutta ohjelma toimii väärin). Oletushaara suoritetaan, kun mikään muu haara ei sovellu.

C-kytkinkomennon syntaksi on peritty monille kielille, mutta sen semantiikka ei aina ole täysin C:n kaltainen. Esimerkiksi C# antaa sinun käyttää merkkijonotyypin valitsinlauseketta ja asianmukaisia ​​tunnisteita.

Loogisten lausekkeiden laskennan ominaisuudet

Ehdollisia lausekkeita sisältävän ohjelman suoritusjärjestykseen voi merkittävästi vaikuttaa kielessä käytettyjen ehdollisten lausekkeiden arviointilogiikka. Kun ehto on monimutkainen boolen lauseke, kuten "f(x) > 0 JA g(y) > 0", sen tuloksen arviointiin on kaksi strategiaa:

  • Täydellinen laskenta: laske f(x), g(y), vertaa tuloksia nollaan ja suorita sitten JA-operaatio tuloksille. Samoin tekee esimerkiksi Visual Basic.
  • Epätäydellinen laskenta: laske f(x), vertaa arvoa nollaan. Jos vertailun tulos on "tosi", arvioi loput lausekkeesta. Jos ensimmäinen ehto on epätosi, ohita toinen ehto, mukaan lukien siihen sisältyvän g(y):n laskenta, koska "AND"-operaation kohdalla, jos jokin operandi on epätosi, koko lauseke on ilmeisen epätosi.

Toinen vaihtoehto on yleisin teollisuuskielille (erityisesti Algol, Fortran, C++, C, Java, JavaScript, ECMAScript, JScript, C#, Python). Näillä kielillä on tiukka sääntö: "Looginen lauseke arvioidaan aina vasemmalta oikealle ja sen arviointi pysähtyy heti, kun koko lausekkeen tulos on määritelty." Tämä tarkoittaa, että jos lauseke koostuu useista osaehdoista yhdistettynä AND-operaattoriin (AND), lausekkeen arviointi pysähtyy heti, kun jokin osaehdoista osoittautuu epätosi (koska "epätosi JA mikä tahansa arvo" johtaa aina "epätosi") ja päinvastoin, jos useita aliehtoja yhdistetään TAI-operaattoriin (OR), arviointi pysähtyy ensimmäisen tosi aliehdon jälkeen, koska tässä tapauksessa koko lauseke on tosi, jatkoarvioinnista riippumatta. Mutta lauseketta, joka sisältää Exclusive OR -operaattorin (XOR), ei voida täysin arvioida, koska yksi sen arvoista ei voi määrittää koko lausekkeen laskennan tulosta.

Kielet Ada ja Erlang käyttävät eri avainsanoja näille muunnelmille: sanat ja ja tai tarkoittavat täydellistä arviointia ja ja sitten, tai muuten (Ada) ja myös, orelse (Erlang) - epätäydellinen. Erlangissa andalsella ja orelsella on alhaisempi prioriteetti kuin vertailuoperaattoreilla, mikä välttää sulkeita alkeistermien ympärillä. Visual Basic .NET -kielellä on samanlaiset avainsanat: AndAlso ja OrElse.

Osaehtojen kiinteä arviointijärjestys (looginen lauseke arvioidaan aina vasemmalta oikealle) otetaan käyttöön, jotta voidaan hallita lausekkeen arviointijärjestystä ja laittaa siihen ensin ne ehdot, jotka tulee ensin arvioida. Muuten, tällä tavalla loogiset lausekkeet eroavat aritmeettisista lausekkeista, joiden osalausekkeiden arviointijärjestystä (ellei sitä määrää operaatioiden prioriteetti ja assosiaatio) useimmissa kielissä ei määritetä kielillä ja se voi olla erilainen erilaisia ​​tapauksia.

Tämän tietyn suorituslogiikan valinta johtuu siitä, että sen avulla voit yksinkertaistaa riippuvia elementtejä käyttäviä loogisia lausekkeita. Klassinen esimerkki on lineaarinen haku taulukossa:

// Hae kokonaislukutaulukosta Pascal-kielellä // Parametrit - haluttu arvo ja avoin kokonaislukutaulukko // Tulos - löydetyn elementin indeksi tai -1, jos elementtiä ei löydy -toiminto Etsi ( e : kokonaisluku ; var a : kokonaislukutaulukko ) : kokonaisluku ; _ _ var i : kokonaisluku ; aloita i := 0 ; while ( i <= Korkea ( a )) JA ( a [ i ] <> e ) tekevät inc ( i ) ; //!!! jos i <= Korkea ( a ) niin Etsi := i else Etsi := - 1 ; loppu ;

Ohjelman toteuttama algoritmi on varsin ilmeinen, mutta toteutuksessa on yksi hienous (katso huutomerkeillä merkitty viiva): silmukkaehto koostuu kahdesta AND-operaattorilla yhdistetystä osasta. Ensimmäinen aliehto tarkistaa, onko indeksi i mennyt taulukon ulkopuolelle, toinen tarkistaa, onko taulukon nykyinen elementti sama kuin haluttu arvo. Jos taulukko ei sisällä haluttua arvoa, niin viimeisen alkion tarkistamisen jälkeen muuttujan i arvo kasvaa yhdellä; seuraavassa iteraatiossa ensimmäinen aliehto on epätosi ja silmukka päättyy tarkistamatta toista aliehtoa. Jos loogiset lausekkeet arvioitiin täysin, niin jos taulukossa ei ole elementtiä viimeisen iteraation jälkeen, tapahtuisi virhe: yritys määrittää a[i] aiheuttaisi virheellisen muistin käytön.

On huomattava, että lausekkeen arvon epätäydellisen arvioinnin lisäksi myös aliehtojen kiinteällä arviointijärjestyksellä on tässä tärkeä rooli: koska rajojen ulkopuolisten joukon tarkistus kirjoitetaan ensin, se tulee aina olemaan suoritetaan ennen halutun arvon saavuttamisen tarkistusta. Jos osalausekkeiden arviointijärjestys olisi määrittelemätön, olisi mahdotonta taata annetun ohjelmafragmentin oikeellisuutta.

Loogisten lausekkeiden täydellisellä laskennalla yllä oleva algoritmi olisi kirjoitettava suunnilleen seuraavassa muodossa:

// Hae kokonaislukujoukosta Pascal-kielellä // Hypoteettinen muunnelma loogisten lausekkeiden täydellisellä arvioinnilla // Parametrit - haluttu arvo ja avoin kokonaislukutaulukko // Tulos - löydetyn elementin indeksi tai -1, jos elementti ei löytynyt toimintoa Etsi ( e : kokonaisluku var a : kokonaislukujono ) : kokonaisluku ; _ _ var i : kokonaisluku ; f : Boolen ; // lisämuuttujan silmukan lopetuslippu begin i := 0 ; f := false ; Mutta ei f do jos i > Korkea ( a ) sitten f := tosi muuten jos a [ i ] = e sitten f := tosi else inc ( i ) ; jos i <= Korkea ( a ) niin Etsi := i else Etsi := - 1 ; loppu ;

Kuten näette, meidän piti keinotekoisesti asettaa järjestys, jossa poistumisolosuhteet laskettiin, ja ottaa käyttöön lisämuuttuja. Tällaisten temppujen välttämiseksi otetaan käyttöön loogisten lausekkeiden epätäydellinen arviointi.

Huomautus: Yllä oleva koodi on esimerkki IF-käskyn käytöstä, mutta ei enempää. Tätä koodia ei voida käyttää sääntönä algoritmien kirjoittamiseen Pascalissa.

Optimaalinen algoritmi luvun löytämiseksi taulukosta on:

toiminto Etsi ( e : kokonaisluku ; var a : kokonaislukutaulukko ) : kokonaisluku ; _ _ var i : kokonaisluku ; alkaa Tulos := - 1 ; for i := Matala ( a ) - Korkea ( a ) aloita jos a [ i ] = e aloita sitten Tulos : = i ; tauko ; loppu ; loppu ; loppu ;

Muistiinpanot

  1. Forthilla on operaattori <условие> ?DUP <выражение>, joka kopioi lausekkeen, jos ehto on tosi