Арифметический расчет в Прологе по спискам

Question

В настоящее время мы работаем над реализацией предиката сокращения, которое должно взять список L, двоичную функцию F, которая работает с элементами L и имеет нейтральный элемент N и отображает их в число E, полученное путем применения F к элементы L рекурсивно.

Вот наш Код на данный момент:

reduce([],F,NEUTRAL,EE).

reduce([H|T],F,NEUTRAL,EE) :-
    Goal =.. [F, H, NEUTRAL, EE],
    call(Goal),
    reduce(T,F,NEUTRAL,EE).

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.

Проблема заключается в том, чтобы: ?- reduce([], add, 0, R). мы просто получаем логическое значение (в данном случае true), для других возвращается ошибка, которая говорит нам о том, что наши аргументы не созданы должным образом. То, к чему мы на самом деле стремимся, это как Ответ R = 0, (для примера, приведенного выше).

Надеюсь, что вы можете помочь нам, пожалуйста, не будьте слишком сложны, так как мы начинающие Пролог;)

Answer 1

Исходя из приведенных выше комментариев и того факта, что вы все еще новичок в Прологе, я постараюсь объяснить некоторые вещи, которые могут быть не очень понятными:

What are variables in Prolog and what is instantiation ?

В Прологе переменные - это все, что начинается с заглавных букв и анонимных переменных. _ (просто подчеркивание определяет анонимную переменную, которая является переменной без имени). Переменные в Прологе означает, что они могут представлять что-либо список, строку, атом (... что угодно), когда вы используете новую переменную, она не создается, что означает, что она может представлять что угодно, но сейчас она действительно представляет - она ​​не имеет не быть bind со списком, атомом... Когда вы хотите создать экземпляр переменной, вы можете сделать это:

• с помощью объединения =/2 например X = 2 унифицирует-создает переменную X с номером 2.
• или с помощью is/2 только для выражений типа X is 2 делает то же, что и выше.

Очень важно, что когда создается экземпляр переменной в Прологе, мы знаем, что она представляет, и не можем, например, изменить X =2, X = 3 will fail!! так как мы знаем, что X связывается с 2, и мы пытаемся восстановить с 3, что не удается.

What is =/2, is/2, and what's the difference between these two prediactes ??

• is/2: он возвращает результат арифметического выражения в необработанную переменную. Это означает, что вы можете использовать его так: X is 2, or X is mod(Z,Y) но важно отметить, что все, что находится в expression MUST be instantiated если это переменная, как Y и Z ранее. Если выражение не было создано, вы получите instantiation error как в твоем случае. Даже простые вещи, как 2 is X+1 потерпит неудачу с ошибкой создания экземпляра, если X не был создан, поэтому не ожидайте, что с помощью / 2 вернет что-то вроде X=1 в предыдущем случае, который является очевидным ответом (но не уникальным, поэтому он будет противоречивым!). Также арифметическое выражение означает, что вы не можете использовать что-то вроде X is [], чтобы объединить X с пустым списком, это, конечно, не получится, поэтому для этого используйте =/2, описано ниже.

• =/2: Используется для объединения переменной (или вообще термина) с другим термином. Например, вы можете использовать его так: X = 2 объединить X с номером 2, или X = [1, 2] объединить X со списком или X = 1 + 2 который не даст 3, а только термин 1 + 2, последние два примера, я думаю, ясно показывают разницу с is/2,

But then how could we use arithmetic expressions like is/2 but more relational ?

Ответ здесь library CLPFD (как рекомендует @lurker в комментариях) все, что вам нужно сделать, это разместить :- use_module(library(clpfd)). в вашем файле и используйте оператор #= вместо is/2, Теперь вы можете попробовать X #= 2, который будет создавать экземпляр переменной X с номером 2 или даже 2 #= 1 + X и теперь вы не получаете ошибку инстанцирования, но вы получаете ответ X = 1 Таким образом, вы можете видеть, что теперь это гораздо более реляционный.

Теперь к вопросу...

Я согласен с @Boris нейтральный не должен быть перенесен через рекурсию, но объявлен с функцией. Хотя я постараюсь не отставать от вашей попытки ответа:

