{"id":766,"date":"2010-10-12T17:09:06","date_gmt":"2010-10-12T21:09:06","guid":{"rendered":"http:\/\/www.elblender.com\/wordpress\/?p=766"},"modified":"2010-11-12T17:55:07","modified_gmt":"2010-11-12T21:55:07","slug":"prolog-using-examples-part-2","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=766","title":{"rendered":"Prolog using Examples – Part 2"},"content":{"rendered":"

Lets begin with cases related with recursion:<\/p>\n

In an imperative style,\u00a0 you would use a loop to produce a result, while in an functional style, it is common to use recursion to produce the same result.<\/p>\n

The most common example related with recursion is the factorial recursion, in which for example the factorial of 6 (6! = 5 * 4 * 3 * 2 * 1) would give us<\/p>\n

\/* Base case of the factorial, when N is 0 then return 1 *\/\r\nfactorial(0, 1).\r\n\r\nfactorial(N, M) :-\r\n\u00a0\u00a0\u00a0 N1 is N - 1,\r\n\u00a0\u00a0\u00a0 factorial(N1, M1),\r\n\u00a0\u00a0\u00a0 M is N * M1.<\/span><\/pre>\n
?- factorial(6, T).\r\nT = 720;\r\nERROR: Out of local stack<\/span><\/pre>\n
Note:<\/span> As you can see, when we added the OR ‘;’, prolog tried to find another\u00a0 answer and went out of bound.
\nTo prevent this we can do an small modification as follows:<\/p>\n
\/* Base case of the factorial, when N is 0 then return 1 *\/\r\nfactorial(0, 1).\r\n\r\nfactorial(N, M) :-\r\n\u00a0\u00a0\u00a0 N > 0\r\n\u00a0\u00a0\u00a0 N1 is N - 1,\r\n\u00a0\u00a0\u00a0 factorial(N1, M1),\r\n\u00a0\u00a0\u00a0 M is N * M1.<\/span><\/pre>\n
?- factorial(6, T).\r\nT = 720;\r\nFalse<\/span><\/span><\/pre>\n
In this case, when we tell Prolog that we wish to find another possible answer, Prolog would indicate false since it cannot find any other possible solution.<\/p>\n
Lets go over some examples:<\/p>\n
Example 1:<\/span> We have a family and we wish to know the descendent of some individual.<\/p>\n
\r\n
\/* Maria is_mother_of Pedro *\/\r\nis_mother_of(Maria, Pedro).\r\n\r\n\/* Susana is_mother_of Maria *\/\r\nis_mother_of(Susana, Maria).\r\n\r\n\/* Pepe is_father_of Pedro *\/\r\nis_father_of(Pepe, Pedro).\r\n\r\n\/* Diego is_father_of Pepe *\/\r\nis_father_of(Diego, Pepe).\r\n\r\n\/* Person is_parent_of Child if Person is_mother_of Child *\/\r\nis_parent_of(Person, Child):- is_mother_of(Person, Child).\r\n\r\n\/* OR *\/\r\n\r\n\/* Person is_parent_of Child if Person is_father_of_Child *\/\r\nis_parent_of(Person, Child):- is_father_of(Person, Child) *\/\r\n\r\n\/* Begin RECURSION *\/\r\n\r\n\/* Recursion Base *\/\r\n\r\n\/* Person is_decendent_of Adult if Adult is_parent_of Person *\/\r\nis_decendent_of(Person, Adult) :- is_parent_of(Adult, Person).\r\n\r\n\/* Recursion *\/\r\n\/* Person is_decendent_of Adult if Older(person) is_parent_of Person AND Older is_decendent_of Adult *\/\r\n is_decendent_of(Person, Adult) :- is_parent_of(Older, Person), is_decendent_of(Older, Adult).<\/span><\/pre>\n
Example 2:<\/span> Fibonacci (http:\/\/en.wikipedia.org\/wiki\/Fibonacci_number<\/a>) is an integer sequence such as 0, 1, 1, 2, 3, 5, 8… As you may notice, the first two numbers are 0 and 1, an the subsequence is form by a number created from the sum of the two previous numbers: 0 + 1 = 1 (0,1,1) , 1 + 1 = 2 (1,1,2), 1 + 2 = 3 (1,2,3), 2 + 3 = 5 (2,3,5) …<\/p>\n
\r\n
\/* Recursion base case *\/\r\nfibonacci(0, 0).\r\n\r\n\/* Recursion base case *\/\r\nfibonacci(1, 1).\r\n\r\n\/* Recursion *\/\r\nfibonacci(N, F) :-\r\n\u00a0\u00a0\u00a0 N1 is N - 1,\r\n\u00a0\u00a0\u00a0 N2 is N - 2,\r\n\u00a0\u00a0\u00a0 fibonacci(N1, F1),\r\n\u00a0\u00a0\u00a0 fibonacci(N2, F2),\r\n\u00a0\u00a0\u00a0 F is F1 + F2.<\/span><\/pre>\n
?- fibonacci(8, T).
\nT = 21;
\nERROR: Out of local stack<\/span>
\nAgain in this case, when asking prolog to find another answer, it would go out of bounds because there is no case that stop it to keep calling itself. We need to modify this program:<\/p>\n
\r\n
\/* Recursion base cases *\/\r\nfibonacci(0, 0).\r\nfibonacci(1, 1).\r\n\r\n\/* Recursion *\/\r\nfibonacci(N, F) :-\r\n\u00a0\u00a0\u00a0 N > 0,\r\n\u00a0\u00a0\u00a0 N1 is N - 1,\r\n\u00a0\u00a0\u00a0 N2 is N - 2,\r\n\u00a0\u00a0\u00a0 fibonacci(N1, F1),\r\n\u00a0\u00a0\u00a0 fibonacci(N2, F2),\r\n\u00a0\u00a0\u00a0 F is F1 + F2. ?- fibonacci(8, T).\r\nT = 21;\r\nFalse<\/span><\/pre>\n
Again, Prolog couldn’t find a different answer when we ask it to search for it and let it know by returning false after the OR ‘;’.<\/p>\n
Example 3:<\/span> The following code is the Ackermann’s predicate (http:\/\/en.wikipedia.org\/wiki\/Ackermann_function<\/a>)\ufeff\ufeff\ufeff.
\nOne of the purposes to doing this kind of function could be to test the limits of the compiler.
\nThe Ackermann’s functions is defined as follows:
\nackermann( m,n ) =\u00a0\u00a0\u00a0 n + 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 if m = 0
\nackermann( m,n ) =\u00a0\u00a0\u00a0 ackermann(m – 1, 1)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 if n = 0 and m > 0
\nackermann( m,n ) =\u00a0\u00a0\u00a0 ack( m-1, ackermann( m, n-1 ) )\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if n >0 and m > 0<\/p>\n
\/* ackermann(m, n) = n + 1 if m = 0 *\/\r\nackermann(Mi, Ni, No):- Mi = 0, No is Ni + 1.\r\n\r\n\/* ackermann(m, n) = ackermann(m - 1, ackermann(m, n - 1)) if n > 0 and m > 0 *\/\r\nackermann(Mi, Ni, No):-\r\n\u00a0\u00a0\u00a0 Mi > 0, Ni > 0,\r\n\u00a0\u00a0\u00a0 Mi2 is Mi - 1, Ni2 is Ni - 1,\r\n\u00a0\u00a0\u00a0 ackermann(Mi, Ni2, No2),\r\n\u00a0\u00a0\u00a0 ackermann(Mi2, No2, No).\r\n\r\n\/* ackermann(m, n) = ackermann(m - 1, 1) if n = 0 and m > 0 *\/\r\nackermann(Mi, Ni, No):-\r\n\u00a0\u00a0\u00a0 Mi > 0, Ni = 0,\r\n\u00a0\u00a0\u00a0 Mi2 is Mi - 1, Ni2 is 1,\r\n\u00a0\u00a0\u00a0 ackermann(Mi2, Ni2, No).<\/span><\/pre>\n
In the next blog posting, we are going to see Lists in Prolog.<\/p>\n\n