Лекция: Языки инженерии знаний.
- Характеристика системы OPS5
Возможности языков высокого уровня также не беспредельны — каждый из них имеет свои ограничения. Например, в языке OPS5 возможности динамической памяти ограничены размещением векторов в рабочей памяти, что не позволяет строить в ней рекурсивные структуры данных, такие как графы или деревья. При разработке системы MORE из-за этого возникли серьезные сложности. Некоторые типы структур управления ходом выполнения, например рекурсивные и итерационные циклы, также с трудом реализуются в этом языке. В общем, это та цена, которую приходится платить за относительную простоту программного кода на языке OPS5 и эффективность его выполнения.
В ранних моделях систем, основанных на порождающих правилах, до 90% времени работы уходило на выполнение операций сопоставления условий. Но позднее Форджи обратил внимание на возможные источники низкой эффективности такого упрощенного подхода. Алгоритм сопоставления RETE, предложенный Форджи и реализованный в языках описания порождающих правил семейства OPS, базируется на двух наблюдениях: - В левых частях порождающих правил, которые размещаются в рабочей памяти, часто встречаются повторяющиеся условия. Если одно и то же условие встречалось в N правилах, то при прежнем упрощенном подходе выполнялось N операций сопоставления. Это пример внутрицикловой итерации (within-cycle iteration).
- Простейший подход (в OPS5) при сопоставлении условий предполагает просмотр в каждом цикле всех элементов рабочей памяти, хотя содержимое рабочей памяти от цикла к циклу изменяется очень мало. Форджи назвал это межцикловой итерацией (between-cycle iteration).
Предложенный Форджи алгоритм значительно снижает количество внутрицикловых итераций за счет использования сети сортировки, имеющей древовидную структуру. Выражения в левой части порождающих правил компилируются и включаются в эту сеть, а алгоритм сопоставления довольно просто определяет конфликтующее множество, просматривая состояние сети в текущем цикле. Количество межцикловых итераций сокращается за счет обработки множества лексем, которые являются индикаторами удовлетворения условий, размещенных в рабочей памяти. Это множество лексем отображает изменения, происходящие в рабочей памяти от цикла к циклу, и таким образом позволяет выявить те условия, которые подлежат проверке. Поскольку никаких других процессов управления, кроме цикла распознавание-действие, в системе не существует, то обработать полученное в результате конфликтующее множество не представляет особого труда. Механизм разрешения конфликтов выполняет это, не обращая внимания на другие аспекты текущего контекста вычислений.
Совершенно очевидно, что попытка использовать рекурсивные структуры данных потребует серьезного усложнения описанного процесса обработки правил. Точно так же и изменение режима управления приведет к тому, что механизм разрешения конфликтов вынужден будет анализировать дополнительную информацию. Разработчики языков, подобных OPS, всегда вынуждены искать компромисс между мощностью выразительных средств языка и эффективностью выполнения программного кода. До сих пор в среде исследователей предметом оживленных дискуссий является вопрос о том, удалось ли разработчикам OPS5 найти такой компромисс. Разработанные позже языки КЕЕ, КАРРА и CLIPS унаследовали от OPS5 синтаксис и механизм активизации правил. Все эти языки используют различные версии алгоритма RETE при формировании множества конфликтующих правил.
Преодоление недостатков программирования порождающих правил лежит не на пути усложнения существующих языков программирования, а скорее на пути объединения их с другими парадигмами программирования, позволяющими использовать рекурсивные структуры данных и управления. Примером такого объединения может служить комбинирование порождающих правил и фреймов, что позволяет сопоставлять условия, специфицированные в правилах, с содержимым слотов фреймов. Для решения проблем управления в последнее время все чаще используется включение наборов правил в более мощную.вычислительную среду, которая позволяет работать со списками заявок и с множеством источников знаний .
- Язык логического программирования PROLOG
Пролог (Prolog) — язык логического программирования, основанный на логике дизьюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.
Начало истории языка относится к 70-м годам XX века. Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи, и сам производит поиск решения, пользуясь механизмом бэктрекинга и унификацией.
Встроенный в PROLOG режим управления использует стратегию обратного логического вывода, которая используется в системах, подобных MYCIN. Таблицы знаний и другие данные можно представить с помощью утверждений.Такие структуры данных, как графы и деревья, можно организовать с помощью фраз языка PROLOG, которые содержат комплексные термы. Языковые средства PROLOG позволят программисту разработать собственный механизм обработки неопределенности, причем не исключается и использование коэффициентов уверенности.
С практической точки зрения, пользуясь языком PROLOG, программист в качестве «бесплатного приложения» получает в свое распоряжение следующие возможности:
- индексированную базу данных фраз, которые можно использовать для представления правил, процедур или данных;
- универсальный механизм сопоставления, который позволяет выполнять сопоставление данных и шаблонов, включающих переменные, и возвращать подстановку, которая может обеспечить их совпадение;
- стратегию управления (поиск в глубину — depth-first search), основанную на правилах нисходящего поиска (фразы, которые размещены в базе данных ближе к «голове», обрабатываются первыми) и вычислении слева направо (подцели обрабатываются в том порядке, в котором они перечислены в списке).
Действительно, дедуктивную порождающую систему довольно ПРОСТО эмулировать на языке PROLOG.(как используется эмуляция) Можно без особого труда разработать и простой интерпретатор, реализующий стратегию построения прямой цепочки вывода. Модификация рабочей памяти выполняется операторами assert и retract, которые добавляют или удаляют формулы из базы данных. Вы уже знаете как можно организовать локальное управление ходом процесса в системе, основанной на фреймах, как организовать обработку значений по умолчанию и исключений, хотя эти методы и не вписываются в стандартную логику.
Успешный опыт применения идей логического программирования, в частности создание программы МЕСНО, продемонстрировал ряд явных отклонений от синтаксиса исчисления предикатов первого порядка и его процедурной интерпретации в стандартной версии PROLOG. Некоторые семантические и синтаксические ограничения в программах МЕСНО и PLANNER до сих пор не преодолены в системах, базирующихся на языках логического программирования.
- Язык функционального программирования LISP
Лисп (LISP, от англ. LISt Processing — «обработка списков») — семейство языков программирования, основанных на представлении программы системой линейных списков, которые притом являются основной структурой данных языка. Лисп считается вторым после Фортрана старейшим высокоуровневым языком программирования.
Традиционный Лисп имеет строгую динамическую систему типов, содержит императивные свойства, но в общем поощряет функциональную парадигму программирования. Существует объектно-ориентированное расширение языка — CLOS
Основная особенность Лиспа — представление программы в виде списков — определяет однородность и простоту синтаксиса. Внешне исходный код программы на Лиспе отличается обилием круглых скобок; редактирование программ значительно упрощается использованием текстового редактора, поддерживающего автоматическое выравнивание кода, подсветку соответствующих пар скобок и команды рода «перейти через список вправо». Хорошо приспособлен к кодированию на Лиспе редактор Emacs (большая часть которого написана на Лиспе), кроме того в коммерческих реализациях (например в LispWorks) IDE содержит удобные редакторы, сохраняющие все достоинства Emacs.
Одним из самых распространённых диалектов Лиспа является Common Lisp. Его реализации существуют для большинства платформ. Есть реализации распространяемые свободно под лицензиями, позволяющими использовать Лисп без ограничений в коммерческих приложениях, кроме этого существуют коммерческие реализации, предлагающие дополнительные возможности (IDE, дополнительные библиотеки и т. п.), в том числе техническую поддержку. С полным списком реализаций можно ознакомиться здесь: Common Lisp Implementation.
Синтаксис
Любая программа на Лиспе состоит из последовательности выражений (форм). Результат работы программы состоит в вычислении этих выражений. Все выражения записываются в виде списков — одной из основных структур Лиспа, поэтому они могут легко быть созданы посредством самого языка. Это позволяет создавать программы, изменяющие другие программы или макросы, позволяющие существенно расширить возможности языка.
Список является последовательностью элементов любого рода, в том числе других списков. Например, (1 3/7 'foo #'+) состоит из целого числа, рациональной дроби, символа foo и указателя на функцию сложения. Выражения представляются списками в префиксной записи: первый элемент должен быть формой, то есть функцией, оператором, макросом или специальным оператором; прочие элементы суть аргументы, передаваемые форме для обработки. Функция list возвращает список состоящий из ее аргументов: например, (list 1 3/7 'foo #'+) возвращает список, упомянутый ранее. Если некоторые элементы являются выражениями, то сначала вычисляется их значение: (list 1 2 (list 1 2)) возвращает (1 2 (1 2)). Арифметические операторы действуют так же, например (+ 4 (* 2 3)) выдаёт 10.
Специальные операторы позволяют управлять последовательностью вычислений. С их помощью реализуются ветвление и циклы. Оператор if позволяет вычислить одно из двух выражений в зависимости от выполнения условия, которое тоже является выражением. Если его результат не nil, то вычисляется первый аргумент, иначе вычисляется второй. Например, (if nil (list 1 2 «foo») (list 3 4 «bar»)) всегда возвращает (3 4 «bar»).
Примеры
Пример куина (программы, выводящей свой исходный код) на Лиспе:
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))
Данная программа должна работать на большинстве диалектов Лиспа, в том числе и на Scheme.
Итеративная версия функции определения N-го числа Фибоначчи:
(defun fibonacci (x)
(if (= x 0)
1
(loop with result = 1
with prev = 1
for i from 0 below (1- x)
do (psetq result (+ result prev) prev result))))