Path: utzoo!mnetor!uunet!husc6!uwvax!oddjob!ncar!gatech!bloom-beacon!oberon!cit-vax!ucla-cs!sdcrdcf!trwrb!aero!srt
From: srt@aero.ARPA (Scott R. Turner)
Newsgroups: comp.ai
Subject: Re: Student versions of OPS5
Message-ID: <28055@aero.ARPA>
Date: 25 Mar 88 16:23:17 GMT
References: <8803161533.AA03130@decwrl.dec.com>
Reply-To: srt@aero.UUCP (Scott R. Turner)
Organization: The Aerospace Corporation, El Segundo, CA
Lines: 35

In article <8803161533.AA03130@decwrl.dec.com> barabash@midevl.dec.com (Digital has you now!) writes:
>
>  In article <26695@aero.ARPA> srt@aero.UUCP (Scott R. Turner) writes:
>> I don't think the Vax version [of OPS5] uses Rete (at least, it allows
>> calculations in the LHS).
> 
>  In fact, VAX OPS5 uses the high-performance compiled Rete, first used
>  by OPS83, wherein each node in the network is represented by machine
>  instructions.  This makes it easy for the compiler to support inline
>  expression evaluation and external function calls in the LHS.

My understanding of the Rete algorithm (and admittedly, I don't have
the paper at hand) was that speed was obtained by building an
immediately executable tree of database checks.  In essence, a
compiled D-Net based on the contents of WM.  So the speed increase
isn't merely because you compile the LHS of all the rules (at some
level every language represents things as machine instructions, after
all), but because the Rete algorithm builds a discrimination tree that
efficiently orders the tests and guarantees that a minimum number of
tests will be taken to determine the applicable rules.  Much of OPS5's
conflict resolution strategy falls directly out of Rete, I think, in
the order in which applicable rules are found.

So, can executable functions be included in the LHS without ruining
this scheme?  I'd say no, with reservations.  At the very least, two
rules with an identical function call in the LHS will result in the
function being executed twice (since the compiler can't guarantee that
the function doesn't have a side-effect which will change its result
between different invocation with identical arguments).  So, in the
Rete scheme, if two rules have an identical WM check in the LHS, that
check is made only once each cycle of the OPS5 machine.  If they have
an executable in the LHS, that gets executed twice.  If you allow
functions which can change WM to exist in the LHS, things get much
worse. 
					-- Scott Turner