Тема 3 Использование структур данных Часть 1 Преподаватель –Юлия Александровна Грачёва

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

Сложную структуру обычно представляют в виде дерева, в котором каждому функтору соответствует вершина, а компонентам – ветви. Каждая ветвь может указывать на другую структуру, так что мы можем иметь структуры внутри структур.

В английском языке имеется очень простое синтаксическое правило построения предложений: предложение состоит из существительного, за которым следует глагольная группа. В свою очередь глагольная группа состоит из глагола и другого существительного. Это отношение между частями предложения может быть описано следующей структурой Используя Пролог, можно заставить ЭВМ «понимать» некоторые простые предложения.

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

Список – это любой пустой список, не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента 'а' есть.(а, [])

Аналогично список, состоящий из атомов a, b и с, мог бы быть записан как.(а,.(b,.(с,[]))), что изображается следующим образом:

Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[ ] и а.(b.(с[]))). Второй список можно было бы записать просто как а.b.с.[], так как функтор точка – право ассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.b отличается от списка b.а.

Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка. Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Упоминавшиеся выше списки могут быть записаны в виде [а] и [а, b, с]. Списки могут содержать другие списки или переменные. Примеры: [] [mister, benks, [like, watch, tv]] [а, V1, b, [X, Y]]

Переменные, входящие в списки, ничем не отличаются от переменных в любой другой структуре. Они в любой момент могут быть конкретизированы, так что их использование может «застолбить пустые места» в списке, которые впоследствии могут быть заполнены данными. Работа со списками основана на расщеплении их на голову и хвост списка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'.

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

Список ГоловаХвост [а, b, с]а[b, с] [а,]а[] [] [[this, cat], eat][this, cat][eat] [this, [cat, eat]]this[cat, eat]] [this, [cat, eat], mouse]this[cat, eat], mouse] [X+Y, х + y]X + Y[x + y]

В Прологе введена специальная форма для записи списка с головой X и хвостом Y: [X|Y], где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, a Y – с хвостом. p([1, 2, 3]). p([this, cat, seat, [on, these, sofa]]). ?- p([X|Y]). X = 1 Y=[2,3] ; X= this Y=[cat, seat, [on, these, sofa]] ?- p([_,_,_,[_|X]]). X=[these, sofa]

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

Список 1Список 2Конкретизация [X, Y, Z] [you,like,fish] X= you Y= like Z = fish [fox] [X| Y] X= fox [X, Y | Z] [i,watch,tv] X = i Y = watch Z = [tv] [[this, Y]|Z] [X, ball], [is, here]] X = this Y = ball Z = [[is, here]] [X, Y|Z, W] (синтаксически некорректная конструкция списка) [horse, X] [black, horse] (сопоставление невозможно) [black | Q] [P | horse]P = black Q = horse Как видно из последнего примера, используя скобочную форму записи списков, можно создавать структуры, похожие на списки, но не заканчивающиеся пустым списком.

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

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

