Prolog SLD Tree For Length Predicate
This animation builds the SLD resolution tree for the query ?- len(Zs,Z) using a Prolog program defining list length recursively. It shows how choosing the fact first yields immediate finite solutions on the left, while the recursive rule generates an infinite rightmost branch. A second version swaps fact and rule order, mirroring the tree and making the program loop forever instead of enumerating answers. Useful for students learning logic programming, unification, and clause ordering effects on termination.
Narrated · 16:9 · Preview before teaching · automatic layout checks do not establish subject accuracy
The prompt that made it
K21: (Prolog-Beweisbaum) Gegeben sei folgendes Prolog-Programm: len([],o). (F) len([X|Xs],s(N)) :- len(Xs,N). (R) a) Zeichnen Sie den Prolog-Beweisbaum für obiges Programm und folgender Query ?- len(Zs,Z). Führen Sie dabei mindestens die beiden am weitesten links stehenden Äste und den am weitesten rechts stehenden Ast auf. Beim am weitesten rechts stehenden Ast sind mindestens die ersten drei Knoten aufzuführen. b) Wie ändert sich der Beweisbaum für die gleiche Query, wenn Sie den Fakt und die Regel vertauschen? Was heißt das für das Prolog-Programm? Lösung: a) ?- len(Zs,Z). [Zs/[],Z/o], (F) (R)[Zs/[Z3|Z1s],Z/s(Z1),Xs/Z1s,N/Z1,X/Z3] [Zs/[],Z/o] ?- len(Z1s,Z1). [Z1s/[],Z1/o] (F) [Z1s/[Z4|Z2s],Z1/s(Z2),Xs/Z2s,N/Z2,X/Z4] [Zs/[Z3|[]],Z/s(o)] ?- len(Z2s,Z2). ... b) Der Beweisbaum wird gespiegelt. D.h. der unendliche Ast steht links und das Prolog- Programm liefert keine Lösung.
Make the next one in this series
- Show how Prolog backtracking explores each branch step by step with variable bindings highlighted
- Animate SLD resolution for append/3 to compare finite versus infinite proof trees
- Illustrate how cut (!) changes the shape and pruning of a Prolog proof tree
