I am wondering if prolog can be used to represent abstract data type.
For example: an axiomatic specification of stack is something like:
top(push(i,s)) = i
isemptystack(createstack) = true
isemptystack(push(i,s)) = false
pop(push(i,s)) = s
Can this set of axioms be represented in prolog directly ?
Thanks in advance.
Feng
--
*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
+ Feng Yang (yf...@watnow.waterloo.edu) +
+ Dept. of Systems Design Engineering, University of Waterloo, ON, Canada +
*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
% define ADT stack with usual operations
%
s_new([]).
s_push(Elt,Stack,[Elt|Stack]).
s_pop([_|Stack],Stack).
s_top(Elt,[Elt|_]).
% define ADT queue with usual operation
%
q_new([]).
q_insert(Elt,Q,Q2) :- append(Q,[Elt],Q2).
q_next(Elt,[Elt|_]).
q_delete([_|Q],Q).
--------------------------------------------------------------------------
David G. Novick | Department of Computer Science and Engineering
| Oregon Graduate Institute of Science and Technology
nov...@cse.ogi.edu | 19600 N.W. Von Neumann Drive
(503) 690-1156 | Beaverton, OR 97006-1999
--------------------------------------------------------------------------
% Create an empty stack
createstack(createstack).
% Check if a stack is empty (succeeds iff true)
isemptystack(createstack).
% Push an item
push(Item, Stack, push(Item, Stack)).
% Retrieve the top of a stack, fail if it's empty
top(push(Item, _), Item).
% Pop an item off a stack, fail if the stack is empty
pop(push(_, Stack), Stack).
If you'd like an error indication for top() or pop() applied to an empty
stack (instead of failure), you can do something like
pop(push(_, Stack), Stack).
pop(createstack, Stack).
This predicate still fails if it is applied to something which isn't a stack.
Jens Kilian
--
Internet: kil...@seas.gwu.edu SnailMail: 4715 MacArthur Blvd.
(I don't know any other addresses ...) Washington, DC 20007
"Sie hawwe-mer so e bekannt Physionomie, ich mahn, ich misst Ihne kenne.
Sinn-Se net, um Vergebung, der Herr Assesser Ranft ?"
I dont know if this answers your question, but it is trivial to
code these in prolog--just make the output an extra argument,
assert predicates you want to return 'true', and omit those you
want to return 'false' so they fail and invoke backtracking;
for example, your:
top(push(i,s)) = i
isemptystack(createstack) = true
isemptystack(push(i,s)) = false
pop(push(i,s)) = s
becomes:
top(push(I,S),I).
is_empty_stack(createstack).
pop(push(I,S),S).
and presumably, you need to have:
push(I,S,push(I,S)).
new_stack(createstack).
push() takes a node I, a stack S, and outputs a new stack
in the third argument; 'push(_,_)' is essentially like a
lisp cons cell here--the 'stack' is really a binary tree
of push(_,_) nodes that grows through its right branches.
A more common way to implement stacks is with prolog lists:
new_stack([]).
push(X,S,[X|S]).
pop([X|S],S).
etc.
but this is really no different than using a push(_,_) tree,
since prolog lists are .(_,_) trees internally (usually).
Now, a prolog program can load these predicates, and create
and manipulate arbitrarily many stacks, without ever needing
to know the actual data structures that implement the stack,
so long as all updates are done with the provided predicates:
some_program :-
new_stack(S),
push(term1,S,S1),
push(term2,S1,S2),
pop(S2,S3),
push(term3,S3,S4),
top(S4,term3),
/* here, S4 = push(term3,push(term1,createstack)) */
new_stack(T),
push(term1,T,T1),
pop(T1,T2),
is_empty_stack(T2),...
/* here, T2 = createstack, i.e. empty */
Note, however, that such a stack must be passed around as an
argument to all routines that use it, each change to a stack
requires a new variable to be bound to the modified stack,
and changes to such stacks will be undone when backtracking
past the point in the computation where the modification was
made; if you want globally accessible stacks, insulated from
the effects of backtracking, you need to use assert/retract,
or some similar facility in your prolog system (never really
a good idea).
Incidentally, prolog is really very good at abstract data types
in general; for example, you could switch the stack representation
from 'push(_,_)' to '[_|_]' arbitrarily, and could even change the
shape of the stack 'tree' to grow to the left without altering
the calling programs:
top(push(S,I),I).
push(I,S,push(S,I)).
pop(push(S,I),S).
etc.
some_program :-
new_stack(S),
push(term1,S,S1),
push(term2,S1,S2),
pop(S2,S3),
push(term3,S3,S4),
top(S4,term3),
/* here, S4 = push(push(createstack,term1),term3) */
As another example, one could define a simple:
new_dict([]).
store(Key,Value,Dict,[(Key,Value)|Dict]).
lookup(Key,Value,Dict) :- member((Key,Value),Dict).
to implement a dictionary with linear lists, and later change
this to use a very different binary tree representation, without
impacting any using programs, provided they only access the
dictionary with the new_dict(), store() and lookup() predicates:
new_dict(nil).
store(K,V,nil,tree(nil,(K,V),nil)).
store(K,V,tree(L,(X,Y),R),tree(L2,(X,Y),R)) :- K < X, store(K,V,L,L2).
store(K,V,tree(L,(X,Y),R),tree(L,(X,Y),R2)) :- K > X, store(K,V,R,R2).
lookup(K,V,tree(L,(K,V),R)).
lookup(K,V,tree(L,(X,Y),R)) :- K < X, lookup(K,V,L).
lookup(K,V,tree(L,(X,Y),R)) :- K > X, lookup(K,V,R).
If one were truly ambitious, they could even use a module facility
to keep everything except the interface predicates hidden from the using
program (provided their prolog system provides modules).
Hope this helps,
Mark Lutz
ml...@convex.com
This can be done automatically quite easily. There is a preprocessor
for NU-Prolog which enables you to write the following:
top(push(I,S)) = I.
isemptystack(createstack).
pop(push(I,S)) = S.
test :- write(top(pop(push(3, push(2, pop(push(1, createstack))))))).
This is translated into the following (plus some goals/declarations):
top(push(A9, B9), A9).
isemptystack(createstack).
pop(push(A9, B9), B9).
test :-
pop(push(1, createstack), A),
pop(push(3, push(2, A)), B),
top(B, C),
write(C).
The preprocessor is ftp-able from mullauna.cs.mu.OZ.AU in
pub/nue_prolog.tar.Z. If anyone has the time to make it more
portable, let me know...
lee
Thats 128.250.35.35 for those without name servers which know about it.
lee
>I am wondering if prolog can be used to represent abstract data type.
>For example: an axiomatic specification of stack is something like:
>
>top(push(i,s)) = i
>isemptystack(createstack) = true
>isemptystack(push(i,s)) = false
>pop(push(i,s)) = s
>
>Can this set of axioms be represented in prolog directly ?
Chapter 5 of Algebraic Specification, (Bergstra, Heering, and Klint
eds.) ACM Press, Addison-Wesley, 1989, gives an overview of several
methods for translating algebraic specifications in Prolog.
Sergio Antoy
Portland State University