Списки и рекурсия

Обработка списков как обработка последовательности элементов - это мощная техника, используемая в Прологе. В этом руководстве мы рассматриваем что такое списки, как их объявлять, и затем приводим несколько примеров, показывающих как использовать работу со списками в приложениях. Мы также определяем два хорошо известных предиката Пролога – member (член, элемент) и append (добавить) – рассматривая обработку списков как с рекурсивной, так и процедурной точки зрения.

Затем мы представляем предикат findall - стандартный предикат языка системы Visual Prolog, позволяющий собирать решения в единую цель. В завершение этого руководства мы обсуждаем составные списки – комбинции различных типов элементов и, кроме того, - пример разбора с помощью разностных списков.

Что такое Список?

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

Список, содержащий числа 1, 2 и 3 записывается как

[ 1, 2, 3 ]

Порядок элементов в этом списке значим:

• Число "1" является первым элементом,
• "2" - второй,
• "3" - третий.

Список [ 1, 2, 3 ] и список [ 1, 3, 2 ] различны.

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

["dog", "cat", "canary"]
["valerie ann", "jennifer caitlin", "benjamin thomas"]

Один и тот же элемент может быть представлен в списке несколько раз, например:

[ 1, 2, 1, 3, 1 ]

Объявление Списков

Для объявления домена - списка целых используется декларация домена, как показано ниже:

domains
  integer_list = integer*.

Звездочка означает "список этого"; то есть, integer* означает "список целых".

Обратите внимание на то, что слово "list" не имеет специального значения в Visual Prolog. Вы равным образом могли бы назвать Ваш списковый домен как zanzibar. Именно звездочка, а не имя, предписывает этому домену быть списком.

Элементами в списке может быть что угодно, включая другие списки. Но все элементы в списке должны принадлежать одному домену, и дополнительно к декларации спискового домена должна быть декларация domains для элементов:

domains
  element_list = elements*.
  elements = ....

Здесь elements должны быть приравнены к простым доменным типам (например, integer, real или symbol) или к набору возможных альтернатив, обозначенных различными функторами. Visual Prolog не допускает смешивание стандартных типов в списке. Например, следующие декларации ошибочно представляют списки, созданные из integers, reals и symbols:

element_list = elements*.
elements =
    integer;
    real;
    symbol.
        /* Неправильно */

Выходом для объявления списков из integer, real и symbols является объявление домена общего для всех типов, где функтор показывает какому типу принадлежит тот или иной элемент. Например:

element_list = elements*.
elements =
    i(integer);
    r(real);
    s(symbol).
        /* функторами являются i, r и s */

(Подробнее об этом - в этом же руководстве в разделе "Составные списки").

Головы и Хвосты

Список на самом деле является рекурсивным составным объетом. Он состоит из двух частей - головы списка, которым является первый элемент, и хвоста - списка, который включает все следующие элементы.

Хвост списка всегда есть список; голова списка есть элемент.

Например,

голова списка [a, b, c] есть a
хвост списка [a, b, c] есть [b, c]

Что происходит, когда мы имеем дело со списком, содержащим один элемент? Ответом является:

головой списка [c] является c
хвостом списка [c] является []

Если многократно отнимать первый элемент от хвоста списка, мы получим в конечном итоге пустой список ([ ]).

Пустой список не может быть разбит на голову и хвост.

Это означает, что, концептуально говоря, списки имеют древовидную структуру подобно другим составным объектам. Древовидная структура списка [a, b, c, d] есть:

    list
   /    \
  a    list
      /    \
     b    list
         /    \
        c    list
            /    \
           d      []

Более того, одноэлементный список, такой как [a] - это не тот же самый элемент, который этот список содержит, поскольку [a] является действительно составной структурой данных, как это видно здесь:

    list
   /    \
  a     []

Представления Списков

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

[a, b, c] эквивалентно [a|[b, c]]

и, продолжая процесс,

[a|[b,c]] эквивалентно [a|[b|[c]]],

что эквивалентно [a|[b|[c|[]]]]

Можно даже использовать оба способа разделения в одном и том же списке, рассматривая вертикальную черту как разделитель самого низкого уровня. Следовательно, можно записать [a, b, c, d] как [a, b|[c, d]]. Таблица 1 дает дополнительные примеры.

Таблица 1: Головы и Хвосты списков

