Выразителен ли почти чистый Пролог?

Просто символы и списки (деревья).

Вам также потребуются логические значения схемы #t и #f, если вы не хотите кодировать все в чистом лямбда-исчислении. Вы также исключаете значения функций, что, к счастью, упрощает этот ответ. Хотя вам придется разрешить особый случай (define name (lambda ...)) форм верхнего уровня. (Все остальное, включая расширенные let выражения, можно отключить.)

Итак, я утверждаю: Нет, нет разрыва в выразительности между этим расплывчатым подмножеством схемы и чистым Прологом, как вы его определили. Мой аргумент (это не доказательство) является конструктивным, поскольку я переведу код схемы для пересечения списков из этого ответа в Prolog.

В частности, это:

(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)))))

становится:

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).

и это:

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

становится:

'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).

Обратите внимание, что вложенные выражения не должны быть вложенными, и во всех случаях, кроме самых тривиальных, это проще всего сделать, задав вспомогательные предикаты Пролога. Это не увеличивает размер кода нелинейно.

В этих определениях используются следующие переводы стандартных конструкций схемы:

'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)).

Некоторые вспомогательные материалы для получения простого значения из тела cond case и для else case:

result(Result, Result).

else('#t').

И это вся необходимая вам внутренне нечистая и внешне чистая поддержка Prolog:

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

Я назвал это if/3 вместо if_/3, потому что это не совсем стандартный if_/3: он ожидает, что условие будет оцениваться как значение истинности схемы, а не true или false. Не стесняйтесь массировать его до стандартной формы. Изменить: есть несколько достаточно хороших способов определить (=)/3, который будет работать в контексте этого ответа, но, чтобы избежать дальнейшего сбрасывания велосипедов, просто используйте определение из https://stackoverflow.com/a/27358600/4391743.

Тесты:

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

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

Если взять чистую схему. Возможно, достаточно чистого Пролога. Чистая схема - это лямбда-выражения с определенной строгой стратегией оценки по значению. Таким образом, мы могли бы реализовать чистую схему в Прологе следующим образом, используя индексы deBruijn:

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).

Если немного изменить репрезентацию, думаю, от порезов можно избавиться. И, возможно, сделаем необходимую арифметику с помощью аксиом Пеано. Эх, вуаля, вы получили чистую схему на чистом Прологе.

Вот пример запроса, SUCC и ZERO взяты из здесь :

?- 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)

Просто symbol/1 и dif/2 являются достаточными расширениями логически чистого Prolog.

Доказательство:

Этот ответ содержит средство оценки для выражений схемы, evil/2. Он понимает lambda и quote и может быть легко расширен для обработки встроенных процедур списков, таких как list, car, cdr и т. Д. Помимо чистого (Horn) Prolog, он использует только symbol/1 и dif/2. Хотя это интерпретатор и будет работать медленно, его существование показывает, что те же операции со списком, которые выполняет Scheme, можно выполнять в таком почти чистом Прологе. (Думаю, symbol/1 тоже не понадобился бы, если бы символы схемы были переведены в symb(prolog_atom), а не прямо в prolog_symbol)

Изменить

Это расширяет evil/2 для обработки if, #t и #f (представленных true и 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).

Это расширяет evil/2 на обработку equalp. Он даже более мощный, чем Scheme eq*, в том, что он также приравнивает некоторые замыкания:

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).