Практикум. 
Символический искусственный интеллект: математические основы представления знаний

Контрольные вопросы и задания

• 1. Что такое однородные и неоднородные системы продукций? Приведите примеры.
• 2. Какие частные случаи неоднородных систем продукций используются? Приведите примеры.

Задачи для самостоятельного решения

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

На берегу реки находятся три миссионера и три людоеда. Имеется лодка, которая вмещает не более двух человек. Управлять лодкой могут как миссионеры, так и людоеды. Если возникает ситуация, при которой людоедов в какомто месте строго больше, чем миссионеров, то людоеды немедленно съедают миссионеров. Каким переправиться на другой берег в полном составе?

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

Расставить четыре ферзя на доске 4×4 кчетки так, чтобы они не били друг друга.

Дополнение: язык программирования РЕФАЛ РЕФАЛ — алгоритмический язык рекурсивных функций (REFAL, REcursive Functions Algorithmic Language) — один из наиболее примечательных алгоритмических языков, разработан в нашей стране и получил мировое признание. Язык РЕФАЛ был создан В. Ф. Турчиным в Институте прикладной математики АН СССР в качестве метаязыка для описания семантики других языков. Впоследствии, в результате развития и реализации, язык стал практически использоваться в качестве языка программирования.

История создания и развития:

• • 1966 г. — появление первой версии языка РЕФАЛ, названной «Базисный РЕФАЛ»;
• • 1968 г. — язык переименован в «РЕФАЛ», написан первый интерпретатор, опубликовано детальное описание;
• • 1970 г. — образована РЕФАЛ-группа: сообщество пользователей языка;
• • 1970;е гг. — появление версии РЕФАЛ-2. Создание компиляторов практически для всех отечественных платформ (М220, БЭСМ, СМ, ЕС ЭВМ);
• • 1977 г. — В. Ф. Турчин вынужден был уехать из страны, и на некоторое время РЕФАЛ был предан забвению;
• • 1985 г. — появление версии РЕФАЛ 5;
• • 1990 г. — появление версии РЕФАЛ +.

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

Суперкомпиляция и метавычисления в ИПС им. А. К. Айламазяна. Суперкомпиляция^[1] является одним из методов метавычислений, мощной техникой преобразования программ. Ближайшие аналоги (частичные вычисления, частичная дедукция, смешанные вычисления) являются более изученными методами, но суперкомпиляция стала мощным инструментом, с помощью которого можно решить задачи, не решаемые другими методами. Суперкомпиляция является некоторым видом абстрактной интерпретации, где используется не только полная информация о некоторых аргументах (как в частичных вычислениях), но и частичная информация.

По направлению «суперкомпиляция для языка РЕФАЛ» в 1994—1993 гг. выполнялась разработка основных принципов суперкомпиляции. В 1995 г. был разработан метод расширения входного языка суперкомпилятора с плоского диалекта языка РЕФАЛ до строгого РЕФАЛа, была на практике продемонстрирована способность суперкомпилятора из наивного алгоритма поиска неизвестного образца фиксированной длины автоматически сгенерировать алгоритм Кнута — Морриса — Пратта. В том же году был разработан метод автоматического построения программы, решающей обратную задачу по отношению к заданной программе, разработан язык рекурсивного описания информации о данных специализируемой программы, поддерживающий рекурсивное использование суперкомпилятора. В 1998 г. разработан функциональный язык Мета-РЕФАЛ, ориентированный на метавычисления и реализацию формальных преобразователей программ, реализована первая версия компилятора из Мега-РЕФАЛ в язык РЕФАЛ^[2].

В 1999 г. суперкомпилятор для языка РЕФАЛ был доведен до «реальной экспериментальной версии»: в качестве входных программ он принимал любые реальные программы на языке РЕФАЛ-5. В 2000 г. суперкомпилятор SCPA получил дальнейшее развитие: разработана и реализована первая версия компилятора из языка РЕФАЛ-графов (язык внутреннего представления программ в суперкомпиляторе SCPA) в язык программирования Си (компилятор оптимизирует функции с «хвостовой» рекурсией и позволяет повысить временную эффективность результата суперкомпиляции, в среднем, в пять раз). В 2008 г. начаты работы по графической поддержке интерфейса суперкомпилятора SCPA и адаптации алгоритмов Хмелевского и Маканина решения уравнений в свободной полугруппе для разработки и анализа описания свойств параметризованных РЕФАЛ-конфигураций.

