Основы современных компьютерных технологий


Списки - часть 3


Первым в теле стоит стандартный предикат write(Head), который выводит на экран значение переменной Head, в данном случае 1, затем выполняется предикат nl - перевод строки и формируется рекурсивный вызов print_list([2,3,4]). Снова обращение к первому варианту правила и снова неуспех - [2,3,4]#[], и снова успешное сопоставление со вторым вариантом и т.д. В конечном итоге переменная Head становится равной 4, a Tail=[], и теперь после рекурсивного вызова printjist([]) сопоставление для первого варианта правила завершится успехом - []=[], этот вариант правила не имеет рекурсии - он является фактом и интерпретируется Прологом как цель достигнута и целевой запрос считается удовлетворенным.

Пример 2. Рассмотрим Пролог-программу подсчета суммы произведений элементов двух векторов X и Y, представленных списками Х=[х1 ,х2,.. .хn] и Y=[y1 ,у2 ,.. ,уn]:

domains


vector=integer*

predicates


prod(vector, vector, integer)

clauses


prod([],[],0).

prod([X|Xs],[Y|Ys],S):-prod(Xs,Ys,Sp),

321

S=X*Y+Sp.

goal


prod([1,2,3],[7,8,9],Rest),white("Rest=",Res).

Предикат prod (...) является трехместным: первый аргумент - список X, второй - список Y и третий - сумма произведений списков. В разделе clauses описаны два варианта правила для этого предиката.

Первый вариант - утверждение о том, что сумма произведений элементов пустых списков равна 0. Второй вариант правила реализован с использованием хвостовой рекурсии. Выражение S=X*Y+Sp означает, что текущая сумма равна сумме произведений текущих элементов вектора и частичной суммы, полученной на предыдущих шагах вычислений.

Схематично действия при выполнении программы представлены в табл. 24.2. Рекурсивное правило описывает отсроченные вычисления - после рекурсивного вызова остается не выполненным хвост правила, копии которого помещаются в стек до тех пор, пока не произойдет сопоставление с первым вариантом правила. И после того, как это произойдет, частичная сумма Sp" получит значение 0 и все накопленные в стеке хвостовые вычисления будут выполнены в обратном порядке.




Начало  Назад  Вперед