Prolog - Question about polymorphism (maybe)

Author

Question about polymorphism (maybe)

seguso

2004-04-17, 11:32 am

Hello,

After 6 months of prolog, I still can't understand how to manage this
situation. In imperative languages it would be easy by using polymorphism.

I have a world containing animate and inanimate objects. both animate and
inanimate objects are subject to the gravity force, but only the animate
ones can move themselves.

I have a main loop where I must both

1) apply gravity to ALL objects (gravity/2 is a predicate that takes a list
of objects and returns a new list of translated objects)

2) let the animate objects move themselves. (I must apply update/2, which
takes an animate object and returns a new obj, translated).

In C# or java I could do something like (pseudocode)

class Object{ ..}

class AnimateObject : inherits Object{}

mainLoop(set<AnimateObject> animateObjs,
list<Object> allObjs)
{
gravity(allObjs); // this modifies allObjs, but
// the references are still valid.
update(animateObjs); //the references are still valid,
// so I can do this.
}

in prolog, I would be tempted to do so:

mainLoop(AnimateList, AllObjectsList):-
% note: AnimateList is a subset of AllObjectsList
gravity(AllObjectsList, TranslatedObjectsList2),
update(???

The problem is: after gravity/2 is applied, AnimateList is not valid
anymore, because there is no concept of "reference"...

I thought I can refactor like that: instead of having a list of all objects,
I have two disjoint lists:

mainLoop(AnimateList, InanimateList):-
gravity(AnimateList, A2),
gravity(InanimateList, I2),
update(I2, I3),
mainLoop(A2, I3).

BUt this means calling gravity/2 twice. It would have been nice to call it
once, with the list of all the objects. Because, after all, gravity/2 acts
on "generic" objects. Is there any way to do that? Is it desirable?

More in general, does the concept of "polymorphism" make sense in prolog?

Thanks for any comment,

--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

Nick Wedd

2004-04-17, 2:32 pm

In message <iEbgc.66267$hc5.2882634@news3.tin.it>, seguso
<look@in.signature> writes
>Hello,
>
>After 6 months of prolog, I still can't understand how to manage this
>situation. In imperative languages it would be easy by using polymorphism.
>
>I have a world containing animate and inanimate objects. both animate and
>inanimate objects are subject to the gravity force, but only the animate
>ones can move themselves.
>
>I have a main loop where I must both
>
>1) apply gravity to ALL objects (gravity/2 is a predicate that takes a list
>of objects and returns a new list of translated objects)
>
>2) let the animate objects move themselves. (I must apply update/2, which
>takes an animate object and returns a new obj, translated).
>
>
>In C# or java I could do something like (pseudocode)
>
>
>class Object{ ..}
>
>class AnimateObject : inherits Object{}
>
>mainLoop(set<AnimateObject> animateObjs,
> list<Object> allObjs)
>{
> gravity(allObjs); // this modifies allObjs, but
> // the references are still valid.
> update(animateObjs); //the references are still valid,
> // so I can do this.
>}
>
>in prolog, I would be tempted to do so:
>
>mainLoop(AnimateList, AllObjectsList):-
> % note: AnimateList is a subset of AllObjectsList
> gravity(AllObjectsList, TranslatedObjectsList2),
> update(???
>
>The problem is: after gravity/2 is applied, AnimateList is not valid
>anymore, because there is no concept of "reference"...
>
>I thought I can refactor like that: instead of having a list of all objects,
>I have two disjoint lists:
>
>mainLoop(AnimateList, InanimateList):-
> gravity(AnimateList, A2),
> gravity(InanimateList, I2),
> update(I2, I3),
> mainLoop(A2, I3).
>
>BUt this means calling gravity/2 twice. It would have been nice to call it
>once, with the list of all the objects. Because, after all, gravity/2 acts
>on "generic" objects. Is there any way to do that? Is it desirable?
>
>More in general, does the concept of "polymorphism" make sense in prolog?
>
>Thanks for any comment,

This does not answer your question - but here is how I might write it.

mainloop( [H|T], [HH|TT] ) :-
gravitate( H, HA ),
selfpropel( HA, HH ),
mainloop( T, TT ).
mainloop( [], [] ).

gravitate( Object, FallenObject ) :-
/* code to move it downwards */.

selfpropel( Object, MovedObject ) :- // this clause handles fliers
flyer( Object ),
!,
/* code for it to fly */.
selfpropel( Object, MovedObject ) :- // this clause handles swimmers
in water
swimmer( Object ),
inwater( Object ),
!,
/* code for it to swim */.
selfpropel( Object, MovedObject ) :- // this clause handles other
animates
animated( Object ),
!,
/* code for it to walk */.
selfpropel( Object, Object ). // this clause handles
non-animates

Nick
--
Nick Wedd nick@maproom.co.uk

seguso

2004-04-17, 5:32 pm

Nick Wedd wrote:

>
> This does not answer your question - but here is how I might write it.

No, this is insightful. You are applying selfPropel to all objects, blindly,
but the predicate does nothing if the object is inanimate. Believe it or
not, I hadn't thought of this. :-)

What would you do if gravitate/2 were actually gravitate/3? In order to find
the new position for the object, you have to take into account the
positions of ALL the other objects. So the additional argument is the list
of all objects.

Thanks anyway,
--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

Nick Wedd

2004-04-17, 7:31 pm

In message <fsggc.67516$hc5.2941888@news3.tin.it>, seguso
<look@in.signature> writes

>What would you do if gravitate/2 were actually gravitate/3? In order to find
>the new position for the object, you have to take into account the
>positions of ALL the other objects. So the additional argument is the list
>of all objects.

(I assume that you want the additional argument to be the list of all
objects in their current partly-processed state. So if two objects are
trying to fall to the same place, the first one on the list gets there,
and the second one finds its way obstructed. This is nothing to do with
the language.)

I shall, for my convenience, use two additional arguments: a list of
the currently unprocessed objects and a list of the currently processed
objects.

mainloop( [H|Raw], Done, AllDone ) :-
gravitate( Raw, Done, H, HA ),
selfpropel( HA, HH ),
mainloop( Raw, [HH|Done], AllDone ).
mainloop( [], AllDone, Alldone ).

gravitate( Raw, Done, Object, FallenObject ) :-
/* code to move it downwards */.

You call my mainloop like this:
mainloop( BeforeList, [], AfterList ).

It has the incidental effect of reversing the order of the list as it
operates. If you don't like this, then replace
mainloop( [], AllDone, Alldone ).
by
mainloop( [], ReversedAllDone, Alldone ) :-
reverse( ReversedAllDone, Alldone ).
where reverse/2 is your favourite list-reversing predicate.

Nick
--
Nick Wedd nick@maproom.co.uk

reader

2004-04-17, 7:31 pm

seguso wrote:
> Hello,
>
> After 6 months of prolog, I still can't understand how to manage this
> situation. In imperative languages it would be easy by using polymorphism.
>
> I have a world containing animate and inanimate objects. both animate and
> inanimate objects are subject to the gravity force, but only the animate
> ones can move themselves.
>
> I have a main loop where I must both
>
> 1) apply gravity to ALL objects (gravity/2 is a predicate that takes a list
> of objects and returns a new list of translated objects)
>
> 2) let the animate objects move themselves. (I must apply update/2, which
> takes an animate object and returns a new obj, translated).
>
>

