[Prev][Next][Index][Thread]
Re: Why Prolog and CBV?
Date: Thu, 14 Nov 91 18:22:54 -0600
A somewhat lesser known fact about Prolog is that it has two forms of
incompleteness. One is that Prolog may go off an infinite path of an
infinite SLD-tree. The second is that, even if there is a finite
SLD-tree, Prolog may not find it.
Breadth-first search obviously solves the first problem, but it may or
may not solve the second problem depending on your viewpoint. If you
view Prolog as really meaning Horn clauses then it does. But, most
Prolog programmers think of the Horn clause notation as just short
hand for their iff-completions. In the latter case, failure is just
as important as success, and breadth-first search (of choice paths)
does not achieve finite failure. In my own opinion, the second form
of incompleteness is more serious than the first. It is possible to
live with depth-first search, in practical terms, if finite SLD-trees
could be found whenever they exist.
The reason for this short tutorial is that, the second form of
completeness (easily achieved by a fair selection strategy) is rather
directly related to the CBV-CBN distinction. It is computationally
expensive for the same reason that CBN is - context switching
overhead. It may be unattractive to programmers for the same reason
as CBN - unpredictable evaluation order.
Uday Reddy