- •Лекция №1 Логическая программа: основные конструкции
- •Лекция №2 Программирование баз данных
- •Структурированные и абстрактные данные
- •Логические программы и модель реляционной базы данных
- •Лекция №3 Рекурсивное программирование
- •Построение рекурсивных программ
- •Бинарные деревья
- •Работа с символьными выражениями
- •Лекция №4 Вычислительная модель логических программ
- •Абстрактный интерпретатор логических программ
- •Лекция №5 Теория логических программ Операционная и декларативная семантика. Интерпретация
- •Корректность программы
- •Лекция №6 Анализ структуры термов
- •Типовые предикаты
- •Составные термы
- •Лекция №7 Металогические предикаты
- •Типовые металогические предикаты
- •Сравнение неосновных термов
- •Использование переменных в качестве объектов
- •Доступность метапеременных
- •Лекция №8 Внелогические предикаты
- •Лекция №9 Недетерминированное программирование
- •Недетерминизм с произвольным выбором альтернативы и недетерминизм с неизвестным выбором альтернативы
- •Лекция №10 Неполные структуры данных
- •Лекция №11 Программирование второго порядка
- •Лекция №12 Методы поиска
- •Лекция №13 Нечеткая логика. Обработка нечетких данных
- •Лекция №14 Constraint-пролог: операционная семантика Программирование в ограничениях
- •Лекция №15 Применение логического программирования в задачах искусственного интеллекта. Тест Тьюринга.
- •Лекция №16 Введение в функциональное программирование
- •Лекция №17 Рекурсивные функции и лямбда-исчисление а.Черча
- •Лекция №18 Функциональные языки программирования Свойства функциональных языков
- •Лекция №19 Программирование в функциональных обозначениях Структуры данных и базисные операции
- •Типы в функциональных языках
- •Лекция №20 Представление и интерпретация функциональных программ Программная реализация
Сравнение неосновных термов
Рассмотрим задачу расширения программы явной унификации (программа 10.5) средством проверки на вхождение. Напомним, что проверка на вхождение является частью формального определения алгоритма унификации, которая препятствует унификации переменной с термом, содержащим эту переменную. Для того чтобы выразить это отношение на Прологе, нам потребуется проверка идентичности переменных (а не просто их унифицируемости, так как унифицируемы любые две переменные). Это – металогический тест.
Для этой проверки в Прологе имеется системный предикат ==/2. Цель (X = = Y)? выполнена, если Х и Y – идентичные константы, идентичные переменные или структуры с одним и тем же главным функтором и одинаковой арностью, а для соответствующих аргументов Xи Y структур Х и Y соотношение X= =Y выполняется рекурсивно. В противном случае цель (X = = Y) не выполнена. Например, цель (X = =5) не выполнена (в отличие от цели Х = 5).
Имеется также системный предикат, значение которого противоположно значению предиката = =. Цель Х \ = = Y? выполнена в тех случаях, когда Х и Y не являются идентичными термами.
Предикат \ = == может быть использован в определении отношения not_occurs_in( Sub, Term), истинного, если терм Sub не входит в терм Term. Данное отношение требуется для построения алгоритма унификации с проверкой на вхождение. Предикат not_occurs_in (Sub, Term) является металогическим предикатом, анализирующим структуру. Он используется в реализующей унификацию с проверкой на вхождение программе 10.6, варианте программы 10.5.
unify (Termi, Term2)
Term1 и Term2 унифицируемы с проверкой на вхождение.
unify (X,Y)
var(X), var(Y), X = Y.
unify (X,Y)
var(X), nonvar(Y), not_occurs_in(X,Y), X = Y.
umfy(X,Y)
var(Y), nonvar(X), not_occurs_in(X,Y), Y = X.
unify (X,Y)
nonvar(X), nonvar(Y), constant(X), constant(Y), X = Y.
unify (X,Y)
nonvar(X), nonvar(Y), compound(X), compound(Y),
term„unify(X,Y).
not_occurs_in(X,Y)
var(Y),X\= =Y.
not occurs in (X,Y)
nonvar(Y), constant (Y).
not_occurs_in(X,Y)
nonvar(Y), compound (Y), functor(Y,F,N),
not_occurs_in(N, X, Y).
not_occurs_in(N,X,Y)
N > 0, arg(N,Y,Arg), not_occurs_m(X,Arg), Nl: = N - 1,
not occurs in(N 1 ,X,Y).
not_occurs_in (0, X, Y)
.
term_unify(X,Y) См. программу 10.5.
Программа 10.6. Алгоритм унификации с проверкой на вхождение.
Заметим, что при определении предиката not_occurs_in область определения не ограничена основными термами. Снять подобное ограничение в случае программы 9.2, задающей отношение Subterm, не так просто. Рассмотрим вопрос Subterm (Х,У)?. Он успешно решается программой 9.2 сопоставлением переменной Х терма У
Определим металогический предикат occurs_in (Sub. Term) обладающий требуемыми свойствами.
Наличие предиката = = позволяет использовать программу 9.2, задающую предикат Subterm как основу определения предиката occurs_in. Механизм возврата порождает все подтермы данного терма, и каждый подтерм проверяется на совпадение с переменной. Записью программы является программа 10.7(а).
occurs Jn (Suh, Term)
Sub является подтермом (возможно, неосновного) терма Term.
а: С использованием предиката = =
occurs_.in(X,Term)
subterm (Sub, Term), X = = Sub.
в: С использованием предиката freeze
occurs_in(X,Term)
freeze(X,Xf), freeze(Term, Termf),
subterm (Xf, Termi). subterm (X, Term) См. программу 9.2.
Программа 10.7. Вхождение.
Исходное определение предиката Subterm корректно только для основных термов. Однако добавление типовых металогических тестов, подобных использованным при определении отношения no_occurs_in в программе 10,6, позволяет легко преодолеть это затруднение.