5 TOTEUTETTU JÄRJESTELMÄ
5.2 Funktionaalinen laskentalogiikka
5.2.3 Laskentasäännön jäsentäminen ja evaluoiminen
C++-ohjelmointikieli ei tue ajonaikana tapahtuvaa lausekkeiden jäsentämistä tai evalu
oimista, joten tarvittavat rutiinit jouduttiin kirjoittamaan kokonaan itse. Jäsennys ja evaluointi toteutettiin alunperin C-kielellä kirjoitetun kirjaston avulla. Kirjasto jouduttiin myöhemmin hylkäämään ja tilalle kirjoitettiin oma oliopohjaisiin
tietorakenteisiin perustuva toteutus.
C-kielisen kirjaston käyttö
C-kielinen toteutus perustui melko suoraan kirjan The UNIX Programming Environment luvussa 8 esitettyyn ohjelmaan hoc (high-order calculator) [KePi84]. Ratkaisussa käytettiin jäsentämisessä hyväksi YACC-nimistä jäsenningeneraattoria. Lähestymis
tavan etuihin kuului helposti ylläpidettävä syntaksi. Muutosten jälkeen voitiin uuden jäsentäjän vaatima koodi muodostaa automaattisesti. Jäsentämisen lopputuloksena
syntyi operaatiopino. Laskenta tapahtui operaatiopinon evaluoimisena.
Otetaan esimerkiksi luokkatasolla kirjoitettava sääntö 'x = 10 + sum ( r.b ) * a'.
Jäsennyksen tuloksena syntyvä operaatiopinot on esitetty kuvassa 18 vasemmalla.
+ +
10 10
* *
sum() sum()
"r.b" ->r."b"
"a" ->a
luokkatason pino instanssissa sidottu pino
Kuva 18 Lauseketta 'x = 10 + sum (r.b) * a' vastaavat operaatiopinot
Jotta pinolle voidaan laskea arvo jossain tietyssä instanssissa, luodaan instanssille kopio luokkatasolla olevasta pinosta ja sidotaan syntynyt pino instanssin omaan ympäristöön.
Sidonnan tuloksena syntynyt pino on kuvassa oikealla. Pinon arvo saadaan laskemalla päällimäisen operaation arvo. Mikäli operaatiolla on argumentteja, lasketaan näiden arvot rekursiivisesti samalla tavalla. Esimerkkilausekkeen arvon laskeminen etenee kuvan 19 mukaisesti.
sidottu pino arvojen sijoittaminen
+ + +
10 10 10
* * *
sum() sum() 110
->r."b" 50,60 0.4
->a 0.4
10 44
54
Kuva 19 Esimerkkilausekkeen arvon laskeminen
Pinoihin perustuva laskenta oli suhteellisen tehokas tapa laskea lausekkeen arvo.
Ongelmia aiheuttivat kuitenkin seuraavat tekijät:
• Pinojen kopioiminen ja sitominen instanssikohtaisesti kulutti paljon muistia.
• Laskennan järjestys alhaalta ylöspäin teki viivästettyyn evaluointiin perustuvat funktiot mahdottomiksi. Esimerkiksi kolmipaikkaista if-funktiota ei voitu toteuttaa siten, että se olisi itse evaluoinut ensin ehto-parametrin ja ehdon totuusarvosta riippuen vain toisen haaran. Viivästetyn evaluoinnin puuttuminen teki mahdot
tomaksi toteuttaa käytännöllisiä sivuvaikutuksellisia funktioita.
e Laskennan aikana tulleista virheistä ei voitu antaa selkeitä virheilmoituksia, koska ei tiedetty tarkkaan, mitä funktiota oltiin evaluoimassa. Virheen jälkeen jouduttiin tekemään C-kielessä vaarallisena pidetty funktiokutsu longjmpO, jolla ohjelman suorituksessa palataan hallitsemattomasti rekursiivisesti syvällä olevasta funktiosta johonkin aikaisempaan ylempään funktioon.
Samalla kun luovuttiin pinoihin perustuvasta evaluoinnista, kirjoitettiin jäsenninkin uudestaan ilman YACC-työkalun apua. Suurin osa jäsentimen koodista olisi joka tapauksessa jouduttu kirjoittamaan uudestaan, mutta jäsentimessä oli lisäksi seuraavia puutteita:
• Jäsentämisen aikana syntyvistä virhetilanteista oli vaikea antaa loppukäyttäjien ymmärtämiä virheilmoituksia.
e Lausekkeen syntaksia laajennettiin globaaleilla viittauksilla ja relaatiopoluilla siten, että jäsentäjän tilan ylläpitäminen muodostui hankalaksi.
• Jäsentäjän tuli tyyppitarkistusten takia olla kiinteässä yhteydessä sovelluksen oliomalliin. Tällöin syntaksin merkitys pieneni ja semantiikan merkitys kasvoi.
YACC-työkalussa oli vaikea esittää tilanteita, joissa sama syntaksi saattoi merkitä erilaisia asioita, esimerkiksi relaatioiden kardinaliteetin huomioiminen.
C++ luokkiin ja jäsennyspuihin perustuva jäsentäminen
Jokaiselle järjestelmään syötetylle laskentasäännölle muodostetaan jäsentämisen tulok
sena puumainen oliorakenne, jota tässä kutsutaan jäsennyspuuksi. Jäsentäminen suorite
taan Top-Down -periaatteen mukaisesti [Sedg88], jolloin tuloksena saadaan
rekursii-vinen jäsenny spun. Itse jäsennin voidaan toteuttaa suoraviivaisesti annetun kieliopin mukaisesti.
Kuva 20 Lauseketta '10 + sum(r.b) * a' vastaava jäsennyspuu
Jäsentäminen tapahtuu kutsumalla TreeParse-luokan funktiota parse, joka palauttaa osoittimen puunjuurena olevaan lausekkeeseen.
Expr *TreeParse::parse(char *formula, MOSClass *ownerClass, MOSAttribute *ownerAttribute);
Tarvittavat funktiot voidaan helposti päätellä laskentasääntökielen syntaksin perusteella.
Käytännössä jäsennin kokeilee erilaisia kieliopin mukaisia vaihtoehtoja peräkkäin.
Mikäli kokeiltu vaihtoehto ei onnistu, peruutetaan kutsuneelle tasolle, jolla voidaan kokeilla seuraavaa vaihtoehtoa. Mikäli yhtäkään onnistunutta tapaa lausekkeen jäsentämiseksi ei löydy, tulostetaan käyttäjälle virheilmoitus ylimmältä tasolta.
Lausekkeita {Expr) vastaavassa C++-luokassa on käytetty unionirakennetta siten, että jokainen muodostuneen puun olio on aidosti Expr-luokan instanssi, ts. Expr-luokalle ei
ole luotu alaluokkia erilaisia puun solmuja varten.
class Expr : public VObject { public :
enum expr_type {
unknown, deletedname, root, listitem, parenth_expr, number, function, path, relation, item, class, instance, rule, string, negate, add,
sub, mul, div, pow, gt, ge, It, le, eq, ne, or, and
}
;private : enum void void void public :
union { Expr
expr_type eType;
pathChanged(MOSObj ect *changedObject);
attributeChanged(MOSAttibute *changedObject);
makeDeletedName(MOSObject *n, Expr *nextE);
♦operand;
struct { Expr *operandi; Expr *operand2; } pair;
VOrdCollect *atoms;
VString »string;
double num;
struct { MOSBaseltem »item; Expr »periods ; } item;
MOSBaseRelation »relation;
struct { MOSElement »ele; Expr »attribute; } ref ; struct { MOSBaseRelation »relation; Expr »next; } path;
struct { VString »name; Expr »next; } deleted;
struct { BuiltinFunc »biFunc; VOrdCollect »params; } f une ; } val;
Expr »parent ;
void changeType(expr_type let);
expr_type getType ( ) { return eType; } boolean
boolean void
calc (CalcValue {¿value, MOSAttribute * resul tObject) ; calculate(MOSAttribute »resultObject);
valueWasChanged(MOSObject », boolean recursive);
Expr * int int boolean
};
switch_right_operand();
isOperator();
getPrecedence();
makePrettyRule (VString {¿text) ;
Jäsennettäessä lauseketta vasemmalta oikealle joudutaan saatu puurakenne järjestämään operaatioiden presedenssien mukaiseksi. Puuta muodostettaessa jokaisen operaation kohdalla vasemmanpuoleiseksi alipuuksi laitetaan edellisessä vaiheessa jäsennetty osuus ja oikeaksi alipuuksi lausekkeen jäsentämätön osuus. Näin esimerkiksi lausekeesta 'A * В + C muodostunut puu ei jäsennyksen jälkeen ole operaatioiden presedenssien mukaisessa järjestyksessä. Tällainen virheellinen tilanne on kuitenkin helppo tunnistaa ja korjata jäsennyksen jälkeen. Tilanne vaatii korjausta, mikäli testattavan operaation A oikeana alipuuna on operaatio В siten, että A:n presedenssi on suurempi kuin B:n.
Laskentajärjestyksen korjaus suoritetaan seuraavien askelten avulla:
1. Korjattavan operaation A oikeaksi alipuuksi asetetaan operaation В vasen alipuu.
2. Operaation В vasemmaksi alipuuksi asetetaan testattava operaatio A.
3. Korjaus suoritetaan rekursiivisesti juureksi siirtyneen operaation В alipuille.
4. Korjauksen jälkeen palautetaan puu, jonka juurena on operaatio B.
ÇÜperation-7r>
ÇgubTree^) ÇÜperation
Ç^ubTree^) Ç^ubTree^
ÇÜperation^B^
ÇÜperation Ç^ubTree^)
Ç^ubTreefo Ç$ubTree^>
Kuva 21 Lausekkeen A *B+C' jäsennyspuun korjaus laskenta]ärjestyksien mukaiseksi Jäsennyspuuhun perustuva evaluointi
Jäsennyspuuta vastaavan lausekkeen arvo lasketaan kutsumalla puun juurena olevan solun (Expr) calculate-metodia antamalla parametriksi attribuutti, johon tulos sijoitetaan. Laskenta suoritetaan sen instanssin ympäristössä, jonka attribuutti annettiin parametriksi.
void Expr::calculate(MOSAttribute *resultObject) {
CalcValue *value = CalcValue::getCalcValue(resultObject);
if (! calc(»value, resultObject)) {
error("Calculation failed for object %s or %s.\n", resultObject->getName()
resultObject->getParent()->getName());
}
value->storeResult(resultObject);
CalcValue:rputCalcValue(value);
}
Lauseke kutsuu metodiaan calc, jolloin ensimmäisenä parametrina olevaan CalcValue- luokan instanssiin tallettuu laskennan tuloksena syntyvä arvo. CaleLb/ive-luokan instanssit ovat laskennan aikana käytettäviä välituloksia. Niitä ei koskaan luoda tai tuhota normaalin muistinhallinnan avulla, vaan ne haetaan ja palautetaan yhteiseen varastoon. Varastoinnilla parannetaan laskennan suorituskykyä.
Lausekkeen arvon laskemisessa varsinaisen työn tekevä calc-metodi valitsee lausekkeen tyypin mukaisesti suoritettavan operaation, esimerkkinä näytetään muutaman valinnan toteuttamisperiaate :
boolean Expr:: calc(CalcValue &value, MOSAttribute »result) { switch (getType()) {
case (lex_negate):
return (val.operand->calc(value,result) &&
value.applySingleOperator(CalcValue: :NEGATE));
case(lex_add): {
boolean res = FALSE;
if (val.pair.operandi->calc(value,result)) {
CalcValue *value2 = CalcValue::getCalcValue(bvalue);
if (val.pair.operand2->calc(*value2,result)) {
res = value.applyDoubleOperator(CalcValue::ADD,*value2);
Lausekkeen evaluoinnin tuloksena syntyvään CalcValue-instanssiin talletettu arvo on täysin polymorfinen. Toteutus on tehty samaan tapaan kuin lausekkeilla, eli arvolla on oma tyyppi, jota se voi muuttaa ja jonka mukaisesti arvossa olevaa unionirakennetta tulkitaan. Esimerkiksi negaatiosta muodostuneen solun arvo saadaan laskemalla ensin solun operaationa olevan lausekkeen arvo ja soveltamalla sitten tähän arvon yksipaikkaista operaatiota negate. Kaksipaikkaisia operaatioita varten on otettava käyttöön uusi tilapäinen CalcValue-luokan instanssi, laskettava molempien operaati
oiden arvot ja sovellettava lopulta ensimmäiseen arvoon kaksipaikkaista operaatiota toisen arvon kanssa. Merkkijonosta, luvusta tai lukulistasta saadaan helposti muodostettua vakioarvo.
class CalcValue : public VObject { public :
enum calc_value_type {
cv_unknown, cv_number, cv_numberlist, cv_string, cv_instance, cv_class, cv_itemlist, cv_instancelist
// Unary Dispatch operators
boolean applyDOperator(op_type op);
boolean applyLOperator(op_type op);
boolean applylOperator(op_type op);
// Binary Dispatch operators
boolean applyDDOperator(op_type op, CalcValue &v2);
boolean applyDDOperator(op_type op, CalcValue &v2);
boolean applyDDOperator(op_type op, CalcValue &v2);
boolean applyDDOperator(op_type op, CalcValue &v2);
boolean applyIDOperator(op_type op, boolean applyIDOperator(op_type op, boolean applyllOperator(op_type op,
CalcValue &v2) CalcValue &v2) CalcValue &v2)
boolean applylnstancelistOperator(op_type op, CalcValue &v2);
boolean applyStringOperator(op_type op, CalcValue &v2);
public :
calc_value_type getType() { return cvType;
cvt) ;
}
// Initialization
void duplicateFrom (CalcValue {¿source) ; boolean makelnstance(MOSInstance *inst);
boolean makeClass(MOSClass *cls);
boolean makeNumber(double value);
boolean makestring(char *value);
boolean makeltem(MOSItem *item, long start, long end);
boolean makeRelation(MOSRelation *rel);
// Unary and Binary Operators, entry points boolean applySingleOperator(op_type op);
boolean applyDoubleOperator(op_type op, CalcValue &value2) ; // Storing results
boolean storeResult(MOSAttribute *calcObj);
};
Funktionkutsut tehdään funktiokirjastoon ajonaikaisesti rekisteröityjen funktio-olioiden avulla. Parametrit evaluoidaan normaalisti automaattisesti ennen kutsua, mutta funktio voi myös itse hoitaa parametrien evaluoinnin omassa koodissaan.
Viittauksien huomioinen laskennassa
Jäsennyspuu sisältää vakioiden, operaatioiden ja funktioiden lisäksi viittauksia sovelluskohtaiseen malliin. Nämä viittaukset on toteutettu tallettamalla puun solmuihin osoittimet mallin luokista löytyviin vastaaviin attribuutteihin. Lausekkeen arvoa laskettaessa etsitään kulloinkin sääntöä käyttävästä instanssista luokkakohtaisia attribuutteja vastaavat perityt attribuutit. Alla olevat funktiot hakevat tietoalkion tai relaation arvon. Polymorfisen CalcValue-instanssin tyyppi on molemmissa tapauksissa funktion alussa cv instance, jolloin vastaavassa unionirakenteessa muuttujassa val.instance on osoitin sovelluksen instanssiin. Tästä instanssista haetaan vastaava peritty attribuutti, jolle annetaan tehtäväksi sijoittaa oma arvonsa CalcValue-instanssiin.
Käytännössä arvon sijoittamisen aikana CalcValue-instanssin tyyppi muuttuu, tietoalkion tapauksessa tyypiksi tulee joko cvnumber, cvnumberlist tai cvstring, relaation kohdalla tyypiksi tulee aina cvjnstancelist.
boolean CalcValue : -.makeltem (MOSBaseltem *base) {
return vai.instance->getlnheritedltem(base)->makeCalcValue(*this);
}
boolean CalcValue::makeRelation(MOSBaseRelation *base) { MOSRelation *r = vai.instance->get!nheritedRelation(base);
changeType(cv_instancelist) ;
L_DO(r->getTargetNetElements(), MOSInstance, inst) vai.instancelist->addO(inst);
L_END
}
Mikäli relaatiopolku jatkuu, sovelletaan ylläolevista funktioista usealle instanssille tehtyjä versioita. Esimerkiksi tietoalkion tapauksessa saadaan lista uusia CalcValue- luokan instansseja.
boolean CalcValue::makeItemList(MOSBaseltem *base) { VOrdCollect singleltems;
L_DO(vai.instancelist, MOSInstance, inst) CalcValue *cv = CalcValue::getCalcValue();
singleltems.add(cv);
cv->changeType(cv_instance);
cv->val.instance = inst;
cv->makeltem(base); // kutsu edellä esitettyyn funktioon L_END
Laskennan aikana voi siis muodostua hyvinkin suuria välituloksia sisältäviä puita.
Lausekkeen 'myynti = sum(tuotteet.myynti)', jossa tuottet-relaatioon on kiinnittynyt kolme kappaletta tuote-luokan instansseja, arvon laskeminen voidaan esittää seuraavan
laisena puuna:
parameters
(^JuotteeT^)
C^yyntO
~<ÇCalcValue:cv_nunribèf>
~<C^ilcValue:cv_nunrí5er>
<Ç^^lcValue:cv_numbèr>
Kuva 22 Jäsennyspuuta vastaava laskennan aikainen laajeneminen
Mikäli relaatioon olisi kiinnittynyt 1000 tuoteluokan instanssia, tarvittaisiin vastaavasti 1000 kappaletta Са/сТа/ме-luokasta luotua välituloksien tallettamiseen käytettävää instanssia. Sz/m-funktio paluttaa luonnollisesti vain yhden arvon, joten funktionkutsun jälkeen järjestelmä vapauttaa kaikki väliaikaiset tietorakenteet uutta käyttöä varten.