RESTIVO@SU-SCORE.ARPA (03/25/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Monday, 25 Mar 1985 Volume 3 : Issue 12
Today's Topics:
Implementations - RF Maple & Cuts & Retract
----------------------------------------------------------------------
Date: Fri 22 Mar 85 11:18:01-MST
From: Uday Reddy <U-REDDY@UTAH-20.ARPA>
Subject: What is a logic language?
The prevalent view, which I disagree with, seems
to be that a language based on "predicate logic"
syntax is a logic language. There are three
problems with this view. Firstly, a functional
language can be couched in predicate (or relational)
syntax without any essential modification of its
operational semantics. Pisa's FPL (in Clarke and
Tarnlund, Logic Programming) and Clarke and Gregory's
relational language (in 1981 Conf on Functional
Programming Lang and Comp Arch) are examples of such
languages. These languages cannot achieve the effects
of logic programming exemplified by Prolog. Secondly,
almost all languages support predicates and boolean
operations. Why should'nt they be called logic
languages? Thirdly, "logic" goes beyond predicate
calculus. Lambda calculus is logic too. Any
programming language is logic, as it gives a formal
syntax for axioms and well-defined inference rules in
terms of its operational semantics. In any case,
syntax is not such big a deal. Real advances are not
made by just using new syntax.
If we examine what is new about Prolog and its notion
of logic programming, the answer is that its operational
semantics supports a notion of "solving". This is a
radical departure from conventional functional languages
and imperative languages whose operational semantics is
based on "rewriting". In a rewriting language, the
computation begins with a ground expression (that does not
contain any free variables) and ends in finding the value
of the expression. On the other hand, in a logic language,
the computation begins with a non-ground expression and
ends in finding instantiations for its free variables.
Hence, my definition is that a "logic language" is one
whose operational semantics supports a notion of solving.
Syntax is now completely irrelevant. It should be possible
to design a logic language with any syntax. In particular,
logic languages can be designed with functional syntax, by
using "narrowing" as the operational semantics.
Now, is RF-Maple a "logic language"? The fact that it has
a sublanguage based on relational syntax with quantifiers
or whatever is irrelevant. Can it "solve"? I wonder how
it can, without using unification.
-- Uday Reddy
------------------------------
Date: Fri, 22 Mar 85 17:53:00 pst
From: Peter Ludemann <ludemann%ubc.csnet@csnet-relay.arpa>
Subject: "soft" cuts
Chris Moss asked in digest V3 #11 about what is involved in
implementing a "soft" cut. I can't speak for other
implementations, but in the Prolog I'm building, it is
extremely easy to implement (in fact, it's already there).
When a "cut" is executed, the parent frame is marked as
having no more alternatives and the stack is popped back
(to eliminate the backtracking). For a soft cut, the
parent frame is marked but the stack isn't popped.
As to last call optimisation. In general, this can be
fully determined only at run time (for example, the famous
"append" is deterministic only if the first two arguments
are instantiated). Some implementations which determine
last call optimisation at compile time require one to use
"hard" cuts to help the compiler. The dynamic optimisation
is applicable if the stack looks like a cut was just done -
that is, the backtrack frame on the stack is the current
goal's parent.
With this implementation of last call optimisation (which
I have done), the soft cut works quite well and has much
nicer semantics than the more common "hard" cut. Just one
question: what should we call this cut (seeing that "!" is
already taken)? I haven't done much experimenting with the
soft cut, so I don't know how useful it is. I suspect that
in general it won't make much difference (assuming the
dynamic last call optimisation) because most things before
the cut will be tests and will just fail backtracking
because they will have no alternatives.
------------------------------
Date: Wed, 20-Mar-85 18:52:33 PST
From: (Lee Naish) Lee@Mungunni.OZ
Subject: retract
I'm not surprised there are buggy versions of retract around.
It is one of the nastiest bits of Prolog to implement and
no-one has even completely defined how it should behave in
all cases. Consider the following kind of goal:
?- . . . p(X), . . . retract(p(Y)), . . .
When we get around to calling retract, the call to p(X) has
just matched some clause, say C. Retracting clauses before
C in the database is not too tricky. If we try to retract
C we cannot reclaim the memory immediately but it should be
done after backtracking or perhaps if cut is called. The
effect on the call to p(X) is not properly defined. The
same is true for retracting clauses after C in the database.
When p(X) backtracks, will it be able to match these
clauses? In some implementations it may depend on whether
there are other references to the clauses (so the memory
cannot be reclaimed immediately).
The situation becomes even worse in a database system, like
the one attached to MU-Prolog. Rather than a simple linked
list (for example) in main memory and accessed
sequentially, we have a fairly complicated dynamic hashing
data structure in a file with concurrent access. The normal
solution to the inevitable problems is the readers/writers
restriction. In Prolog this leads to deadlocks since the
same process is doing the reading and writing. Our current
solution in the database system is to make people put a cut
between p(X) and retract(p(Y)). This means that the call
to p reading the database can be killed before retract
writes on the database. The operational semantics are also
(relatively) unambiguous.
This is just one of many examples where retract (and assert
and cut) is not defined properly. Does anyone have any
sugestions for well defined semantics (preferably possible
to implement) or alternatives?
-- Lee Naish
------------------------------
End of PROLOG Digest
********************