Using Structures: Terms in Prolog
Mikhail Soutchanski October 1, 2021
Example: Data Base about Families
To illustrate terms we consider a database with structured information about people and families. We introduce the following.
Copyright By PowCoder代写 加微信 powcoder
The predicate family (Husband , Wife, ListOfChildren) is true if the 1st and the 2nd argument represent a father and a mother of children in the 3rd argument
Two terms:
person(FirstName, LastName, DOB, Job) date(Day , Month, Year )
These terms can be used as arguments of the predicate family to represent information in a more structured way.
Since person and date are terms, they can only occur inside the predicate family or as arguments of “equality” (=).
Example: consider the predicate “less than” and a term composed from the function “sum”, both written with the usual notation, e.g.,
(a + b) + c ≤ (b + c)
Notice terms are arguments of the predicate “≤”. But an arithmetical expression (b + c) by itself would not have a truth value.
Predicates vs Terms
In discrete mathematics you studied relations and function. Similarly, in logic we have
predicates – logical statements that represent relations between individuals. Each predicate can be true or false, depending on its arguments. Example: parent(Human,P) is a predicate. Each human has 2 parents, a human is in relation with parents.
terms – functions that map given individual(s) into a unique individual in a domain. Each function may take different values depending on the arguments. Example: mother(Human) = M. Each human has only one mother, this is a functional dependence.
Terms correspond to structures in other programming languages. They help to represent structured data as a single unit.
Note that atomic statements and rules can use predicates only, but inside predicates we can use arguments composed from terms.
Terms can be used only as arguments of predicates or as arguments of =.
Two atomic statements from the data base
To be more specific, let us consider a couple of atomic statements using the predicate family.
person(tom, fox , date(7, may , 1992), ibm), person(ann, fox , date(9, may , 1994), microsoft ), [person(pat , fox , date(5, august , 2017), unemployed ), person(jim, fox , date(5, august , 2017), unemployed )]).
person(john, nixon, date(29, february , 1996), unemployed ), person(mary , nixon, date(15, august , 1997), unemployed ), [ ] ).
And so on… Given this collection of atomic statements about families, we can retrieve information in a structured way using Prolog queries.
Pay attention how we use person and date inside family
Queries with terms
For the sake of simplicity, let us assume that a wife and a husband have the same family name. Recall the arguments:
family (Husband , Wife, ListOfChildren) person(FirstName, LastName, DOB, Job) date(Day , Month, Year )
Formulate a query in Prolog that retrieves information about all families with the last name “armstrong” such that the husband was born after 1977.
?- family(person(Name,armstrong,date(D,M,Y),J), W, L), Y > 1977.
Formulate a query in Prolog to find information about all employed women who have at least 2 children. Assume that all people without a job have the constant unemployed as the 4th argument of their term person.
?-family(H,person(FirstN,LastN,D,J),[Ch1,Ch2|List]), notJ=unemployed.
Binary Trees as Terms
We can use term with 3 arguments
tree(Element,LeftBranch,RightBranch)
to represent a binary tree. The empty tree can be represented by the constant void We represent the tree
as tree(a, tree(b, void, void), tree(c,void,void))
It is important to realize that binary tree is a recursive data structure: a
sub-tree of a tree is a tree itself.
If we consider the root of the tree, then its left child is a root of a left sub-tree, which is also a tree. Similarly, its right child is a root of a right sub-tree, which is also a binary tree.
Consider a few recursive programs take advantage of recursiveness of binary trees.
As usual, we do case analysis to write recursive programs.
Defining new predicates using family predicate
We can easily define several new useful predicates using the predicate family. To do this, it is sufficient to remember the meaning of its arguments. In the following questions, you have to write Prolog rules in terms of family:
husband(X) :− …
wife(X) :− …
child(X) :− …
human(X) :− …
dateofbirth(X,Day,Month,Year):−…
/*What to write here? */ /*What to write here? */ /*What to write here? */ /*What to write here? */
/*Howtoimplementthis?*/
husband(X) :− family(X,M,L).
wife(X) :− family(H,X,L).
child (X ) : − family (H , W , Children), member (X , Children).
human(X) :− husband(X). human(X) :− wife(X). human(X) :− child(X).
dateofbirth(X , Day , Month, Year ) : −human(X ),
X =person(FN,LN,date(Day,Month,Year),Job).
Recursion over terms.
The predicate binaryTree(X) is true if X is a binary tree. What is the base case ? What is a recursive case ?
binaryTree(void).
binaryTree( tree(Element, Left, Right) ) :-
binaryTree(Left), binaryTree(Right).
The predicate memberOfTree(Element , T ) is true if Element is a member of
a binary tree T . To implement this predicate do case analysis.
/* memberOfTree(Element, tree(Root,Left,Right) ) :- Element=Root.*/
memberOfTree(Element, tree(Element,Left,Right) ).
memberOfTree(Element, tree(Node,Left,Right) ) :-
memberOfTree(Element,Left).
memberOfTree(Element, tree(Node,Left,Right) ) :-
memberOfTree(Element,Right).
Lists as terms
Another example of terms. We can represent a list [Head | Tail] using a term next(Head,Tail). This somewhat resembles a linked list notation, but term notation is shorter. Also, we can represent the empty list as the constant nil.
Example: the usual list [a,b,c] = [a | [b,c]] = [a | [b | [c]]] can be represented using terms as next(a, next(b, next(c, nil))).
Using this term-based representation of lists, we can write recursive programs over terms similarly to recursive programs over lists.
Exercise: re-implement the predicate member(X,List) using terms.
Exercise: re-implement the predicate length(List, N) using terms.
Accumulator technique
Example: reverse(L1, L2) holds if L2 is the list of elements from L1 in the opposite order. If we query ? − reverse([a, 1, 9, b], L2). then we expect that the list L2 = [b, 9, 1, a] will be returned as an output.
The predicate reverse(L1, L2) can be easily implemented using append . How? This is an exercise for you. But the question remains if it can be implemented without using append.
We can use an accumulator as an extra argument in a helping predicate. reverse(L1,L2):−revAux(L1, [],L2).
revAux([],L, L).
revAux([H|L1], L2, L3) :− revAux(L1, [H|L2], L3).
?− reverse([a,b,c],L).
revAux([a ||[b, c]], [ ], L) |
revAux([b | [c]],[a], L). |
revAux ([c | [ ]], [b, a], L). |
revAux([ ],[c,b,a], L). |
success L=[c,b,a]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com