Prolog

Lucas Dohmen: Hallo und herzlich Willkommen zu einer neuen Folge des innoQ-Podcasts. Mein Name ist Lucas Dohmen und heute habe ich zu Gast: Joy Clark. Hallo, Joy!

Joy Clark: Hallo!

Lucas Dohmen: Sag uns doch mal ganz kurz, wer du bist und was du so bei innoQ tust.

Joy Clark: Danke. Ja ich bin die Joy Clark, ich bin Consultant bei innoQ und ich beschäftige mich hauptsächlich mit Webtechnologien und auch mit funktionaler Programmierung. Wobei wir eigentlich heute über logische Programmierung reden wollen.

Lucas Dohmen: Was ist denn logische Programmierung?

Joy Clark: Logische Programmierung ist ein anderes Paradigma von Programmiersprachen. Es beschäftigt sich hauptsächlich… also es ist eine andere Art zu programmieren. In den meisten imperativen Programmiersprachen definieren wir - oder wir erzählen, was der Rechner tun soll und in der logischen Programmierung geht es darum, das Problem zu beschreiben, auf eine Art und Weise, dass der Computer das selber lösen kann oder selber eine Lösung dafür finden kann.

Lucas Dohmen: Ok, das klingt auf jeden Fall sehr interessant. Du hast vorher erzählt, dass die Programmiersprache, mit der du das am liebsten machst, Prolog ist. Kannst du dazu auch noch etwas sagen?

Joy Clark: Ja, Prolog ist eine Programmiersprache, sie ist 1972 entstanden, davon gibt es mehrere Implementierungen. Die zwei bekanntesten Implementierungen sind SWI-Prolog und SICStus-Prolog, wobei SWI-Prolog umsonst zu benutzen ist und SICStus-Prolog eine Lizenz braucht. Sie unterscheiden sich nicht so sehr in Implementierungsdetails, aber sie haben teilweise andere Bibliotheken und so und sind nicht komplett miteinander kompatibel.

Lucas Dohmen: Aha. Und du hast gesagt: Man beschreibt, was man möchte und man schreibt aber nicht hin, wie das geht. Wie kann man sich das denn vorstellen? Was muss ich denn diesem Prolog sagen?

Joy Clark: Es basiert auf Logik, das ist die Basis und dabei können wir zwei Dinge definieren. Wir definieren als erstes Fakten, das ist zum Beispiel, wenn wir sagen, dass Bob der Vater von Tom ist. Wir können dann auch als Fakt definieren, dass Fred der Vater von Bob ist. Dann haben wir zwei Fakten und das können wir sehr einfach definieren. Aber was dann besonders ist, ist, dass man mit Prolog dann Regeln definieren kann. Wie man diese Fakten zusammen kombiniert. Oder einfach Regeln definieren kann, zum Beispiel dass, wenn der Großvater von Person A Person C ist, dann können wir eine Regel definieren, wie wir das berechnen. Und zwar, dass der Großvater von C… Es ist ein bisschen schwer zu erklären. Also ich kann dann eine Regel definieren, der Vater von A ist B und der Vater von B ist C, dann muss der Großvater von A C sein.

Lucas Dohmen: Okay, also ich schreibe hin: Das sind einfach Fakten über die Welt, dass diese beiden miteinander in einer Vater-Sohn-Beziehung stehen, und dann kann ich daraus hinschreiben, wenn ich so etwas weiß, dann stimmt auch noch zusätzlich etwas anderes.

Joy Clark: Es ist ein bisschen schwer, das mündlich zu erklären, weil eigentlich ist die Regel eine Implikation, aber es geht rückwärts. Also man schreibt dann eine Liste an Regeln, in Prolog, wie das so aussieht, man sagt: Ich möchte dieses definieren, ich möchte dieses ausrechnen und wie kann ich das machen. Dann macht man das in Prolog so, es ist eigentlich eine umgedrehte Implikation und dann listet man eine Liste von anderen Regeln auf, die das implizieren, was man berechnen möchte. Das ist, wie es geht.

Lucas Dohmen: Okay. Und wie kann man sich das vorstellen, wie Prolog dann auf Basis von diesen Fakten und Regeln irgendwie Fragen beantworten kann?