Область применения. РЕФАЛ — это функциональный язык программирования, основными областями применение которого являются:

• • символьные преобразования: обработка символьных строк, перевод с одного языка на другой;
• • аналитические вычисления (системы компьютерной алгебры);
• • разработка трансляторов с языков программирования, когда сам РЕФАЛ используется как метаязык;
• • создание быстро совершенствующихся узкоспециализированных языков программирования (в областях военной техники);
• • эквивалентные преобразования программ, оптимизации исходных текстов программ, суперкомпиляция;
• • искусственный интеллект.

В искусственном интеллекте РЕФАЛ применяется и как конечное средство разработчика, и как инструмент для создания языков представления знаний, ориентированных на конкретные области применения в ИИ. Одним из фундаментальных направлений, позволяющих эффективно использовать мощь РЕФАЛа, является анализ естественных языков. С помощью РЕФАЛа созданы лингвистические процессоры, экспертные системы и т. д.

Особенности и преимущества РЕФАЛа. Сравнивать РЕФАЛ следует с языками того же класса и той же области применения. Наиболее заслуженными языками в этом классе являются ЛИСП и ПРОЛОГ.

Основу РЕФАЛа составляет сопоставление с образцом (унификация). Поскольку это базисная техника для прикладных систем с элементами искусственного интеллекта, то типовая программа на РЕФАЛе вдвое-втрое меньше по объему, чем на ЛИСПе, и вдобавок более читаема.

РЕФАЛ отличает концептуальная простота. Его сопоставление с образцом работает в прямом направлении, а не в обратном (начиная от цели), как в ПРОЛОГе.

РЕФАЛ использует более общие структуры данных (выражения) в отличие от ЛИСПа и ПРОЛОГа, которые применяет только линейные списки.

Основные конструкции. Основными конструкциями языка РЕФАЛ являются символы и выражения, которые делятся па объектные выражения и выражения-образцы.

Символ в РЕФАЛе — это минимальный синтаксический элемент структур данных. Используются следующие виды символов:

• • символы-имена, называемые также идентификаторами, они начинаются с буквы;
• • знаки клавиатуры, они заключаются в кавычки;
• • неотрицательные целые числа (макроцифры) в диапазоне от 0 до 2³² — 1. Числа, превосходящие 2³² — 1, могут быть составлены из макроцифр с использованием основания 2³²;
• • действительные числа. Действительное число в языке РЕФАЛе всегда представлено символом, занимающим одно машинное слово;
• • специальные знаки: структурные скобки «(», «)» — выделение подвыражений, вычислительные скобки «» — вызовы функций.

Выражения. Произвольная последовательность символов, включающая и правильно расставленные скобки, называется объектным выражением.

Примеры выражений:

А (А'+'В) (C'-'D).

Begin (Ho-ho-ho '(' ('A joke')) End.

() (О'ЮО'ЮОО (О)) [[.

Более точно, объектное выражение — это последовательность конечного числа термов, где каждый терм является одним символом либо выражением, заключенным в скобки. Количество термов в выражении может быть и нулем, так что пустое объектное выражение является допустимым.

Выражения-образцы (или просто образцы) РЕФАЛа отличаются от объектных выражений тем, что они могут включать свободные переменные.

Свободные переменные состоят из указателя типа, точки и индекса. Индексом переменной является идентификатор либо целое число. Если индекс является одпобуквенным идентификатором или одноразрядным числом, точка может быть опущена. Идентификатор, используемый как индекс после точки, может начинаться как со строчной, так и с прописной буквы.

Имеется три типа свободных переменных:

• 5-переменные: значением является один символ (любого типа), например, s. 1,.

s. 2;

• •^{-переменные:} любой терм (терм — это либо символ, либо выражение в структурных скобках) t. Head, t. Tail;
• •^{-переменные:} любое выражение, например, el.

Образец можно рассматривать как множество объектных выражений, которые могут быть получены в результате придания допустимых значений всем переменным. Так, образец, А е. 1 представляет множество всех объектных выражений, начинающихся с символа А. Всем вхождениям одной и той же переменной следует придавать одно и то же значение. Образец s. 1 е. 2 s. 1 можно рассматривать как множество всех объектных выражений, которые начинаются и заканчиваются одним и тем же символом и состоят, по крайней мерс, из двух символов.

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

Сопоставление объектного выражения Е с образцом Р в РЕФАЛе обозначается через Е: Р, где двоеточие — еще один специальный знак, знак сопоставления, Е — аргумент, Р — образец операции сопоставления.

Если существует такая подстановка S для переменных в Р, что применение S к Р приводит к Е, то говорят, что сопоставление является успешным, т. е. Е распознается как частный случай Р. Переменные в Р принимают значения, предписываемые подстановкой S. В противном случае сопоставление считаем неудавшимся. Если имеется несколько способов присваивания значений свободным переменным в образце, при которых сопоставление может быть успешно, то выбирается такой способ, при котором самая левая e-перемениая принимает наиболее короткое значение. Если это нс приводит к однозначности, подобный выбор делается для следующей (самой левой)^{-переменной} и т. д. Иными словами, при выполнении распознавания аргумент Е обозревается слева направо и выбирается первое успешное сопоставление Е с Р.

Примеры:

• 1) сопоставление АВС: А е. 1 успешно, переменная е. 1 принимает значение В С;
• 2) сопоставление ('АВС') ' + + ': s .X е. 1 не успешно, поскольку левая

