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

Обработка списков как обработка последовательности элементов - это мощная техника, используемая в Прологе. В этом руководстве мы рассматриваем что такое списки, как их объявлять, и затем приводим несколько примеров, показывающих как использовать работу со списками в приложениях. Мы также определяем два хорошо известных предиката Пролога – 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,
    !,    /* If H is negative, just skip it */
    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).

List Membership

Suppose you have a list with the names John, Leonard, Eric, and Frank and would like to use Visual Prolog to investigate if a given name is in this list. In other words, you must express the relation "membership" between two arguments: a name and a list of names. This corresponds to the predicate

isMember : (name, name*).
    /* "name" is a member of "name*" */

In the e01.pro program, the first clause investigates the head of the list. If the head of the list is equal to the name you're searching for, then you can conclude that Name is a member of the list. Since the tail of the list is of no interest, it is indicated by the anonymous variable. Thanks to this first clause, the goal

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

is satisfied.

/* Program 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").

If the head of the list is not equal to Name, you need to investigate whether Name can be found in the tail of the list.

In English:

Name is a member of the list if Name is the first element of the list, or
Name is a member of the list if Name is a member of the tail.

The second clause of isMember relates to this relationship. In Visual Prolog:

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

Appending One List to Another: Declarative and Procedural Programming

As given, the member predicate of the e01.pro program works in two ways. Consider its clauses once again:

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

You can look at these clauses from two different points of view: declarative and procedural.

From a declarative viewpoint, the clauses say:Name is a member of a list if the head is equal to Name;

if not, Name is a member of the list if it is a member of the tail.

From a procedural viewpoint, the two clauses could be interpreted as saying:To find a member of a list, find its head;

otherwise, find a member of its tail.

These two points of view correspond to the goals

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

and

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

In effect, the first goal asks Visual Prolog to check whether something is true; the second asks Visual Prolog to find all members of the list [1,2,3,4]. Don't be confused by this. The member predicate is the same in both cases, but its behavior may be viewed from different angles.

Recursion from a Procedural Viewpoint

The beauty of Prolog is that, often, when you construct the clauses for a predicate from one point of view, they'll work from the other. To see this duality, in this next example you'll construct a predicate to append one list to another. You'll define the predicate append with three arguments:

append(List1, List2, List3).

This combines List1 and List2 to form List3. Once again you are using recursion (this time from a procedural point of view).

If List1 is empty, the result of appending List1 and List2 will be the same as List2. In Prolog:

append([], List2, List2).

If List1 is not empty, you can combine List1 and List2 to form List3 by making the head of List1 the head of List3. (In the following code, the variable H is used as the head of both List1 and List3.) The tail of List3 is L3, which is composed of the rest of List1 (namely, L1) and all of List2. In Prolog:

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

The append predicate operates as follows: While List1 is not empty, the recursive rule transfers one element at a time to List3. When List1 is empty, the first clause ensures that List2 hooks onto the back of List3.

One Predicate Can Have Different Uses

Looking at append from a declarative point of view, you have defined a relation between three lists. This relation also holds if List1 and List3 are known but List2 isn't. However, it also holds true if only List3 is known. For example, to find which two lists could be appended to form a known list, you could use a goal of the form

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

With this goal, Visual Prolog will find these solutions:

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

You can also use append to find which list you could append to [3,4] to form the list [1,2,3,4]. Try giving the goal

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

Visual Prolog finds the solution

L1=[1,2].

This append predicate has defined a relation between an input set and an output set in such a way that the relation applies both ways. Given that relation, you can ask

Which output corresponds to this given input?

or

Which input corresponds to this given output?

The status of the arguments to a given predicate when you call that predicate is referred to as a flow pattern. An argument that is bound or instantiated at the time of the call is an input argument, signified by (i); a free argument is an output argument, signified by (o).

The append predicate has the ability to handle any flow pattern you provide. However, not all predicates have the capability of being called with different flow patterns. When a Prolog clause is able to handle multiple flow patterns, it is known as an invertible clause. Many of list predicate can be found in the list class.

Finding All the Solutions at Once

Backtracking and recursion are two ways to perform repetitive processes. Recursion won out because, unlike backtracking, it can pass information (through arguments) from one recursive call to the next. Because of this, a recursive procedure can keep track of partial results or counters as it goes along.

But there's one thing backtracking can do that recursion can't do – namely, find all the alternative solutions to a goal. So you may find yourself in a quandary: You need all the solutions to a goal, but you need them all at once, as part of a single compound data structure. What do you do?

Fortunately, Visual Prolog provides a way out of this impasse. The built-in construction list comprehension takes a goal as one of its arguments and collects all of the solutions to that goal into an output single list. list comprehension takes two arguments:

The first argument, VarName, specifies which argument in the specified predicate is to be collected into a list.

The second, mypredicate, indicates the predicate from which the values will be collected.

The output ListParam, is a variable that holds the list of values collected through backtracking.

The e02.pro program uses list comprehension to print the average age of a group of people.

        /* Program 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
 
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
 
goal
    console::init(),
    L = [ Age || my::person(_, _, Age)],
    my::sumlist(L, Sum, N),
    Ave = Sum/N,
    stdio::write("Average=", Ave, ". ").

The list comprehension clause in this program creates a list L, which is a collection of all the ages obtained from the predicate person. If you wanted to collect a list of all the people who are 42 years old, you could give the following subgoal:

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

The following code will create the list of positive items:

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

Compound Lists

A list of integers can be simply declared as

integer*

The same is true for a list of real numbers, a list of symbols, or a list of strings.

However, it is often valuable to store a combination of different types of elements within a list, such as:

[2, 3, 5.12, ["food", "goo"], "new"].
        /* Not correct Visual Prolog*/