Список	Голова	Хвост
['a', 'b', 'c']	'a'	['b', 'c']
[ 'a' ]	'a'	[]
/*пустой список*/ [ ]	неопределен	неопределен
[[1, 2, 3], [2, 3, 4], []]	[1, 2, 3]	[[2, 3, 4], []]

В Таблице 2 приведены некоторые примеры унификации списков.

Таблица 2: Унификация Списков

Список 1	Список 2	Связывание Переменных
[X, Y, Z]	[эгберт, ест, мороженое]	X=эгберт, Y=ест, Z=мороженое
[7]	[X | Y]	X=7, Y=[]
[1, 2, 3, 4]	[X, Y | Z]	X=1, Y=2, Z=[3,4]
[1, 2]	[3 | X]	fail

Использование Списков

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

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

Вывод Списков на печать

Например, если Вы хотите только вывести на печать элементы списка, то вот что Вы делаете:

class my
predicates
  write_a_list : (integer*).
end class
 
implement my
clauses
  write_a_list([]). /* Если список пустой, ничего не делаем. */
  write_a_list([H|T]):- /* Сопоставляем голову с H и хвост с T, и... */
    stdio::write(H),stdio::nl, /*выводим H и переводим строку*/
    write_a_list(T).
end implement
 
goal
  console::init(),
  my::write_a_list([1, 2, 3]).

Здесь мы видим два клауза write_a_list, которые можно выразить но обычном языке:

• Для вывода на печать пустого списка ничего не надо делать.
• Иначе, для вывода на печать списка, вывести на печать его голову (она есть просто элемент), и потом вывести на печать хвост списка (он, как известно, есть список).

Первый раз, когда вызывается:

my::write_a_list([1, 2, 3]).

такой вызов сопоставляется со вторым клаузом, с головой H=1 и T=[2, 3]. Это приводит к выводу на печать 1, затем рекурсивно вызывается write_a_list с аргументом в виде хвоста списка:

my::write_a_list([2, 3]).
  /* Это вызов write_a_list(T). */

Этот второй вызов опять сопоставляется со вторым клаузом, где, на этот раз H=2 и T=[3], поэтому выводится 2 и опять рекурсивно вызывается write_a_list:

my::write_a_list([3]).

С каким клаузом теперь такой вызов сопоставлятся? Напомним, что, хотя список [3] имеет всего один элемент, у него есть голова и хвост - голова есть 3, а хвост есть []. Таким образом, этот вызов опять сопоставляется со вторым клаузом с H=3 и T=[]. Теперь выводится 3 и вызывается рекурсивно write_a_list:

my::write_a_list([]).

Теперь становится понятно для чего нужен первый клауз. Второй клауз не может быть сопоставлен с таким вызовом, поскольку [] не может быть разделен на голову и хвост. Если бы первого клазуа здесь не было бы, то выполнение goal оказалось бы неуспешным. Но, поскольку он есть, то первый клауз сопоставляется с вызовом и выполнение goal успешно завершается и нечего более не делается.

Подсчет элементов в Списке

Рассмотрим теперь, как подсчитать число элементов в списке, или какова длина списка? Логично определить:

• Длина пустого списка [] есть 0.
  
• Длина любого другого списка есть 1 плюс длина его хвоста.

Можно ли это запрограммировать? На Прологе это очень просто. Всего два клауза:

class my
predicates
  length_of : (A*, integer) procedure(i,o).
end class
 
implement my
clauses
  length_of([], 0).
  length_of([_|T], L):-
    length_of(T, TailLength),
    L = TailLength + 1.
end implement
 
goal
  console::init(),
  my::length_of([1, 2, 3], L),
  stdio::write(L).

Посмотрите прежде всего на второй клауз. Строго говоря, [_|T] сопоставляется с любым непустым списком, связывая T с хвостом списка. Значение головы неважно, если она есть, она может быть учтена как один элемент.

Тогда вызов:

my::length_of([1, 2, 3], L)

сопоставляется со вторым клаузом, с T=[2, 3]. Следующим шагом является вычисление длины хвоста T. Когда это сделано (не имеет значение, как), TailLength получит значение 2, и компьютер теперь может добавить 1 к ней и связать L со значением 3. Как выполняется этот промежуточный шаг? Надо найти длину списка [2, 3], путем удовлетворения цели

