SICS T92:01

Thomas Sjöland

SICS

December 1991

SICS Technical Report ISSN 1100-3154

Swedish Institute of Computer Science

Box 1263, S-164 29 Kista, SWEDEN

Thomas Sjöland

SICS, Box 1263, S-164 28 Kista, Sweden

Kombinationen av objektorienterad programmering och logikprogrammering har traditionellt inte behandlats i teorin för logikprogram. Den pragmatiska fördelen av objektorienterad programmering har dock gjort att några leverantörer av logikprogrammeringssystem har konstruerat objektorienterade stödsystem till prologsystem. Kommersiella system som är kända för oss är Prolog++ från Logic Programming Associates [Vasey, Spencer et.al.90], Logical Object Systems (LOS) från Imperial College (F. G. McCabe) [McCabe89] och ELSA från ELSA Software. Av dessa har vi tillgång till Prolog++. I den mån det påpekas skillnader i de tre systemen är beskrivningen av dessa hämtad ur LPAs dokumentation. Dessutom finns icke-kommersiella system som t.ex. LOCO/KIWIS som kopplar samman en databas, ett grafiskt användargränssnitt (Openlook) och en objektorienterad utvidgning av Prolog [Vermeir et.al. 89,91a,91b]. Arbete pågår på universitetet i Antwerpen med att anpassa LOCO/KIWIS till SICStus Prolog. LOCO/KIWIS är resultatet av ett ESPRIT-projekt där electruminstitutet SISU har deltagit [KIWIS91]. Systemet Explore/L [Fromherz91] är ett system som på många sätt liknar Prolog++. Rapporten som anges i referenslistan är på 72 sidor och innehåller ingående tekniska detaljer för en prologprogrammerare som vill implementera detta system. Även frågor om deklarativ semantik för objektorienterad logikprogrammering behandlas.

Allmänt kan sägas att kombinationen av objektorienterad programmering och logikprogrammering med Prolog har inslag av "ad hoc"-lösning. Det saknas "programmeringskultur" runt objektorienterad prologprogrammering. Detta leder liksom i andra fall, som t.ex. grafiska användargränssnitt (GUI), till att olika leverantörer kommer fram med sinsemellan inkompatibla lösningar. Vi lutar oss i denna framställning mot Prolog++ av flera skäl:

- SICS har kontakt med LPA.

- LPA delägs numera av Quintus Systems, ett Intergraph-företag vars Prolog-system i stor utsträckning tjänat som förlaga för designen av SICStus Prolog.

- Prolog++ är en genomarbetad produkt som är väl integrerad i ett marknadsledande prologsystem på Macintosh och PC-datorer.

System för objektorienterad programmering implementeras ofta tillsammans med en grafisk programmeringsomgivning. I denna finns förutom naturliga metoder att ge tillämpningarna ett grafiskt gränssnitt även interaktiva grafiska verktyg för att utveckla program. LPA saluför t.ex. MacObject som är en miljö för att utveckla Prolog++-program som integrerats i den grafiska miljön som LPA också utvecklat för Macintosh respektive Windows.

Logikprogrammering med SICStus Prolog [CaWiJAnSAnBoNiSj91,AlAnFlFrNiSu91] innebär kortfattat (och förenklat) att man programmerar definitioner av relationer (predikat). Två former av definitioner finns:

- atomära klausuler som definierar enkla fakta, t.ex:

farfar(nils,lisa).

far(sture,bengt).

far(bengt,anna).

farfar(X,Y) :- far(X,Z), far(Z,Y).

fint_träd(löv).

fint_träd(träd(löv1,träd(Gren, löv2))) :- fint_träd(Gren).

Ett program kan fördelas på flera filer och kan förutom definitioner även innehålla direktiv, procedurer som exekveras vid inläsningen.

Ett program kan läsas logiskt, som definitioner av relationer över datastrukturer eller procedurellt, som definitioner av procedurer vilka utföres i en ordning som bestäms av programmets syntax. Programkörningen kan ses som en sökning efter en lösning till ett problem som formuleras som ett mål, t.ex målet

