Wie viele Dreiecke sehen Sie?…oder die Eleganz der deklarativen Programmierung

Mai 2021, Markus Schacher

Vielleicht ist Ihnen die folgende Denksportaufgabe auch schon über den Weg gelaufen:

Mit ein bisschen überlegen und/oder zählen kommt man auf die erstaunliche Anzahl von 24 Dreiecken. Nun möchte ich aber dieses Beispiel als Grundlage für eine „Denksportaufgabe zweiten Grades“ nehmen: Wie bringe ich einem Computer bei, diese Aufgabe zu lösen?

Das Beispiel eignet sich hervorragend dazu, die Eleganz deklarativer Programmierung (im Gegensatz zur imperativen Programmierung) aufzuzeigen. Als Programmiersprache verwende ich daher Prolog (statt bekanntere und gängigere Sprachen wie C++, Java und ähnliche). Bei der imperativen Programmierung muss bekannterweise der Ansatz zur Lösung eines Problems in Form einer (oder mehreren) Prozeduren beschrieben werden, die dem Rechner Schritt für Schritt aufzeigen, wie das Problem zu lösen ist. Im Gegensatz dazu wird bei der deklarativen Programmierung dem Rechner lediglich das Problem beschrieben und der Rechner sucht sich dann selbständig eine Lösung, die passt.

Im Falle der obigen Denksportaufgabe umfasst die Problembeschreibung zwei Teile:

  1. Wie sieht die Figur aus?
  2. Was ist ein Dreieck?

Ein Prolog-Programm ist eine Menge von Sätzen, die jeweils durch einen Punkt abgeschlossen sind und die jeweils entweder Fakten oder Regeln darstellen. Diese Sätze sind aus domänenspezifischen Worten (oder Worten aus einem vordefinierten Grundwortschatz) sowie ein paar wenigen Satzzeichen aufgebaut und müssen strikten Gross-/Kleinschreibungsregeln folgen.

Beschreibung der Figur

Die Beschreibung obiger Figur erfolgt durch 7 Fakten, die jeweils eine Linie in obiger Figur beschreiben und durch welche Punkte sie führen. In Prolog sieht sie wie folgt aus:

linie([1, 5, 11]).
linie([1, 4, 6, 10]).
linie([1, 3, 7, 9]).
linie([1, 2, 8]).
linie([2, 3, 4, 5]).
linie([5, 6, 7, 8]).
linie([8, 9, 10, 11]).

Definition eines Dreiecks

Der zweite Teil der Problembeschreibung ist eine Regel, die beschreibt, wann drei Eckpunkte A, B und C ein Dreieck bilden. Eine Regel ist so etwas wie ein „bedingtes Faktum“ – eines, das nur wahr ist, wenn gewisse Bedingungen erfüllt sind. Für unsere Aufgabe sieht das in Prolog wie folgt aus:

dreieck(A, B, C) :-
  linie(L1),
  linie(L2),
  linie(L3),
  L1 \= L2,
  member(A, L1),
  member(B, L1),
  member(A, L2),
  member(C, L2),
  member(B, L3),
  member(C, L3),
  A < B,
  B < C.

Die erste Zeile ist das „bedingte Faktum“ das besagt, dass beliebige Eckpunkte A, B, und C ein Dreieck bilden. Die Bedingung wird durch das Satzzeichen „:-“ eingeleitet und durch die folgenden Zeilen formuliert. Die Bedingung selber umfasst mehrere Zeilen von Einzelbedingungen, die jeweils durch ein Komma getrennt sind, was in Prolog eine „UND“-Verknüpfung darstellt. Grossbuchstaben versteht Prolog als logische Variabeln, deren Wert Prolog selbständig bestimmen soll.

  • Die ersten vier Teilbedingungen besagen, dass für ein Dreieck überhaupt drei Linien L1, L2 und L3 existieren müssen und zumindest die ersten zwei unterschiedlich sein müssen (sonst könnten alle Punkte eines Dreiecks auf einer einzigen Linie liegen).
  • Die nächsten 6 Zeilen besagen, dass es auf jeder dieser drei Linien jeweils zwei Punkte geben muss, die unseren drei gesuchten Punkten des Dreiecks entsprechen. Man beachte, dass beispielsweise Punkt A auf Linie L1 und L2 jedoch nicht auf L3 liegen muss. Die einzelnen Punkte werden durch die in der Figurenbeschreibung gezeigten Zahlen identifiziert. member(Element, Liste) ist dabei ein Wort (genauer gesagt: ein Prädikat) aus einem vordefinierten Grundwortschatzz das besagt, dass es genau dann wahr ist, wenn Element in der Liste enthalten ist.
  • Mit den letzten zwei Teilbedingungen schränken wir schliesslich ein, dass die drei Punkte eines Dreiecks jeweils in aufsteigender Reihenfolge zu betrachten sind. Somit wird verhindert, dass das Dreieck „1-8-11“ als ein anderes Dreieck betrachtet wird als „11-1-8“. Da die ganze Regel einen einzigen Satz bildet, muss sie wiederum mit einem Punkt abgeschlossen werden.

Abfrage der Lösung

Damit ist das Problem für Prolog vollständig formuliert und wir können Prolog nach der Lösung fragen. Prolog ist von Natur aus eine interaktive Sprache, bei der wir einem Prolog-System Fragen stellen können und (hoffentlich) Antworten geliefert bekommen. Dies sieht dann konkret wie folgt aus („?-“ ist die Aufforderung von Prolog eine Frage zu stellen, „;“ ist die Aufforderung nach einer weiteren Lösung „ODER“):

?- dreieck(A, B, C).
A=1, B=5, C=6 ;
A=1, B=5, C=7 ;

A=7, B=8, C=9 ;
no

Nach der 24. Lösung antwortet Prolog mit „no“ – es gibt keine weiteren Lösungen mehr! Eine etwas komplexere Frage, die zwei weitere eingebaute Worte aus dem Grundwortschatz nutzt (findall(Lösung, Frage, Lösungen) und length(Liste, Anzahl)), kann gleich mehrere Antworten auf’s Mal liefern und sieht wie folgt aus:

?- findall((A,B,C), dreieck(A,B,C), Dreieckliste), length(Dreieckliste, Anzahl).
Dreieckliste=[(1,5,6),(1,5,7),(1,5,8),(1,4,5),(1,10,11),(1,6,7),(1,6,8),(1,3,5),
(1,9,11),(1,3,4),(1,9,10),(1,7,8),(1,2,5),(1,8,11),(1,2,4),(1,8,10),(1,2,3),
(1,8,9),(4,5,6),(3,5,7),(2,5,8),(5,8,11),(6,8,10),(7,8,9)], Anzahl=24

Selber ausprobieren!

Falls Sie Prolog einmal selber ausprobieren möchten, gibt’s eine einfach zu bedienende Browser-Variante: SWISH — SWI-Prolog for SHaring – keine Installation notwendig!

Zusammenfassung

Gewisse (logische) Probleme lassen sich hervorragend mit deklarativen Sprachen wie Prolog formulieren und lösen. Dies verschafft diesen Programmiersprachen einen entscheidenden Vorteil gegenüber konventionellen Sprachen. Bei KnowGravity haben wir mit CASSANDRA sogar ein ganzes Betriebssystem in Prolog geschrieben, mit dem sich beispielsweise in eXecutable UML (xUML) formulierte Spezifikationen ausführen und testen lassen. Wenden Sie sich an uns, wenn Sie mehr wissen möchten!