Искусственный интеллект и экспертные системы

     Основные идеи  Smalltalk’а Основными идеями Smalltalk’а являются:

«Всё — объекты». Строки, целые числа, логические значения, определения  классов, блоки кода, стеки, память —  всё представляется в виде объектов. Выполнение программы состоит из посылок сообщений между объектами. Любое сообщение может быть послано  любому объекту; объект-получатель определяет, является ли это сообщение правильным, и что надо сделать, чтобы его  обработать.

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

Динамическая типизация  — это означает, что вы не указываете типы переменных в программе, что  делает язык гораздо лаконичней. (Как  объяснено выше, является ли операция правильной, определяет объект-получатель, а не компилятор).

Model-view-controller (MVC) шаблон структуры пользовательского интерфейса. (В последнее время используют и другие концепции реализации пользовательского интерфейса — например, Morphic в Squeak и Pollock в VisualWorks).

Dynamic translation: современные коммерческие виртуальные машины компилируют байткоды в машинные коды для быстрого выполнения.

 

Smalltalk также использует другие современные идеи:

Сборка мусора встроена в  язык и незаметна разработчику

Программы Smalltalk’а обычно компилируются в байткоды и выполняются виртуальной машиной (ВМ), что позволяет выполнять их на любом оборудовании, для которого существует ВМ.

 

    Одной из неожиданных  особенностей Smalltalk’а является то, что традиционные конструкции: if-then-else, for, while, и т. д. не являются частью языка. Все они реализованы с помощью объектов. Например, решение принимается с помощью посылки сообщения ifTrue: логическому объекту, и передаёт управление фрагменту кода если логическое значение истинно. Есть всего три конструкции:

посылка сообщения объекту;

присваивание объекта  переменной;

возвращение объекта из метода;

 и несколько синтаксических  конструкций для определения  литеральных объектов и временных  переменных.

    Чтобы лучше  понять, как работает механизм  обмена сообщениями, можно представить  каждый объект как веб-сервер, отвечающий на запросы. При  этом, на запросы можно просто выдавать заранее предопределённый ответ, аналог этому — выдача веб-страницы, расположенной по определённому пути; можно перенаправить запрос-сообщение другому объекту, аналог — прокси-сервер; изменить запрос по определённым правилам, аналог — техника url rewriting. Если для реакции на сообщение нет предопределённого метода, то вызывается метод #doesNotUnderstand:, так же, как веб-сервер открывает страницу с сообщением об ошибке, если задан несуществующий путь к веб-странице.

    Следующий пример  показывающий нахождение гласных  в строке иллюстрирует стиль  Smalltalk’а. Символ ( | определяет переменные, : определяет параметры, а символы [ и ] можно, для начала, воспринимать, как аналог фигурных скобок { и } в С-подобных языках:

 

 | aString vowels |

 aString := 'This is a string'.

 vowels := aString select: [:aCharacter | aCharacter isVowel].

    В последней строке посылается сообщение select: с аргументом в виде блока кода. Дальше идёт код в суперклассе Collection который выполняет работу:

| newCollection |

 newCollection := self species new.

 self do: [:each |

(aBlock value: each)

 ifTrue: [newCollection add: each]].

 ^newCollection

    Он отвечает  на сообщение путём перебора  своих элементов (это метод  do:) выполняя код aBlock для каждой буквы; когда выполняется aBlock (aCharacter isVowel) он создаёт логическое значение, которому затем посылается ifTrue:. Если это значение true, буква добавляется в возвращаемую строку. Из за того что select определён в абстрактном классе Collection, мы также можем использовать его так:

 | rectangles aPoint|

 rectangles := OrderedCollection

 with: (Rectangle left: 0 right: 10 top: 100 bottom: 200)

 with: (Rectangle left: 10 right: 10 top: 110 bottom: 210).

 aPoint := Point x: 20 y: 20.

 collisions := rectangles select: [:aRect | aRect containsPoint: aPoint].

    История

    Smalltalk был создан группой исследователей возглавляемой Аланом Кэйем в исследовательском центре Xerox PARC. Первая реализация, известная как Smalltalk-71, была создана за несколько месяцев как результат спора о том, что язык программирования, основанный на идее посылки сообщений, подсказанной Симулой, должен реализовываться на «странице кода». Более поздняя версия, действительно использованная для исследовательской работы, известна сейчас как Smalltalk-72. Его синтаксис и модель исполнения сильно отличались от современного Smalltalk’а, настолько, что его надо рассматривать как другой язык. После существенных переработок которые зафиксировали несколько сторон семантики выполнения для увеличения эффективности, была создана версия известная как Smalltalk-76. В этой версии добавились наследование, синтаксис более близкий к Smalltalk-80, и среда разработки включающую большинство инструментов знакомых сейчас Smalltalk-ерам. В Smalltalk-80 были добавлены метаклассы, что делало фразу «всё объекты» истинной путём связывания с индивидуальными классами свойств и поведения (например, поддержки различных способов создания экземпляров). Smalltalk-80 был первой версией доступной за пределами PARC, сначала как Smalltalk-80 Version 1, розданной небольшому количеству компаний и университетов для «экспертной оценки». Позже (в 1983) общедоступная реализация, известная как Smalltalk-80 Version 2, стала доступна как образ (независимый от платформы файл содержащий объекты) и спецификации виртуальной машины. Сейчас существует две реализации Smalltalk, являющихся прямыми потомками Smalltalk-80. Это Squeak и VisualWorks. Как выглядел Smalltalk-80 можно увидеть на скриншоте. Образ Smalltalk-80 version 2 запущен на Hobbes, виртуальной машине ST-80 реализованной на VisualWorks.

5.3 Языки инженерии знаний. Характеристика системы 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.