Lambda the Ultimate

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.