Podcast

Prolog

Was ist Logische Programmierung?

In dieser Folge unterhalten sich Joy Clark und Lucas Dohmen √ľber logische Programmierung und √ľber die Programmiersprache Prolog. Was ist logische Programmierung? Wo spielt es seine St√§rken aus?

Zur√ľck zur Episode

Transkript

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.