Упражнение

1. Что получится, если выполнить следующее целевое утверждение?

length_of(X, 3).

Выполнится ли оно, и если да, то, что будет присвоено X? Почему?

(Разберитесь внимательно, как это сработает.)

2. Запишите предикат с названием sum_of, который работает также, как

length_of, за исключением того, что он работает со списком чисел и

суммирует их.

Например, целевое утверждение:

sum_of([1, 2, 3, 4], S)

должно присваивать 10 - S.

3. Что будет, если вы попробуете выполнить целевое утверждение:

sum_of(List, 10).

Это целевое утверждение требует: "Создай мне список, к элементам ко-

торого надо добавить 10". Можно ли сделать это в Турбо Прологе? Если

нет, почему? (Подсказка: в Турбо Прологе нельзя выполнять арифмети-

ческие операции с неопределенными переменными.)

Хвостовая рекурсия

Возможно, вы заметили, что length_of не может иметь хвостовую рекур-

сию потому, что рекурсивный вызов не является последним шагом в своем

предложении. Можно ли написать предикат для определения длины списка, ко-

торый будет иметь хвостовую рекурсию. Да, но это потребует некоторых уси-

лий.

Проблема использования length_of в том, что нельзя посчитать длину

списка, пока не подсчитана длина тела. Но оказывается, есть обходной спо-

соб. Для определения длины списка вам потребуется предикат с тремя аргу-

ментами.

` Первый - это сам список, который компьютер сводит на нет по каждо-

му вызову, пока список не опустеет, также как и раньше.

` Второй - свободный параметр, который будет хранить промежуточный

результат (длину).

` Третий - счетчик, который считает от нуля и прибавляет 1 при каж-

дом вызове.

Когда список станет пустым, вы получите в счетчике независимый (со-

ответствующий) результат.

/* Программа CH08EX03.PRO - длина списка с применением хвосто-

вой рекурсии*/

domains

list = integer* /* или любой другой тип */

predicates

length_of(list, integer, integer)

clauses

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Если список пуст, присвоить значение второго агрумента *

* (рузультат) - третьему (счетчик). *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

length_of([], Result, Result).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Иначе, добавить 1 к счетчику и повторить, с присвоением *

* Result в текущем вызове - Result в следующем. *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

length_of([_|T], Result, Counter) :-

NewCounter = Counter + 1,

length_of(T, Result, NewCounter).

goal

length_of([1, 2, 3], L, 0), /* начать со счетчика = 0 */

write(L), n1.

Данная версия предиката length_of более сложная и менее логичная,

чем предыдущая. Она продемонстрирована лишь для доказательства того, что

хвостовые рекурсивные алгоритмы для целевых утверждений (которые, возмож-

но, требует различных типов рекурсии), можно найти различными средствами.