скобка не символ, так что она не может быть сопоставлена с переменной s. X.

Предложения и программы. РЕФАЛ-программа есть перечень функциональных определений. Функциональное определение имеет одну из следующих форм:

• • имя-функции { блок };
• • SENTRY имя-функции { блок }.

Имя функции является идентификатором. Блок есть перечень предложений, разделяемых точками с запятой; последнее предложение также может заканчиваться точкой с запятой.

Предложение имеет вид:

левая-часть = правая-часть, где левая часть является выражением-образцом, а правая часть — общим выражением. Напомним, что объектное выражение может включать только символы и структурные скобки, а выражение-образец может, кроме того, — свободные переменные. Общее же выражение, в дополнение к составляющим выражения-образца, может включать еще вычислительные скобки ««. Они входят в него как части вызовов функций:

.

где имя-функции является идентификатором либо одним из четырех знаков арифметических операций («+» ,"-", «*», и «/»); а аргумент — общим РЕФАЛ-выражеиием. Таким образом, вычислительные скобки могут быть вложенными. Заметим, что имя функции должно следовать непосредственно за открывающей вычислительной скобкой, оно не допускает включения пробелов или конца строки.

Кроме того, в РЕФАЛ-программах могут быть комментарии. Они начинаются с символа * и продолжаются до конца строки.

Абстрактная РЕФАЛ-машина. РЕФАЛ-машиной называется абстрактное устройство (виртуальная машина), которое выполняет РЕФАЛ-программы. Она имеет два потенциально бесконечных хранилища информации: поле программы и поле зрения. Поле программы содержит РЕФАЛ-программу, которая загружается в машину перед запуском и не изменяется в ходе выполнения. Поле зрения хранит выражение без свободных переменных; напомним, что такие выражения называются объектными. Поле зрения (т.е. выражение в этом поле) изменяется в ходе работы машины.

Работа РЕФАЛ-машины осуществляется в пошаговом режиме. Каждый шаг выполняется следующим образом. Если выражение в поле зрения не включает вычислительных скобок (такие выражения называют пассивными), РЕФАЛ-машина приходит к нормальному останову. В противном случае машина выбирает в поле зрения первичное активное подвыражение. Оно определяется как первое (слева) подвыражение, такое, что Е пассивно, т. е. не содержит вычислительных скобок, a F является именем функции из числа функций, определенных в поле программы.

Первичное подвыражение трансформируется следующим образом. РЕФАЛ-машина сравнивает Е с последовательными предложениями из определения F, начиная с первого, осуществляя поиск первого применимого предложения.

Предложение применимо, если Е может быть распознано как его левая часть L, т. е. сопоставление Е: L является успешным. После нахождения первого применимого предложения РЕФАЛ-машина копирует его правую часть R и применяет к ней подстановку, полученную при сопоставлении Е: L. Таким образом, свободные переменные в R замещаются значениями, которые они должны принять для успешного сопоставления. Затем сформированное при этом выражение замещает первичное активное подвыражение в ноле зрения. Этим завершается текущий шаг, и машина переходит к выполнению следующего шага. Если же применимых предложений в определении F не имеется, РЕФАЛ-машина приходит к аварийному останову «Отождествление невозможно».

Кроме функций, определяемых в РЕФАЛе посредством предложений, существует несколько функций, которые не должны (а во многих случаях и не могут) определяться в РЕФАЛе, но могут применяться, поскольку они встроены в систему. К этой категории, в числе прочих, относятся функции ввода-вывода и функции выполнения арифметических операций.

