DMG Forums | An example about the advantage of setting the length of a list before constructing it
DMG Forums >> 4th Semester >> CSEN 403 - Concepts of Programming Languages >> An example about the advantage of setting the length of a list before constructing it
An example about the advantage of setting the length of a list before constructing it
Author Topic
slim.abdennadher@guc.edu.eg

GUC Faculty

Join Date: 7/8/2008
Posts: 7

Posted: 4/19/2009 12:51:16 PM

Dear All,

If we consider a KB consisting of the following facts:

male(john).
male(harry).
male(tom).
male(tony).
male(david).
male(michael).
male(claudio).
male(friedhlem).

We need to write a rule construct(L,N) that constructs a list L of size N, where L is a list of males (may have duplicates). Consider writing the following two versions of the rule:

list_males_ver1(L,N) :- length(L,N), construct(L).

list_males_ver2(L,N) :- construct(L), length(L,N).

construct([]).
construct([H|T]):- male(H), construct(T).


Now, let's discuss how the following query will be evaluated:

?- list_males_ver1(L,6)

For the first version, we first specify the number of elements to be added to the list. Thus, the interpreter knows that the list to be constructed consists of N elements, and that it has to find out what these elements are.

?- list_males_ver2(L,6)

The second version, constructs the list then checks for whether the constructed list has the required length or not. This means that, the interpreter will first construct the [], then discovers that its length is 0, not 6, so it will discard this solution. After that, all lists of length 1 will be constructed and then discarded because of the length constraint. The same holda for all possible lists of length 2,3,4 and 5. Then when a list is constructed with length 6, the length constraint will be true, and this list will be a valid solution.

From this discussion, we conclude that the first version is much more efficient than the second one. This is made more obvious when the KB is huge and the list to be constructed has a big length. In this case, the program may never terminate.
ismail.el-shaarawy@student.guc.edu.eg

Student

Join Date: 10/13/2008
Posts: 1

Posted: 4/19/2009 1:14:41 PM

Thnx professor :)
ahmed.helal@student.guc.edu.eg

Student

Join Date: 9/28/2008
Posts: 1

Posted: 11/2/2009 9:04:18 PM

thx
omar.alfar@student.guc.edu.eg

Student

Join Date: 10/13/2008
Posts: 1

Posted: 1/17/2010 2:38:02 PM

ibrahim.kessba@student.guc.edu.eg

Student

Join Date: 10/21/2008
Posts: 2

Posted: 3/8/2010 12:07:48 AM

yasmine.magdi@guc.edu.eg

GUC Faculty

Join Date: 9/9/2009
Posts: 6

Posted: 3/18/2010 12:45:14 PM

This error appears when the expression that should be evaluated has a free variable. In this case, prolog cannot evaluate the expression, since it cannot find a value for that variable.

RenewSession