I would probably use a scheme something like this (comment out
anything that ISO-style Prolog does not recognize):

domains

OBJECTS = OBJECT*
OBJECT = animate(ATTRS,METHODS,STATE) ; inanimate(PROPS,STATE)

ATTRS = attrs(IDENT,AGE,WEIGHT)

IDENT = STRING
AGE = INTEGER
WEIGHT = REAL

METHODS = METHOD*
METHOD = method1(SYMBOL) ; method2(SYMBOL)

PROPS = props(MASS)
MASS = REAL

STATE = loc(X,Y)
X = REAL
Y = REAL

/*
1) apply gravity to ALL objects (gravity/2 is a predicate that takes a
list of objects and returns a new list of translated objects)
*/
predicates

apply_gravity_to_all_objects(OBJECTS,OBJ
ECTS)
translate_object(OBJECT,OBJECT)
translate_animate(ATTRS,STATE,STATE)
translate_inanimate(PROPS,STATE,STATE)

clauses

apply_gravity_to_all_objects([],[]).
apply_gravity_to_all_objects([OBJECT|OBJECTS],
[NewOBJECT|NewOBJECTS]) :-

translate_object(OBJECT,NewOBJECT),
apply_gravity_to_all_objects(OBJECTS,New
OBJECTS).

translate_object(animate(ATTRS,METHODS,S
TATE),
animate(ATTRS,METHODS,NewSTATE)) :-