Для определения истинности предиката надо проверить два условия. Первое условие говорит, что X будет элементом списка Y, если X совпадает с головой списка Y. Этот факт записывается следующим образом: belong (X,[X |_]). Эта запись констатирует, что X – это элемент списка, который имеет X в качестве головы. Мы использовали анонимную переменную '_' для обозначения хвоста списка потому, что хвост списка в этом факте не используется. Это правило могло бы быть записано и по- другому: belong(X,[Y|_]:- X = Y.

Второе правило говорит о том, что X принадлежит списку, если он входит в хвост этого списка, обозначаемый через Y. Тут удобно использовать тот же самый предикат принадлежит для того, чтобы определить, принадлежит ли X хвосту списка. В этом и состоит суть рекурсии. На Прологе это выглядит так: belong(X,[_ |Y]):- belong(X,Y). и констатирует, что X является элементом списка, если X является элементом хвоста этого списка. Поскольку нас не интересует имя переменной, обозначающей голову списка, используется анонимная переменная '_.

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

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

belong(Х, [X | _]). belong(Х,[_|Y]):- принадлежит (X,Y). ?- belong(d,[a,b,с,d,e,f,g]). yes ?- belong(2,[3,a,4,f]). no Важно помнить, что каждый раз, когда при согласовании принадлежит с базой данных выбирается второе утверждение этого предиката, Пролог рассматривает рекурсивное обращение к предикату принадлежит как попытку найти соответствие для некоторой новой его «копии».

Предикат принадлежит представляет практически наименьший полезный пример рекурсивного предиката: определение предиката принадлежит содержит утверждения, которые могут быть проверены с помощью только его самого. Рекурсивные определения часто встречаются и полностью равноправны с другими определениями. Но надо быть осторожным, чтобы не допускать «закольцованные» определения: parent(X,Y):- child(Y,X). child(A,B):- parent(B,A).

Есть важная проблема, на которую следует обращать внимание в рекурсивных определениях; это лево- сторонняя рекурсия. Она возникает тогда, когда правило порождает подцель, по существу эквивалентную исходной цели, которая явилась причиной использования этого правила. dog(X):- dog(Y), master (Х,Y). dog(adalat). ?-dog(X). Сначала применили бы правило, рекурсивно породив подцель dog (Y). Попытка найти ей соответствие вновь привела бы к выбору первого правила и породила бы еще одну новую эквивалентную подцель.

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

Решение проблемы с зациклившейся задачкой: dog(adalat). dog(X):- dog(Y), master (Х,Y). ?-dog(X). Есть хороший эвристический принцип: помещать, где это возможно, факты перед правилами. Иногда при размещении правил в некотором конкретном порядке может возникнуть ситуация, когда они будут правильно работать для целей одного вида и не будут работать для целей другого вида.

Пример list([A|B]):- list(B). list([]). Если задаются вопросы типа ?- list([a,b,c,d]). ?- list([]). ?- list(f(1,2,3)) всё работает корректно. Если вопрос ?- list(X). программа зациклится.

Рассмотрим программу на Прологе, которая в ответ на введенное предложение (на английском языке) печатает предложение, являющееся преобразованным исходным предложением. Вот пример диалога: Вы: you are a doctor (Вы - врач) Пролог: i am not a doctor (Я – не врач) Вы: do you speak french (Вы говорите по-французски?) Пролог: no i speak german (Нет, я говорю по-немецки)

Для этого достаточно просто последовательно выполнять следующие действия: 1. Ввести предложение, набранное пользователем на терминале. 2. Заменить каждое вхождение слова you на слово i. 3. Аналогичным образом заменить are на am not. 4. Заменить french на german. 5. Заменить do на nо. Если применить данную схему преобразования к надлежащим образом подобранным предложениям, подобным использованным в приведенном выше диалоге, то получим осмысленные преобразованные предложения.

Программа на Прологе, преобразующая предложение английского языка в другое, реализуется так. Между исходным предложением и преобразованным имеется отношение. Определим предикат new (преобразовать). new(Х, Y) значит, что предложение X может быть преобразовано в предложение Y. Предложения X и Y удобно представлять в виде списков атомов, обозначающих слова, так что предложения могут быть записаны следующим образом: [this,is,a,sentence] (это некоторое предложение).

Если исходный список пуст, то пустой список преобра- зуется в пустой список: new([], []) Основные действия предиката new: 1. Заменить голову входного списка соответствующим словом и поместить это слово в выходной список в качестве головы. 2. Преобразовать хвост входного списка и сделать его хвостом выходного списка. 3. Если мы достигли конца входного списка, то к выходному списку больше ничего добавлять не надо, и мы можем завершить выходной список пустым списком [].

Переводя это на язык, более близкий к Прологу, можно сказать: Преобразование списка с головой H и хвостом T дает список с головой X и хвостом Y, если замена слова H дает слово X, а преобразование списка T дает список Y. Теперь следует сказать, что значит «заменить» одно слово на другое. Это может быть сделано при наличии в базе данных фактов вида change(Х, Y), означающих, что слово X может быть заменено словом Y. В конце базы данных следует поместить факт-«ловушку», так как если слово не заменяется другим словом, то его следует заменить самим собой. Роль такого факта-ловушки выполняет факт change(Х,Х), который обозначает, что слово X заменяется самим собой.

База знаний: change(уоu,i). change(аrе, [am,not]). change(french,german). change(dо,nо) change(Х,Х). /* это факт-ловушка */ new([],[]). new([Н|T],[X|Y]):-change(Н, X), new(Т,Y). ?- new([уоu,are,a,computer],Z). Z = [i,[am,not], a, computer]

Факты, подобные факту new ([],[]) и факту-ловушке change(Х,Х), часто включаются в программу, когда требуется проверить выполнение граничных условий. Выход на граничные условия происходит тогда, когда входной список становится пустым и когда оказываются просмотренными все факты для предиката change. В обоих случаях выхода на граничные условия необходимо выполнить определенные действия. Когда входной список становится пустым, необходимо завершить выходной список (вставив пустой список в его конец). Если просмотрены все факты для предиката change, но при этом не обнаружен факт, содержащий данное слово, то это слово должно остаться неизменным (путем замены его самим собой).