Как рекурсивные функции работают в Prolog?

Question

Я читал рекурсивную функцию в прологе, которая возвращает сумму всех элементов в списке, как показано ниже:

sum([ ], 0). 
sum([Elem | Tail], S):- sum(Tail, S1), 
         S is S1 + Elem. 

Я не могу понять две проблемы:

1: В левой части ": -" у нас есть Цель. Это означает, что все вычисления будут выполнены в правой части «: -», а затем мы можем использовать Цель как обычная функция. Это означает, что мы приводим наши аргументы и переменные, чтобы результат был нанесен на них, а правильная сторона отвечает за вычисление.

Но в этом коде Цель, сама вычисляет голову и хвост. Я имею в виду в моем уме код должен быть, как это (однако он не работает!):

sum(Tail, S1):-sum([Elem | Tail], S),........ 

Поскольку цель должна дать аргументы и правая сторона отвечает за вычисление.

2: Я не могу понять, как этот код работает шаг за шагом. может ли кто-нибудь дать мне очень простой пример, например, как он вычисляет сумму [1,2,3]?

Answer 1

В левой части :- у вас есть глава правила ; с правой стороны у вас есть тело правила. Когда отсутствует сторона и тело :-, правило становится фактом.

Неверно сказать, что расчет выполняется только в теле, поскольку процесс принятия решений Prolog работает с обеими сторонами правила. Концепция, в которой главой правила играет важную роль, является объединение , процесс, посредством которого язык решает, какие положения применимы к запросу, и делает проверки и временные назначения переменных в заголовке правила частям запроса («унифицирует» их).

Например, при запросе sum([1,2,3], X), Prolog проверяет оба sum положения, и решает, что запрос объединяет только со второй, потому что [] не может быть объединен с [1,2,3].

Теперь нужно объединить [1,2,3] с [Elem | Tail] путем временного назначения, которое длится до тех пор, пока мы находимся в теле правила: Elem=1 и Tail = [2,3]. На этом этапе он пытается снова решить sum, минуя [2,3] в качестве первого параметра. Первое правило не соответствует, поэтому выполняется еще одно временное присвоение Elem=2 и Tail=[3]. На третьем уровне рекурсии мы получаем задание Elem=3 и Tail=[]. Это когда мы попали в первое правило, производя назначение S1=0. Третий уровень призыва добавляет к нему 3; второй уровень добавляет 2. Первый уровень добавляет 1 и возвращается с X, установленным на 6.

Answer 2

Ваши предположения о том, что происходит во время исполнения, довольно странные. Никакие функции не задействованы вообще.

Для оценки цели sum([1,2,3], X), второй пункт выбран потому, что нет соответствия между [1,2,3] (первым аргументом цели) и [] (в верхней части первой статьи).

Соответствующие экземпляры Elem=1, Tail=[2,3] и S = X. Затем оценивается цель sum([2,3], S1) и успешно (после рекурсии), возвращая подстановку S1=5. Затем S=5+1 связывает S до 6.

Answer 3

Важной частью пролога является соответствие (в более общем плане, объединение). Когда время выполнения Prolog встречает цель, например sum(X,Y), она попытается сопоставить этот термин с левыми (главными) правилами для суммы в том порядке, в котором они появляются. Если первое правило выходит из строя, система перейдет ко второму правилу и так далее.

В этом случае первая глава будет соответствовать только в том случае, если X является пустым списком. Если он не пуст, совпадение не выполняется, и следующая голова проверяется. Это будет успешным, если X - любой непустой список. Это будет не только успешно, но и привяжет первый элемент списка к Elem, остальная часть списка (которая может быть пуста) до Tail. Поскольку второй аргумент в главе этого правила является переменной, он будет привязан к тому, что Y является.

Давайте работать через несколько примеров:

сумма ([], X)?

Первая головка спички, связывание X 0.

суммы ([1], X)?

Первый головка не соответствует, потому что [1] не соответствует []. Второй - с Elem < - 1, Tail < - []. Таким образом, мы можем приступить к правой части правил:

sum(Tail,S1), S is S1 + Elem 

< Так как хвост - [], сумма цели (хвост, S1), приведет к получению связывания S1 < -0 (смотрите выше). Таким образом, с Elem < -1 и S1 < -0, S1 + Elem = 1.

И так далее. Надеюсь, здесь вас будет достаточно, чтобы сделать все остальное.