Computation is not subsumed by deduction (contra claim by Kowalski)

The challenge to the generality of Logic Programs as a foundation for computation was officially thrown in The Challenge of Open Systems [Hewitt 1985] to which [Kowalski 1988b] replied in Logic-Based Open Systems. This was followed up with Guarded Horn clause languages: are they deductive and logical? [Hewitt and Agha 1988] in the context of the Japanese Fifth Generation Project (see section below). All of this was against Kowalski who stated “Looking back on our early discoveries, I value most the discovery that computation could be subsumed by deduction.” [Kowalski 1988].

However (contrary to Kowalski), computation in general is not subsumed by deduction. Mathematical models of computation do not determine particular computations as follows: The Actor Model makes use of arbitration for determining which message is next in the reception order of an Actor that is sent multiple messages concurrently. For example Arbiters can be used in the implementation of the reception order of messages sent to an Actor which are subject to indeterminacy in their reception order. Since reception orders are in general indeterminate, they cannot be inferred from prior information by mathematical logic alone. Therefore mathematical logic cannot implement computation in open systems. Consequently, Logic Programs can axiomatize but not in general implement computation.

Shared financial accounts had been developed as a paradigmatic example of Actors [Hewitt, Bishop and Steiger 1973]. For example in ActorScript, a simple account can be implemented as follows:

CreateEuroAccount.[startingBalance:Euros] ≡
  Actor with currentBalance:=startingBalanceâ—Š
     implements Account using
      GetBalance[]→ currentBalance¶
      Deposit[anAmount]→  Void afterward currentBalance:=currentBalance+anAmount¶
      Withdraw[anAmount]→
          (anAmount > currentBalance) ¿ True ↝ Throw OverdrawnException[];
                                        False ↝  Void afterward currentBalance:=currentBalance–anAmount ?§▮

However, the above program cannot be implemented using logical deduction.

The Procedural Embedding paradigm is strictly more general than the Logic Program paradigm. Nevertheless, Logic Programs (like Functional Programs) can be a useful idiom.

For more information see Inconsistency Robustness in Logic Programs.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Alan Kay on objects and logic

I was just viewing Alan Kay's contribution to the History of Computing lectures at San José State University, two years ago.
Scroll down to "Invention of the Dynabook, the forerunner of today's laptop and tablet computers - 11/16/11".

At 70:55 Alan starts talking about Planner, Actors, Prolog and Linda. He discusses a limitation of Prolog: a backwards chainer, whereas Planner could go both directions.

"A lot of the great ideas in Planner did not make it into Actors either. When Gelernter did Linda, (...) this is how to unify objects and what Planner was all about; how to unify objects and logic in the nicest way".

The Actor Model is pure message passing

The Actor Model is pure message passing, which is universal for (concurrent) computation. As such it has been the foundation for program languages that perform forward and backward chaining in addition to much more.

Message passing...

I guess you mean asynchronous message passing with FIFO queues, right? Or are these properties not essential?

A goal is that a message sent is received exactly once

A goal is that a message sent to an Actor is received exactly once. It's up to implementations to achieve this goal.

Shouldn't that be:A message

Shouldn't that be:

A message sent to an Actor is processed exactly once

In the Coursera Principles of Reactive Programming course we learn that messages may be lost, so that they may have to be rest every once in a while, until acknowledgement. The addressee should only process such a resent message once.

A message received exactly once is processed exactly once

A message received exactly once is processed exactly once.