translate_animate(ATTRS,STATE,NewSTATE).

translate_object(inanimate(PROPS,STATE),

inanimate(PROPS,NewSTATE)) :-

translate_inanimate(PROPS,STATE,NewSTATE
).

translate_animate(attrs(IDENT,AGE,WEIGHT
),STATE,NewSTATE) :-
stub .

translate_inanimate(props(MASS),STATE,Ne
wSTATE) :-
stub .

/*
2) let the animate objects move themselves. (I must apply update/2,
which takes an animate object and returns a new obj, translated).
*/

predicates

let_animate_objects_move_themselves(OBJE
CTS,OBJECTS)
let_animate_object_move_itself(OBJECT,OB
JECT)
update(ATTRS,METHODS,STATE,STATE)

clauses

let_animate_objects_move_themselves([],[]).

let_animate_objects_move_themselves([OBJECT|OBJECTS],
[NewOBJECT|NewOBJECTS]) :-

let_animate_object_move_itself(OBJECT,Ne
wOBJECT),
let_animate_objects_move_themselves(OBJE
CTS,NewOBJECTS).

let_animate_object_move_itself(
inanimate(PROPS,STATE),
inanimate(PROPS,STATE)).

let_animate_object_move_itself(
animate(ATTRIBS,METHODS,STATE),
animate(ATTRIBS,METHODS,NewSTATE)) :-

update(ATTRIBS,METHODS,STATE,NewSTATE).

update(attrs(IDENT,AGE,WEIGHT),METHODS,S
TATE,NewSTATE) :-

stub.

I hope this is reasonably close to the description you provided.

I'm never sure what "polymorhism" means, but the general scheme I am
using here seems simple enough: given a domain of terms of the forms

dom = f1(dom11,...) | f2(dom21,...) | ... | fn(domn1,...)

I usually parse a predicate that is supposed to be complete w/r dom
somnething like this:

p(f1(X,...),...) :-
f1(X,...),
p(f2(Y,...),...) :-
f2(Y,...)
...
p(fn(Z,...),...) :-
fn(Z....).

Prolog rules are like axioms: absent any use of non-logical predicates
such as "!", Prolog gives you soundness, but if you want completeness,
your axioms have to /be/ complete -- i.e., you cannot leave unsaid
anything that needs to be said.

--
billh
sequitur AT sonic DOT net

Andrzej Lewandowski

2004-04-17, 7:31 pm

On Sat, 17 Apr 2004 15:00:30 GMT, seguso <look@in.signature> wrote:

>Hello,
>
>After 6 months of prolog, I still can't understand how to manage this
>situation. In imperative languages it would be easy by using polymorphism.
>
[...]
>
>More in general, does the concept of "polymorphism" make sense in prolog?
>
>Thanks for any comment,

See the manual for SICStus Prolog. SICStus has its own object
system, and the manual presents the details of implementation and
internal working.

See also the LogTalk, Prolog object system that works with majority
of Prolog implementations.

A.L.

Bill Spight

2004-04-17, 9:31 pm

Dear Seguso,

> After 6 months of prolog, I still can't understand how to manage this
> situation. In imperative languages it would be easy by using polymorphism.
>

Polymorphism is not difficult in Prolog. See below.

> I have a world containing animate and inanimate objects. both animate and
> inanimate objects are subject to the gravity force, but only the animate
> ones can move themselves.
>
> I have a main loop where I must both
>
> 1) apply gravity to ALL objects (gravity/2 is a predicate that takes a list
> of objects and returns a new list of translated objects)
>
> 2) let the animate objects move themselves. (I must apply update/2, which
> takes an animate object and returns a new obj, translated).
>
>

You might do something like this:

mainLoop(OldObjects) :-
updateObjects(OldObjects, NewObjects), !,
mainLoop(NewObjects).

updateObjects([],[]) :- !.
updateObjects([Head0 | Tail0], [Head | Tail]),
updateObject(Head0, Head),
updateObjects(Tail0, Tail).

updateObject(inanimate(Object0), inanimate(Object)) :-
applyGravity(inanimate(Object0), inanimate(Object)).
updateObject(animate(Animal0), animate(Animal)) :-
applyGravity(animate(Animal0), animate(Animal1)),
move(animate(Animal1), animate(Animal)).