?- farfar(Farfar, Barnbarnet).

Farfar=nils

Barnbarnet=lisa

Om det finns alternativa lösningar kan man få dem också, t.ex.:

Farfar=sture

Barnbarnet=anna

Exekveringen kan fås att avvika från den givna sökordningen genom att man skriver in speciella mål, s.k. kontrollprimitiver. I prologprogram kan man manipulera programmet under körning genom att lägga till eller ta bort definitioner. Detta motiveras av att man vill se programmet som en databas av fakta och regler där vissa regler kan påverka innehållet i databasen. Program som modifierar databasen saknar logisk läsning.

I SICStus Prolog finns ett modulsystem som ger programmeraren möjlighet att strukturera sina definitioner så att en viss inkapsling uppnås. Predikat ingår i filer som kan namnges som moduler. Predikat kan exporteras och importeras mellan modulerna för att göra dem direkt kända utanför den definierande modulen. Predikat kan även vidareexporteras. Alla predikat kan nås genom att man i målet anger deras modulnamn. Moduler kan också skapas 'dynamiskt', dvs. under exekveringen. Modulsystemet i SICStus Prolog kan användas för att efterlikna arvsmekanismer i objektorienterad programmering. 'Inkapsling' av predikatnamn för att uppnå dolda, 'lokala' definitioner är dock inte möjligt.

En klass av programmeringsspråk som är nära besläktad med logikprogrammeringsspråk är de funktionella programspråken. Ett funktionellt program kan ses som en samling definitioner av funktioner. Exekveringen blir då att på ett målinriktat, algoritmiskt, sätt söka efter värdet på en funktion som definierats i termer av andra funktioner och inbyggda, s.k. elementära funktioner. I funktionell programmering finns högre ordningens funktioner, dvs. funktioner som kan operera på funktioner som fullvärdiga data, och abstraktion, t.ex. lambda-abstraktion, som viktiga metoder för programmering. Funktioner har typer som kan härledas automatiskt vid inläsningen av programmet. Programkörningen utgör en evaluering av värdet hos ett funktionsuttryck för givna indata.

I logikprogram kan de flesta mekanismer från funktionell programmering modelleras genom att man kodar funktioner som relationer. Typsystemet hos ett funktionellt programmeringssystem har ingen direkt motsvarighet i Prolog. Man kan dock använda datastrukturer för att sätta "tag" på värden och uppnå effekten av en typkontroll hos funktioner. I funktionell programmering är lat evaluering ett väsentligt begrepp. Detta innebär att funktionsuttryck evalueras först när värdet behövs och inte enligt en enkel syntaktisk evalueringsprincip. Lat evaluering kan ofta efterliknas genom att använda 'coroutining' i SICStus Prolog.

Användningen av begreppet "funktionssymbol" i logikprogrammeringslitteraturen gäller givetvis inte evaluerbara funktioner i denna mening utan istället datastrukturer. Förklaringen till detta begrepp ligger i modellteorin för logikprogram som definitioner av predikat över objekt i termtolkningen (symbolen '=' tolkas som syntaktisk likhet).

De kanske mest spridda programmeringsspråken som C, ALGOL, ADA, FORTRAN, Cobol etc. baseras på idén om procedurer. Liksom för klausuler i logikprogrammering och funktionsuttryck i funktionell programmering kan man i procedurorienterad programmering definiera procedurer rekursivt . Ett mål delas upp i delmål som körs successivt. En procedur definierar hur ett antal tillståndsvariabler förändrar sina värden genom att programmet körs. Under exekveringen skapas rekursiva instanser av delmängder av tillståndsvariablerna för proceduren, s.k. lokala omgivningar. Procedurerna kan också påverka värdena hos tillståndsvariabler som nås från alla omgivningar, s.k. globala omgivningar. Överföring av värden mellan instanser av procedurer kan ske på ett flertal olika sätt. I språket C används kopiering av värden som princip. För att innehållet i en tillståndsvariabel skall kunna modifieras måste en pekare överföras till proceduren.

