Is "almost pure" Prolog expressive?

Question

@false commented earlier:

Yes, you can implement a Turing machine without dif/2. But you cannot even implement intersection or similar predicates.

Suppose we do extend pure Prolog (Horn FOL + CWA + UNA) with call/N, dif/2, and (=)/3, to be used in if_/3, would there still be gaps in its expressiveness, i.e. things that are trivial to define in, say, Scheme, but are much harder to state in such extended (almost pure) Prolog?

In particular, does such a Prolog allow manipulating Prolog lists about as conveniently as Scheme allows manipulating Scheme lists?

---

Edit: Assume Scheme without mutation, macros, continuations, laziness, streams, numbers, strings, vectors or characters. Just symbols, booleans and lists (trees).

Answer 1

Just symbols and lists (trees).

You also need Scheme booleans #t and #f if you don't want to encode everything in pure lambda calculus. You're also excluding function values, which thankfully makes this answer simpler. Although you will have to allow the special case of top-level (define name (lambda ...)) forms. (Anything else, including expanded let expressions, can be defunctionalized.)

So, my claim is: No, there is no gap in expressiveness between this vague Scheme subset and pure Prolog as you defined it. My argument (it's not a proof) is constructive, by translating Scheme code for list intersection from this answer to Prolog.

Specifically, this:

(define intersect
  (lambda (set1 set2)
    (cond
      ((null? set1)(quote ()))
      ((member? (car set1) set2)
       (cons (car set1)
             (intersect (cdr set1) set2)))
      (else (intersect (cdr set1) set2)))))

becomes:

intersect(Set1, Set2, Result) :-
    cond([
        ['null?'(Set1), result([])],
        [cond_1(Set1, Set2), body_1(Set1, Set2)],
        [else, body_2(Set1, Set2)]], Result).

cond_1(Set1, Set2, Result) :-
    car(Set1, Car),
    'member?'(Car, Set2, Result).

body_1(Set1, Set2, Result) :-
    car(Set1, Car),
    cdr(Set1, Cdr),
    intersect(Cdr, Set2, PartialIntersection),
    cons(Car, PartialIntersection, Result).

body_2(Set1, Set2, Result) :-
    cdr(Set1, Cdr),
    intersect(Cdr, Set2, Result).

and this:

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (equal? (car lat) a) 
                (member? a (cdr lat)))))))

becomes:

'member?'(A, Lat, Result) :-
    cond([
        ['null?'(Lat), result('#f')],
        [else, or([or_case_1(Lat, A),
                   or_case_2(Lat, A)])]], Result).

or_case_1(Lat, A, Result) :-
    car(Lat, Car),
    'equal?'(Car, A, Result).

or_case_2(Lat, A, Result) :-
    cdr(Lat, Cdr),
    'member?'(A, Cdr, Result).

Note that nested expressions need to be un-nested, and in all but the most trivial cases this is simplest by defining auxiliary Prolog predicates. This doesn't increase code size non-linearly.

These definitions use the following translations of standard Scheme constructs:

'equal?'(X, Y, '#t') :-
    =(X, Y, true).
'equal?'(X, Y, '#f') :-
    =(X, Y, false).

'null?'(Value, Result) :-
    'equal?'(Value, [], Result).

car([Car | _Cdr], Car).

cdr([_Car | Cdr], Cdr).

cons(Car, Cdr, [Car | Cdr]).

or([], '#f').
or([Goal | Goals], Result) :-
    if(Goal,
       Result = '#t',
       or(Goals, Result)).

cond([], _Result) :-
    throw(error(cond_without_else, _)).
cond([[Condition, Body] | OtherCases], Result) :-
    if(Condition,
       call(Body, Result),
       cond(OtherCases, Result)).

Some support stuff for getting a simple value out of a cond case body, and for the else case:

result(Result, Result).

else('#t').

And this is all the internally-impure, externally-pure Prolog support you need:

if(Goal, True, False) :-
    call(Goal, Truth),
    (   Truth == '#t' -> call(True)
    ;   Truth == '#f' -> call(False)
    ;   throw(error(type_or_instantiation_error(Truth), _)) ).

I called this if/3 instead of if_/3 because it's not exactly the "standard" if_/3: It expects the condition to evaluate to a Scheme truth value rather than true or false. Feel free to massage it into "standard" form. Edit: There are several "good enough" ways to define a (=)/3 that will work in the context of this answer, but to avoid further bikeshedding, just use the definition from https://stackoverflow.com/a/27358600/4391743.

Tests:

?- 'member?'(a, [x, y, a, c], Result).
Result = '#t' ;
false.

?- intersect([a, b, c, d], [c, d, e, f], Result).
Result = [c, d] ;
false.

Answer 2

Just symbol/1 and dif/2 are sufficient extensions of logically pure Prolog.

Proof:

This answer contains an evaluator for Scheme expressions, evil/2. It understands lambda and quote, and can be easily extended to handle built-in list procedures like list, car, cdr, etc. Aside from pure (Horn) Prolog, it uses only symbol/1 and dif/2. While it is an interpreter and will run slowly, its existence shows that the same list operations done by Scheme can be done in such almost pure Prolog. (I think symbol/1 wouldn't be needed either, if Scheme symbols were translated into symb(prolog_atom) instead of directly into prolog_symbol)

---

Edit

This extends evil/2 to handle if, #t and #f (represented by true and false):

evil(true, _, true).
evil(false, _, false).

evil([if, E1, E2, E3], Env, Val) :-
    evil(E1, Env, false),
    symbols(E2),
    evil(E3, Env, Val).

evil([if, E1, E2, E3], Env, Val) :-
    evil(E1, Env, V),
    dif(V, false),
    symbols(E3),
    evil(E2, Env, Val).

This extends evil/2 to handle equalp. It's even more powerful than Scheme's eq* in that it will equate some closures too:

evil([equalp, E1, E2], Env, true) :-
    evil(E1, Env, V),
    evil(E2, Env, V).

evil([equalp, E1, E2], Env, false) :-
    evil(E1, Env, V1),
    evil(E2, Env, V2),
    dif(V1, V2).

Answer 3

If you take a pure Scheme. Possibly pure Prolog is enough. Pure Scheme would be lambda expressions with a certain strict call-by-value evaluation strategy. So we could implement pure Scheme as follows in Prolog, drawing on deBruijn indexes:

eval(P*Q, H) :- !,
   eval(P, R),
   eval(Q, S),
   reduce(R, S, H).
eval(X, X).

reduce(b(R), S, J) :- !,
   subst(R, 0, S, H),
   eval(H, J).
reduce(R, S, R*S).

If you change the respresentation a little bit, I guess you can get rid of the cuts. And maybe do the necessary arithmetic via Peano axioms. Eh voila you got pure Scheme in pure Prolog.

Here is an example query, SUCC and ZERO are from here:

?- ZERO = b(b(0)), SUCC = b(b(b(1*(2*1*0)))), 
   eval(SUCC*(SUCC*ZERO)*f*a, X).
ZERO = b(b(0)),
SUCC = b(b(b(1*(2*1*0)))),
X = f*(f*a)