IBM’s Logic Algorithms in Dyalog APL
Vector 4:1, page 104
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 104
Abstract¶
The algorithms developed by Brown et al for use in APL2 can be converted to run in Dyalog APL. Various minor improvements are possible. A by-product of this is a set of functions to convert nested arrays of logical data into simple character vectors. These are developed to provide ways of testing logical data for consistency with notational rules, correcting errors in data entry, and recovering formal-logic versions of APL logic data.
1. Simple Substitutions¶
1.1 The Original Material¶
In their APL86 tutorial [1] James Brown and his colleagues give a very useful and comprehensive account of the ways and means of embedding artificial intelligence algorithms into APL2. Their reference for the underlying theory is the book by Charniak and McDermott [2] and I have indeed found that a very effective way of learning about AI is to work through their APL functions and examples first, and then read Charniak once one can visualise, from the APL, what is going on. However, since my own computer is an RT running Dyalog APL, it was necessary to adapt the IBM functions to fit. Not only are the dialects different, but the published functions contain IBM proprietary ⎕functions that had to be circumvented.
Thus the first section of this paper contains an account of the minimal adaptations needed to get the IBM system running under Dyalog, in the sense of doing what Brown et al say in their tutorial that it should do. The rest of the work consists of improvements (perhaps) and adaptations.
Throughout, I have had to assume some familiarity with the underlying ideas. The original tutorial runs to some sixty pages, and I can’t repeat more than a fraction of it. I have, however, tried to ensure that someone who knows AI, but not the tutorial, will have a clear idea of what is going on.
1.2 Data Structures¶
The data structures used in AI work are nested character vectors of considerable complexity. In IBM’s terminology the highest level is the database, which is a vector of clauses, each of which is taken to be asserted. A clause is a two element vector of lists of predicates:
which is interpreted as: “at least one of A,B,… is true if all of P,Q,… are true”, or as “either at least one of A,B… is true or at least one of P,Q,… is false”. These interpretations are equivalent in classical logic. Brown et al prefer the second, which brings out the rule that an unconditional fact is coded by a clause with the empty character vector as the second element (with statements of falsity going the other way round).
A predicate is a statement which is essentially indivisible, such as:
which is made up of a relation ‘is_ a_man’ and a term ‘Socrates’. The general form is:
where terms may be variable or fixed. Predicates are the building blocks of logic statements. Thus the clause asserting that “all men are mortal” is represented semi-formally as:
being the pair
In APL all variables (the ‘X’s inside predicates) get a ‘delta’ in front of them, and ‘is’ and ‘are’ disappear. Thus typical predicates are:
while terms can be complex structures
and clauses are always vectors of rank 2, for example:
means “X is married to Y, if Y is married to X”, which is the kind of assertion that often has to be carefully spelled out in logical databases. ‘Married’ is a reflexive relationship, unlike (say) 'is_husband_of'. You know this, but the machine has to be told.
1.3 Inference Functions¶
There are two core functions in the approach to AI that is discussed here. They are unification and resolution. The job of unification is to compare two statements (usually half-clauses) and say whether they are identical, or could be identical if some or all of their variables took particular values. If so, the UNIFY function should return these values. For instance
unifies with
under the substitution
A more complex APL example is:
Resolution takes two clauses and uses unification to find their common ground, if any. Thus (remembering that a simple fact is a clause with an empty second element) the clauses
and
have the resolvant
using the same substitution of ‘socrates’ for ‘X’. To give an APL example, the sort of thing that we really want is:
ST2
on box table
ST3
by ∆Z ∆Y by ∆X ∆Y on ∆Z ∆X
ST2 RESOLVE ST3
by box ∆Y by table ∆Y ∆X←'table' ∆Z←'box'
However, there is no assurance, in the absence of special precautions, that the resolvant is not more obscure than the originals.
Careful consideration will show that the result is in fact trivially true. The OBVIOUS function in section 2.1 detects such nuisance results.
1.4 The Unification Algorithms¶
∇ Z←X UNIFYA Y ⍝ unify X with Y
[1] →((0=⍴X)∧(0=⍴Y))/FAIL ⍝fail if both clauses empty
[2] X Y←EVAL DEPTH1 (X Y) ⋄ →(X≡Y)/GOOD⍝do substitutions
[3] X Y←(1=≡Y)⌽X Y ⍝put atom first, if any
[4] →((0=≡X)∧(0=≡Y)∧(~X≡Y))/FAIL ⍝avoid infinite loops of 'a' swop 'b'
[5] →(1≠≡X)/RECUR ⍝if not an atom apply to each; else:
[6] X Y←('∆'≡⊃Y)⌽X Y ⍝put variable first, if any
[7] →(~'∆'≡⊃X)/FAIL ⍝if no variable, items are different
[8] →(X SEARCH Y)/FAIL
[9] ⍎X,'←Y' ⋄ →GOOD ⍝do substitution
[10] RECUR:→(~(⍴X)≡⍴Y)/FAIL
[11] →(1=X(UNIFYA UNTIL 0)Y)/GOOD
[12] FAIL:→Z←0
[13] GOOD:Z←1
∇ Z←X UNIFY Y;T;USUBS
[1] ⍝Unification main algorithm: Z is 2-item vector
[2] ⍝<0 or 1 for failure or success> <the substitutions>
[3] T←⎕EX'∆'⎕NL 2 ⋄ Z←X UNIFYA Y
[4] T←↓'∆'⎕NL 2 ⋄ →(0=⍴USUBS←T)/END
[5] USUBS←(T∘.,'←'), SCRIPT ⍎ T
[6] END:Z←Z USUBS
Except for a certain amount of compression, these are the same as in [1] apart from lines 8 and 11 of UNIFYA and lines 4 and 5 of UNIFY. Sameness is modulo direct ‘machine translation’ between APL2 and Dyalog in as much as the same functions sometimes have different symbols, of which by far the commonest in this particular workspace is ‘disclose’: ↑ in APL2 ; ⊃ in Dyalog.
Line 11 of UNIFYA is a speeded-up version according to IBM’s own suggestion. Line 8 is the ‘occurs check’ to avoid perverse substitutions. In the original, this uses the idiom ‘epsilon-underline monadic epsilon’, neither element of which occurs in Dyalog. An equivalent effect, using a different principle, is given by:
∇ Z←X SEARCH Y ⍝models APL2 'X⍷∊Y' for use in the UNIFYA function
[1] Z←~(''∘.≡DEPTH1 Y)≡(X∘.≡DEPTH1 Y)
In line 9 of UNIFYA substitution is made by giving a value to a particular variable. This value is stored as an instruction inside USUBS, so that the variable can be deleted at the start of the next call to UNIFY. The IBM original uses
which is a proprietary function. The Dyalog XFER functions work very differently, so we introduce
∇ Z←SCRIPT A;BL;BR;Q;E ⍝ A is a CHARACTER variable
[1] BL←'(' ⋄ BR←')' ⋄ Q←'''' ⋄ E←',⊂' ⍝ set up working variables
[2] ⍝ A is the material, BL, BR the brackets, Q quote mark, E enclosure
[3] →(''≡DECON A)/NULL ⋄ →(1=≡A)/VEC ⋄ →(0=≡A)/SCAL ⋄ →(2≤⍴A)/REC ⋄ →ENC
[4] REC:Z←BL,(⊃,/SCRIPT A),BR.⋄ →0 ⍝ Result is simple vector
[5] ENC:Z←BL,E,(SCRIPT⊃A),BR ⋄ →0 ⍝ Scalar is 1-element vector
[6] VEC:→(1≥⍴A~' ')/NEXT ⋄ Z←Q,(A~' '),Q,' ' ⋄ →0
⍝ Only one word per vector
[7] NEXT:→(0=⍴A)/NULL ⋄ Z←BL,',',Q,(A~' '),Q,BR ⋄ →0 ⍝ No trailing zeros
[8] NULL:Z←Q,Q ⋄ →0 ⍝ Null clause is empty vector
[9] SCAL:Z←BL,',',Q,A,Q,BR ⋄ →0 ⍝ Scalar is 1-element vector
[10] ⍝ Replaces APL2 '2 ⎕TF A' for use in the UNIFY function
The DECON function cited in line 3 is intended to be an equivalent for IBM’s monadic epsilon, i.e. it destroys structure and just returns contents.
∇ R←DECON X ⍝ Tries to remove all structure from X
[1] →(1<|≡X)/REC ⋄ R←,X ⋄ →0 ⍝ Ravels simple objects
[2] REC:⍎((,0)≡⍴X)/'R←'''' ⋄ →0' ⋄ R←⊃,/DECON X
⍝ Deals recursively with complex objects
SCRIPT has several intended side-effects, of which more in subsequent sections. Indeed, most of its elaborations are never used during unification, which only involves very simple objects: usually ordinary vectors, sometimes vectors of depth 2. There is therefore no penalty in terms of cpu time. However SCRIPT, though introduced out of necessity in the first place and only extended later, proves to have an amazing range of uses.
The unification algorithms are the core of this sort of AI. It is surprising to what degree any troubles at higher levels tend to refer back to unresolved problems in this group of functions.
1.5 The Resolution Algorithms¶
The resolution algorithms are a straightforward case of machine translation except for what appears to be a misprint in IBM’s RESOLVANT. As it is given in [1], this does not seem to pass on the substitutions as well as the resolvant itself. This omission has no effect on the FORWARD goal- proving function, but it plays havoc with the PROLOG group of functions. We therefore quote:
∇ Z←AR RESOLVANT BR;T
[1] ⍝UNIFY AR with BR, Z is 0 or the implied resolution.
[2] ⍝A & B are global
[3] Z←0 ⍝Assume failure
[4] →(⊃T←AR UNIFY BR)↓0 ⍝return with 0 if no UNIFY
[5] Z←(((1⊃A)~⊂AR),1⊃B)((2⊃A),(2⊃B)~⊂BR)
[6] Z←(EVAL DEPTH1 Z)(2⊃T)
∇
∇ Z←A RESOLVE B
[1] Z←,(1⊃A)∘.RESOLVANT(2⊃B)
[2] B A←A B
[3] Z←Z,,(1⊃A)∘.RESOLVANT(2⊃B)
[4] Z←Z~0
∇
∇ Z←A RESOLVEGOAL B
[1] Z←,(1⊃A)∘.RESOLVANT(2⊃B)
[2] Z←Z~0
∇
where line 6 of RESOLVANT is the only significant change.
1.6 Higher Levels¶
The front-end functions work more or less on sight, after ‘machine translation’, provided that one has faith. For instance, the depth-first search algorithm
∇ Z←CGS DF DB;DBI;GI;ASUBS;GSUBS;SG;T;GOAL;NEW
[1] GOAL ASUBS←2↑CGS ⍝ divide argument
[2] SG←SPLITGOAL⊃GOAL ⍝get simple goals
[3] →(3>⍴CGS)/START
[4] GI GSUBS DBI←3⊃CGS
[5] DBI[(GI-1)↓⍳⍴DBI]←1 ⋄ →BACK
[6] START:GI←1 ⋄ GSUBS←(⍴SG)⍴'0' ⋄ DBI←(⍴SG)⍴1 ⍝first goal, initial subs
[7] NEXT:T←⎕EX'∆'⎕NL 2 ⋄ T←⍎DEPTH1 ASUBS GSUBS
[8] T←EVAL DEPTH1(DBI[GI]⊃DB) ⍝ select next rule
[9] NEW←T RESOLVEGOAL EVAL DEPTH1 GI⊃SG
[10] →(0≠⍴NEW)/RES ⍝ branch if something found
[11] NEXTDB:→((⍴DB)≥(DBI[GI]←DBI[GI]+1))/NEXT ⍝ try next rule
[12] DBI[GI]←1 ⍝ initialize index again
[13] BACK:→(0=(GI←GI-1))/Z←0 ⍝ back up to previous goal
[14] GSUBS[⊂GI]←'0' ⋄ →NEXTDB ⍝ forget old subs, find another proof
[15] RES:GSUBS[⊂GI]←⊂2⊃⊃NEW ⍝ record substitutions
[16] →(0=⍴1 ↓ 2⊃NEW)/NEXTG ⍝ branch if proved
[17] T←((VRENAME⊃NEW)[1])(ASUBS GSUBS)DF DB ⍝ do sub-goal
[18] →(⊃T)/SGOK ⍝ branch sub-goal OK
[19] GSUBS[⊂GI]←'0' ⋄ →NEXTDB ⍝ forget old subs, find another proof
[20] SGOK:GSUBS[⊂GI]←,/GSUBS[⊂GI],2⊃T ⍝ record new substitutions
[21] NEXTG:GI+←1 ⋄ →(GI≤⍴SG)/NEXT ⍝ on to the next goal, if any
[22] DONE:Z←1 GSUBS(GI GSUBS DBI)
and its user-friendly front end
∇ Z←L PROLOG R;T
[1] →(~''≡⊃L)/START ⋄ L←⊂L
[2] START:Z←1 ⋄ →(⊃T←(L'0')DF R)/GOOD
[3] →Z←0
[4] GOOD:'VALUES: '(2⊃T) ⋄ →(';'≠⊃⍞)/0
[5] →(⊃T←(L'0'(3⊃T))DF R)/GOOD
otherwise differ from their originals only in lines 14,15 (=19) and 20 of DF and in the beginning of line 1 of PROLOG.
GO2
john loves ∆X ∆X is female
↑DATA2
john loves food
jane is female
john loves jane
GO2 PROLOG DATA2
VALUES: ∆X←'jane'
1
SCRIPT GO2
(''(('john' 'loves' '∆X' )('∆X' 'is' 'female' )))
↑SCRIPT DATA2
((,⊂('john' 'loves' 'food' ))'')
((,⊂('jane' 'is' 'female' ))'')
((,⊂('john' 'loves' 'jane' ))'')
Exhibit 1. Use of PROLOG.
Prolog logic progamming[3] assumes that all data can be represented by Horn clauses (clauses with only one element on the left hand side), in which case its system of depth-first searching and backtracking is an extremely effective way of testing existence statements. In exhibit 1, the goal is to test the assertion
and return with the correct answer ‘Jane’. Prolog handles such statements by putting them on the right hand side of a clause. This is equivalent to:
i.e.
but since X is a free variable, this is equivalent to
so if a contradiction appears during the search we have
which is equivalent in classical logic to
In other words, we add the negation of the thing that we want, look for a contradiction, and report what caused it.
The clever part of the Prolog approach is the ability to forget false starts. In the example, any resolution-based system will lock first of all onto X=food before getting into trouble trying to show that “food is female”. Prolog does too, but then discards the first statement and starts again. Furthermore, the PROLOG cover function allows the user to send the machine back to find other examples, if any. The other method used in [1] is forward chaining. In this instance, we have altered the way it works, and so it is discussed in the next section.
2. Minor Improvements¶
2.1 Eliminating Tautologies¶
In the course of resolving clauses, a logic program will on occasion come up with a statement that is true, but trivially so; that is, a tautology. In particular, if the same assertion appears on both sides of a clause, then that clause is a tautology. Remember that a clause holds if any element on the left hand side follows from the right hand side. Such a tautology can be detected by:
∇ Z←OBVIOUS X ⍝ Checks to see if a predicate occurs both sides of X
[1] →(2≠⍴X)/Z←0 ⍝ Precaution: is X a clause?
[2] →(1=∨/(⊂'')≡¨ X)/Z←0 ⍝ Precaution: is X a fact (pos or neg)
[3] Z←∨/,⊃((∘.≡)/X) ⍝ Matches each of X[1] to each of X[2]
This function is used in the new version of the forward chaining function:
∇ PZ←GOAL FORWARD DB;NEW;NEW2
[1] PZ←1 ⋄ VCOUNT←1
⍝ assume goal will be found. VCOUNT external
[2] NEW←DB ⍝ DB against itself first time
[3] L1:→((⊂GOAL)∊NEW)/0 ⍝ done if goal is found
[4] NEW2←NEW∘.RESOLVE DB ⍝ resolve everything
[5] DB←DB,NEW ⍝ add last set of results to DB
[6] DB←∪DB ⍝ delete duplicates
[7] NEW←⊃ ⊃,/,NEW2 ⍝ bring out new inferences
[8] NEW←∪NEW ⍝ delete duplicates
[9] NEW←(~OBVIOUS NEW)/NEW ⍝ attempt to eliminate tautologies
[10] NEW←VRENAME NEW ⍝ rename variables
[11] →(0=⍴NEW)/FAIL ⋄ →L1
⍝ fail if nothing new, else redo resolution
[12] FAIL:PZ←0
Lines 6 and 8 of FORWARD have been altered to use the Dyalog ‘unique’ function. Line 9 is a pure addition to eliminate tautologies. Exhibit 2 shows the effects of omitting line 9 to give FORWARD1. The display is achieved by altering the function to print out NEW at each stage. FORWARD generates two items in the first pass and four in the second, before recognising that one of them is the thing it was asked to prove. FORWARD1 generates three items in the first pass and seven in the second, including an annoying wrap-round. The extra items are offspring of the tautology allowed through in the first pass.
For completeness, we also show the effect of using the PROLOG function, remembering to reverse the goal first. PROLOG reports the individual values involved, whereas FORWARD (except when, as here, it has been altered to print out the intermediate working) simply reports that the goal is true. On the RT, PROLOG is more than twice as fast on this problem as the terse version of FORWARD. However FORWARD is much more robust. PROLOG can be thrown simply by permuting DATABASE. Possible precautions are discussed in the next section.
VCOUNT controls the renaming of variables in line 10 of FORWARD and line 17 of DF. The fact that a variable X is mentioned in two different clauses does not mean that it will take the same value in both. Renaming variables ensures that no two machine-generated clauses have the same variables, and so no interference during substitution will occur. In defining the initial database, this may need to be done by hand.
GO
by box window
↑DATABASE
by table window
on box table
by ∆Z ∆Y by ∆X ∆Y on ∆Z ∆X
GO FORWARD DATABASE
by ∆Z window on ∆Z table
by box ∆Y by table ∆Y
by box window
by ∆Z window on ∆X table on ∆Z ∆X
by ∆Z ∆Y by table ∆Y on ∆Z box
by box ∆Y3 by ∆X ∆Y3 on table ∆X
1
GO FORWARD1 DATABASE
by ∆Z window on ∆Z table
by box ∆Y by table ∆Y
by ∆X ∆Y by ∆X ∆Y on ∆X ∆X on ∆X ∆X
by box window
by ∆Z window on ∆X table on ∆Z ∆X
by ∆Z ∆Y by table ∆Y on ∆Z box
by box ∆Y3 by ∆X ∆Y3 on table ∆X
by table window on table table on table table
by ∆Z ∆Y by ∆X ∆Y on ∆X ∆X on ∆X ∆X on
by ∆X4 ∆Y4 by ∆X ∆Y4 on ∆X4 ∆X on ∆X4 ∆X4
∆Z ∆X
on ∆X4 ∆X4
1
VCOUNT←1
(⊖GO) PROLOG DATABASE
VALUES: ∆Y←'window' ∆Z←'box' ∆X2←'table'
1
Exhibit 2. Two variants of the FORWARD function.
2.2 Stabilising PROLOG¶
In section 2.1 we stated that PROLOG was better than twice as fast, on a test problem, as FORWARD. But it may fail if we reorder the assertions in the database. To see why, we trace line 2 of DF, which lists the subgoal(s) at each stage. D is a vector of all the orderings of the variable DATABASE as used in exhibit 2.
2 ⎕TRACE 'DF'
(⊖GO) PROLOG 1⊃D
DF[2] by box window
DF[2] by ∆X1 window on box ∆X1
VALUES: ∆Y←'window' ∆Z←'box' ∆X1←'table'
1
The system decides that in order to prove ‘by box window’ it must simultaneously prove the next two assertions: the two sub-goals. This it does, and returns the successful values.
But another permutation has to be stopped by an interrupt.
(⊖GO) PROLOG 3⊃D
DF[2] by box window
DF[2] by ∆X2 window on box ∆X2
DF[2] by ∆X3 window on box ∆X3
DF[2] by ∆X4 window on box ∆X4
The system finds the same subgoals (give or take renumbering) as before. It then finds them again as subgoals of the first subgoal, and goes into an infinite branching process. The first sub-goal is, in full:
and the machine has the general rule
which, together with the current substitutions, gives
RESOLVE legitimately matches X2 with ‘box’ and DF tries, yet again, to prove the right hand side of the second expression. This is an explosive process. It will happen for any ordering that presents the general formula before the fact
After the final substitution, the remaining checking is safe enough.
One safeguard is always to ensure that all facts come before the general rules. This is good Prolog style, but is not a complete protection. Another possibility is to alter line 17 of the DF function to:
This shifts the database along one when testing the subgoals (the only point at which it can be touched), and again when testing sub-subgoals, and so on. It seems to be successful in practice, as long as there is a route through the database and only one line is causing the trouble. Sooner or later that line will arrive at the end and never be reached. It fails if there is no such route at all. An example of an unreachable goal is ‘by(box, table)’:
CONSTRUE NUMB
~by(box, table)
NUMB PROLOG DATABASE
DF[2] by box table
DF[2] by ∆X16 table on box ∆X16
DF[2] by ∆X17 table on box ∆X17
DF[2] by ∆X18 table on box ∆X18
This is using the improved version of DF. With an unprovable assertion to be tested, there is no safe route through the database for the permutations to bring to the front. FORWARD also fails to halt (we use the chatty version that prints NEW at each stage):
(⊖NUMB) FORWARD DATABASE
by ∆Z window on ∆Z table
by box ∆Y by table ∆Y
by box window
by ∆Z window on ∆X table on ∆Z ∆X
by ∆Z ∆Y by table ∆Y on ∆Z box
by box ∆Y3 by ∆X ∆Y3 on table ∆X
Again an interrupt is necessary. The very powerful nature of the general rule means that intermediate rules can be generated ad infinitum. It seems more promising to attack PROLOG again, as the fault here is much more specific.
We first write a function that discovers if the variables have only been relabelled, so that at least one of the new goals is in reality the same as the original.
∇ Z←X FRAUD Y;T ⍝Determines if X is the same as Y modulo labelling
[1] Z←0 ⋄ →(X≡Y)/0 ⍝ 0 means fraud. Exit if identical
[2] T←⎕EX'∆'⎕NL 2 ⋄ T←X UNIFYA Y ⋄ ⍎(T=0)/'Z←1 ⋄ →0'
[3] ⍝ If X and Y do not unify, no fraud. Else look for substitutions
[4] T←↓'∆'⎕NL 2 ⋄ ⍎(0=⍴T)/'Z←1 ⋄ →0' ⍝ Precaution against null case
[5] T←⍎ T ⋄ →(∧/'∆'≡¨ ⊃¨ T)/0 ⍝ If all substitutions are simple variables
[6] Z←1 ⍝ then fraud, else pass it as having some content.
We then feed it into the function RESOLVEGOAL:
∇ Z←A RESOLVEGOAL B
[1] Z←,(1⊃A)∘.RESOLVANT(2⊃B)
[2] Z←Z~0 ⋄ →(0=⍴Z)/0 ⍝ Exit if empty, else check for fraudulent subs.
[3] Z←(∧/(2⊃B)FRAUD 2⊃⊃⊃Z)/Z
This modifies the behaviour of DF and hence that of PROLOG:
There is little value in also using the permutation suggestion for line 17 of DF as this reduces the consistency of timing over permutations of the database. The negative result takes roughly the same average time as the positive, but is even more consistent. FORWARD shows the least variation in speed, but the average time is twice as long as PROLOG for the positive search. As we saw, the negative search never terminates.
FRAUD allows substitutions of the form ‘f(x)’ for ‘x’. We leave a potential for infinite branching, because it is possible that a complex substitution into a simple rule may give a useful instance.
2.3 Consistency of Notation¶
X
p 'a p ∆X q
Y
r p a
Y1
r p a
+C←X RESOLVE Y
p ∆X q r p a q r ∆X←(,'a')
+C1←X RESOLVE Y1
p ∆X q r p a q r ∆X←(,'a')
C≡C1
1
Y≡Y1
0
YY
r p a
X RESOLVE YY
DISPLAY Y Y1
.→---------------------------. .→--------------------------.
| .-----. .---------------. | | .→----. .→-------------. |
| | .→. | | .→----------. | | | | .→. | | .→----------. | |
| | |r| | | | .→. .→. | | | | | |r| | | | .→. .→. | | |
| | '-' | | | |p| |a| | | | | | '-' | | | |p| |a| | | |
| '∊----' | | '-' '-' | | | | '∊----' | | '-' '-' | | |
| | '∊----------' | | | | '∊----------' | |
| '∊--------------' | | '∊--------------' |
'∊---------------------------' '∊--------------------------'
DISPLAY YY
.→-----------------.
| .→. .→---------. |
| |r| | .→. .→. | |
| '-' | |p| |a| | |
| | '-' '-' | |
| '∊---------' |
'∊-----------------'
Exhibit 3. Effect of Variations in Notation.
In exhibit 3, we have an example from [1], p.149 (Test 2). Using the ‘pure’ logic notation in which single letters can stand for words and brackets are used to indicate application, so that ‘p(a)’ means “the property ‘p’ holds for the individual ‘a’”, X stands for:
and Y, Y1, YY are all formulations of:
so that X RESOLVE Y gives the two immediate resolutions:
using the substitution 'varX = a' to match the first term in X with the right hand side of Y and
matching the second term in X likewise
The same confusion between a one-element vector and a scalar gives rise to the difference between Y and Y1 in exhibit 3. Both do the job and get exactly the the same outcome, but the APL cannot recognise that they are the same. Conversely, it is very hard to spot the difference by eye. It is necessary to use the full DISPLAY function (risking advanced wrap-round if the clause is a long one) and then spot a single character difference in the result.
YY is another attempt to encode the same clause, and follows the rules in that it has two elements, the first containing the consequence and the second the condition. In fact, YY is just ‘disclose each of Y’ (or of Y1). Unfortunately, it doesn’t resolve with X, because the system attempts to match the predicate on its right hand side with the whole of the left hand side of X, instead of with any one individual predicate. The obvious solution is to use ‘enclose-each’ on YY to get the depth up to that of X, but the result of this is Y, not the more correct Y1. To ensure that every element, at every level, is a vector it is necessary to use ‘ravel-jot-enclose-each’.
The problems with the exact way in which statements are to be coded into APL begin at the lowest level. In Dyalog, at least, it is not possible to enclose a scalar, so that when we try to enter separate one-letter statements they tend to stick together.
This can be overcome by use of IBM’s ENCODE principle by putting an ‘a’ on the front of everything. However I find that this approach makes ordinary words unreadable.
The choice of rule is governed by the fact that the standard format (thorn) operator gives a one-element vector when applied to a one-digit number. If the unification algorithm is to recognise machine-generated values when they occur in rules, the SCRIPT function must be adapted to match, the line dealing with scalars being:
An analogous rule using ‘ravel-enclose’ ensures that non-simple scalars are turned into one-element vectors.
In general, the system as developed so far is fairly tolerant of any consistent approach to the APL representation of statements. For instance, an individual user is unlikely to use both the forms Y and Y1, while the failure of YY is precisely because of failure to ensure similarity of depth in objects of the same nature. However, I have a nasty feeling that real-life systems will be used by more than one person, so that some form of consistency check seems essential. But in fact I have found that the one that I propose below is life-saving as a diagnostic aid even in single-user conditions.
2.4 The CHECK Function¶
The essence of the approach is to make use of the fact that SCRIPT has already been constructed to obey all the rules of layout. So powerfully so, that it automatically alters the shape of anything unorthodox that it meets, returning the same data in an improved layout. This motivates the simple-minded function:
DISPLAY C
.→-----------------.
| .→---------. |
| | .→. .→. | f |
| | |p| |q| | - |
| | '-' '-' | |
| '∊---------' |
'∊-----------------'
CHECK C
0
DISPLAY ⍎SCRIPT C
.→-----------------.
| .→---------. .→. |
| | .→. .→. | |f| |
| | |p| |q| | '-' |
| | '-' '-' | |
| '∊---------' |
'∊-----------------'
CHECK Y
0
CHECK Y1
1
Y1≡⍎SCRIPT Y
1
CHECK YY
1
Exhibit 4. Use of CHECK and SCRIPT.
As seen in exhibit 4, this enables us to isolate dodgy layout. I have not made it overwrite the original. That would be to assume that an inconsistency necessarily arose from an error in shaping, which may not be the case. For instance, ‘execute-SCRIPT’ will only occasionally rescue an attempt to enter a single-element vector without precautions. It works in the case of C in exhibit 4 because there is only one such object, but an attempt to use something of the form
will never recover because SCRIPT will refuse to split the resulting word ‘pqr’. It might, after all, be a real word in somebody’s universe.
The main use of ‘execute-SCRIPT’ is to convert more complex objects into their proper form. For instance, it will detect that it is Y rather than Y1 that is imperfect in exhibits 3 and 4, and then convert Y into Y1 without the user having to worry about the exact location of the error. Conversely, SCRIPT was written, or evolved, mainly to do this second job. It is possible that a much simpler function might be adequate for its original purpose as one of the Unification algorithms.
There is no way in which CHECK can spot the error in YY. That is because the inconsistency is with the coding of X, and not a failure to meet some more general principle. If CHECK also ‘knew’ that the object to be checked was a clause, then it might be able to run a test on the depth of the object. However, in a propositional context (with no variables or individuals involved) the depth of each half of a clause can legitimately be 3, as in YY. It is only if there is at least one variable or individual mentioned somewhere in the database that it is certain that at least one half-clause must have a depth of at least 4. The null statement, which makes up half of every factual statement, has, of course, much lower depth. All of this makes a depth check very far from simple even to visualise.
Another ‘invisible’ problem is the possibility of different standards for the empty statement. The logic functions will accept many formulations: the empty character vector; the enclosure of it; a vector containing it. It will sometimes fail even to reject inconsistent versions, although the form of the resolvant is then unpredictable. The null statement ought to be standardised as the empty character vector, which motivates the presence in SCRIPT of the first element of
[3] →(''≡DECON A)/NULL ⋄ →(1=≡A)/VEC ⋄ →(0=≡A)/SCAL ⋄ →(2≤⍴A)/REC ⋄ →ENC
which branches to
[8] NULL:Z←Q,Q ⋄ →0
Line 6 of SCRIPT has a similar purpose:
It is difficult to spot the difference between the following two statements by eye alone, but the first is probably a fatal error:
+A1←'function' 'word1 word2'
function word1 word2
+A2←'function' 'word1' 'word2'
function word1 word2
CHECK A1 A2
0 1
CHECK detects this because SCRIPT throws out blanks characters within vectors. A user who needs embedded blanks can easily edit SCRIPT to allow them.
Monitoring of cpu time indicates that all this elaboration does not add to the time needed to do logic processing. The substitutions that are SCRIPTed by logic functions are very simple vectors and most lines of SCRIPT are never accessed. SCRIPTing an entire database is something that will only be done interactively and may involve a perceptible delay. It is extensive recursion that is expensive in terms of time.
3. Recovering Logical Form¶
Even when an expression has been checked for formal consistency, it often far from obvious what it actually says. The DISPLAY function is often needed, and takes up far too much of the screen. Even then, it may not be clear whether the variables are quantified by ‘there exists’ or by ‘for all’. For instance, the expression
really means
In other words, I can choose any X and Y that I like, provided I can find some Z (by searching and unification) that fits into the right hand side.
Formal logic uses the standard symbols for for all and there exists, but they are not available in APL, being the letters A and E printed upside- down and reversed. Other symbols are also used, for instance the variable on its own in brackets may mean for all. However, the easiest thing in APL is to use the intersection sign for for all and the union sign for there exists. The connection is a standard one in model theory and in set theory, and should not be in any way confusing. Thus
reads
and means that any (arbitrary) object X has at least one inverse (which may or may not be correct, depending on context; it is simply an assertion).
As well as putting in these quantifiers, we also have to choose a standard form in which to represent clauses. We apply the following rules: facts are unadorned; negatives have a not sign in front of them (the tilde); two-element clauses are treated as implications rather than as disjunctions of positive and negative elements. We try to minimise the number of brackets, but not at the risk of ambiguity.
First of all, we treat those cases in which the type of expression – database, clause, list, predicate – is taken to be known. Life becomes much harder once we ask the machine to work out the logical type for us.
3.1 Expressions of KnowKnowne¶
The underlying functions, whose use is shown in exhibit 5, are meant to be used inside a CONSTRUE cover-function that will check the object for correctness and, if not told by a parameter, make a guess at its type. The level-1 function for databases is very simple, merely laying things out for readability and getting rid of the ‘del’s in the variables.
The level-2 function, for clauses, is much more complicated, since it needs to discover, without external prompting, what variables are present and then decide
CONSTRUE1 DATABASE
by(table, window)
on(box, table)
(∩Z)(∩Y)(by(Z, Y) ← (∪X)(by(X, Y) ∧ on(Z, X)))
CONSTRUE2 3⊃DATABASE
(∩∆Z)(∩∆Y)(by(∆Z, ∆Y) ← (∪∆X)(by(∆X, ∆Y) ∧ on(∆Z, ∆X)))
'∧' CONSTRUE3 2⊃3⊃DATABASE
(by(∆X, ∆Y) ∧ on(∆Z, ∆X))
CONSTRUE4 ⊃⊃3⊃DATABASE
by(∆Z, ∆Y)
Exhibit 5. Use of CONSTRUE Sub-Functions
whether they belong to one or other side, or to the whole. Most of the work, however, simply consists of editing brackets in and out as needed.
∇ R←CONSTRUE2 RA;T;V;LH;RH;F ⍝Logical form of clause
[1] T V←DELDREDGE RA ⍝Find the variables on each side
[2] LH RH←'∨∧'CONSTRUE3 RA ⍝Find the logical form of each side
[3] F←T∩V ⋄ R←T~V ⋄ V←V~T ⋄ T←R⍝F is the universals on both sides
[4] ⍝V is the existentials on the right, T is left hand universals
[5] ⍎(0≠⍴F)/'F←⊃,/,(⊂''(∩''),F,[1.1]'')'' '⍝Format universals in F
[6] ⍎(0≠⍴T)/'T←⊃,/,(⊂''(∩''),T,[1.1]'')'' '⍝Format universals in T
[7] ⍎(0≠⍴V)/'V←⊃,/,(⊂''(∪''),V,[1.1]'')'' '⍝Format existentials in V
[8] →(RH≡'')/fact ⋄ →(LH≡'')/neg ⋄ →imp ⍝Detect type of clause
[9] fact:⍎((0=⍴T)∨~'∨'∊LH)/'LH←1↓¯1↓LH ' ⍝Delete unwanted brackets
[10] R←T,LH ⋄ →0 ⍝ add universal quantifier(s)
[11] neg:⍎(~'∧'∊RH)/'RH←1↓¯1↓RH ' ⍝Delete unwanted brackets
[12] R←'~',V,RH ⋄ →0 ⍝Construct negative statement
[13] imp:⍎(~'∨'∊LH)/'LH←1↓¯1↓LH ' ⍝Delete unwanted brackets
[14] ⍎(~'∧'∊RH)/'RH←1↓¯1↓RH ' ⍝Delete unwanted brackets
[15] ⍎(0=⍴F)/'R←T,LH,'' ← '',V,RH ⋄ →0'⍝If no common variables
[16] R←F,'(',T,LH,' ← ',V,RH,')' ⍝Construct full-blown implication
The auxiliary function DELDREDGE for finding variables is discussed below. If the expression’s notation is wrong (especially the wrong null clause) CONSTRUE2 misfires, but usually comes back with a comprehensible Prolog- like expression.
Below this level, variables are treated simply as strings, without bothering about quantification. The level-3 function, for lists of predicates, takes external prompting as to what symbol shall separate the elements of the list.
∇ R←LA CONSTRUE3 RA
⍝ LA is separator, RA is list of predicates
[1] ⍎(0=⍴RA)/' R←'''' ⋄ →0' ⍝Catch the null string
[2] RA←CONSTRUE4 RA ⍝ Get logical form of each predicate
[3] R←'(',(¯3↓⊃,/,RA,[1.1]⊂' ',LA,' '),')' ⍝ Result will have brackets
The final function deals with predicates. The standard form of a predicate is: relation, term1, term2 etc., where any term may be of the form function, term11, term12,… This means that CONSTRUE4 has to be recursive. On the other hand, an expression at this level may be a proposition, an assertion that does not have a sub-structure. In this case, a ‘predicate’ may be of depth 1 (and not, in fact, a proper predicate at all).
∇ R←CONSTRUE4 RA;T⍝ Logical form of predicates
[1] ⍎(1=≡RA)/'R←RA~'' '' ⋄ →0'⍝ Leave simple strings alone
[2] R←CONSTRUE4 RA ⍝ Construct component parts
[3] T←¯2↓⊃,/,(T←1↓R),[1.1]⊂', '⍝ Get inside terms separated by commas
[4] R←(⊃R),'(',T,')' ⍝ Put predicate in front, with brackets
Finally, we have the auxiliary functions from CONSTRUE2, the idea being that DREDGE1 dives down into the structure to look for variables and passes them back up to DELDREDGE.
∇ R←DELDREDGE A ⍝ Look for variables in A
[1] R←'' ⍝ Initialise list for variables
[2] DREDGE1 A ⍝ Search A. Variables are passed to R
[3] R←∪R~⊂'' ⍝ Delete duplicates and header
∇ DREDGE1 A ⍝ Pass variables back to R in DREDGE
[1] ⍎(1≥|≡A)/'R,←⊂(''∆''=⊃A)/A ⋄ →0' ⍝ If A simple & variable, keep it
[2] DREDGE1 A ⍝ If complex, look one stage lower
3.2 Guessing the Type¶
CONSTRUE RTEST1
(p ∨ q ∨ r) ← s
q ← (p ∧ t)
≡RTEST1
4
CONSTRUE RTEST7
(∩X)(∩Y)(p(X, f(a)) ∨ p(X, f(Y)) ∨ q(Y))
~(∪Z)(p(Z, f(a)) ∧ q(Z))
≡RTEST7
¯6
≡X
¯5
CONSTRUE X
(∩∆X)(∩∆Y)(p(∆X, f(a)) ∨ p(∆X, f(∆Y)) ∨ q(∆Y))
CONSTRUE ⊃X
(p(∆X, f(a)) p(∆X, f(∆Y)) q(∆Y))
CONSTRUE ⊃⊃X
p(∆X, f(a))
CONSTRUE ⊃⊃⊃X
p
Exhibit 6. CONSTRUE in action.
It is much more difficult to write a function that will recognise the type of assertion that it is dealing with. In fact, the result is long and imperfect. All we can guarantee is that it works on all the test items available, as in exhibit 6, but it is essentially a function that guesses. The reader may recognise examples from [1] pp148-50.
∇ R←(LA)CONSTRUE RA;L;P ⍝ Logical version of APL data
[1] RA←⍎SCRIPT RA ⍝ Make certain that the notation is reasonable
[2] →(2≠⎕NC'LA')/guess ⍝ If level not specified by LA
[3] branch:⍎(LA=3)/'R←'' '' CONSTRUE3 RA ⋄ →0' ⍝ Level 3 needs left arg.
[4] R←⍎'CONSTRUE',(1 0⍕LA),' RA' ⋄ →0 ⍝ Other levels as needed
[5] guess:⍝ Rough heuristics to estimate the type of object
[6] ⍎(1=≡RA)/'LA←4 ⋄ → branch' ⍝Only predicates can have depth 1
[7] L←'∆'∊DECON RA ⋄ P←⍳4 ⍝L predicate logic, P possibilities
[8] ⍎(∨/(⊂'')≡¨ RA)/'LA←2 ⋄ → branch' ⍝Only clauses contain <null>
[9] ⍎(∨/'∆'∊ RA)/'LA←4 ⋄ → branch' ⍝Only predicates contain ∆
[10] ⍎((⊃∨/2≠⍴¨ RA)∨(L+4)>|≡RA)/'P←P~1'⍝Necessary conditions for database
[11] ⍎((2≠⍴RA)∨(L+3)>|≡RA)/'P←P~2' ⍝Necessary conditions for clause
[12] ⍎((L+2)>|≡RA)/'P←P~3' ⍝Necessary conditions for list
[13] LA←⌊/P ⋄ →branch ⍝Make guess upwards
If it is given a left argument, then all it does is run the appropriate sub-function on a consistency-checked version of the object. The extra material is its way of guessing. It uses the following principles:
- Simple vectors only appear at the lowest level.
- The null assertion can only appear in a clause.
- A variable must be inside a predicate.
- A database must be of depth at least 5 (or 4 if propositional) and each of its elements must have exactly two items.
- A clause must contain exactly two items and be of depth at least 4 (or 3 if propositional).
- A list must be of depth at least 3 (or 2 if propositional).
- If in doubt, assume maximal complexity.
We remark that this function shows the problem attached to trying to use contrapositives, arguments of the form:
Of course, they could be added to a logical database as positive implications, by turning them round, but then we have the problem of looking for a unique type for our object. Prolog might find a possible value, but how to be sure that it is unique?
3.3 The Need for Consistency¶
The logical algorithms themselves are very tolerant of variations in notation. For instance, exhibit 1 uses data lifted directly from [1], section 4.5 at p.125, and it does exactly what it’s supposed to. However, when we come to construe the bits, we find:
CONSTRUE DATA2
john(loves, food)
jane(is, female)
john(loves, jane)
CONSTRUE GO2
~(∪∆X)(john(loves, ∆X) ∧ ∆X(is, female))
It is, of course, nice to find that CONSTRUE has still got the structure dead right, but it is clear that it is far less tolerant than PROLOG is. Equally, it would clearly be fatal to mix DATA2 with anything entered according to the standard notation. I suspect that in any real-life situation with more than one user, or even with more than one development programmer, fatal clashes in notation would be very common. It is remarkably hard to be consistent even when on your own, indeed the functions in this section were developed in exactly that situation just to find out what was really going on.
The obvious thing to do is to develop a front-end function that will convert any sentence in formal logic into its proper standard form in APL. But that is another story. It will be far from easy in the general case. Even to take in a simple contrapositive, it must recognise that it will need careful handling and considerable adaptation.
References
- Brown et al., ‘Algorithms for Artificial Intelligence in APL2’ in APL86 Tutorials, ed Camacho, London 1986, pp 87 – 150.
- Charniak, E. and McDermott, D., Introduction to Artificial Intelligence, Addison Wesley, 1985.
- Sterling, L. and Shapiro, E, The Art of Prolog, M.I.T., 1986.
Appendix: The Remaining Functions.¶
∇ Z←EVAL R ⍝evaluate logic variables in R
[1] Z←R ⍝initialize result
[2] →(~'∆'≡⊃R)/0 ⍝exit if not a logic variable
[3] →(2≠⎕NC R)/0 ⍝exit if no value in variables
[4] Z←EVAL DEPTH1⍎R ⍝replace variables with values
∇
∇ Z←SPLITGOAL G
[1] ⍝ G is a single possibly conjunctive goal, Z a vector of simple goals
[2] Z←(⊂⊂''), ⊂ ⊂ 2⊃G
∇
∇ Z←VRENAME R
[1] VCOUNT←VCOUNT+1 ⋄ Z←VRENAME1 DEPTH1 R
∇
∇ Z←VRENAME1 R
[1] Z←R ⋄ →('∆'≠⊃R)/0 ⋄ Z←R,(⍕VCOUNT)
∇
∇ Z←(FN DEPTH1)B
[1] →((0>≡B)∨(1<≡B))/rec
[2] Z←FN B ⋄ →0
[3] rec:Z←FN DEPTH1 B
∇
∇ Z←L(F UNTIL THIS)R;I ⍝EACH THAT QUITS ON TRUE/FALSE
[1] →(0≠⍴⍴L)/L1 ⍝branch L not scalar
[2] L←(⍴R)⍴L ⍝extend scalar left
[3] L1:→(0≠⍴⍴R)/L2 ⍝branch R not scalar
[4] R←(⍴L)⍴R ⍝extend scalar right
[5] L2:Z←I←0 ⍝initialize result and counter
[6] LP:→(I≥⍴R)/0 ⍝exit when counter exceeds length
[7] →(THIS≡Z←(⊃I↓L)F(⊃I↓R))/0 ⍝exit when result THIS
[8] I←I+1 ⋄ →LP ⍝continue
∇