Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Abstract Type in Prolog ?

152 views
Skip to first unread message

Feng Yang

unread,
Jan 3, 1991, 10:47:17 AM1/3/91
to
Hello there !

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 +
*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*

David G. Novick

unread,
Jan 3, 1991, 2:26:42 PM1/3/91
to
Following up yf...@watnow.waterloo.edu's inquiry about abstract
data types in Prolog, here are a couple of definitions
I've used. Note that these do *not* create or necessarily
reference persistent objects.

% 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
--------------------------------------------------------------------------

Jens Kilian

unread,
Jan 3, 1991, 2:39:18 PM1/3/91
to
Sure, you can represent abstract data types in Prolog. The main problem is
that axiomatic specifications of abstract data types are functional, so you
have to add an output argument to each of the functions to get the
corresponding Prolog predicates. The stack example is straightforward :

% 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 ?"

Mark Lutz

unread,
Jan 3, 1991, 7:01:00 PM1/3/91
to

in article 2819 of comp.lang.prolog, yf...@watnow.waterloo.edu writes:
> 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 ?


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

Lee Naish

unread,
Jan 3, 1991, 10:16:51 PM1/3/91
to
In article <24...@sparko.gwu.edu> kil...@seas.gwu.edu (Jens Kilian) writes:
>Sure, you can represent abstract data types in Prolog. The main problem is
>that axiomatic specifications of abstract data types are functional, so you
>have to add an output argument to each of the functions to get the
>corresponding Prolog predicates.

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

Lee Naish

unread,
Jan 6, 1991, 9:20:26 PM1/6/91
to
In article <63...@munnari.oz.au> l...@munmurra.UUCP (me) writes:
>The preprocessor is ftp-able from mullauna.cs.mu.OZ.AU

Thats 128.250.35.35 for those without name servers which know about it.

lee

Sergio Antoy

unread,
Jan 10, 1991, 7:32:46 PM1/10/91
to
In article <1991Jan3.1...@watserv1.waterloo.edu>
yf...@watnow.waterloo.edu (Feng Yang) writes:

>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

0 new messages