updateObject/2 is polymorphic, treating animate objects and inanimate
objects differently.

Best,

Bill

Bill Spight

2004-04-18, 12:33 am

I wrote:

> updateObject(inanimate(Object0), inanimate(Object)) :-
> applyGravity(inanimate(Object0), inanimate(Object)).
> updateObject(animate(Animal0), animate(Animal)) :-
> applyGravity(animate(Animal0), animate(Animal1)),
> move(animate(Animal1), animate(Animal)).
>

Hmmm. Isn't this better? :-)

updateObject(inanimate(Object0), inanimate(Object)) :-
applyGravity(Object0, Object).
updateObject(animate(Animal0), animate(Animal)) :-
applyGravity(Animal0, Animal1),
move(Animal1, Animal).

Bill

seguso

2004-04-18, 4:31 am

Bill Spight wrote:

>
> updateObject(inanimate(Object0), inanimate(Object)) :-
> applyGravity(Object0,_Object).
> updateObject(animate(Animal0), animate(Animal)) :-
> applyGravity(Animal0,_Animal1),
> move(Animal1,_Animal).
>
>

Thank you :-)

By the way, I see you are wrapping all your objects with inanimate/1 and
inanimate/1, as a means of telling animate fron inanimate. I don't quite
like it. I would like to distinguish one another by checking whether some
predicate is defined for them. e.g. I would like to tell animate object by
the fact that they can walk. Is it possible?

--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

seguso

2004-04-18, 4:31 am

Nick Wedd wrote:

>
> mainloop( [H|Raw], Done, AllDone ) :-
> gravitate(_Raw,_Done,_H,_HA_),
> selfpropel(_HA,_HH_),
> mainloop(_Raw,_[HH|Done],_AllDone_).
> mainloop( [], AllDone, Alldone ).

I see. This is getting a bit artificial (gravitate/3 would have been
better), but it's ok.
Thanks again!
--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

seguso

2004-04-18, 4:31 am

seguso wrote:

>
> I see. This is getting a bit artificial (gravitate/3 would have been
> better),

thinking better, calling append/3 before gravitate/3 will do the trick :-)
--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

Bill Spight

2004-04-18, 9:31 am

Dear seguso,

> By the way, I see you are wrapping all your objects with inanimate/1 and
> inanimate/1, as a means of telling animate fron inanimate. I don't quite
> like it. I would like to distinguish one another by checking whether some
> predicate is defined for them. e.g. I would like to tell animate object by
> the fact that they can walk. Is it possible?

Sure. Just use IF-THEN-ELSE.

Ciao,

Bill

Fergus Henderson

2004-04-19, 2:32 am

seguso <look@in.signature> writes:

>The problem is: after gravity/2 is applied, AnimateList is not valid
>anymore, because there is no concept of "reference"...

If you really need references, it is possible to implement this notion
in Prolog, by allocating identifiers (e.g. sequential integers) to
"refer" to your objects, and keeping a data structure which records
the mapping between object identifiers and object values. Generally
a balanced tree representation (e.g. 234-trees, AVL trees, or red-black
trees) works well for that kind of data structure, but if you don't have
many objects then an association list works OK too, and is quite a bit
easier to implement.

--
Fergus Henderson | "I have always known that the pursuit
| of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
------------ And now a word from our sponsor ------------------
Want to have instant messaging, and chat rooms, and discussion
groups for your local users or business, you need dbabble!
-- See http://netwinsite.com/sponsor/sponsor_dbabble.htm ----

Paul Singleton

2004-04-19, 8:37 am

Fergus Henderson wrote:

> If you really need references, it is possible to implement this notion
> in Prolog, by allocating identifiers (e.g. sequential integers) to
> "refer" to your objects, and keeping a data structure which records
> the mapping between object identifiers and object values. Generally
> a balanced tree representation (e.g. 234-trees, AVL trees, or red-black
> trees) works well for that kind of data structure, but if you don't have
> many objects then an association list works OK too, and is quite a bit
> easier to implement.