my::length_of([2, 3], TailLength)

Другими словами, length_of вызывает себя рекурсивно. Этот вызов сопоставляется со вторым клаузом, связывая

• [3] и T в вызове клаузы и
• TailLength с L в клаузе.

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

Итак, теперь задача - найти длину списка [3], которая есть 1, и мы добавляем 1 к этому значению, чтобы получить длину списка [2, 3], что будет 2. Ну и хорошо!.

Аналогично, length_of вызывает себя рекурсивно опять для получения длины списка [3]. Хвост [3] есть [], поэтому T связывается с [], и задача теперь - получение длины списка [] и добавление к ней 1, что дает длину списка [3].

Теперь все просто. Цель:

my::length_of([], TailLength)

сопоставляется с первым клаузом, связывая TailLength с 0. Поэтому теперь компьютер может добавить 1 к нему, получая длину списка [3], и возвращаясь теперь в вызывавший клауз. Это, в свою очередь, опять добавляет 1, давая длину списка [2, 3], и возвращается в клауз, который его вызывал; этот первоначальный клауз добавит снова 1, давая длину списка [1, 2, 3].

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

my::length_of([1, 2, 3], L1).
my::length_of([2, 3], L2).
my::length_of([3], L3).
my::length_of([], 0).
L3 =  0+1 = 1.
L2 = L3+1 = 2.
L1 = L2+1 = 3.

Обратите внимание, что Вам не нужно каждый раз создавать такого рода предикаты самостоятельно, Вы можете использовать готовый предикат list::length из PFC.

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

Вы, очевидно, заметили, что length_of не является (и не может быть) предикатом с хвостовой рекурсией, поскольку рекурсивный вызов не является последним шагом в его клаузе. Возможно ли создать предикат, определяющий длину, так, чтобы он был предикатом с хвостовой рекурсией? Да, но это потребует некоторых усилий.

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

• Один из них - это список, от которого компьютер будет откусывать по одному элементу на каждом вызове до тех пор, пока этот список, как и прежде, не превратится в пустой список.
• Второй - это свободный аргумент, который в конечном итоге вернет результат (длину).
• Третий - это счетчик, значение которого начинается с нуля и увеличивается с каждым вызовом.

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

class my
predicates
  length_of : (A*, integer, integer) procedure(i,o,i).
end class
 
implement my
clauses
  length_of([], Result, Result).
  length_of([_|T], Result, Counter):-
    NewCounter = Counter + 1,
    length_of(T, Result, NewCounter).
end implement
 
goal
  console::init(),
  my::length_of([1, 2, 3], L, 0), /* Начинаем со счетчиком Counter = 0 */
  stdio::write(" L = ", L).

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

Модификация Списка

Иногда требуется создать другой список из заданного списка. Это делается путем просмотра списка, элемент за элементом, заменяя каждый элемент вычисленным значением. Например, как эта программа, которая добавляет 1 к каждому элементу исходного списка:

class my
predicates
  add1 : (integer*, integer*) procedure(i,o).
end class
 
implement my
clauses
  add1([], [])./* граничное условие */
  add1([Head|Tail],[Head1|Tail1]):- /* отделяем голову от остального списка*/
    Head1 = Head+1, /* добавляем 1 к элементу-голове */
    add1(Tail, Tail1)./* далаем это с остальной частью списка*/
end implement
 
goal
  console::init(),
  my::add1([1,2,3,4], NewList),
  stdio::write(NewList)).

На обычном языке это звучит так:

• Добавление 1 ко всем элементам пустого списка порождаем пустой список,
• Для добавления 1 ко всем элемента любого другого списка:
  • добавить 1 к голове и сделать эту голову головой результирующего списка, а затем
  • добавить 1 к каждому элемента хвоста и этот хвост сделать хвостом результата.

Загрузим программу и выполним такую цель

add1([1,2,3,4], NewList).

Цель вернет

NewList=[2,3,4,5]
1 Solution

Опять о хвостовой рекурсии

Является ли предикат add1 проедикатом с хвостовой рекурсией? Если у Вас есть опыт использования Lisp или Pascal, Вы могли бы подумать, что нет, поскольку Вы бы рассуждали так:

• Делим список на Head и Tail.
• Добавляем 1 к Head, получаем Head1.
• Рекурсивно добавляя 1 ко всем элементам списка Tail, получаем Tail1.
• Соединяем Head1 и Tail1, что дает результирующий список.

