LISP VERSUS PROLOG - a discussion extracted from the AIList

------------------------------

Date: Wed, 14 Aug 85 00:40:17 EDT
From: Carl E. Hewitt <HEWITT@MIT-MC.ARPA>
Subject: Prolog will fail as the foundation for AI; so will LOGIC as
         a PROGRAMMING Language

Prolog (like APL before it) will fail as the foundation for Artificial
Intelligence because of competition with Lisp.  There are commercially
viable Prolog implementations written in Lisp but not conversely.

LOGIC as a PROGRAMMING Language will fail as the foundation for AI because:

  1.  Logical inference cannot be used to infer the decisions that need to be
      taken in open systems because the decisions are not determined by
      system inputs.

  2.  Logic does not cope well with the contradictory knowledge bases inherent
      in open systems.  It leaves out counterarguments and debate.

  3.  Taking action does not fit within the logic paradigm.


  [Carl also sent this message to the philosophy of science mailing
  list (Phil-Sci-Request%MIT-OZ@MIT-MC), and it has triggered several
  responses about Prolog/Logic Programming/AI.  I am happy to let
  Phil-Sci carry the discussion, although it could just as easily
  have fit within AIList or the Prolog digest.  For a good elaboration
  of Carl's thesis on open systems (networks, banking systems,
  nondeterministic distributed systems, etc.), see his article in
  the April '85 issue of BYTE.  It's interesting reading, as are most
  of the articles in this special issue on AI.  (The April Fool's
  What's Not column on pp. 96-97 is fun too.)  -- KIL]

------------------------------

Date: Sat 17 Aug 85 10:38:41-PDT
From: PEREIRA@SRI-AI.ARPA
Subject: Hewitt's tirade against Prolog

Carl Hewitt's message is based on several misconceptions:

1. (the least interesting one) All the so-called commercially viable
Prolog systems in Lisp are not really Prolog systems written IN Lisp,
but rather Prolog systems written FOR Lisp machines. Or is it that a
microcode sublanguage or Lisp machine pointer-smashing operations are
part of List as we know it? Without those machine-level operations,
those Prolog systems would run too slow and use too much memory to be
useful for serious Prolog programming. From the Prolog implementation
point of view, what is important about the Lisp machines is not that
they run Lisp, but that they can be microcoded and have good support
for tagged data types and stack operations.

2. If the decisions (actions) of a system are not determined by its
inputs, the system is nondeterministic. Nondeterminism in a system can
be either an artifact of our incomplete knowledge (or lack of
interest) of the detailed operation of the system; or it can be
``real physical'' nondeterminism. It would take us to far to discuss
whether the second kind of nondeterminism is ``real'' or also an
artifact. In any case, most uses of nondeterminism, say in models of
concurrency, are of the first kind, and can be expressed appropriately
in various temporal/dynamic logics. Admittedly, these are not Prolog,
but then Common Lisp is not Lisp 1.5! (Prolog is 13 years old, Lisp
25).

3. The first logic course dictum ``from a contradiction one can
conclude anything'' is getting in the way. Notice that the dictum says
``can'', not ``must''. There is an enormous difference between things
that are in principle true and things that an agent knows to be true
in a way that can affect its action. An agent might know ``p'' and
``not p'', but it might well never come to infer the dreaded totally
unrelated ``q'' which IN PRINCIPLE follows from the contradiction.
This inference might not happen either because of inference control
mechanisms of the agent (eg. it uses the set-of-support strategy) or
because the agent's logic is just TOO WEAK to conclude anything from a
contradiction (vide Hector Levesque's work in the proceedings of the
last AAAI). In any case, Horn clauses (the basis of Prolog) are too
weak to represent contradictions... :-)

4. The question of whether ``taking action'' fits in a logic paradigm
tends to be answered negatively after an hour's worth of
consideration.  If you persist for several years, though, this
question becomes a source of insight on the relations between
knowledge, state and action that is not available to those who started
by dismissing the question after that initial hour. There is just too
much work on logics of knowledge and action in AI and computer science
for me to try to discuss it here. Some of this work has been applied
to logic programming, either in the form of new logic programming
languages based on temporal or dynamic logics or in representations of
temporal reasoning and decision in, say, Prolog.

5. It is curious to see someone by implication defend Lisp as a
language for expressing the taking of action! We know by now that the
most difficult issue in ``reactive systems'' is not EXPRESSING action,
but rather keeping it under control to prevent unwanted interactions.
In this area, less is REALLY more, and highly complex languages like
Lisp are just not suitable for the formal reasoning about programs
that is needed to help us believe our programs do what we intend. To
those who say ``...but we can keep to a carefully constrained subset
of Lisp, use only message passing for interactions,...'' I will answer
that the history of all large Lisp programs I know (and I think that
is a representative sample) is littered with the brutalized corpses of
constrained programming styles. Anyone who has looked at the current
flavor mechanism in Zetalisp and its use in the window system will
know what I mean...