Although if Prolog really supported polymorphism (or do
I mean "interface inheritance"?) it wouldn't matter which
was "easier to implement" as they would already be near-optimally
implemented in standard libraries, you could use whichever
implementation you fancied, and your application code wouldn't
care anyway (as in Java's Map interface etc)

Paul Singleton

seguso

2004-04-19, 3:50 pm

Fergus Henderson wrote:

>
> If you really need references, it is possible to implement this notion
> in Prolog, by allocating identifiers (e.g. sequential integers) to
> "refer" to your objects, and keeping a data structure which records
> the mapping between object identifiers and object values.

Thanks, but I solved in an easier way. Reference are just unique names. So I
added a name field to my objects. And I find the right object with

...
member(M, List),
name(M, Name),
...

which takes O(N) instead of O(1), but doesn't affect the overall compexity.

--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

Stephan Lehmke

2004-04-20, 1:40 pm

In article <YMUgc.75335$hc5.3241712@news3.tin.it>,
seguso <look@in.signature> writes:
>
> Thanks, but I solved in an easier way. Reference are just unique names. So I
> added a name field to my objects. And I find the right object with
>
> ...
> member(M, List),
> name(M, Name),
> ...
>
> which takes O(N) instead of O(1), but doesn't affect the overall compexity.

If I'm not misunderstanding anything, this will take O(N^2) because
name will fail on all objects with the wrong name, making member
re-inspect the list every time on backtracking.

You should exchange the calls to name and member (would mercury do
this automatically?).

regsrds
Stephan

--
Stephan Lehmke Stephan.Lehmke@cs.uni-dortmund.de
Fachbereich Informatik, LS I Tel. +49 231 755 6434
Universitaet Dortmund FAX 6555
D-44221 Dortmund, Germany http://ls1-www.cs.uni-dortmund.de

seguso

2004-04-20, 1:40 pm

Stephan Lehmke wrote:

> In article <YMUgc.75335$hc5.3241712@news3.tin.it>,
> seguso <look@in.signature> writes:
>
> If I'm not misunderstanding anything, this will take O(N^2) because
> name will fail on all objects with the wrong name, making member
> re-inspect the list every time on backtracking.
>

Sorry, I don't understand!

member(M, List) scans all elements of the list at worst.
name(M, Name) takes O(1).

The worst thing that can happen is that the object with the right name is
the last one in the list. In this case we spend exactly N (the length of
L). Or don't we?

> You should exchange the calls to name and member (would mercury do
> this automatically?).

I don't follow you... This way name(M, name) would be called with M
unbound... and fail, I suppose. name/2 is something like

name(obj(N, _, _, _), N).

Thanks!
--
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it

Stephan Lehmke

2004-04-21, 4:34 am

In article <cJchc.112423$rM4.4372010@news4.tin.it>,
seguso <look@in.signature> writes:
> Stephan Lehmke wrote:
>
>
> Sorry, I don't understand!
>
> member(M, List) scans all elements of the list at worst.
> name(M, Name) takes O(1).

Yes, but if Name is bound before this snippet is called,
then name(M,Name) will fail on all objects with a name other
than Name, backtracking to member(M,List)...

Oops, I see. Of course this still needs only O(N) time...

>
> I don't follow you... This way name(M, name) would be called with M
> unbound... and fail, I suppose. name/2 is something like
>
> name(obj(N, _, _, _), N).

Yes. So M would be bound to a partial structure before member
starts, moving the point of failure to the time when member
inspects a list element. I still think this is better than
forcing the `longer' backtrack in the first variant...

regards
Stephan

--
Stephan Lehmke Stephan.Lehmke@cs.uni-dortmund.de
Fachbereich Informatik, LS I Tel. +49 231 755 6434
Universitaet Dortmund FAX 6555
D-44221 Dortmund, Germany http://ls1-www.cs.uni-dortmund.de

Paulo Moura

2004-04-21, 8:38 pm

Paul Singleton <paul.singleton@bcs.org.uk> wrote in message news:<c60f32$e9k$1$8302bc10@news.demon.co.uk>...
> Fergus Henderson wrote:
>
>
> Although if Prolog really supported polymorphism (or do
> I mean "interface inheritance"?) it wouldn't matter which
> was "easier to implement" as they would already be near-optimally
> implemented in standard libraries, you could use whichever
> implementation you fancied, and your application code wouldn't
> care anyway (as in Java's Map interface etc)

Logtalk (http://www.logtalk.org/) supports both interface and
implementation inheritance (something that is not possible using
Prolog modules).

Cheers,

Paulo

Sponsored Links