У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой Xи хвостом Y. Это записывается как [X|Y], где для разделения Xи Yиспользуется вертикальная черта. При конкретизации структуры подобного вида Xсопоставляется с головой списка, a Y– с хвостом списка, как это показано в следующем примере:

p([1, 2, 3]).

p([эта, кошка, сидела, [на, этой, подстилке]]).

?- p([X|Y]).

X = 1 Y=[2,3] ;

X=эта Y=[кошка, сидела, [на, этой, подстилке]]

?- p([_,_,_,[_|X]]).

X=[этой, подстилке]

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

Как видно из последнего примера, используя скобочную форму записи списков, можно создавать структуры, похожие на списки, но не заканчивающиеся пустым списком. Одна из таких структур, [белая|лошадь],обозначает структуру, головой которой является белая,а хвостом – лошадь.Константа лошадьне является ни списком, ни пустым списком, и, как мы увидим далее, обработка таких структур требует большой осторожности, когда они используются в качестве хвоста списка.

Существует еще одна область применения списков – это представление строк литер. Иногда возникает необходимость в использовании строк литер для печати или ввода текста. Если строка литер заключена в двойные кавычки, то эта строка представляется как список кодов, соответствующих литерам строки. Для кодировки литер используется код ASCII, который обсуждался в разд. 2.2. Например, строка "system"преобразуется в Прологе в следующий список: [115, 121, 115, 116, 101, 109].

Предположим, что имеется некоторый список, в котором Xобозначает его голову, a Y– хвост списка. Напомним, что такой список мы можем записать так: [X|Y]. Этот список мог бы содержать, например, клички тех лошадей потомков жеребца Coriander,которые все выиграли скачки в Великобритании в 1927 году:

[curragh_tip, music_star, park_mill, portland]

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

Если совпадает, то наш список завершается успехом. Если нет, то мы проверяем, есть ли кличка в хвосте исходного списка. Это значит, что снова проверяется голова, но уже хвоста списка. Затем проверяется голова очередного хвоста списка. Если мы доходим до конца списка, который будет пустым списком, то наш поиск завершается неудачей: указанной клички в исходном списке нет.

Для того чтобы записать все это на Прологе, сначала надо установить, что между объектом и списком, в который этот объект может входить, существует отношение. Это отношение, называемое отношением принадлежности, представляет достаточно распространенное в повседневной жизни понятие. Так, мы говорим о людях, являющихся членами клубов, и о других тому подобных вещах. Для записи этого отношения мы будем использовать предикат принадлежит:целевое утверждение принадлежит(X, Y)является истинным («выполняется»), если терм, связанный с X, является элементом списка, связанного с Y. Имеются два условия, которые надо проверить для определения истинности предиката. Первое условие говорит, что Xбудет элементом списка Y, если X совпадает с головой списка Y. На Прологе этот факт записывается следующим образом:

принадлежит(X,[X |_]).

Эта запись констатирует, что X является элементом списка, который имеет X в качестве головы. Заметим, что мы использовали анонимную переменную '_' для обозначения хвоста списка. Это сделано потому, что мы никак не используем хвост списка в этом частном факте. Заметим, что данное правило могло бы быть записано и по-другому:

принадлежит(X,[Y|_]:- X = Y.

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

Второе, и последнее, правило говорит о том, что Xпринадлежит списку при условии, что он входит в хвост этого списка, обозначаемый через Y. И нет лучшего пути, чем использовать тот же самый предикат принадлежитдля того, чтобы определить, принадлежит ли Xхвосту списка! В этом и состоит суть рекурсии. На Прологе это выглядит так:

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

и констатирует, что X является элементом списка, если X является элементом хвоста этого списка. Заметим, что мы использовали анонимную переменную '_', так как нас не интересует имя переменной, обозначающей голову списка. Два этих правила в совокупности определяют предикат для отношения принадлежности и указывают Прологу, каким образом просматривать список от начала до конца при поиске некоторого элемента в списке. Наиболее важный момент, о котором следует помнить, встретившись с рекурсивно определенным предикатом, заключается в том, что прежде всего надо найти граничные условия и способ использования рекурсии.

Для предиката принадлежитв действительности имеются два типа граничных условий. Либо объект, который мы ищем, содержится в списке, либо он не содержится в нем. Первое граничное условие для предиката принадлежитраспознается первым утверждением, которое приведет к прекращению поиска в списке, если первый аргумент предиката принадлежитсовпадает с головой списка, соответствующего второму аргументу. Второе граничное условие встречается, когда второй аргумент предиката принадлежитявляется пустым списком.