FUNKCIONALNO PROGRAMIRNI SISTEMX Borut Robifl. Jurij Silc in Branko Mihavi lovifl Institut 'Jotet Stefan', Ljubljana UDK: 681.3.06 Redukcijske raflunalniSke arhitekture zahtevajo funkcionalno programirne je- zike. Funkcionalno programirni sisteni predstav1jajo enega izmed možnih na- Cinov funkcionalnega programiranja. fieprav eo SibkejSi od lambda ratiuna, pa so predvsea zaradi preglednosti in hierarhiCne zgradbe primernejSi 2a praktifino uporabo. FUNCTIONAL PROGRAMMING SYSTEMS - Some nev kinds of coroputer architectures re- quire functional programming languages. Besides lambda style there is another functional style o( programm mg , namely functional programming 5ystems. These systems have properties uhich make them more useful than lambda style although they are not as powerfi.il. U vo d Sodobne raCunalniSke arhitekture. ki teme- ljijo na paralelnem procesiranju, lahtevajo progranske jezike brez stranskih uCinkov. Primer takega jezika je LISP, ki teinelji na laabda raCunu. V lambda raflunu so izvor nuvih funkcij lambda izrazi skupaj s pripadajodjmi pravili zamene. Z lambda izrazi 1 ohko delini-- ramo vse izraCunljive (unkcije s poljubno mnogo argumenti. To moC lambda računa pa je zaradi nepreglednosti njegovih izrazov prakti- Cno zelo težko izkoristiti. Laobda raCun je le en nafiin ti. funkcionalne- ga programiranja. Orug pristop k (unkcianalne- •u programiranju pa predstavljajo funkcianalno programirni sistemi ( v nadaljnem FP si&temi ). Ti sisteni so SibkejSi od lambda ra&una, toda fflnogo preglednejSi. Tudi FP siste.ii ne poznajo stranskih ufiinkov. Program v FP eistemu (v nadaljnem FP prograrc) je funkcija, ki preslika en objekt v drugega. Objekt je bodisi a) nedefiniran , b) atom ali pa c) zaporedje, sestavljeno iz atomov ali za- poredij. Zaporedje je lahko tudi pi-azno. FP program je lahko a) osnoven, b) sestavljen na podlagi funkcijske oblike, t.j. j)i'avila, ^ ka- terim lahko obstojetie FP progi-ame in objekte sestavimo v nov FP program ali pa c) je defi- nlran s pomofijo definicije. FP prograru i deluje nad objektom x in vrne rezultat f:x. Pravimo, da f:x opisuje uporabo (aplikacijo) programa ( nad objektom x. Podobno kot lamda raflun ima tudi FP sistem zelo enostavno semantiko. in R P c :=0j tor i : = 1 c := o to n tlo + aCi]*bCi3 j edLjira lneg programa Ce zapiSemo zaporedje stavkov za izraflun ska- larnega produkta dveh vektorjev v tnera od prc- ceduralnih nekatere operacije so opisane s simboli, ki so porazdeljeni po programu, namesto da bi bile opisane s simbolom r\a enem mestu. FP program za raflunanje skalarnega lahko definiramo kot: DEF SP = (/+)o(a*)oTrans produktd Sestavljajo ga tri osnovne funkcije: BeStt-va- nje + , mnoJenje * in transpozicija Trans tfi tri (unkcijske oblike: vstavljanje / , upora- ba nad vseoii elementi a in kampozitun o . Progran ima sledefl pomen : 367 i Co<*)oTrans t razbij vhodna vektorja v S istoleZnih parov izrafiunaj produkte vseh taka dobljenih parov seStej vse daliljtne produkte Uporabo (apl ikacii jo) funkcijt- ( riod argumentom x zapiše.no z f :x . Tedaj lahko izvajanje zgor- njega prugi-aiiia naJ aLgumenloiTi, ki je par vek- tnrjev << 1 1?13>,<6,S,'»>>, up iS*.no tako: SP:< <1 ^.^^i.S,^ > = - (/•) {.>•) Trans:-; i ! ,2 ,3> , •'. 6,5 , 4> > = - f/+i <*«):< Trsns:< < 1 ,2 ,3> , '.6 ,3 ,4> > ) = / < 2 > - H : •' i , • : •' •! 0,12 > > = • *:<3,4> > = = 23 Opa:i.T>- slede^e lastnosti programa SP : ,<1 rsC.unanje tpjielji le na dveh pravilih: na pr.ivilu upcirabe funkoije nad objektom in lii'cfvi.lu razVoja funkcijske oblike ; ijl f.iT.grain js hi erarhifien, kar poraeni, da je 5fcr.f-.jv1 jsn na podlagi pravil, ki enostav- n«j"j dele prugrama sestavljajo v kompleks- Tudi ti enostavnejSi deli sa sestav- iia pudlagi istih pravil, ali pa so clenipntfirni (osnovne funkcije ali objekti); j* statiCen, kar pomeni, da lahko njegov pomt>n razumema Ke, Ce ga.beremo z desne v ievo , sevtdd ob predpostavki, da poznamo pnmpn o&novnih funkcij in funkcijskih oblik iieluje nat) celimi vektorji hkrdti uporabifTio ga lahko nad poljubno dolgimi vektocji, saj ne vsebuje nobene konstante ; ni? pciimenuje svojih argumentov , ker deluje ln nad njihovimi vrednostmi . J ljeni 1no pragrainicni s i s t FP sisten sestavljajo: objektov 0 F funkoij, ki presl ikava jo objekte v objekte - operator : aplikacije (unkcije nad abjektom - mncSica E f ui^ikci jsk ih oblik, 5 katerimi se- stavljamo obstojefie Junkcije in objekte v nove funlicije - iiinoifica D definictj, ki nekaterim funkcijam iv F prirejajo nova imena Obiakt Primeri objektov : l 1.5 0 AB3 Prvi in zadnja objekta so nedeliniraru . Aplikaciia FP slstem ima sano eno operacijo, ki jo imenu- jeno aplikacija. Ce je f funkcija in x objtkt, potera aplikacijo ( nad x zapiSemo z i:x . Tu je f operator, x pa operand aplikacije f:x . f:x je objekt, ki je rezultat i2vrSitvt funk- cije I nad objektom x. Primeri aplikacije : +:<1,2>=3 2:» Funkci ie Vse funkoije preslikavajo objekte v objekte in tudi ohranjajo nedefiniranost, torej velja f:l = i za vsako funkcijo f . Funkcija je lahko : - osnovna ( primitivna ) ; - sestavljena j - definirana . Osnovne funkcije podaja ie sam FP sistem. Sestavljeno lunkcijo dobimo na podlagi obsio- jefiih osnovnih, sestavljenih ali definiranih lunkcij, Oe nad njimi uporabimo eno ali vefl pravil sestavljanja tj. funkcijskih oblik. Oe je funkcija osnovna, je tudi sestavljena. Delinirana funkcija je (unkcija i, za katero v ono2ici definicij obstaja detinicija oblike DEF i = E(f ,g, . . . ,h), pri Cemer je desni del definicije sestavljena funkcija. Razlikujemo dva primera, ko je f:x = 1 . te se rafiunanje (:x konfia v konCno mnogo korakih in vrne vrednost 1 , je i nedefinirana pri x. To- rej se izraSun t nad x konfla, vendar ne vrne Bniselnega rezultata. Ce pa se izrattun { nacl x ne konfia v konflno mnogo korakih, zopet velja f:x = 1 , vendar tokrat pravimo, da je f pri x neustavljiva . Zaleljeno je, da FP sisten vsebuje Siroko upo- raben nabor osnovnih funkcij. V naslednjih prinerih je opisanih nekaj osnovnih funkcij, stroge definicije pa so podane v dodatku A. 'Selekoija' je funkcija i, ki vrne i-ti ele- merit danega zaporedja. fle takega elementa ni, vrne vrednost X . Primeri selekcije: 3:=1 1 :<<1 ,2>,3> = <1,2> 'Rep' je funkcija tl, ki izlotfi prvi element zaporedja in vrne njegav preostanek . Primeri: tl:= tl:=0 tl:0 =1 'Atom' ugotovi, 6e je dani objekt atom. Pri- oeri atooa: Atom:B=T Atom:-F Otijekt. je lahko: - nEdefiniran, in ga oznafiima z 1 j - ihGn ; - zapcn-edje < x, , x2 ,. . . , xn >, kjer je X|Objekt. ?5;ioredje, ki ne vsebuje nobenega elementa aznaaiino z 0. Zaparedje je nedef inirano, torej .--.',ako 1 , He vsabuje vsaj en nedefiniran ele- ifiit. Tsrej irbrana itmojica atomov A in pravilo ses- tjvljanja v zsporedje doloCata mnoSico objek- tov 0. ?a mnolfico atomov navacfno izberemo mno- 2ico konfinih nizav Crk, cifer ali posebnih znatov. Atoma T in F uporahl jano za opis logi- Knih vrednosti True in False. 'Enakost' je lunkoija eq, ki ugotavlja enakost dveh eleaentov zporedja. Prineri enakosti: eq:=F eq: ,D>>=T 'Praznast' je funkcija null, ki ugotovi, tie je zaporedje prazno. Prigier: null:0 =T null: i=l null:=F 'Obrat' je lunkoija reverse, ki obrne vrstni red elementov zaporedja. Primer obrata: reverse:> = <,B,A> 368 'Transpazicija' je funkcija trans, ki istoleJ- ne elemente zaporedij zdruJi v nova zaporedja. Primer transpoziclje: trans:<,,,> = = <,,> Funkciiske oblike Funkcijska' oblika je izraz, ki oznafluje funk- cija. Le-ta je odvisna od drugih lunkcij ali objektov - para.iietfov lunkcijske cblike. Npr., Ce ita f in g funkciji, je Jog funkcijska ublika, kl ji pravimo kompozitum funkcij ( in g. f in g sta parametra te iunkcijske oblike. fog js (unkcija, katere pomen opiBeroo takole: (fog):* = (:(g:x). Funkcijske ablike imajo lahko za parametre tudi objekte. tie je x objekL, je 7 funkcija, ki nad vsakim defini- rar-iin objektfjiii zavzame vtednaat x. V naslednjih primerih je opisanih nekaj funk- cijskih ablik, njihove stroge definicije pa so podane v dodatku B. Primer komposituma funkcij 'rep' in 'obrat' : Uoreverse: = tl: = . Kmisti.-iikci.ja funkcij f in g je (unkcija Cf,g3. Futikoijo rf ,gi ufporabimo nad objektom tako, da nad njim istoRasno uporabimo funkciji i in g ter dobljsna L-e?ultata zdruSimo v zaporedje. Priiiif-r konatrukcije : DEF 1ast <==> nullotl —> 1 lastotl rtl ,21: = < vstavljanje funkcije f opifiemo z levega vstavljanja lunkcije • : H . / + s<1,2,3> = +:<1 ,/+:<2 = + : >' 1 , + : < 2, / + : (3 > > > = + = +: '-\ ,5> = 6 Istcfiasno upocabo funkcije ir.antL zaporertja opiSemo z af funVcije « nad vsemi: :<2,3>> = t nad vsemi ele- Primer uporabe definira isto funkcijo kot lasti, tokrat na rekurziven naHin. last: = (nullotl —> 1) lastotl): = lastotl: = last:(tl:) = last: = (nullotl —> 1; lastotl)t = 1: = B Lahku se zgodi, da kaka definicija definira funkcijo, ki ni ustavljiva. Mnoiica definicij je dobro oblikovana , fie ne vsebuje nobene de- finicije z enako levo in desno stranjo. Sem ar> t i k RP FP sistem je dolofien, Ce poznamo: atomov A ; osnovnih funkcij P j - oino^ico funkcijskih oblik F ; - dobro oblikovano mnaiico definicij D • Za to, da bi poznali semantiko danega FP sis- tema, raoramo za vsako funkcijo t in objekt x vedeti, kako uporabimo t nad x. Obstajaja Sti- ri moSnosti : - f je osnovna funkcija ; - f je sestavljena ; - ( je definirana ; - za t ne velja nobena od zgornjih totik . Uporabo osnovne (unkclje pojasnjuje 2e sam FP sistera. Uporaba sestavljene funkcije temelji na razvoju funkcijske oblike, na podlagi ka- tere je nastala, ter na uporabi parametrov te funkcijske oblike. Definirano funkcija upcu-a- bima tako, da uporabimo desni del njene do(i- nicije. de za f ne velja nobena od zgornjih toCk, velja (:K = 1 za vsak objekt x. Pogojnd izvcSitev funkcij t in g glede na funkcljo p opiSemo s (p —>f j g). Rezultat izvrSitve funkcije (p -->f j g) nad objektom x je odvi-sen od vrednosti p:x. Ce je le-ta enaka T (True) , je rezultat f:x, sicer pa g:x. Priiw»r t F" P sistemi k o t. (Atora —> reverse) : = . Definiciie Petinicija v FP sistemu je izraz oblike DEF 1 <==> r kjer je na levi strani nek Se neuporabljen siitbol, na deeni pa funkcija. Leva stran defi- nicije lahko vstopa kot parameter v desni del, s Cimer omogaCimo tudi rekurzivne definicije. Primeri definicij : DEF u <==> C1 , tl,23 Npr. u: = C1 ,tl ,2] := OEF lasti <==> "Ureverse Funkcija 1ast1 izbere zadnji element zaporedja. Npc. Iast1:<1,2,3> = 1orev:<1,2,3>=1:<3,2,1>=3 FP sisteme lahko smatramo za programii-ne je- zike. Osnovne funkcije in funkcijske oblilt so osnovni stavki danega programirnega je^ik^. Izbira razlifinih osnovnih funkcij in funkcij- skih oblik omogoea izgradnjo programirnih je- zikov razlifinih zmogljivosti. Mno2ica defini- cij je progranska knjiinica. Funkcija t je program, objekt x je vsebina pomnilnika ( vhodni podatek ), f:x pa vsebina pannilnika po izvrSitvi programa f nad x. Dokazavanje pravilnosti programov v konvencio- nalnih Cvon Neumannovih) jezikih je zapleteno. Z definiranjem algebre programov, prirejene FP sistemom, je podana asnova za nehaniCno ugo- tavljanje in dokazovanje lastnosti programov FP si&tema. Algebra progranov omogofia tudi uporabniSkemu programerju, da ugotavlja in do- kazuje tastnosti svojih programov, ne da bi zahtevala ad njega pretirano teoretitno znanje. Prednost takega dokazovalnega sistena je tudi ta, da programer uporablja pri dokazovanju isti jezik, v katerem so napisani programi . Torej pri dokazovanju lastnosti programov ni potrebno preiti na nek viSji, junanji logitni nivo. Jedro algebre progranov sestavlja mnofica za- konov in izrekov, ki povedo, kdaj je neka funkcija ekvivalentna drugi (unkciji. 369 Spremenljivke algebre programov so funkcije ustreznega FP sistema, operaoije algebre pa so funkcijske ablike tega sistema. Tako je npr. Cf,g3oh izraz v algebri pragramov, v Katerem £0 spremenljivke f^g^h poljubne funkcije FP sistetna. Zakon v algebri programav ima npr. ohliko Cf,gloh <==> Cfoh,goh3. Ta zakon pravi, da ZJ poljubne (unkcije f,g,h sistema' vel ja, ds je funkcija na levi strani ekvivalentna funkciji nd desni. Nekaj Zdkonov algebre progi-amov: (p--:[;gloh < = = > (poh-->f oh ; goh) hofp-->fjg) <= = > (p-->ho/;hog) Cf.fp —>g;h)3 < = = ;• fp —> Cf ,gl; C f ,hD ) Vsat. a.Raalika.Produkt.Kvocient +:K <==> x= in y,z Stevili --> y+z 5 1 -:x <==> x= in y,z Stevili --> y-z ; 1 •:x <==> x= in y,j Stevili --> y«z i i div:x <==> K= in y,z Stevili —> y/z ; kjer y/0 = i Inkrementiranie.Dekrementiran ie ad:x <==> x Stevilo --> x+1 i 1 sb:x <==> » St&vilo --> x-1 ; 1 Ti-anspoz ici ia toans:x <==> x=<0,...,0> —> 0 ) K = —> kjer x, = <«„ ,x,2 , . . . ,xim > in : > 1 D o d e, ; p2— >?2; ... pM— >ek); eR katerih pomen je 51 e d e fi : £e p, tedaj e, stcer pa (*-e p2 tedaj e2 sicer pa f.e pk1'-edaj ek.,5icer pa ek . V iief inici jah so x , x, , y , y, ,z,Z| objekti. S e 11; k c i i n 1:x r= = > K=.'K, , . . . ,xn> --> X, i 1 iri ?.a vsako pozitivno Stevilo s: =.:< ' = = ? « = <«, ,...,»„> in nis —> xs; 1 R.-n 1.1 :x <==> x = --> e ; «=>'«, ,...,xn> in n^2 —> ; i Identiteta id:x <==> x A t; L) (II aton:« <= = > x je atom —> T j x ni J. —> F : 1 Fnaknst tq:» •:==> x= in y=z --> T ; x = in yl=z —> F ; 1 Praznost • nulliK < = => *=0 —> T ; x ni i ~> F j 1 Obrat revsx <==> x=0 —> 0 ; x= —> i 1 • Distribuci 1a z leve disl:x <==> x= --> 0 ; «=> —> <, . . . ,> j 1 Distribuci ia z desne disr:x <==> x=<0,y> —> 0 j x=<,y> —> <,.. . ,> ; 1 Koniunkciia.Disiunkciia.Neoaciia and:x <==> x= —>T ; x= ali x= ali K= —> F i 1 or:x <==> x= ali x= ali x= —> T ; x= —> F ; 1 not:x <==> x= —> F j x= —> T ; 1 Levo in desno prlpenianie apndl:x <==> x= --> ; x=> —> ; 1 apndr:x <==> x=<0,y> --> j x = <,y> —> ; 1 Desna selekciia. Desni rep •1rin <==> x = —> xn j 1 2t-:x < = = > x = in ni2 --> xn., J 1 itd. tlr:x <= = > x= --> 0 ; x= in nž2 --> i J- Leva in desna rotaciia rotl:x < = = > x=0 --> 0 ; x = —> ; x= in n*2 —> < ,Kn,X,> i 1 rotr:x < = = > x=0 --> 0 ; x= —> ; x = in n-2 —> < xn , x, , x2 ,. . . , xn., > i 1 D od Kompozici ia (fog):x <==> f:(g:x) Konstrukci ia Cfi ,...,fn3:x<==> Poaoi

f; g):x <==> (p:x)=T --> f:x ; (p:x)=F —> g:x;l Konstanta x :y <==> y=l —> 1 j x Levo in desno vstavlianie /l :x < = = > x= --> x, j X= in n^2 --> f: > ; l \f sx <==> x= —> x, j K = in n^2 --> f : <\f < x, ,. . . , xn., >, xn >; 1 Uporaba nad vsemi o.l: >i <==> x=0 --> 0 j x = --> ; 1 370 DvoiiSko v enigko (bu i x):y <==> f: kjer je x ohjekt Zanka (uhile p I):x < = = > p:x=T— Muhile p f):(f:x) ; J. Backus: 'Cjn Programming Be Liberated frora von tJauir.ann Style? A Functional 5tyle and Its Algebi-a oJ Programs' , Comrn. 31 the ACM. Vol 21, No.8, August 1978 J. Bar.kus: 'The Algebra Ql Functional Progr-ftma: Function Level Reasoning, Line- ar Equatton» and Extended 0e(initions', Fnrniiii i :at.i on of Progfammir.g Concepts, Lv-iiture Hotes in Comcuter Science. 107 W.B.Ackerman: 'Data Flow Languages', Com- putec, Spwcial Issue on Oata Flow Systems, Va!.1S, Na.2, February 17B2 J.'gilc,B.Robie,B.Mihoviloviei 'Podatkovno vodene caBunilniKke arhitekture', Pasve- tovanje in fcsminarji Infornatica '8B, Mnvi Gorica, September 1985