Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!convex!news
From: mlutz@convex.COM (Mark Lutz)
Newsgroups: comp.lang.prolog
Subject: Re: Abstract Type in Prolog ?
Message-ID: <1991Jan04.000100.10872@convex.com>
Date: 4 Jan 91 00:01:00 GMT
References: <1991Jan3.154717.27057@watserv1.waterloo.edu>
Sender: news@convex.com (news access account)
Reply-To: mlutz@convex.COM (Mark Lutz)
Organization: Convex Computer Corporation; Richardson, TX
Lines: 133
Nntp-Posting-Host: mozart.convex.com


in article 2819 of comp.lang.prolog, yfeng@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
mlutz@convex.com