PROLOG-REQUEST@SU-SCORE.ARPA (06/03/83)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Friday, 3 Jun 1983 Volume 1 : Issue 7
Today's Topics:
Representation - Declaring Predicates Transitive,
Applications - Objects
----------------------------------------------------------------------
Date: 30 May 1983 1543-EDT (Monday)
From: Vijay.Saraswat@CMU-CS-A
Subject: Declaring Predicates Transitive
The following solution is adequate for all the 4 cases mentioned by
Abbott:
transitive(R,Elem):-
atom(R), nonvar(Elem),
Rxy=..[R,X,Y], Rxz=..[R,X,Z], Rzy=..[R,Z,Y],
assert((Rxy:- nonvar(X),Rxz, X \==Z, Rzy)),
assert((Rxy:-nonvar(Y),Rzy, Y \==Z, Rxz)),
assert((Rxy:- X is Elem, Rxy)).
Elem is any element in the domain over which R is defined.
-- V. Saraswat.
------------------------------
Date: Tuesday, 31 May 1983 14:12-PDT
From: Narain at Rand-Unix
Subject: Reply to Henry Liebermann
1) I agree that actors may be implemented in any language. The
advantage of of choosing Prolog is however that you can use its most
powerful features like pattern matching, automatic backtracking,
deductive facility and well understood theoretical foundations.
Because of these features, an object oriented interpreter in Prolog
has a very simple definition.
Both styles "Object Oriented" and "natural Prolog" are very powerful
and the nice thing is to be able to use both in the same system.
2) An improvement in Kahn's "Actors in Prolog".
In Kahn's paper, actor behaviors are stored as clauses under just one
single predicate "sent", each of which has the form:
sent(Actor,Message,Result):-<body having other calls to sent>.
To compute the result "R" of passing message "M" to actor "A", one
simply makes the call:
:-sent(A,M,R)
Clearly, as more objects are added and more behaviors defined, any
call to "sent" will have to search through all clauses under "sent".
This effectively means that the knowledge base of all actors is being
searched, even when many actors may be totally irrelevant to the one
that received the message.
A fairly straightforward improvement over this search strategy is
given. Essentially, the search for a matching procedure is made on
nodes only along one branch of the inheritance tree instead of on all
the nodes of the inheritance tree. The idea is simple and no doubt
exists in other object oriented implementations. It does at Rand
where we have developed a language called ROSS for doing
knowledge-based simulations.
When an actor receives a message, it determines its immediate ancestor
and examines its knowledge base for a matching procedure. If it finds
a match it executes it, otherwise it goes on to the next ancestor in
the inheritance tree.
The convention adopted here is that all clauses in an <actor-name>'s
knowledge base are stored under the predicate <actor-name>_behavior.
Thus to search the knowledge base of <actor-name> we only need to
examine clauses under <actor-name>_behavior, and not all clauses under
"sent".
The modified interpreter is:
sent(Actor, Msg, Result):-
ancestor(Actor, Actor_anc),
procedure(Actor_anc, Actor, Msg, Result, Procedure),
call(Procedure),
!.
/* The "cut" is necessary only if we wish to constrain the response
to be the first one found. It is strictly unnecessary otherwise.
When "Actor" receives "Msg", the result is "Result" if "Actor_anc"
is an ancestor of "Actor", and "Procedure" is a call to
<Actor_anc>_behavior, and "Procedure" is successfully called.
Kahn's actor classes or generic actors are essentially "records"
and are implemented using Prolog lists. A generic actor is just
a list of partially instantiated elements where each element
represents one field of the "record". An instantiation of this
generic actor is just a term that matches the generic actor (a list).
Predicate "procedure" defines for each generic actor (its first
argument), the call to clauses inside its knowledge base, and binds
"Procedure" to this call. "Myself" is the actor that was originally
sent the message.
Thus: */
procedure([list], Myself, Msg, Result, list_behavior(Myself, Msg,
Result)). procedure([nlist,_,_,_],
Myself,Msg,Result,nlist_behavior(Myself,Msg, Result)).
procedure([slist|X],Myself,Msg,Result,slist_behavior(Myself,Msg,Result)).
procedure([],Myself,Msg,Result,null_list_behavior(Myself,Msg,Result)).
/* Definition of 'ancestor' */ ancestor(X,X). /* search begins with
the actor, so it is its own "ancestor" */ ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).
/* Hierarchy in the context of lists */ parent([],[list]).
parent([nlist,_,_,_],[list]). parent([slist|X],[list]). /* a simple
list, where "slist" stands for "cons" */
/* Now "nlist_behavior", "list_behavior" etc. are defined as they
were originally by Kahn. Only the behaviors for the "print_elements"
message are outlined here, but other behaviors in Kahn's paper
including the Sieve of Eratosthenes alorithm were also programmed.
Note that behaviors are still defined with the same clarity, if the
naming convention is adhered to */
list_behavior(Myself,print_elements,_):-
sent(Myself,you_are_empty,true),!.
list_behavior(Myself,print_elements,_):-
write(' '),
sent(Myself, first, First),
write(First),
sent(Myself, rest, Rest),
sent(Rest,print_elements,_).
/* Special behavior for nlist */
nlist_behavior(Nlist,print_elements,_):-
sent(Nlist,length,Length),
Length > 5,
sent(Nlist, print_elements_with_dots, _).
When an actor of the form [slist|X] receives a message to
"print_elements" it finds no behaviors in its own knowledge base. It
then determines that it is an instance of [list] and finds an
appropriate response under "list_behavior". It does not look under
"nlist_behavior".
On a DEC-20, the Sieve algorithm as programmed originally generated
only 11 primes (till 31) before running out of space. The algorithm
when reprogrammed as above generated 103 primes (till 563) before
running out of space, and ran three times as efficiently.
-- Sanjai Narain
------------------------------
Date: Thursday, 2 June 1983, 01:07-EDT
From: Henry Lieberman <Henry%MIT-OZ@MIT-MC>
Subject: Object-Oriented Programming in Prolog, reply to Narain
Sanjai,
Thank you for your informative reply. My intention was just to
distinguish the claim "Prolog is a good language for implementing
object-oriented programming languages", which your arguments support,
from the claim "Prolog IS a good object-oriented programming
language". The first claim I am sympathetic to, because of the
features you cite, but the second I am skeptical about, since all such
attempts I've seen involve adding additional interpretive mechanism
and changing programming style conventions rather drastically. I
believe Kahn's original intent in Intermission was to support the
first claim rather than the second.
The problem with the "hundred flowers" approach to supporting multiple
programming styles in the same language (efficiency aside) is
confusion for the poor user. In your scheme, a programmer might start
out thinking "I'm not going to use the hairy features of Actors, why
don't I just program directly in Prolog" and writes predicates like
Above(Block-1, Block-2). Then later in the evolution of the system,
the need for default information arises, so all previous code has to
be rewritten to say Sent(Block-1, Above, Block-2, True). This comes up
all the time in Lisp-embedded object-oriented programming [Flavors,
Loops, etc.] The point is if you're convinced enough about the virtues
of object-oriented programming, you might as well make your language
use it for everything.
I like your optimization to Kahn's message reception scheme, it works
out very nicely. Something I think Prolog-based object-oriented
languages might be promising for is in dealing with the so-called
"multiple-inheritance problem" which has been a difficult point in
other languages so far. Perhaps it would be possible in such a scheme
to just add some more clauses involving Ancestor and Parent relations
to resolve inheritance conflicts.
-- Henry
------------------------------
End of PROLOG Digest
********************