Compound lists are lists that contain more than one type of element. You need special declarations to handle lists of multiple-type elements, because Visual Prolog requires that all elements in a list belong to the same domain. The way to create a list in Prolog that stores these different types of elements is to use functors, because a domain can contain more than one data type as arguments to functors.

The following is an example of a domain declaration for a list that can contain an integer, a character, a string, or a list of any of these:

domains
        /* the functors are l, i, c, and s */
    llist = l(list); i(integer); c(char); s(string).

The list

[ 2, 9, ["food", "goo"], "new" ]
        /* Not correct Visual Prolog */

would be written in Visual Prolog as:

[i(2), i(9), l([s("food"), s("goo")]), s("new")]
        /* Correct Visual Prolog */

The following example of append shows how to use this domain declaration in a typical list-manipulation program.

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("FIRST LIST: ", 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("SECOND LIST: ", Ans2, "\n\n&quot).

Parsing by Difference Lists

The ch07e10.pro program demonstrates parsing by difference lists. The process of parsing by difference lists works by reducing the problem; in this example we transform a string of input into a Prolog structure that can be used or evaluated later.

The parser in this example is for a very primitive computer language. Although this example is very advanced for this point in the tutorial, we decided to put it here because parsing is one of the areas where Visual Prolog is very powerful. If you do not feel ready for this topic, you can skip this example and continue reading the tutorial without any loss of continuity.

#include @"pfc\exception\exception.ph"
#include @"pfc\string\string.ph"
#include @"pfc\console\console.ph"
 
class my_t
    predicates
        tokl : (string, string*) procedure (i,o).
end class
 
implement my_t
    clauses
        tokl(Str, [H|T]) :-
            string::fronttoken(Str, H, Str1), !,
            tokl(Str1, T).
        tokl(_, []).
end implement
 
/* * * * * * * * * * * * * * * * * *
* This second part of the program
* is the parser *
* * * * * * * * * * * * * * * * * */
class my_p
    domains
        program = program(statement_list).
        statement_list = statement*.
        /* * * * * * * * * * * * * * * *
        * Definition of what constitutes
        * a statement *
        * * * * * * * * * * * * * * * */
        statement =
            if_Then_Else(exp, statement, statement);
            if_Then(exp, statement);
            while(exp, statement);
            assign(id, exp).
        /* * * * * * * * * * * * * *
        * Definition of expression *
        * * * * * * * *  * * * * * */
        exp = plus(exp, exp);
            minus(exp, exp);
            var(id);
            int(integer).
       id = string.
 
    predicates
        s_program : (string*, program) procedure (i,o).
        s_statement : (string*, string*, statement) determ (i,o,o).
        s_statement_list : (string*, string*, statement_list) determ (i,o,o).
        s_exp : (string*, string*, exp) determ (i,o,o).
        s_exp1 : (string*, string*, exp, exp) determ (i,o,i,o).
        s_exp2 : (string*, string*, exp) determ (i,o,o).
end class
 
implement my_p
    clauses
        s_program(List1, program(StatementList)):-
            s_statement_list(List1, _, StatementList),
            !.
        s_program(_, program([])).
 
    clauses
        s_statement_list([], [], []) :- !.
        s_statement_list(
            List1, List4, [Statement|Program]) :-
            s_statement(List1, List2, Statement),
            List2=[";"|List3],
            s_statement_list(List3, List4, Program).
        s_statement(["if"|List1], List7,
            if_then_else(Exp,
            Statement1, Statement2)):-
            s_exp(List1, List2, Exp),
            List2=["then"|List3],
            s_statement(List3, List4, Statement1),
            List4=["else"|List5],!,
            s_statement(List5, List6, Statement2),
            List6=["fi"|List7].
        s_statement(["if"|List1], List5,
            if_then(Exp, Statement)) :- !,
            s_exp(List1, List2, Exp),
            List2=["then"|List3],
            s_statement(List3, List4, Statement),
            List4=["fi"|List5].
        s_statement(["do"|List1], List4,
            while(Exp, Statement)) :- !,
            s_statement(List1, List2, Statement),
            List2=["while"|List3],
            s_exp(List3, List4, Exp).
        s_statement([ID|List1], List3,
            assign(Id,Exp)) :-
            string::isname(ID),
            List1=["="|List2],
            s_exp(List2, List3, Exp).
        s_exp(List1, List3, Exp):-
            s_exp2(List1, List2, Exp1),
            s_exp1(List2, List3, Exp1, Exp).
        s_exp1(["+"|List1], List3, Exp1, Exp) :- !,
            s_exp2(List1, List2, Exp2),
            s_exp1(List2, List3, plus(Exp1, Exp2), Exp).
        s_exp1(["-"|List1], List3, Exp1, Exp) :- !,
            s_exp2(List1, List2, Exp2),
            s_exp1(List2, List3, minus(Exp1, Exp2), Exp).
        s_exp1(List, List, Exp, Exp).
        s_exp2([Int|Rest], Rest, int(I)) :-
            trap(I = toTerm(Int),Error,
                exception::clear_fail(Error)),
            !.
        s_exp2([Id|Rest], Rest, var(Id)) :-
            string::isname(Id).
end implement
 
goal
    console::init(),
    my_t::tokl("b=2; if b then a=1 else a=2 fi; do a=a-1 while a;", Ans),
    stdio::write(Ans),
    my_p::s_program(Ans, Res),
    stdio::write(Res).

Load and run this program, then enter the following goal:

goal
    my_t::tokl("b=2; if b then a=1 else a=2 fi; do a=a-1 while a;", Ans),
    my_p::s_program(Ans, Res).

Visual Prolog will return the program structure:

Ans = ["b","=","2",";","if","b","then","a","=","1",
    "else","a","=","2","fi",";","do","a","=","a",
    "-","1","while","a",";"],
Res=program([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))))
    ])
