RESTIVO@SU-SCORE.ARPA (02/28/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Thursday, 28 Feb 1985 Volume 3 : Issue 6
Today's Topics:
Query - New Engine
Implementation - CP Bounded Merge & AT1
----------------------------------------------------------------------
Date: Fri, 22 Feb 85 16:16:14 gmt
From: William Clocksin <WFC%Cl.Cam@UCL-cs.arpa>
Subject: Query
Has anybody else tried to implement David Warren's New
Engine from his SRI Report 300? Am I correct in thinking
that nrev(X,[1,2]) fails to work properly? I think the
problem can be solved by changing the [deallocate]
instruction to copy any permanent variables down to the
previous environment if the call is non-determinant.
------------------------------
Date: Fri 22 Feb 85 17:38:52-EST
From: Vijay <Vijay.Saraswat@CMU-CS-C.ARPA>
Subject: Bounded merge in Concurrent Prolog.
The bounded merge problem in Concurrent Prolog is to
write merge/3 such that its third argument is an
indeterminate merge of its first two arguments.
(All three arguments may be thought of as streams.) In
addition it must be the case that if an input stream
already has some value in it, that value must be passed
to the output stream within a bounded number of steps.
The solution I propose is rather strong. It ensures
that if and when an input is present at the head of an
input stream, it will be the first or the second
subsequent output of the merge process. It does this by
ensuring that if anelement is popped off a stream and
there is an element on the other then that is popped
off too.
merge(X?, A.Y, A.Z):- merge(X?, Y?, Z).
merge(A.X, Y?, A.Z):- merge(X?, Y?, Z).
merge(A.X, B.Y, A.B.Z):- merge(X?, Y?, Z).
merge(A.X, B.Y, B.A.Z):- merge(X?, Y?, Z).
The reason this works is as follows. Because there is
only one occurrence of X in the head of the first clause
and it is write-protected, it can only match a variable.
Therefore the first clause is a candidate clause iff the
first stream is empty and the second has an element in it
(assuming that in the call both the streams are write
protected). Symmetrically for the second. The third and
fourth clauses ensure there is no built in bias between the
two streams.
This hinges on an understanding of the '?' read-only
annotation in Concurrent Prolog. My understanding of this
annotation is that if a term with that annotaion is unified
against another term than this unification succeeds iff
the first term is already instantiated (and normal unification
would succeed) or else the first term is a uninstantiated and
the other is a read-only variable or a variable.
------------------------------
Date: Wed, 27 Feb 85 16:50:07 pst
From: Newton@CIT-Vax (Mike Newton)
AT1 was designed as an extension to Prolog that would
allow the user to combine Logical and Functional
programming notations in one program. Unlike Loglisp,
the language that was extended was Prolog. In fact,
the extension is conservative up to the use of the
arrow and quote symbols (All Prolog programs that use
neither '=>' nor '#' as functors will run identically
in the new language).
The extensions were in the form of rewrite rules:
a(args.a) => b(args.b) :- c(args.c)
which meant that when rewriting a term with head 'a',
one could rewrite it to the term 'b', if the Prolog
goals 'c' were satisfiable. In all cases arity has
to agree -- if 'a(foo,blah)' were being rewritten
it would have to match a rewrite rule with a head of
the form a/2.
In addition, the monadic rewrite arrow is added. If
a Prolog goal has no monadic rewrite symbol, it is
treated as a normal Prolog goal to be proved. If,
however, it has a monadic rewrite symbol (not quoted),
the unifier will start rewriting this goal.
The programmer maintains control by the inclusion (or
absence) of monadic rewrite arrow within a rewrite rule.
Thus,
sick(tests) => sick(exams) :- true.
would cause only a single rewriting, whereas:
sick(tests) => =>sick(exams) :- true.
would cause rewriting to be continued.
Much of the effort in the project involved designing a
clean semantics that was usable (and controllable). I
will not go into that here, but the curious can see:
Technical Report 5172:TR:85
Caltech Computer Science
Caltech 256-80
Pasadena, CA 91125
Unfortunately, they charge $4 for a copy!
During the process of checking the proposed language,
I built an interpreter that runs under Prolog. A copy
of this has been put in the [SU-SCORE]::<Prolog> directory
as well as several samples of AT1 code (1 large example
and several small test cases).
The technical report mentioned above also contains a
section on the compilation of AT1 code using an extension
of Warren's abstract instruction set. This implementation
of this is currently being investigated.
[ {SCORE:}<Prolog>AT1_Bigger.txt ! large maze example
AT1_Smaller.txt ! smaller examples
AT1_Interpreter.pl ! the vehicle ]
------------------------------
End of PROLOG Digest
********************