GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
AI::Prolog::Cookbook(3) User Contributed Perl Documentation AI::Prolog::Cookbook(3)

AI::Prolog::Cookbook - Recipes for common Prolog problems

 $Id: Cookbook.pod,v 1.1 2005/08/06 23:28:40 ovid Exp $

Logic programming can take some time to get used to. This document is intended to provide solutions to common problems encountered in logic programming. Many of the predicates listed here will depend on other predicates defined here. If in doubt, see AI::Prolog::Builtins for which predicates AI::Prolog supports directly.

Like most predicates in Prolog, the following predicates can be reused in ways to generate answers that a human could logically infer from the data presented. However, many times those "answers" can result in infinite loops. For example, in the "gather/3" predicate listed below, we can gather the items from a list which match the supplied list of indices.

 gather([1,3], [a,b,c,d], Result). % Result is [a,c]

Or we can figure out which indices in a list match the resulting values:

 gather(Indices, [a,b,c,d], [a,d]). % Indices is [1,4]

However, if we wish to understand which lists will have the given lists for the given indices, we have an infinite result set. AI::Prolog and (other Prolog implementations) will return one result and then enter an infinite loop if you request the goal be resatisfied (i.e., if you ask for another result). If you see behavior such as this in your programs, you can issue the "trace." command to see how Prolog is internally attempting to satisfy your goal. "notrace." will turn off tracing.

Usage: "append(List1, List2, Result)."

 append([], X, X). % appending an empty list to X yields X
 append([W|X], Y, [W|Z]) :-
    append(X, Y, Z).

Usage: "member(Item, List)."

 member(X, [X|_]).
 member(X, [_|Tail]) :-
    member(X, Tail).

Usage: "member(Index, Item, List)."

 member(1, SearchFor, [SearchFor|_]).
 member(Index, SearchFor, [_|Tail]) :-
    member(Previous, SearchFor, Tail),
    Index is Previous + 1.

Please note that assignment in Prolog is via the "is/2" infix operator. The above code will fail if you use "=/2". This is a common source of bugs for programmers new to Prolog. The "=/2" predicate will unify the right hand side with the left hand side. It will not evaluate the left hand side. Thus:

 X = 3 + Y.
 % X is now plus(3,Y) (the internal form of the +/2 infix operator.)

If you prefer your list indices start with zero, alter the first clause as follows:

  member(0, SearchFor, [SearchFor|_]).

Usage: "gather(Indices, FromList, Result)."

This definition depends on the "member/3" predicate defined in this document.

 gather([], _, []).
 gather([First|Remaining], FromList, [ResultHead|ResultTail]) :-
    member(First, ResultHead, FromList),
    gather(Remaining, FromList, ResultTail).

Example queries:

 gather([2,4], [a,b,c,d,e], Result).      % Result = [b,d]
 gather(FromIndices, [a,b,c,d,e], [b,d]). % FromIndices = [2,4]

This example is tricky when one realizes that one can reuse predicates. In this case, it might be tempting to see which lists from which one can gather certain values from certain indices. The first time you try it, you may get results as follows:

 gather([2,4], WhichList, [x,y]).

This query, when executed in the "aiprolog" shell will output a response similar to this:

 gather([2,4], [A,x,B,y|C], [b,d]).

When examining this, we see that the first, third, and fifth elements (and beyond) of the list are variables. Unfortunately, as an infinite number of lists will satisfy this goal, attempting to fetch the a second result from the same query will result in an infinite loop.

Usage: "intersection(List1, List2, Intersection)."

This definition depends on the "member/2" predicate defined in this document.

 intersection([H|T], L, [H|U]) :-
    member(H,L),
    intersection(T,L,U).
 intersection([_|T], L, U) :-
    intersection(T,L,U).
 intersection(_,_,[]).

The "intersection/3" predicate will compute the intersection of two lists. You probably only want the first result from this predicate. See "trace/0" to understand why it returns more than one intersection.

Usage: "reverse(List, ReversedList)."

 reverse(List, Reverse) :-
    reverse_accumulate(List, [], Reverse).
 reverse_accumulate([], List, List).
 reverse_accumulate([Head|Tail], Accumulate, Reverse) :-
    reverse_accumulate(Tail, [Head|Accumulate], Reverse).

Reversing a list is tricky. If this predicate were written in an imperative manner, it might look something like this:

 sub reverse {
   my @list = @_;
   my @reverse;
   while (my $element = shift @list) {
     unshift @reverse, $element;
   }
   return @reverse;
 }

This method of reversing a list runs in O(n) time. However, new Prolog programmers often write what is known as the "naive reverse" which uses the "append/3" predicate to reverse a list:

 reverse([],[]).
 reverse([Head|Tail], Reverse) :- 
    reverse(Tail, ReverseTail), 
    append(ReverseTail, [Head], Reverse).

For this, you take the tail of the list, reverse it and append the head of the list to it. However, this runs in "O(N^2)". This runs so slowly that reversing a 30 element list takes 496 logical inferences. As a result, the naive reverse is frequently used as a benchmarking tool for logic programs.

If reversing a 30 element list via the naive reverse takes .1 seconds, we can say that the Prolog implementation is running at about 5000 logical inferences per second. This is known by the unfortunate acronym of LIPS, the standard measure of the speed of logic programs. Modern Prolog implementations frequently measure their performance in MLIPS, or MegaLIPS. By contrast, the human mind is frequently estimated to run between 1 to 4 LIPS. This demonstrates that there's much more to cognition than logic.

Usage: "subset(Subset, List)."

This definition depends on the "member/2" predicate defined in this document.

 subset([Head|Tail], List) :-
    member(Head, List),
    subset(Tail, List).
 subset([], _). % The empty list is a subset of all lists

Usage: "delete(Term, List, Result)."

 delete(_,[],[]). % deleting anything from an empty list yields an empty list
 delete(Term, [Term|Tail], Result) :- 
    delete(Term, Tail, Result).
 delete(Term, [Head|Tail], [Head|TailResult]) :- 
    delete(Term, Tail, TailResult).

Usage: "partition(Value, List, LHS, RHS)."

Note that the term at Value will be included in the LHS.

 partition(Value, [Head|Tail], [Head|LHS], RHS) :-
    Head <= Value,
    partition(Value, Tail, LHS, RHS).
 partition(Value, [Head|Tail], LHS, [Head|RHS]) :-
    partition(Value, Tail, LHS, RHS).
 partition(_,[],[],[]).

Usage: "sort(List, Sorted)."

This definition depends on the "partition/4" and "append/3" predicates defined in this document.

 sort([], []).
 sort([Head|Tail], Sorted) :-
    partition(Head, Tail, LHS, RHS),
    sort(LHS, Temp1),
    sort(RHS, Temp2),
    append(Temp1, [Head|Temp2], Sorted).

Note that (currently), this will only sort numeric values.

AI::Prolog

AI::Prolog::Builtins

AI::Prolog::Introduction

W-Prolog: <http://goanna.cs.rmit.edu.au/~winikoff/wp/>

X-Prolog: <http://www.iro.umontreal.ca/~vaucher/XProlog/>

Roman Barták's online guide to programming Prolog: <http://kti.ms.mff.cuni.cz/~bartak/prolog/index.html>

Curtis "Ovid" Poe, <moc tod oohay ta eop_divo_sitruc>

Reverse the name to email me.

Copyright 2005 by Curtis "Ovid" Poe

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

2007-01-15 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.