Ein funktionales Programm besteht aus Funktionen im mathematischen Sinn: Das Ergebnis hängt nur von den Argumenten ab, und keine Variable ändert im Lauf des Programms ihren Wert. Solche Funktionen heißen rein. Schleifen werden durch Rekursion ersetzt. Zwei Mittel prägen den Stil:

• Kombination: Eine Funktion ruft andere Funktionen auf oder bekommt deren Ergebnis als Argument. So entstehen aus kleinen Funktionen größere.
• Abstraktion: Ein Muster, das mehrfach vorkommt, wird zu einer Funktion mit Parameter. Auch eine Funktion kann Parameter sein (Funktion höherer Ordnung).

Wir schreiben die Funktionen in Python-Schreibweise, aber ohne Schleifen und ohne veränderte Variablen.

Hier beschreibst du ein Gebiet durch Wissen. Wir nutzen die Schreibweise der Sprache Prolog. Grundlage ist die Prädikatenlogik: Ein Prädikat ist eine Aussage über Dinge, etwa $\texttt{eltern(anna, ben)}$ für „Anna ist Elternteil von Ben“. Die Zahl der Argumente heißt Stelligkeit, $\texttt{eltern}$ ist zweistellig. Namen mit kleinem Anfangsbuchstaben sind feste Dinge, Namen mit großem Anfangsbuchstaben sind Variablen. Aussagen mit Variablen gelten für alle Belegungen (Allquantor $\forall$). Eine Anfrage mit Variablen fragt, ob es mindestens eine Belegung gibt (Existenzquantor $\exists$).

Das Wissen steht in Klauseln, hier in zwei Arten:

• Ein Fakt ist eine Klausel ohne Bedingung, etwa $\texttt{eltern(anna, ben).}$
• Eine Regel $\texttt{kopf :- rumpf.}$ liest man „kopf gilt, wenn rumpf gilt“. Im Rumpf bedeutet das Komma „und“. „Oder“ schreibst du als mehrere Regeln mit demselben Kopf.

Eine Anfrage beginnt mit $\texttt{?-}$ und fragt, ob eine Aussage aus dem Wissen folgt und für welche Werte der Variablen. Fakten und Regeln zusammen heißen Wissensbasis. Eine Regel entspricht einer Formel der Prädikatenlogik:

Die Inferenzmaschine leitet aus der Wissensbasis Antworten her. Sie arbeitet rückwärts vom Ziel:

• Sie sucht von oben nach unten die erste Klausel, deren Kopf zum Ziel passt, und bindet dabei Variablen an Werte.
• Bei einem Fakt ist das Ziel erfüllt. Bei einer Regel werden die Teilziele des Rumpfs von links nach rechts bearbeitet.
• Findet sie für ein Teilziel keine Klausel, schlägt es fehl. Dann kehrt sie zum letzten Punkt zurück, an dem noch eine andere Klausel zur Wahl stand, löst die Bindungen wieder und probiert die nächste. Das ist Backtracking.

Alle Möglichkeiten bilden einen Baum, in dem jedes Ziel zu Teilzielen verzweigt. Die Inferenzmaschine durchläuft ihn per Tiefensuche: Sie folgt einem Pfad bis zum Erfolg oder Misserfolg und geht erst dann zurück. Das ist dasselbe Prinzip wie bei der Tiefensuche in Graphen und beim Backtracking in der Rekursion.

Vorgehen: Du klärst, welche Dinge und Beziehungen vorkommen, und legst die Prädikate mit Stelligkeit fest. Gesicherte Tatsachen werden Fakten, allgemeine Zusammenhänge Regeln. Zuletzt testest du mit Anfragen, die gelingen, und mit solchen, die misslingen sollen.

Beispiel Schulbibliothek: Mitglieder dürfen verfügbare Bücher ausleihen. Fakten: $\texttt{mitglied(lea).}$ $\texttt{mitglied(tom).}$ $\texttt{verfuegbar(faust).}$ $\texttt{verfuegbar(momo).}$ Regel: $\texttt{darf\_ausleihen(P, B) :- mitglied(P), verfuegbar(B).}$ Die Anfrage $\texttt{?- darf\_ausleihen(lea, B).}$ liefert $\texttt{B = faust}$ und $\texttt{B = momo}$. Die Anfrage $\texttt{?- darf\_ausleihen(max, B).}$ liefert $\texttt{false}$, weil $\texttt{mitglied(max)}$ nicht in der Wissensbasis steht. Was nicht herleitbar ist, gilt dem System als falsch (Annahme der geschlossenen Welt).

SQL ist ebenfalls deklarativ: $\texttt{SELECT}$ beschreibt das Ergebnis, nicht den Weg. Die Regel $\texttt{grosseltern}$ ist eine Zeile, imperativ bräuchtest du zwei verschachtelte Schleifen über alle Elternpaare.