6. Underlying Carl Hewitt's misconceptions is the old chestnut ``logic
is static, systems are dynamic''. Any language, be it first-order
logic or Lisp, is static; it is its USE which is dynamic (changes the
state of communicating agents). A good analogy here is the use of
differential equations to model dynamic systems in classical
mechanics. The differential equations themselves do not say directly
what happens when (they are ``static'' in Hewitt's jargon). It is
their SOLUTIONS that tell us the sequence of events. Even the
solutions are given as static objects (functions from an open interval
of the reals to some space). Does anyone worry that such equations do
not ``really'' describe the dynamic behavior of a system? Is it not
possible to combine such ``static'' entities with an incremental
solution procedure to build systems that actually control their
(classical mechanical) environment?

-- Fernando Pereira

------------------------------

Date: Mon, 19 Aug 1985  13:30 EDT
From: Hewitt@MIT-MC
Subject:   Prolog will fail as the foundation for AI

Misconceptions?

    From: PEREIRA at SRI-AI.ARPA

    Carl Hewitt's message is based on several misconceptions:

    1. (the least interesting one) All the so-called commercially viable
    Prolog systems in Lisp are not really Prolog systems written IN Lisp,
    but rather Prolog systems written FOR Lisp machines. Or is it that a
    microcode sublanguage or Lisp machine pointer-smashing operations are
    part of List as we know it? 

Yes.  They are DEFINITELY part of Common Lisp as we know it being
implementations of reading and writing operations on record
structures.  Such implementation methods are NOT part of Logic as a
Programming language.

    Without those machine-level operations,
    those Prolog systems would run too slow and use too much memory to be
    useful for serious Prolog programming. From the Prolog implementation
    point of view, what is important about the Lisp machines is not that
    they run Lisp, but that they can be microcoded and have good support
    for tagged data types and stack operations.

It is important to many users that they can make use of ALL the software
available to the community and not just be limited to the tiny amount
in Prolog.  Furthermore in the future good software will be ported
from stand alone Prolog systems to Prolog implemented on Lisp.  However
to good Lisp software will not be able to be ported to the stand
alone Prolog systems.

    2. If the decisions (actions) of a system are not determined by its
    inputs, the system is nondeterministic. Nondeterminism in a system can
    be either an artifact of our incomplete knowledge (or lack of
    interest) of the detailed operation of the system; or it can be
    ``real physical'' nondeterminism. It would take us to far to discuss
    whether the second kind of nondeterminism is ``real'' or also an
    artifact. In any case, most uses of nondeterminism, say in models of
    concurrency, are of the first kind, and can be expressed appropriately
    in various temporal/dynamic logics. Admittedly, these are not Prolog,
    but then Common Lisp is not Lisp 1.5! (Prolog is 13 years old, Lisp
    25).

Yes indeed there is a large problem here that poses fundamental problems
for using Logic as a Programming language to make decisions in Open
Systems.

    3. The first logic course dictum ``from a contradiction one can
    conclude anything'' is getting in the way. Notice that the dictum says
    ``can'', not ``must''. There is an enormous difference between things
    that are in principle true and things that an agent knows to be true
    in a way that can affect its action. An agent might know ``p'' and
    ``not p'', but it might well never come to infer the dreaded totally
    unrelated ``q'' which IN PRINCIPLE follows from the contradiction.
    This inference might not happen either because of inference control
    mechanisms of the agent (eg. it uses the set-of-support strategy) or
    because the agent's logic is just TOO WEAK to conclude anything from a
    contradiction (vide Hector Levesque's work in the proceedings of the
    last AAAI). In any case, Horn clauses (the basis of Prolog) are too
    weak to represent contradictions... :-)

I claim that in practice the contradictions lie close to the surface and
occur in any nontrivial application.  Thus the contradictions
pose fundamental problems for using Logic as a Programming Language.

    4. The question of whether ``taking action'' fits in a logic paradigm
    tends to be answered negatively after an hour's worth of
    consideration.  If you persist for several years, though, this
    question becomes a source of insight on the relations between
    knowledge, state and action that is not available to those who started
    by dismissing the question after that initial hour. There is just too
    much work on logics of knowledge and action in AI and computer science
    for me to try to discuss it here. Some of this work has been applied
    to logic programming, either in the form of new logic programming
    languages based on temporal or dynamic logics or in representations of
    temporal reasoning and decision in, say, Prolog. 

I have been thinking about the problem for many years having designed
Micro-Planner, the first "procedural embedding of logic" programming
language in 1967.  I claim that the problem of taking action poses
fundamental problems for using Logic as a Programming language.

    5. It is curious to see someone by implication defend Lisp as a
    language for expressing the taking of action!

I claim that current Lisp systems are better than current Prolog
systems for taking action because the only ways to take action in
current Prolog systems are kludges.


    We know by now that the
    most difficult issue in ``reactive systems'' is not EXPRESSING action,
    but rather keeping it under control to prevent unwanted interactions.
    In this area, less is REALLY more, and highly complex languages like
    Lisp are just not suitable for the formal reasoning about programs
    that is needed to help us believe our programs do what we intend. To
    those who say ``...but we can keep to a carefully constrained subset
    of Lisp, use only message passing for interactions,...'' I will answer
    that the history of all large Lisp programs I know (and I think that
    is a representative sample) is littered with the brutalized corpses of
    constrained programming styles. Anyone who has looked at the current
    flavor mechanism in Zetalisp and its use in the window system will
    know what I mean...

    5. Underlying Carl Hewitt's misconceptions is the old chestnut ``logic
    is static, systems are dynamic''.

Note that the above quotation is NOT anything that I said.

    Any language, be it first-order
    logic or Lisp, is static; it is its USE which is dynamic (changes the
    state of communicating agents). A good analogy here is the use of
    differential equations to model dynamic systems in classical
    mechanics. The differential equations themselves do not say directly
    what happens when (they are ``static'' in Hewitt's jargon).

I do not deny that dynamic systems can be DESCRIBED using logic only
that they can be CONTROLLED.

    It is
    their SOLUTIONS that tell us the sequence of events. Even the
    solutions are given as static objects (functions from an open interval
    of the reals to some space). Does anyone worry that such equations do
    not ``really'' describe the dynamic behavior of a system? Is it not
    possible to combine such ``static'' entities with an incremental
    solution procedure to build systems that actually control their
    (classical mechanical) environment?

I do not believe that the control system can be implemented using Logic
as a Programming language

------------------------------