1 Solution

The transformation in this example is divided into two stages: scanning and parsing. The tokl predicate is the scanner; it accepts a string and converts it into a list of tokens. All the predicates with names beginning in s_ are parser predicates. In this example the input text is a Pascal-like program made up of Pascal-like statements. This programming language only understands certain statements: IF THEN ELSE, IF THEN, DO WHILE, and ASSIGNMENT. Statements are made up of expressions and other statements. Expressions are addition, subtraction, variables, and integers.

Here's how this example works:

The first scanner clause, s_program, takes a list of tokens and tests if it can be transformed into a list of statements.

The predicate s_statement_list takes this same list of tokens and tests if the tokens can be divided up into individual statements, each ending with a semicolon.

The predicate s_statement tests if the first tokens of the token list make up a legal statement. If so, the statement is returned in a structure and the remaining tokens are returned back to s_statement_list.

The four clauses of the s_statement correspond to the four types of statements the parser understands. If the first s_statement clause is unable to transform the list of tokens into an IF THEN ELSE statement, the clause fails and backtracks to the next s_statement clause, which tries to transform the list of tokens into an IF THEN statement. If that clause fails, the next one tries to transform the list of tokens into a DO WHILE statement.

If the first three s_statement clauses fail, the last clause for that predicate tests if the statement does assignment. This clause tests for assignment by testing if the first term is a symbol, the second term is "=", and the next terms make up a simple math expression.

The s_exp, s_exp1, and s_exp2 predicates work the same way, by testing if the first terms are expressions and – if so – returning the remainder of the terms and an expression structure back to s_statement.

Summary

These are the important points covered in this tutorial:

Lists can contain an arbitrary number of elements; you declare them by adding an asterisk at the end of a previously defined domain.

A list is a recursive compound object that consists of a head and a tail. The head is the first element and the tail is the rest of the list (without the first element). The tail of a list is always a list; the head of a list is an element. A list can contain zero or more elements; the empty list is written [].

The elements in a list can be anything, including other lists; all elements in a list must belong to the same domain. The domain declaration for the elements must be of this form:

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

where elements = one of the standard domains (integer, real, etc.) or a set of alternatives marked with different functors (int(integer); rl(real); smb(symbol); etc.). You can only mix types in a list in Visual Prolog by enclosing them in compound objects/functors.

You can use separators (commas, [, and |) to make the head and tail of a list explicit; for example, the list

[a, b, c, d]

can be written as:

[a|[b, c, d]] or[a, b|[c, d]] or[a, b, c|[d]] or[a|[b|[c, d]]] or[a|[b|[c|[d]]]] or even[a|[b|[c|[d|[]]]]]

List processing consists of recursively removing the head of the list (and usually doing something with it) until the list is an empty list.

The list predicates can be found in the list class.

Visual Prolog provides a built-in construction, list comprehension, which takes a goal as one of its arguments and collects all of the solutions to that goal into a single list. It has the syntax

Result = [ Argument || myPredicate(Argument) ]

Because Visual Prolog requires that all elements in a list belong to the same domain, you use functors to create a list that stores different types of elements.

The process of parsing by difference lists works by reducing the problem; the example in this tutorial transforms a string of input into a Prolog structure that can be used or evaluated later.

References