Next: Sorten als First-Class Up: Integration von Sortenals ausgezeichnete Previous: Contents

Einleitung

Strukturierungstechniken haben in der modernen Programmierung immer mehr an Bedeutung gewonnen. Datentypen sind mittlerweile Bestandteil fast jeder prozeduralen Sprache [Wir85]. Objekt-orientierte Sprachen wie etwa SmallTalk[GR85], die auf dem Konzept der Klassenhierarchien aufbauen, verbreiten sich zunehmend. Auch in Anwendungen, z.B. Spracherkennung oder Automatisches Beweisen, bedient man sich mehr und mehr des Typ-Konzepts. Strukturierung erscheint f"ur gr"o"sere Softwareanwendungen nicht mehr nur w"unschenswert, sondern sogar unabdingbar. Auf der anderen Seite bietet sich f"ur komplexere Programme die deklarative Programmierung, etwa im Sinne von purem PROLOG, aus Gr"unden der Erweiterbarkeit und Lesbarkeit an. Daher halten Typ-Konzepte auch verst"arkt Einzug in die logische Programmierung. Die flexible Integration ,,mehrstufiger Typen`` (Sorten) in die relational-funktionale Sprache RELFUN [BEH93] ist das Thema dieser Arbeit.

Konzeptionell werden Individuen (mit gleichen Eigenschaften) zu je einer Sorte zusammengefa"st. Sorten werden zun"achst extensional beschrieben, d.h. alle Individuen der Sorten werden explizit aufgez"ahlt und dann extensional oder intensional benutzt. Durch die Einf"uhrung von Sorten kann das Behauptungswissen (Wissen bzgl. des Anwendermodells) strukturiert werden: auf der Menge der Sorten wird eine explizite Ober-/Untersorten-Relation definiert, wodurch eine partielle Ordnung (,,order-sorted``) entsteht. Man erh"alt so ein neues Abstraktionsniveau, welches durch die Sorten beschrieben und benannt wird [Mey94]. Damit steigt bei der Abarbeitung von Regeln mit Typrestriktionen die Effizienz, da sich der Suchraum bei der L"osungsfindung drastisch reduziert[Sti83][Bei87][Wal84]. Benutzt man getypte Variablen (d.h. Variablen, die nur an Elemente einer gegebenen Sorte gebunden werden k"onnen) im Kopf einer Regel, wird nur versucht die Regel anzuwenden, wenn die Argumentterme von den entsprechenden Sorten sind. In diesem Sinn kann man Sorten als Constraints betrachten [Tsa94]. Aus der Sicht von KL-ONE [BS85] entspricht eine hier direkt zu definierende Sortenhierarchie einer Taxonomie, wie sie eine vorgeschaltete Klassifikation aus einer Menge intensionaler Konzept- oder Sortendefinitionen automatisch produzieren k"onnte . Analog k"onnte die Zuordnung von Individuen zu Sorten durch eine vorgeschaltete Realisation im Sinne von KL-ONE automatisiert werden. Es stellt sich aber heraus, da"s von diesem Ausgangspunkt aus eine Reihe weiterer interessanter Problemstellungen existieren sowie Dienstleistungen und Inferenzen einf"uhrbar sind, wie dies z.T. schon in LIFE [AK88][AKP] gezeigt wurde.

F"ur die Erweiterung der Unifikation zur Sortenunifikation ben"otigt man:

  1. einen Test, der pr"uft, ob ein Individuum zu einer Sorte geh"ort. "Uber die partielle Ordnung, die auf den Sorten definiert wurde, kann man diese Instanzenpr"ufungen von Sorten prinzipiell nach ,,unten`` oder ,,oben`` (wir werden die Richtung nach ,,unten`` benutzen, d.h. ,,r"uckw"arts`` schlie"sen) weiterreichen.
  2. eine GLB-Berechnung (greatest lower bound, Infimum), welche die gr"o"ste gemeinsame Untersorte von zwei gegebenen Sorten bestimmt. Diese kann dynamisch (Modell_1, Modell_2) oder statisch (Modell_3) erfolgen.

In deklarativen Sprachen wie RELFUN kann man Sorten nach dem Muster endlicher Dom"anen als First-Class Citizens einf"uhren [Bol94]; das bedeutet, Sorten werden in die Sprache in nat"urlicher Weise als vollwertige Objekte integriert, indem man sie weitgehend wie gew"ohnliche Terme behandelt. Man kann sie z.B. an logische Variablen binden und als Funktionswert zur"uckgeben (siehe Kapitel ).

Auf die m"oglichen Anforderungen an die Ordnung, die die Taxonomie beschreibt, und an die Interpretation der Sorten wird kurz in Kapitel 3 eingegangen. Anschlie"send werden die beiden Modelle mit dynamischer GLB-Berechnung vorgestellt. Modell_1benutzt ein second-order Pr"adikat, subsumes, und Modell_2verwendet Partitionierung zur Abgrenzung des Sortenwissens vom Behauptungswissen (siehe Kapitel ). Modell_3ist eine Modifikation des zweiten Modells. Es benutzt eine effizientere statische GLB-Berechnung. In Anhang wird ein realistisches Beispiel aus dem Bereich recyclingrelevanter Materialien, RTPLAST [Buh94], gezeigt.



Next: Sorten als First-Class Up: Integration von Sortenals ausgezeichnete Previous: Contents


Harold Boley & Victoria Hall (hall@dfki.uni-kl.de)