Это не похоже на хвостовую рекурсию, поскольку последний шаг - не рекурсивный вызов.

Однако, и это важно, – Это не то, что делает Пролог. В Visual Prolog add1 является предикатом с хвостовой рекурсией, поскольку выполняется в действительности следующим образом:

• Связать голову и хвост исходного списка с Head и Tail, соответственно.
• Связать голову и хвост результирующего списка с Head1 и Tail1, соответственно. (Head1 и Tail1 пока не получили значений.)
• Добавить 1 к Head, что дает Head1.
• Рекурсивно добавить 1 ко всем элементам списка Tail, что дает Tail1.

Когда это сделано, Head1 и Tail1 уже являются головой и списком результата и отдельной операции по их соединению нет. Поэтому рекурсивный вызов и является последним шагом.

Снова Модификация Списков

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

class my
predicates
  discard_negatives : (integer*, integer*) procedure(i,o). /*удалить отрицательные*/
end class
 
implement my
clauses
  discard_negatives([], []).
  discard_negatives([H|T], ProcessedTail):-
    H < 0,
    !, /* Если H отрицательно, пропускаем его */
    discard_negatives(T, ProcessedTail).
  discard_negatives([H|T], [H|ProcessedTail]):-
    discard_negatives(T, ProcessedTail).
end implement
 
goal
  console::init(),
  my::discard_negatives ([2, -45, 3, 468], X),
  stdio::write(X).

Напрмер, цель

my::discard_negatives([2, -45, 3, 468], X)

дает

X=[2, 3, 468].

А вот - предикат который копирует элементы списка, добавляя для каждого элемента его дубликат:

doubletalk([], []).
doubletalk([H|T], [H, H|DoubledTail]) :-
  doubletalk(T, DoubledTail).

Принадлежнось списку

Допустим, имеется список с именами John, Leonard, Eric и Frank и требуется, используя Visual Prolog, выяснить, принадлежит ли заданное имя этому списку. Другими словами, надо определить "отношение" между двумя аргументами: именем и списком имен. Это соответствует предикату

isMember : (name, name*).
  /* "name" принадлежит списку "name*" */

В программе e01.pro первый клауз исследует голову списка. Если голова списка совпадает с искомым именем, то можно сделать заключение, что Name принадлежит списку. Поскольку хвост списка нас не интересует, то это мы представляем анонимной переменной. Благодаря первому клаузу, цель

my::isMember("john", ["john", "leonard", "eric", "frank"])

удовлетворена.

/* Программа e01.pro */
class my
predicates
  isMember : (A, A*) determ.
end class
 
implement my
clauses
  isMember(Name, [Name|_]) :-
    !.
  isMember(Name, [_|Tail]):-
    isMember(Name,Tail).
end implement
 
goal
  console::init(),
  my::isMember("john", ["john", "leonard", "eric", "frank"]),
  !,
  stdio::write("Success")
  ;
  stdio::write("No solution").

Если голова списка не есть Name, то надо исследовать, не содержится ли Name в хвосте списка.

На обычном языке:

Name принадлежит списку, если Name является первым элементом списка, или
Name принадлежит списку, если Name принадлежит хвосту.

Второй клауз предиката isMember относится к этому отношению. Таким образом на Visual Prolog:

isMember(Name, [_|Tail]) :-
    isMember(Name, Tail).

Добавление списка к другому списку: декларативное и рекурсивное решения

Рассмотренный предикат member программы e01.pro работает в двух направлениях. Вернемся к его клаузам:

member(Name, [Name|_]).
member(Name, [_|Tail]) :-
  member(Name, Tail).

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

• С декларативной точки зрения, клаузы выражают:
  • Name (Имя) принадлежит списку, если голова списка есть Name
  • иначе Name принадлежит списку, если оно (Имя) принадлежит хвосту.
• С процедурной точки зрения, эти же два клауза могут быть интерпретированы так:
  Чтобы найти элемент списка
  • Найдите его голову
  • иначе найдите элемент хвоста списка.

Эти две точки зрения соответствуют целям

member(2, [1, 2, 3, 4]).

и

member(X, [1, 2, 3, 4]).