På senare tid har objektorienterad programmering blivit populärt [Haridi91]. Med detta avses en programmeringsmetodik som utnyttjar en hierarki av objektdefinitioner och d:o instanser. Ett objektorienterat system använder ärvningsmekanismer och exekveringskontrollen kan beskrivas med sändning av meddelanden mellan objekt. Objekten är modifierbara och innehåller tillståndsvariabler (attribut), evaluerbara funktioner och metoder. Det förväntas i avancerade objektorienterade system att objekt kan skapas och tas bort genom utförande av programsatser (sändning av meddelanden) samt att systemet kan automatiskt lösa arvskonflikter (skuggning, multipel ärvning). Objektsystemet bör även kunna skydda innehållet i objekten för icke-önskvärd åtkomst och/eller modifikation, samt stödja programmering av s.k. demoner, dvs. kod som exekveras när vissa händelser inträffar.

I rapporten "Jämförelse mellan Ada och C++" [Sahlin90], citeras definitioner ur boken "Research Directions in Object-Oriented Programming" [Shriver87], s. 508.

Objekt Ett objekt har en mängd operationer och ett tillstånd som minns effekten av operationerna.

Klass En klass specificerar ett gränssnitt för operationer. Den fungerar som en mall efter vilken objekt med det givna gränssnittet kan skapas.

Klassärvning Klassärvning är en mekanism för sammansättning av gränssnitt från en eller flera superklasser med gränssnittet från en subklass. En subklass kan komma åt operationerna i en superklass om det inte finns några namnkonflikter.

Sahlin skriver vidare:

Språk med stöd för objekt kallas i boken för "object-based", med stöd för objekt och klasser kallas "class-based" och språk med objekt, klasser och klassärvning kallas "object-oriented". Enligt denna definition blir Ada "object-based" och C++ "object-oriented".

LPAs terminologi är något annorlunda. Normalt används i texter om objektorientering begreppet "klass" för att tala om beskrivningen av ett gränssnitt och "objekt" för att beskriva de instanser som kan skapas under exekveringen. I denna text används LPAs konvention att tala om "objekt" för klass och "instanser" för objekt. Objekt och instanser är i stort sett likvärdiga men med den väsentliga skillnaden att instanserna inte syns explicit i programkoden utan skapas under exekveringen.

Objektorientering har i logikprogrammeringssystem implementerats på några principiellt olika sätt:

- genom att man betraktar predikatdefinitionerna som objektdefinitioner, modifierar begreppet bindningsomgivning med olika inkapslings- och åtkomstmekanismer och implementation av arvsrelationer, m.m. I ESPRIT-projektet ALPES [ALPES90] valdes en liknande lösning kallad "contextual logic programming" som kan vara av intresse att studera. Denna infallsvinkel övervägs dock inte vidare i denna text.

- genom att man betraktar ett objekt som en samling av predikat, vilka definierar attribut (objektvariabler), evaluerbara funktioner och metoder för det namngivna objektet. I systemet införs mekanismer för att skapa objekt och instanser samt för sändning av meddelanden till objekten (instanserna) och för datadriven exekvering av metoder. Prologsystemet ligger till grund för implementationen av objektsystemet genom att Prolog++-programmen översätts till prologprogram. Prologprogram kan användas från objektens metoder och funktioner.

Objekten kan ses ha denna form:

objekt(<ObjektNamn>,<InstansNr>,<Attribut>,<Funktioner>,<Metoder>).

Refererade komponenter (attribut, funktioner och metoder) söks via hierarkilänkarna om de inte finns i det aktuella objektet. (Hierarkilänkarna är attribut). Komponenter kan även ärvas från namngivna objekt utan hänsyn taget till hierarkin genom att detta speciellt anges. Demoner är metoder som anropas då vissa händelser inträffar, t.ex. att ett attribut eller en instans skapas, tas bort eller modifieras.