Joy Clark: Prolog berechnet alles durch Resolution und, wie ich gesagt habe, die Regeln, die man in Prolog definiert, sind eigentlich eine umgedrehte Implikation und was Prolog dann macht, es versucht deine Regel zu verneinen und dann diese Verneinung zu negieren, also zu widerlegen. Wenn das erfolgreich ist, dann hat Prolog eine Lösung gefunden. Das ist, wie Resolution funktioniert.

Lucas Dohmen: Aber dabei kommt es jetzt nicht zu einer Endlosschleife oder sowas?

Joy Clark: Es kann manchmal nicht terminieren. Aber das liegt meistens daran, dass man eine Rekursion oder so geschrieben hat, die nicht stimmt.

Lucas Dohmen: Also es klingt auf jeden Fall nach einer ganz anderen Art, wie wenn man jetzt in Java oder in Ruby programmiert.

Joy Clark: Ja, das ist es auf jeden Fall.

Lucas Dohmen: Okay, das heißt, wenn ich dann meine Fakten und meine Regeln hingeschrieben habe, kann ich dann dem Programm Fragen stellen oder wie kann ich mir das vorstellen. Also, ich will dann in deinem Beispiel wissen: Wer ist der Großvater von Bob? Wäre das eine Frage, die ich dann stellen kann?

Joy Clark: Ja. Genauso funktioniert das. Man definiert so ein Programm von dem, was wir kennen über die Welt, die Regeln und die Fakten, die so stimmen und dann - in der Regel - macht man häufig so ein REPL (Read Eval Print Loop) auf und stellt dann Queries zusammen. In Prolog sind die Variablen großgeschrieben, nicht kleingeschrieben, und dann versucht Prolog mit - es heißt Unifikation - es versucht, Lösungen für die Variablen zu finden, damit die Regeln und Fakten so stimmen, es eine Lösung finden kann. Und die Lösung ist das, was Prolog berechnet, diese Werte für die Variablen, die dann in dem Fall wahr sind. Prolog kann auch mehrere Lösungen für Regeln finden.

Lucas Dohmen: Also, ist das so ein bisschen, wie man das vielleicht aus dem Mathe-Unterricht kennt, dass man sagt: x + 2 = 7 und dann kann man Prolog fragen: Was ist jetzt x?

Joy Clark: Ja. Wobei das Coole daran ist, dass man auch zum Beispiel sowas sagen kann, wie x + y = 8, finde mir alle Lösungen für x und y, damit das stimmt. Also es ist nicht… Wenn wir programmieren, denken wir sehr oft iterativ, aber Prolog kann auch rückwärts berechnen, weil es keine wirkliche Reihenfolge von den Variablen gibt. Prolog weiß nicht, dass es nicht aus einer… also x + y = z, dass es das nicht rückwärts berechnen kann, denn es kann das. Das ist ziemlich cool.

Lucas Dohmen: Aber das würde wahrscheinlich ziemlich lange dauern.

Joy Clark: Mit Addition, weil das nicht so sehr auf Logik basiert in den meisten Fällen, das stimmt, das dauert länger, aber zum Beispiel wenn man Peano-Arithmetik oder so in Prolog selber definiert, kann man das wirklich machen und relativ flott.

Lucas Dohmen: Ok. Und wie kann ich mir dann die Syntax so ungefähr vorstellen? Wie schreibe ich das hin? Sieht das so aus wie C?

Joy Clark: Das sieht aus wie Erlang. Beziehungsweise Erlang sieht aus wie Prolog, weil Prolog zuerst kam. Im Wesentlichen hat man einfach, wie gesagt, so die Regeln, Regeln definiert man so mit einem Namen der Regel, offenen Klammern und die Sachen, die dazwischen sind, also entweder Variablen oder Atome oder irgendwas, was dazwischen kommt, und dann in Prolog ist ein Komma “und”, ein Semikolon ist “oder” und ein Doppelpunkt-Strich ist diese umgedrehte Implikation.

Lucas Dohmen: Und dann gibt es ja noch irgendwie einen Punkt, der da auch immer häufig benutzt wird.

Joy Clark: Ein Punkt ist immer am Ende. Das sagt, dass diese Regel zuende ist. Eine Regel besteht aus diesen Compound-Terms oder was auch immer - dieser Syntax - und dann dieser Doppelpunkt-Strich, das ist auch da drinnen, aber wenn ich sage: Das ist das Ende, ich habe das fertig definiert, dann macht man einen Punkt.

Lucas Dohmen: Also so ähnlich wie ein Semikolon in anderen Programmiersprachen vielleicht?