В результате первый вызов поручает Visual Prolog(у) проверить, истино ли нечто (принадлежность числа 2 списку [1,2,3,4]). Второй вызов поручает Visual Prolog(у) найти все члены списка [1,2,3,4]. Не смущайтесь этим. Предикат member является одним и тем же, но на его поведение можно смотреть под разными углами.

Рекурсия с процедуральной точки зрения

Прелесть Пролога заключается в том, что часто, когда мы конструируем клаузы для предиката, будучи на одной точке зрения, они будут работать и при взгляде с другой точки зрения. Чтобы обнаружить эту дуальность, мы приведем пример предиката для добавления (append) одного списка к другому. Мы определяем предикат append с тремя аргументами:

append(List1, List2, List3).

Этот предикат интегрирует списки List1 и List2 в форму списка List3 так, что список List2 дописывается в конце списка List1. То есть содержательно - осуществляется добавление списка List2 к списку LIst1. Опять мы используем рекурсию (на этот раз с процедуральной точки зрения).

Если список List1 пустой, результатом добавления списка List1 к списку List2 будет тот же самый List2. Запишем это на Прологе:

append([], List2, List2).

Если список List1 не пустой, то можно преобразовать списки List1 и List2 к форме списка List3, сделав голову списка List1 головой списка List3. В приведенном коде переменная H используется в качестве головы как списка List1, так и списка List3. хвост списка List3 есть список L3, который составлен из остатка списка List1 (а именно, L1) и всего списка List2. Опять выразим это на Прологе:

append([H|L1], List2, [H|L3]) :-
   append(L1, List2, L3).

Предикат append работает следующим образом: пока список List1 не пустой, рекурсивное правило дописывает один элемент каждый раз к списку List3. Когда список List1 становится пустым, первый клауз clause обеспечивает дописывание списка List2 в конец списка List3.

Варианты использования одного предиката

Подходя к предикату append с декларативной точки зрения, мы определили его как отношение между тремя списками. Это отношение справедливо также, если списки List1 и List3 известны, а List2 - нет. Более того, это также работает, если только List3 известен. Например, для того, чтобы выяснить, какие два списка могли бы быть соединены для получения известного списка, можно использовать вызов в форме

append(L1, L2, [1, 2, 4]).

С таким целевым вызовом, Visual Prolog найдет следующие решения:

L1=[], L2=[1,2,4]
L1=[1], L2=[2,4]
L1=[1,2], L2=[4]
L1=[1,2,4], L2=[]
4 Solutions

Можно использовать предикат append для нахождения списка, который следовало бы добавить к списку [3,4] для получения списка[1,2,3,4]. Попробуем такой вызов

append(L1, [3,4], [1,2,3,4]).

Visual Prolog находит решение

L1=[1,2].

Предикат append определяет отношение между входным набором (input set) и выходным набором (output set) таким образом, что отношение применимо в обе стороны. При таком отношении возникает вопрос

Что является выходным набором для заданного входного? или Какой входной набор соответствует заданному выходному?

Статус аргументов данного вызова предиката известен как поток (или шаблон) ввода-вывода. Аргумент, который связан или наследуется в момент вызова является входным аргументом и обозначается как (i). Свободный аргумент является выходным аргументом и обозначается как (o).

Предикат append обладает свойством поддерживать любой шаблон ввода-вывода, какой требуется. Однако не все предикаты имеют возможность вызова с различными шаблонами ввода-вывода. Когда клауз Пролога способен поддерживать множество шаблонов ввода-вывода, он называется инверсным клаузом. Целый набор предикатов для обработки списков содержится в классе list.

Все Решения Сразу

Откаты и рекурсии являются двумя способами выполнения повторяющихся процессов. Рекурсия предпочтительнее, поскольку, в отличие от отката, позволяет передать данные через аргументы от одного рекурсивного вызова к следующему. Благодаря этому, рекурсивные процедуры могут использовать промежуточные результаты или счетчики по ходу выполнения.

Однако есть одна вещь, которую, в отличие от рекурсии, могут делать откаты, а именно – искать все альтернативные решения посредством одного вызова. Поэтому Вы можете оказаться в затруднительном положении: Вам нужно получить все решения за один вызов, и, при этом, они Вам нужны все сразу, как часть единой интегрированной структуры данных. Что делать?

К счастью, Visual Prolog позволяет найти выход из этого положения. Предопределенная конструкция обработки списков получает целевой вызов в качестве своего аргумента и собирает все решения для этого вызова в единый выходной список. Такая конструкция для списков имеет два аргумента:

