programming languages - 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.