Joy Clark: Außer, dass in Prolog ein Semikolon “oder” bedeutet.

Lucas Dohmen: Ok. Du hast eben das Wort “Atom” benutzt, was bedeutet Atom?

Joy Clark: Atome sind einfach Werte, die für sich selber stehen. Also zum Beispiel Bob, das ist so ein Name. Aber ich schreibe einfach Bob hin und das ist ein Atom und steht für sich selber.

Lucas Dohmen: Und der muss kleingeschrieben sein?

Joy Clark: Der muss kleingeschrieben sein, ja.

Lucas Dohmen: Okay. Und gibt es auch andere Sachen außer Atomen und Variablen?

Joy Clark: Ja, es gibt Zahlen: Integer und Floats, es gibt Compound Terms, das ist so ein… man nennt es… Punkte und Argumente, das sind so genannte Tupel, zum Beispiel Listen sind eine besondere Art von Compound Terms. Wie man das in Lisp kennt, so ein Cons: Man hat das erste Element und dann den Rest von der Liste als zweites Argument von diesen Terms. Seit 2016, glaube ich, gibt es Dicts und Strings.

Lucas Dohmen: Wow!

Joy Clark: Die sind jetzt dran. Es war historisch, als ich Prolog gelernt habe, vor so 3 Jahren oder so…

Lucas Dohmen: Sehr historisch!

Joy Clark: …gab es noch keine Strings, sondern sie haben dann tatsächlich Listen von den Atom Codes, also von den ASCII-Codes, die Werte, das waren dann Strings. Das war manchmal sehr lästig. Aber jetzt inzwischen, habe ich herausgefunden, dass zumindest in SWI-Prolog es seit ungefähr einem Jahr Strings gibt.

Lucas Dohmen: Wow! Also, nach so einer langen Geschichte Strings einzuführen, ist äh… Es bedeutet auf jeden Fall: die Sprache ist nicht tot. Es entwickelt sich immer noch weiter, ne?

Joy Clark: Oft, ja.

Lucas Dohmen: Okay, also wir kennen jetzt Regeln, Fakten und Datentypen und du hast auch schon beschrieben, wie man die so definiert. Aber was sind denn so typische Techniken, die ich benutze in der Programmiersprache?

Joy Clark: In Prolog schreibt man fast immer alles rekursiv. Also, man benutzt Pattern Matching sehr, sehr stark ,und zum Beispiel ist es sehr häufig, dass man irgendwie über eine Liste so… in Java würde man iterieren. In Prolog hat man nicht diese Möglichkeit zu iterieren, sondern man macht das wirklich mit Pattern Matching und sagt, ich definiere eine Regel: Wenn diese Liste leer ist, dann muss ich diesen Wert zurückgeben oder diesen Wert definieren. Aber wenn sie nicht leer ist, dann entpacke ich die Liste, ich mache irgendetwas mit dem ersten Element und dann bearbeite ich die Liste weiter, also den Tail von der Liste mit einem rekursiven Aufruf. Das ist sehr häufig, das ist das Pattern, das am häufigsten benutzt wird in Prolog, würde ich sagen.

Lucas Dohmen: Okay. Das klingt so ein bisschen nach funktionaler Programmierung, oder?

Joy Clark: Es ist leicht funktional. Wobei man nicht… Also, in funktionaler Programmierung hat man Funktionen und man benutzt so high-order functions. Es gibt einige high-order functions auch in Prolog, zum Beispiel ‘map’. Aber in funktionalen Programmiersprachen ist es nicht häufig, dass man Rekursion benutzt, hab ich das Gefühl. In Prolog benutzt man viel häufiger Rekursion.

Lucas Dohmen: Das heißt, man erkennt Dinge aus der funktionalen Programmierung wieder, aber es gibt keine Funktionen, ja?

Joy Clark: Zum Beispiel immutable data structures sind dabei, weil es tatsächlich nicht… also in der Logik gibt es so etwas nicht, etwas, das mutable sein kann.

Lucas Dohmen: Also ein Fakt ist auch immutable?

Joy Clark: Ja.

Lucas Dohmen: Okay. Also, wenn ich das so höre, klingt das für mich ein bisschen so, als wäre das näher an der funktionalen Programmierung als an der objektorientierten Programmierung. Würdest du das so sehen?