Ett statiskt objektsystem skapar inga objekt under körningen. Därför bortfaller behovet att särskilja objekt och instanser helt. Varje objekt som används har sin egen definition och en explicit angiven mängd av tillståndsvariabler. Användbarheten hos ett statiskt objektsystem är begränsad.

Ett dynamiskt objektsystem tillåter att programmeraren skapar objekt i systemet som instanser av de givna objektdefinitionerna. Genom att länkar mellan objekt anges kan metoder, attribut och funktioner från andra objekt utnyttjas utan att definitionerna upprepas.

Följande operatorer definieras för Prolog++.

:- op(1200,fy,[open_object,close_object]).

:- op(1150,fx,[private,dynamic]).

:- op(800,fx,['<-').

:- op(800,xfx,['<-']).

:- op(700,xfx, [':=','+=','-=','*=','/=',':==','+==','-==','*==','/==']).

:- op(600,fx,inherit).

:- op(400,yfx,'//').

:- op(100,yfx,'::').

Inbyggda predikat introduceras i manualen för Prolog++.

Ett objekt (en instans) har en uppsättning unika tillståndsvariabler som benämnes attribut. Dessa kan användas i uttryck och förändras med en uppsättning operationer.

De metoder som tillhör ett objekt utförs när objektet mottar ett meddelande med begäran om exekvering. En metod förstås som en lokal procedur.

I Prolog++ finns möjligheten att definiera exekverbara funktioner. Dessa kan ingå i uttryck och är väsentligen metoder som returnerar ett värde.

När objekt saknar en komponent kan systemet leta efter denna i ett annat objekt. Genom att definiera vilka objekt som ligger högre formar man en partiell ordning av objekt, en objekthierarki. Ärvning innebär att komponenten söks i de klasser som anges som högre. Multipel ärvning uppnås genom att flera "föräldrar" tillåts. Skuggning innebär att komponenter som hittas i objekt som ligger lägre i hierarkin gör att komponenter från "högre" objekt inte syns. En separat ordning kan etableras genom att precisera explicit ärvning för attribut, metoder och/eller funktioner.

Namnen på ett objekt och namnen på dess publika komponenter utgör dess abstraktion.

Värdena hos attributen kan användas och /eller modifieras. Till attributet liksom till objekten kan associeras en eller flera demoner.

Den centrala operationen för ett objektorienterat system är överföring av meddelanden.

Meddelanden skickas till objekt och är av tre typer:

1) begäran om exekvering av en metod:

obj1 <- message(hej)

2) begäran om modifikation av ett attribut:

obj1::attribute3 := nytt_värde

3) I uttrycken kan även förekomma attributvärden och funktionsuttryck. Dessa kan också betraktas som överföring av meddelanden, ett för att hitta attributet, och ett som återsänder dess värde till den som skickat meddelandet för att användas i det uttryck vari attributet förekommer:

X=obj2::function(1,2,3)

É

metod(InData) :-

super(myself) <- metod(InData).

É

Genom att hierarkilänkarna är attribut kan explicita sökningar i hierarkin programmeras med stor frihet.

Polymorfism uppnås genom att samma metodnamn används för att definiera olika beteenden i olika objekt.

En grupp meddelanden kan skickas till en grupp av objekt som en operation.

En demon är en metod som exekveras vid en speciell händelse i Prolog++ :

- när instanser av objekt skapas eller tas bort

- när nya värden definieras för attribut i objekt eller objektinstanser

- när den lokala databasen hos ett objekt eller en instans ändras (med detta avses när metoder eller funktioner ändras eller när attribut tas bort eller läggs till)

En demon definieras som ett objekt och kan ingå i objekthierarkin, sända meddelanden, anropa prologmål osv. En vanlig användning är för att fånga speciella händelser t.ex. för att generera grafisk utmatning.

I Prolog++ finns två inbyggda objekt, s.k. meta-objekt:

Implementationsförslagen nedan baseras på ett försök att förstå vad som sker bakom kulisserna i Prolog++ genom studium av manualen för Prolog++, ej på något dokument som beskriver LPAs implementation.

I valet av representation för de olika språkkomponenterna (objekt, instanser, attribut, metoder, funktioner, demoner, hierarki och andra länkar) måste implementatören avväga effektivitet mot arbetsinsatsen som erfordras för respektive implementationsstategi.

Några väsentliga egenskaper bör upprätthållas av alla implementationer:

- Prologmål skall kunna anropas från metoder och funktioner i Prolog++-objekt.

- Språket Prolog++ skall kunna kompileras och dekompileras till/från Prolog. Detta ger möjlighet till utnyttjande av Prolog-kompilatorn.

I Prolog++ används prologsyntaxen för definitioner.

En objektdefinition avgränsas av

open_object <ObjectName>.

<definitioner av hierarki, attribut, metoder, funktioner>

close_object <ObjectName>.

object(<ObjectName/No>).

super(<ObjectName/No>,<Lista av andra ObjectName/No>).

attribute(<ObjectName/No>, <AttributeName>, <AttributeValue>).

method(<ObjectName/No>, <MethodName>, <Method>).

function(<ObjectName/No>, <FunctionName>, <Function>).

vem = allan.

listan is [].

Dessa deklarationer kan översättas till prologklausulerna:

attribute(<ObjectName/No>, vem, allan).

attribute(<ObjectName/No>,listan, []).

En metod specificeras t.ex.:

dothis(Attribute, NewValue) :- myself::Attribute := NewValue.

En översättning blir:

method(<ObjectName/No>,dothis(AttributeName,NewValue)) :-

'::'(<ObjectName/No>,AttributeName,FoundAttribute),

':='(FoundAttribute,NewValue).

square(X) = X*X :- X>0.

Funktionen översätts lämpligen (om man inte vill ha icke-deterministiska funktioner) till:

function(<ObjectName/No>,square(X),Sq) :- X>0, !, Sq is X*X.

Operationerna som kan läsa värden hos attribut löser upp objekthierarkin för att finna det aktuella attributet, medan operationer som modifierar ett attribut dessutom måste modifiera databasen i Prolog eller de globala tillståndsvariablerna.

I Prolog++ kan man skriva

private.

i definitionen av ett objekt. De därpå följande definitionerna av komponenter blir då osynliga utanför objektet självt. Detta implementeras med ett extra argument i komponentklausulen. Endast publika komponenter kan nås vid sökningen i hierarkin.

Instanser skall kunna skapas baserat på en objektdefinition. En instans skall även kunna tas bort.

Meddelanden skall kunna skickas till objekt (instanser). "Multicast" skall understödjas så att flera meddelanden skall kunna skickas till flera objekt i en operation.

Metoder skall kunna associeras till speciella händelser för ett objekt så att metoden automatiskt anropas när händelsen inträffar.

Mekanismerna för Prolog++ kan implementeras med rimlig effektivitet om SICStus Prolog utvidgas med operationer för att allokera och modifiera globala tillståndsvariabler som innehåller godtyckliga prologtermer. Demoner kräver dessutom att prologmål kan associeras till tillståndsvariablerna. Explicit avallokering är nödvändig.

En enklare, men mindre effektiv implementation är möjlig genom att använda prologfakta för att representera attribut. Denna metod är adekvat om den huvudsakliga beräkningen ligger i metoder och funktioner genom anrop till Prolog.

En måhända besvärlig fråga är huruvida Prolog++ är det lämpligaste systemet att basera en objektorienterad utvidgning av SICStus Prolog på. En industriell utvärdering där man jämför Prolog++ eller Explore/L på Macintosh med t.ex. LOCO/SICStus som antas bli tillgänglig under våren 1992 rekommenderas innan slutgiltigt beslut tas. Rapporten om Explore/L verkar vara tillräckligt detaljerad för att kunna utgöra en implementationsspecifikation för ett examensarbete.