Реализация РЕФАЛ-машины отличается от абстрактной РЕФАЛ-машины тем, что перед просмотром определения функции в поле программы система проверяет, входит ли имя функции в список имеющихся встроенных функций. Если оно обнаружено в списке, активизируется соответствующая подпрограмма, которая выполняет требуемые операции и замещает вызов функции в поле зрения на его вычисленное значение.

Функции. Рассмотрим пример функции, которая меняет символ «+» на «-» в заданной строке. Сначала запишем алгоритм на естественном языке.

Взять первый символ аргумента. Если это «+», то заменить его на «-». В противном случае скопировать первый символ. Теперь применить трансформацию к оставшейся части аргумента так, чтобы результат был дописан к этому символу. Если строка пустая, выходная строка также пуста.

Эта функция на языке РЕФАЛ может быть описана следующим образом (алгоритм 2.10).

Алгоритм 2.10. Пример описания функции на языке РЕФАЛ

* Chpm, Заменить плюс на минус Chpm {.

' + ' е.1 =; * нашли плюс.

s.2 е.1 = s.2; * скопировать символ.

=; } * пустая строка Рассмотрим последовательность вычислений для конкретного примера:

'a'.

'ab'CChpm '+c-+d'>

'ab-'.

'ab-c'.

'ab-c-'.

'ab-c—'.

'ab-c—d'.

'ab-c—d'.

Можно предложить альтернативное решение:

Chpm {.

e.l ' + ' e.2 = e. l ;

e.1 = e. l; }.

В этом случае последовательность вычислений оказывается короче:

'ab-'cChpm 'c-+d^/>

'ab-c—'CChpm 'd'>

'ab-c—d'.

Выполнение программы. PE ФАЛ-программа состоит из набора функций, которые записаны в поле программы. Работа программы заключается в вычислении некоторого рабочего выражения в иоле зрения. Начальное состояние поля зрения всегда имеет вид, где D — некоторая функция, описанная с помощью служебного предложения $ ENTRY (входная точка программы). По соглашению, начальным содержимым поля зрения является, а в программе всегда должна быть функция $ENTRY Go {. }.

РЕФАЛ обеспечивает возможность построения программы из нескольких модулей. Для вызова в одном модуле функции другого в вызываемом модуле функция должна быть снабжена ключевым словом SENTRY перед именем функции (объявлена как входная функция), а вызывающем модуле функция должна быть объявлена как внешняя с помощью объявления вида SEXTRN F1. Пример приведен в алгоритме 2.11.

Алгоритм 2.11. Пример описания программы на языке РЕФАЛ

* Программа:

* вводит одну строку символов.

* с помощью внешней процедуры Input,.

* разбивает строку на слова,.

* переставляет в обратном порядке буквы.

* в каждом слове.

* и печатает полученное выражение процедурой Prout $EXTRN Input, Prout ;

$ENTRY Go { =.

Word {.

e.l ' ' e.2 = cinverse e. l> ' ' ;

}.

Inverse {.

s.a e. l = cinverse e. l> s. a;

}.

Рассмотрим, как будет работать эта программа, если процедура ввода прочитает входную строку 123 45:

' ' >

>

'321 ' >

CProut '321 ' Clnverse '5'> '4' > cProut '321 ' Clnverse > '54' > CProut '321 54' >

Далее произойдет печать 321 54.

Валентин Федорович Турчин, 1931—2010 — советский и американский физик и кибернетик.

Создатель языка программирования РЕФАЛ.

В программировании заложил основы метавычислений, предложив качественно новый метод преобразования и оптимизации программ — суперкомпиляцию.

Первый непобедимый капитан команды КВН, редактор сборника «Физики шутят» (1966). Общественная деятельность, попытки призвать руководителей ЦК КПСС к демократизации общества в конце концов навесили на Турчина ярлык диссидента и вынудили в 1977 г. эмигрировать в США.

• [1] Абрамов С. М., Кондратьев Н. В. Компилятор, основанный на методе частичных вычислений // Некоторые вопросы прикладной математики и программного обеспечения ЭВМ.М.: Изд-во МГУ, 1982.
• [2] Nemytykh А. Р., Pinchuk V. A., Turchin V. F. A Self-Applicable Supercompiler // LectureNotes in Computer Science. 1996. No. 1110. P. 322—337.