Joy Clark: Das kann sein. Ich würde aber sagen, ich packe das schon in eine eigene Kategorie. Und meiner Meinung nach gibt es mindestens vier Paradigmen: es gibt imperativ, objektorientiert, funktional und logisch. Logisch ist schon eine eigene Kategorie. Und ich finde, es ist gut, wenn man eine von allen gesehen hat. Das hilft sehr viel. Einfach, weil man auf jeden Fall umdenken muss. Man muss lernen, auf eine andere Weise zu denken, als wenn man eine von den anderen Sprachen benutzt. Und das bringt einem sehr viel, auch wenn man dann nicht unbedingt alle… man macht dann nicht alles in Prolog. Aber man hat diese Denkweise schon mal gesehen und das bringt sehr viel, das aus dem Grund zu lernen.

Lucas Dohmen: Für mich klang das jetzt ein bisschen so… wenn ich jetzt typischerweise eine Webanwendung schreibe, kann ich mir jetzt nicht so richtig vorstellen, dass ich das alles in Fakten und Regeln ausdrücke, vielleicht. Wo siehst du denn die Stärken? Wo würdest du persönlich Prolog benutzen und keine andere Programmiersprache?

Joy Clark: Ich sehe die Stärke vor allem, wenn man so etwas hat wie: Ich möchte eine Lösung für irgendetwas haben und ich kenne die constraints, die das beeinflussen. Zum Beispiel, wir haben bei uns in der Firma für unsere Events so “Project Speed Dating”. Das ist so, wir haben nicht genügend Zeit, also, wir wollen, dass alle mit allen reden, aber wir sagen, wir wollen dann irgendwie Tupel bilden von drei Paaren. Also, dass jede Person gezwungen wird, mit drei verschiedenen Personen zu reden, damit wir Projektaustausch haben können und so. So was. Und wir haben das einmal gemacht und alle haben sich beschwert, weil dieser Algorithmus schlecht war. Es wurde einfach gewürfelt. Und alle haben gemeint: Ich bin aber bei jemandem gelandet, mit dem ich sowieso in einem Projekt bin, und ich rede mit dieser Person jeden Tag. Dann sind diese zehn Minuten, die man dort vor Ort hat, einfach verschwendet. Das ist so quasi der Fall, wo man Prolog verwendet. Weil man kann einfach dann Fakten definieren: Also, diese Person ist in diesem Projekt, und die wirklich deklarativ aufschreiben und Prolog sagen, berechne mir diese Paare, sodass keine Person mit jemandem zusammen ist, der im gleichen Projekt ist. Ich hab das innerhalb von einem Tag vielleicht geschrieben und es hat einfach funktioniert. Denn das ist einfach etwas, was Prolog kann.

Lucas Dohmen: Okay, das heißt, du kanntest dann also da unsere Firmenstruktur beschreiben, zum Beispiel die Joy ist in dem Projekt xy, und danach fragen, welche Leute haben nicht so viel miteinander zu tun, im Prinzip?

Joy Clark: Also, ich hab dann einfach so eine strenge Regel definiert. Ich habe die Liste von Menschen genommen und bin dann rekursiv die Liste durchgegangen und habe versucht, einen Partner für diesen Mensch zu finden. Also, finde einen Partner aus dem Rest der Liste. Die davor haben schon einen Partner, quasi. Das ist, wie ich es gemacht habe. Und dann habe ich gesagt: Finde mir einen Partner, der passt, aus dem Rest der Liste. Da habe ich dann eine Regel dafür definiert, dass diese Person nicht im gleichen Projekt sein darf, wie die Person, für die ich gerade suche. Und der Vorteil davon, also von Prolog, ist dann, falls das nicht klappt, falls in diesem Fall keine Lösung gefunden wurde, weiß Prolog, wie zu backtracken. Es weiß: Das hat nicht geklappt, also geht er dann zurück. Man kann sagen, falls diese Regel nicht klappt, kann ich definieren, was ich nachher machen möchte. Und dadurch kann, falls es eine Lösung gibt zu dieser Liste von Menschen, die ich angebe, und den Regeln, die ich definiert habe, wird Prolog das finden und zwar relativ zügig. Also, es ist nicht so, dass es ewig dauert. Jemand hat gesagt: Ah, das kannst du nicht machen, das wird constraint Programming und so, dann dauert das eine Ewigkeit, bis man die Lösung gefunden hat, weil es zu viele Möglichkeiten gibt, aber es dauert so zwei Sekunden. Weil Prolog gut darin ist.