• Первый аргумент, VarName, определяет аргумент в вызываемом целевом предикате, значения которого будут собираться в список.
• Второй - mypredicate - определяет предикат, который будет получать значения.
• Выходной параметр ListParam, является переменной, которая содержит список значений, полученных в ходе отката.

Программа e02.pro использует обработку списка для вывода среднего возраста группы людей.

        /* Программа e02.pro */
class my
domains
  name = string.
  address = string.
  age = integer.
 
predicates
  person : (name, address, age) nondeterm anyflow.
  sumlist : (age*, age, integer)procedure(i,o,o).
end class my
 
implement my
clauses
  sumlist([],0,0).
  sumlist([H|T], Sum, N):-
    sumlist(T, S1, N1),
    Sum=H+S1, N=1+N1.
 
  person("Sherlock Holmes","22B Baker Street", 42).
  person("Pete Spiers","Apt. 22, 21st Street", 36).
  person("Mary Darrow","Suite 2, Omega Home", 51).
end implement my
 
goal
  console::init(),
  L = [ Age || my::person(_, _, Age)],
  my::sumlist(L, Sum, N),
  Ave = Sum/N,
  stdio::write("Average=", Ave, ". ").

Клауз обработки списка в этой программе создает список L, который является списком всех возрастов, полученных от предиката person. Если бы потребовалось бы собрать список всех людей в возрасте 42 лет, можно было бы задать следующий цель-вызов:

List = [ Who || my::person(Who, _, 42) ]

Следующий код порождает список всех положительных чисел исходного списка:

List = [ X || X = list::getMember_nd([2,-8,-3,6]), X > 0]

Смешанные списки

Список целых объявляется просто

integer*

То же верно и для списков вещественных чисел (integer), символьных (symbol) списков или списков строк (string).

Однако часто приходится хранить комбинацию различных типов элементов в составе одного и того же списка, такую как:

[2, 3, 5.12, ["food", "goo"], "new"].
        /* Не корректно для Visual Prolog*/

Смешанные списки - списки, содержащие элементы более чем одного типа. Для работы со списками разнотипных элементов должны использоваться специальные объявления, поскольку Visual Prolog требует, чтобы все элементы списка принадлежали бы одному и тому же домену. Способом создания списка, который хранит такие различные типы элементов является использование функторов, поскольку домен может представляться более, чем одним функтором, каждый со своими типовыми аргументами.

Пример объаявления списка, который может хранить целые, символы, строки или списки таких даных:

domains
  /* функторами являются l, i, c, and s */
  llist = l(list); i(integer); c(char); s(string).

Список

[ 2, 9, ["food", "goo"], "new" ]
/* Не корректно для Visual Prolog */

на Visual Prolog следовало бы записать так:

[i(2), i(9), l([s("food"), s("goo")]), s("new")]
        /* Корректно для Visual Prolog */

Следующий пример предиката append показывает как использовать такого рода декларации в стандартных программах манипулирования списками.

class my
domains
  llist = l(list); i(integer); c(char); s(string).
 
predicates
  append : (A*,A*,A*) procedure (i,i,o).
end class
 
implement my
clauses
  append([], L, L).
  append([X|L1], L2, [X|L3]):-
    append(L1, L2, L3).
end implement
 
