Next: Program trace. Writing a Towers of Hanoi program. Using recursion often involves a key insight that makes everything simpler. Often the insight is determining what data exactly we are recursing on - we ask, what is the essential feature of the problem that should change as we call ourselves? May 04, 2017 prolog-hanoi. Towers of Hanoi in Prolog. The towers of Hanoi. A mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
![]()
Recursion: Towers of HanoiUp:.Prev:.Next:.Tracing our Towers solutionCall stackTo use this trace, just keep clicking on the ``Make one step'button. You can use the ``Finish this call' button to skip to the stepafter finishing the current level.The call stack in the display above represents where we arein the recursion. It keeps track of the different levels going on. Thecurrent level is at the bottom in the display.When we make a new recursive call, we add a new level to the call stackrepresenting this recursive call.When we finish with thecurrent level, we remove it from the call stack (this is calledpopping the stack) and continue with where we left off in thelevel that is now current.Another way to visualize what happens when you runMoveTower is called a call tree.
This is a graphicrepresentation of all the calls. Here is a call tree forMoveTower(3,A,B,C).We call each function call in the call tree a node.The nodes connected just below any node n representthe function calls made by the function call for n.Just below the top, for example, are MoveTower(2,A,C,B) andMoveTower(2,C,B,A), since these are the two function callsthat MoveTower(3,A,B,C) makes.
At the bottom are many nodeswithout any nodes connected below them - these represent basecases.Make sure you understand our MoveTower program well.Now we ask: If the monks use MoveTower, how long is it beforethe world ends? To answer this question, we need to learn aboutrecurrences.Next:.
2.2 Two factorial definitionsTwo predicate definitions that calculate the factorial function are in file 22.pl, whichthe reader can view by clicking on the 'Code' link at the bottom of this page. The firstof these definitions is:factorial(0,1).factorial(N,F):-N0,N1 is N-1,factorial(N1,F1),F is N. F1.This program consists of two clauses. The first clause is a unit clause, having no body.The second is a rule, because it does have a body. The body of the second clause is onthe right side of the ':-' which can be read as 'if'. The body consists of literals separatedby commas ',' each of which can be read as 'and'.
The head of a clause is the wholeclause if the clause is a unit clause, otherwise the head of a clause is the part appearing tothe left of the colon in ':-'. A declarative reading of the first (unit) clause says that 'thefactorial of 0 is 1' and the second clause declares that 'the factorial of N is F if N0 andN1 is N-1 and the factorial of N1 is F1 and F is N.F1'.The Prolog goal to calculate the factorial of the number 3 responds with a value for W,the goal variable:?- factorial(3,W).W=6Consider the following clause tree constructed for the literal 'factorial(3,W)'.As explained in the previous section, the clause tree does not contain any free variables,but instead has instances (values) of variables.
Each branching under a node is determined by aclause in the original program, using relevant instances of the variables; the node isdetermined by some instance of the head of a clause and the body literals of the clausedetermine the children of the node in the clause tree.Fig. 2.2All of the arithmetic leaves are true by evaluation (under the intended interpretation), andthe lowest link in the tree corresponds to the very first clause of the program for factorial.That first clause could be writtenfactorial(0,1):- true.and, in fact,?- true is a Prolog goal that always succeeds (true is built-in). For the sakeof brevity, we have not drawn 'true' leaves under the true arithmetic literals.The program clause tree provides a meaning of the program for the goal at the root of the tree.That is, 'factorial(3,6)' is a consequence of the Prolog program, because there is aclause tree rooted at 'factorial(3,6)' all of whose leaves are true. The literal'factorial(5,2)' is, on the other hand, not a consequence of the program because there is noclause tree rooted at 'factorial(5,2)' having all true leaves. Thus the meaning of theprogram for the literal 'factorial(5,2)' is that it is false. In fact,?- factorial(3,6).yes?- factorial(5,2).noas expected.
![]()
Clause trees are so-called AND-trees, since, in order for the root to be aconsequence of the program, each of its subtrees must also be rooted at literals which arethemselves consequences of the program. We will have more to say about clause treeslater. We have indicated that clause trees provide a meaning or semantics for programs.We will see another approach to program semantics in Chapter 6. Clause trees doprovide an intuitive, as well as a correct, approach to program semantics.We will need to distinguish between the program clause trees and so-called Prolog derivation trees.The clause trees are 'static' and can be drawn for a program and goal regardless of theparticular procedural goal-satisfaction mechanism. Roughly speaking, the clause treescorrespond to the declarative reading of the program.Derivation trees, on the other hand, take into account the variable-binding mechanism of Prolog and theorder that subgoals are considered.
Derivation trees are discussed in Section 3.1 (butsee the animation below).A trace of a Prolog execution also shows how variables are bound in order tosatisfy goals. The following sample shows how a typical Prolog tracer is turned onand off.?- trace.% The debugger will first creep - showing everything (trace).yestrace?- factorial(3,X).(1) 0 Call: factorial(3,8140)?(1) 1 Head 2: factorial(3,8140)?(2) 1 Call (built-in): 30?(2) 1 Done (built-in): 30?(3) 1 Call (built-in): 8256 is 3-1?(3) 1 Done (built-in): 2 is 3-1?(4) 1 Call: factorial(2, 8270)?(1) 0 Exit: factorial(3,6)?X=6trace?- notrace.% The debugger is switched offyesThe animated tree below gives another look at the derivation tree for the Prologgoal 'factorial(3,X)'. To start (or to restart) the animation, simply click on the'Step' button.The title of this section referred to two factorial definitions. Here is the other one, withthe same predicate name, but using three variables.factorial(0,F,F).factorial(N,A,F):-N 0,A1 is N.A,N1 is N -1,factorial(N1,A1,F).For this version, use the following type of a goal:?- factorial(5,1,F).F=120The second parameter in the definition is a so called an accumulating parameter. This version isproperly tail recursive. It is very important for the student to complete the following exercises.Exercise 2.2.1 Using the first factorial program, show explicitly that there cannot possiblybe an clause tree rooted at 'factorial(5,2)' having all true leaves.Exercise 2.2.2 Draw an clause tree for the goal 'factorial(3,1,6)' having all true leaves, ina fashion similar to that done for factorial(3,6) previously. How do the two programsdiffer with regard to how they compute factorial?
Also, trace the goal 'factorial(3,1,6)' using Prolog.Prolog for this section.Prolog Tutorial.
![]() Comments are closed.
|
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
March 2023
Categories |