Lucas Dohmen: Okay, das, würde ich sagen, ist ausreichend schnell. Und hast du schon andere Sachen mit Prolog gebaut?

Joy Clark: Ja, Prolog ist auch gut für Interpreter, weil man mit definite clause grammars quasi eine Grammatik von einem Parser definieren kann, einfach so. Es sieht aus wie ein Parser, also ich definiere, wie meine Grammatik für einen Parser ist und dann schreibe ich es so auf und dann parst Prolog diesen String. Und ich hab dafür so einen Brainfuck-Interpreter geschrieben.

Lucas Dohmen: Und den kann man, glaube ich, sogar auf GitHub sehen, ne?

Joy Clark: Ja.

Lucas Dohmen: Cool.

Joy Clark: Das ist so das typische Beispiel von einem Interpreter. Also der Witz daran ist, dass das eine Uniaufgabe war und typischerweise benutzt man einen Stack und verwaltet so ganz viele Dinge mit diesem Ding und das ist mir nicht eingefallen als Lösungsvorschlag. Ich hab einfach dieses Programm geparst, weil es in Prolog super einfach ist, einen Parser zu schreiben, und habe dann quasi aus dem abstract syntax tree, der da raus gekommen ist, einen normalen Interpreter geschrieben mit ein paar Regeln und das lief sehr gut.

Lucas Dohmen: Aber da musstest du ja dann auch schon auf die nicht vorhandenen Strings zurückgreifen, ne, weil du ja auf einem Programm parsen musst.

Joy Clark: Das ist genau die Stelle, wo ich herausgefunden habe, dass Strings jetzt existieren. Denn das Programm hab ich aus meinem Unikram herausgeholt, weil ich dachte, ah, ja, das war witzig, ich hab das mal gemacht, ich möchte das wieder anschauen. Das war letzten August oder so, als ich das auf GitHub packen wollte, und ich habe es ausgestestet und ja, wie, es hat inzwischen Strings? Also ich hab dann ein bisschen umschreiben müssen.

Lucas Dohmen: Und das hat dann funktioniert?

Joy Clark: Es hat funktioniert.

Lucas Dohmen: Ah, cool. Und wir hatten ja am Anfang über logische Programmierung gesprochen und Prolog war ein Beispiel dafür. Gibt es da denn noch andere Programmiersprachen, die so funktionieren?

Joy Clark: Ja, es gibt ein paar. Ich kenne mich da nicht so gut aus. Es gibt zum Beispiel miniKanren, was ich selber nicht ausprobiert habe, aber ich möchte sie noch ausprobieren. Der Vorteil daran ist, dass die in eine andere Sprache eingebettet werden können. Zum Beispiel gibt es core.logic im Clojure Universum, das ich unbedingt ausprobieren möchte und nur noch nicht zu gekommen bin.

Lucas Dohmen: Das klingt ja nach einer interessanten Kombination, wenn man dann für die Sachen, für die es besonders stark ist, die Logik benutzen kann und für den Rest den funktionalen Teil.

Joy Clark: Ja. Und eben nicht eine andere Sprache lernen muss.

Lucas Dohmen: So, wenn ich jetzt als Zuhörer denke, das mit diesem Prolog, das klingt ziemlich cool, was kann ich denn da machen? Also gibt es da Tutorials oder Bücher?

Joy Clark: Ja, es gibt einige Tutorials im Internet, die können wir bestimmt verlinken. Ich selber habe in der Uni Prolog gelernt und benutzt und deswegen kann ich die Tutorials nicht so gut einschätzen, wie gut sie sind.

Lucas Dohmen: Okay. Aber wir packen trotzdem mal ein paar Links in die Shownotes dazu. Du hattest am Anfang gesagt, es gibt verschiedene Interpreter oder verschiedene Implementierungen, womit würde ich am besten anfangen als…

Joy Clark: Also, wenn man es einfach ausprobieren möchte, definitv SWI-Prolog. Weil SICStus eine Lizenz braucht und die hat man üblicherweise nicht und es lohnt sich nicht, die zu kaufen, um es in Prolog auszuprobieren.

Lucas Dohmen: … wenn man es nur ausprobieren will. Okay, super. Gut, dann danke ich dir für den Überblick über die logische Programmierung.

Joy Clark: Bitteschön.

Lucas Dohmen: Und den Zuhörern bis zur nächsten Folge vom innoQ-Podcast.