goal
  console::init(),
  my::append
    (
    [my::s("likes"),my::l([my::s("bill"), my::s("mary")])],
    [my::s("bill"), my::s("sue")], 
    Ans
    ),
  stdio::write("Первый список: ", Ans,"\n\n"),
  my::append
    (
    [my::l([my::s("This"),my::s("is"),my::s("a"),my::s("list")]),my::s("bee")], 
    [my::c('c')], 
    Ans2
    ),
  stdio::write("Второй списко: ", Ans2, "\n\n&quot).

Разбор с использованием списков

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

Этот разборщик предназначен для примитивного формального языка. Хотя этот пример достаточно сложен с точки зрения этого руководства, мы решили поместит его здесь, поскольку разбор является одной из областей, где Visual Prolog очень эффективен. Если Вы чувствуете себя не вполне готовым для этого раздела, Вы можете этот пример пропустить и продолжить чтение руководства без потери содержательности.

#include @"pfc\list\list.ph"
#include @"pfc\string\string.ph"
#include @"pfc\application\exe\exe.ph"
#include @"pfc\console\console.ph"
 
/*******************************************
* Lexer
*******************************************/
class lexer
    predicates
        tokl : (string Input) -> string* TokenTL.
end class lexer
 
implement lexer
    clauses
        tokl(Input) = [Tok|tokl(Rest)] :-
            string::fronttoken(Input, Tok, Rest),
            !.
        tokl(_) = [].
end implement
 
/*******************************************
* Parser
*******************************************/
class parser
    domains
        program = statement*.
 
    domains
        statement =
            if_Then_Else(expression Condition, statement ThenPart, statement ElsePart);
            if_Then(expression Condition, statement ThenPart);
            while(expression Condition, statement Body);
            assign(id Variable, expression Expression).
 
    domains
        expression =
            plus(expression, expression);
            minus(expression, expression);
            var(id);
            int(integer).
 
    domains
       id = string.
 
    predicates
        program : (string* TL) -> program ProgramTree determ.
 
end class
 
implement parser
    clauses
        program(TL) =  Prog :-
            Prog = statement_list(TL, TL0),
            [] = TL0.
 
    class predicates
        statement_list : (string* TL1, string* TL0 [out]) -> program Program determ.
    clauses
        statement_list([], []) = [] :-
            !.
        statement_list(TL1, TL0) = [Statement|Program] :-
            Statement = statement(TL1, TL2),
            TL2=[";"|TL3],
            Program = statement_list(TL3, TL0).
 
    class predicates
        statement : (string* TL1, string* TL0 [out]) -> statement Statement determ.
    clauses
        statement(["if"|TL1], TL0) = if_then_else(Condition, ThenPart, ElsePart) :-
            Condition = expression(TL1, TL2),
            TL2=["then"|TL3],
            ThenPart = statement(TL3, TL4),
            TL4=["else"|TL5],!,
            ElsePart = statement(TL5, TL6),
            TL6=["fi"|TL0].
 
        statement(["if"|TL1], TL0) = if_then(Condition, Statement) :-
            !,
            Condition = expression(TL1, TL2),
            TL2=["then"|TL3],
            Statement = statement(TL3, TL4),
            TL4=["fi"|TL0].
 
        statement(["do"|TL1], TL0) = while(Condition, Statement) :-
            !,
            Statement = statement(TL1, TL2),
            TL2=["while"|TL3],
            Condition = expression(TL3, TL0).
 
        statement([ID|TL1], TL0) = assign(Id,Exp) :-
            string::isname(ID),
            TL1=["="|TL2],
            Exp = expression(TL2, TL0).
 
 
    class predicates
        expression : (string* TL1, string* TL0 [out]) -> expression Expression determ.
    clauses
        expression(TL1, TL0) = Exp:-
            PreTerm = term(TL1, TL2),
            Exp = termTail(TL2, TL0, PreTerm).
 
    class predicates
        termTail : (string* TL1, string* TL0 [out], expression PreExpr) -> expression Expr determ.
    clauses
        termTail(["+"|TL1], TL0, Exp1) = Exp :-
            !,
            Exp2 = term(TL1, TL2),
            Exp = termTail(TL2, TL0, plus(Exp1, Exp2)).
 
        termTail(["-"|TL1], TL0, Exp1) = Exp :-
            !,
            Exp2 = term(TL1, TL2),
            Exp = termTail(TL2, TL0, minus(Exp1, Exp2)).
 
        termTail(TL, TL, Exp) = Exp.
 
    class predicates
        term : (string* TL1, string* TL0 [out]) -> expression Expression  determ.
    clauses
        term([Int|Rest], Rest) = int(I) :-
            try
                I = toTerm(Int)
            catch _ do
                fail
            end try,
            !.
 
        term([Id|Rest], Rest) = var(Id) :-
            string::isName(Id).
end implement parser
 
goal
    console::init(),
    TokenTL = lexer::tokl("b=2; if b then a=1 else a=2 fi; do a=a-1 while a;"),
    if ProgramTree = parser::program(TokenTL) then
        foreach Stmt = list::getMember_nd(ProgramTree) do
            stdio::write(Stmt, "\n")
        end foreach
    else
        stdio::write("Parse error\n")
    end if.

Программа выведет:

assign("b",int(2))
if_then_else(var("b"),assign("a",int(1)),assign("a",int(2)))
while(var("a"),assign("a",minus(var("a"),int(1))))

Преобразование в этом примере представлено двумя шагами: сканирование и разбор. Предикат tokl - это сканер. Он принимает строку и преобразует ее в список токенов. Все предикаты с именами, начинающимися с s_ являются предикатами парсера. В этом примере входный текст представляет программу на языке, подобном языку Паскаль, и состоящей из Паскале-подобных предложений. Этот язык программирования позволяет только предложения вида: IF THEN ELSE, IF THEN, DO WHILE и присваивание (ASSIGNMENT). Предложения состоят из выражений и вложенных предложений. Выражения - сложение, вычитание, переменные и целые.

Далее, как это работает:

• Предикат program, принимает список токенов и вызывает предикат statement_list передав ему этот список. Затем проверяется все ли токены были использованы в процессе разбора.
• Предикат statement_list принимает список токенов и проверяет возможность деления токенов на предложения, завершающиеся точкой с запятой.
• Предикат statement проверяет могут ли начальные токены списка (токенов) представлять собой правильное предложение. Если да, то такое предложение возвращается в виде структуры, а остаток токенов передается рекурсивно вызываемому предикату statement.
• Четыре клауза предиката statement соответствуют четырем типам, которые парсер понимает.
• Если первый клауз предиката statement не может преобразовать список токенов в предложение вида IF THEN ELSE, то клауз завершается неуспешно и в порядке отката переходит к следующему клаузу предиката statement.
• Теперь делается попытка преобразовать список токенов в конструкцию вида IF THEN.
• Если эта попытка неуспешна, то в следующем клаузе делается попытка преобразования к предложению вида DO WHILE.
• Если первые три клауза предиката statement завершаются неуспешно, то последний клауз этого предиката провереяет представлена ли в списке токенов операция присваивания. Этот клауз проверяет "на присваивание" является ли первый терм символом, второй - знаком равно ("="), а следующие термы представляют простое математическое выражение.
• Предикаты expression, term и termTail работают аналогично, путем проверки являются ли начальные термы выражениями и, если это так, то предикату statement возвращается остаток термов и математическое выражение в виде структуры.

Заключение

В этом руководстве раскрыта следующие важные моменты:

• Списки могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки (*) в конце ранее определённого домена.
• Список является рекурсивным составным объектом, состоящим из головы и хвоста. Голова есть первый элемент, а хвост - остальная часть списка (без первого элемента). Хвост списка - всегда список; голова списка - всегда элемента. Список может содержать ноль или более элементов; Пустой список обозначается [].
• Элементами списка может быть что угодно, включая другие списки; все элементы списка должны принадлежать одному домену. В этом случае объявление домена элементов должно выглядеть так:

domains
  element_list = elements*.
  elements = ....

где elements = один из стандартных доменов (integer, real, etc.) или набор альтернатив обозначенных различными функторами (int(integer); rl(real); smb(symbol); и т.д.). Смешение типов в списках языка системы Visual Prolog допускается только включением их в составные объекты или функторы.

• Можно использовать разделители (запятые, [ и |) для явного отделения головы списка от хвоста. Так, список

[a, b, c, d]

может быть записан как:

[a|[b, c, d]] 
или
[a, b|[c, d]] 
или
[a, b, c|[d]] 
или
[a|[b|[c, d]]] 
или
[a|[b|[c|[d]]]] 
или даже
[a|[b|[c|[d|[]]]]]

• Обработка списков заключается в рекурсивном отщеплении головы списка (и выполнении действий над ней) до опустошения списка.
• Предикаты для работы со списками содержаться в классе list.
• Visual Prolog поддерживает встроенную конструкцию обработки списков, которая принимает целевой предикат в качестве одного из аргументов и собирает все решения этого целевого предиката в едином списке. Синтаксис такой конструкции

Result = [ Argument || myPredicate(Argument) ]

• Поскольку Visual Prolog требует, чтобы все элементы списка принадлежали бы одному и тому же домену, следует использовать функторы для создания списков, хранящих элементы различного типа.
• процесс разбора с использованием разностных списков (parsing by difference lists) работает путем сокращения задачи; пример в этом руководстве преобразует строку входных данных в структуру, которая может обрабатываться позже.