Прежде всего, когда я пытаюсь просмотреть файл с вашим кодом в swi prolog, я получаю:

Warning: /Users/Desktop/reduce.pl:1:
    Singleton variables: [F,NEUTRAL,EE]

Это говорит о том, что переменные F,Neutral,EE однозначны в этом пункте:

reduce([],F,NEUTRAL,EE). 

Как вы можете видеть, вы не используете в этом пункте, например, переменную F.

На мой взгляд, предикат Reduce должен завершиться ошибкой с пустым списком, поскольку вы не можете выполнять какие-либо операции с нейтральным элементом и функцией, которая принимает два параметра. Поэтому в качестве базового варианта я бы определил использование списка только с одним элементом:

reduce([H],F,NEUTRAL,EE):-
        Goal =.. [F, H, NEUTRAL, EE], 
        call(Goal).

Затем, как объяснено выше правила, такие как

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

вызовет ошибку инстанцирования, так как в EE есть var, и вы не можете использовать его в is/2, но даже если он был инстанцирован, вы также не можете использовать его, потому что, как объяснено EE is EE + whatever не будет работать, потому что you try to reinstantiate a variable..!!

Чтобы исправить это, я бы попытался использовать другую переменную для следующей рекурсии, а затем вычислить результат следующим образом:

 reduce([H],F,NEUTRAL,EE):-
     Goal =.. [F, H, NEUTRAL, EE], 
     call(Goal).
  reduce([H|T],F,NEUTRAL,EE) :-
     reduce(T,F,NEUTRAL,EE1),
     Goal =.. [F, H, EE1, EE],
     call(Goal).

(Здесь добавлена ​​новая переменная EE1, выполнить рекурсивный вызов и затем вычислить результат на основе результата EE1, который будет возвращен из рекурсивного вызова.)

Теперь давайте проверим это:

?- reduce([1,2,3,4],add,0,L).
L = 10 ;
false.

?- reduce([1,2,3,4],mult,1,L).
L = 24 ;
false.

Еще одна вещь, когда он дал вам результат L=10 нажав ";" мы запрашиваем дополнительные ответы и возвращаем ложные, поскольку возможных ответов нет. Ложные или истинные вещи - это просто способ, которым верхний уровень Пролога сообщает вам, если предикат успешен или неуспешен. Например:

?- reduce([1,2,3,4],mult,1,24).
true ;
false.

Это говорит о том, что вышеприведенное верно, и когда мы спрашиваем, есть ли другие способы, чтобы это могло быть правдой, он возвращает ложь... Так вот, в конце концов, Пролог, кажется, не так уж плох:) (согласно вашему описанию)).
В качестве упражнения вы можете попытаться написать то же самое, используя CLPFD, чтобы быть более реляционным и иметь возможность отвечать на такие запросы: reduce(L,mult,1,24). и, может быть, идея @ Бориса о том, чтобы не переносить нейтраль до конца через рекурсию.

---

РЕДАКТИРОВАТЬ

В соответствии с предложением @false и полезными комментариями я напишу второй способ, используя call/N, который явно лучше (см. Комментарии...):

reduce([H],F,NEUTRAL,EE):-
        call(F, H, NEUTRAL, EE).
reduce([H|T],F,NEUTRAL,EE) :-
        reduce(T,F,NEUTRAL,EE1),
        call(F, H, EE1, EE).

Answer 2

Вам нужен нейтральный элемент, чтобы закончить рекурсию. Вам это не нужно на каждом шагу. Я бы почти сказал, что нейтральный элемент принадлежит оператору, а не редуктору. Что-то вроде этого:

operation_neutral(add, 0).
operation_neutral(mult, 1).

Тогда ваш reduce может выглядеть так:

reduce([], Op, Result) :- operation_neutral(Op, Result).
reduce([X|Xs], Op, Result) :-
    reduce(Xs, Op, R0),
    call(Op, X, R0, Result).

Но давайте пока будем проще и сделаем так, как предложено в вопросе. Нейтральный элемент нужен только в том случае, если список операндов пуст, чтобы установить свой результат:

reduce([], _, N, N).

В противном случае перейдите в рекурсию и затем примените операцию к результату (и вы можете использовать call непосредственно):

reduce([X|Xs], Op, N, R) :-
    reduce(Xs, Op, N, R0),
    call(Op, X, R0, R).

Вы можете увидеть здесь, как использовать reduce/4 например с append/3,

Ты видишь N внутри call? Я не вижу этого, и это не принадлежит там.

Для полноты, два оператора:

add(X, Y, R) :- R is X+Y.
mult(X, Y, R) :- R is X*Y.

Также нет упоминания о нейтральном элементе.

---

Кстати, то, что вы назвали "уменьшить", также называется "сворачиванием" по списку. Вы могли бы определить свой reduce/3 с точки зрения foldl как это:

reduce(List, Op, Result) :-
    operation_neutral(Op, N),
    foldl(Op, List, N, Result).

Рекурсия и call оба происходят внутри foldlтебе не нужно reduce/4 совсем.

---

Как бы вы решили это на процедурном языке? Используя псевдокод с C-подобным синтаксисом и предполагая, что у нас есть некоторая поддержка обобщений, это может выглядеть так:

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    return reduce(operands, op, 0);
}

template <typename A, typename Op>
A reduce(A[] operands, Op op, int n) {
    if (n == operands.length) return neutral<Op>();
    return op(operands[n], reduce(operands, op, n+1));
}

(очевидно, если бы это был действительно C++, мы бы использовали итераторы, а не индекс...)

Это ничем не отличается от версии Пролога. И если вы сделали это так же, как foldl выше, это, вероятно, будет выглядеть так:

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    A x = neutral<Op>();
    for (int n = 0; n < operands.length; ++n)
        x = op(x, operands[n]);
    return x;
}

Опять же, нет упоминания о нейтральном элементе внутри цикла, ни в вызове op(),

Answer 3

Я надеюсь, что этот частичный ответ не слишком не по теме, поэтому лишает его возможности участвовать в этом обсуждении.

Относительно оператора OP "к тем же типовым запросам, как?- Reduce([], add, 0, R). Мы просто получаем логическое значение (в данном случае true)", важно иметь хорошую интерпретацию того, что вы подразумеваете под "правда". По моему мнению, НЕ уместно считать, что "возвращаемое значение", которое вы определили (.ie (неявное) возвращаемое значение), имеет тип "логический". Это потому, что с булевым типом >>"false" означает противоположное истинному<<. В прологе в этом конкретном контексте (.ie в отношении (неявного) возвращаемого значения) применение ожидания логического типа не применяется, потому что в случае этого типа и не похожего на логический тип --- >>"false" означает нечто иное, чем "истинно"<<.

Answer 4

Как упоминалось в предыдущих ответах, вы действительно хотите устранить свою зависимость от call/99,

Вот кое-что, чтобы вы начали. Это ваш оригинальный полностью нефункциональный код с другим синтаксисом. Я имею в виду, что я надеюсь представить syntaz alternativ, который может быть полезен для вас, но сломанные семантики оригинала остаются неизменными.

  % [ reduce , VECTOR , FUNCTION , NEUTRAL , EE ] 

  :- [library(clpfd)] .

  [reduce , [] , F , NEUTRAL , EE] :- ( true ) .

  [reduce , [N|NN] , F , NEUTRAL , EE]
  :-
  (
      [F , N , NEUTRAL , EE] ,
      [reduce , NN , Z , NEUTRAL , EE] 
  )
  .

  [add , N , NEUTRAL , EE] :- ( EE #= EE + N + NEUTRAL ) .

  [mult , N , NEUTRAL , EE] :- ( EE #= N * EE * NEUTRAL ) .

Вот оригинал для удобного сравнения...

  %

  reduce([],F,NEUTRAL,EE).

  reduce([H|T],F,NEUTRAL,EE) :-
      Goal =.. [F, H, NEUTRAL, EE],
      call(Goal),
      reduce(T,F,NEUTRAL,EE).

  add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

  mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.