Языки программирования

В качестве языков программирования, используемых дня построе­ния СИИ, наиболее широко используются Си, Лисп, Пролог, Паскаль. Особенно следует отметить языки Лисп и Пролог в первую очередь в силу наличия в них встроенных средств для организации интеллектуальных процедур (унификация, альтернативный поиск, возврат (backtracking), обработка символьной информации, возможности реали­зации функций базы данных). Языки программирования делятся на три класса:

- императивные языки;

- функциональные языки;

- логические языки.

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

Декларативные языкииспользуются для написания спецификаций некоторой предметной области. Спецификация характеризует некото­рое множество объектов предметной области и заданные на нем отно­шения между объектами. Декларативные языки делятся налогическиеифункциональные.

Наиболее важным среди функциональных языков является язык Лисп. Лисп основан на функциональном - исчислении Черча. На его базе разработаны мощные инструментальные оболочки экспертных сис­тем KEE, LOOPS, ART, S.I и др. Такие широко распространенные вер­сии языка Лисп как Интерлисп и Мехлисп имеют развитые редакторы и средства отладки.

Лисп был изобретен в 1956 г. Мак Карта. С момента изобретения Лисп трансформировался с языка чисто символьной обработки в язык общецелевого назначения. Большинство лисповских программ записы­ваются в форме функций: значения одних функций являются аргу­ментами других.

Например, если PLUS - функция сложения, то выражение X + Y по­лучает в Лиспе вид

(PLUS X Y),

а выражение (Х + Y + Z) принимает форму

(PLUS X (PLUS Y Z))

Аргументы и имена функций разделяются запятыми или пробела­ми.

Присваивание в форме X = а имеет вид

(SET X a).

Для записи условных выражений используется функция COND, первый аргумент которой представляет условную часть выражения (часть "ЕСЛИ..."), а второй - операционную часть (часть "ТО..."). Например,

(COND ((ZEROP S) (SET X 5)))

представляет условное выражение, условная часть "ЕСЛИ..." которою соответствует (ZEROP S), а операционная (SЕТ X 5). ZEROP есть функция сравнения с нулем. Приведенное выше выражение проверяет, равно ли S нулю, и в случае положительного результата проверки при­сваивает X значение 5.

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

АТОМ - проверяет, является ли аргумент атомом или списком

NULL - проверяет, является ли аргумент связанной или несвязанной переменной

EQUAL - проверяет равенство двух аргументов

GREATERP - проверяет, что один аргумент больше второго.

Пользователь может определять свои функции с помощью l - выражений Черта, например:

(LAMBDA (A B) (DIFFERENCE (TIMES A A) (TIMES B B)))

здесь А, В - аргументы функции, которая сама имеет следующую струк­туру:

(DIFFERENCT (TIMES A A) (TIMES B B))

где DIFFERENCE - функция вычитания X - Y;

TIMES - функция умножения X * Y.

Таким образом, нетрудно видеть, что приведенное выражение эквивалентно следующему алгебраическому выражению

X² - Y².

Для того, чтобы выражение объявить как функцию, используется новая функция - DEFUNE. В общем случае, если f_i - l-выражение для функции f_i, то ее объявление таково:

(DEFUNE (имя_функции (f_i))

Так, в случае выше имеем следующее объявление функции FUN 1 с двумя аргументами:

(DEFUNE (FUN1 (LAMBDA (A B) (DIFFERENCE (TIMES A A) (TIMES B B))))

Теперь, например, подстановка FUN1 (5 3) дает в результате 16.

Важнейшее место в Лиспе занимают операции над списками, ос­новными из которых являются функции CAR. (выделяющая первый эле­мент списка), CDR (выделяющая остаток списка после удаления перво­го элемента) и CONS (соединяющая два списка).

Например, если:

X есть (2 6 4 7) то (CAR X) есть 2

X есть (3 2 1) то (CDR X) есть (2 1)

X есть ((2 6)(4 7) то (CDR X) есть (4 7)

X есть (5) то (CDR X) есть NIL.

X есть (2 4) и Y есть (6 7), то (CONS X Y) есть ((2 4) (6 7))

NIL - специальное обозначение для "лжи" или пустой список.

Языки программирования, подобные языку Лисп, представляют максимальную гибкость разработчику СИИ, но не подсказывают ему, как представлять знания и строить механизмы их обработки. Это ограни­чение в значительной мере снято в языке Пролог. Язык Пролог "реализует" математическую логику в программировании согласно идее, предложенной А. Кольмероэ и Р. Ковальским. Собственно, Пролог базируется на разновидности исчисления предикатов -так называемом клаузальном исчислении Хорна.

Клоз, это формула вида

"x₁ "x₂ ... "x_s (L₁ Ú ... Ú L_m) (1.48)

где L_i - атомарная формула (литерал), ,

x_j - переменная, входящая вL_i, j = .

Среди атомарных формул L_i выделяют позитивные (без отрица­ния) и негативные (с отрицанием) литералы:

(1.49)

или с учетом эквивалентности имеем

"x₁ ... "x_s (A₁ Ú ... Ú A_k B₁ & B₂ & ... & B_n) (1.50)

Определение. Программнымклозом называется формула

B₁, B₂, ..., B_n A,

содержащая ровно один позитивный литерал А, называемый головным (или просто заголовком). Часть клоза B₁, B₂, ..., B_nназывается телом клоза (запятая, разделяющая литералы В, эквивалентна логической конъюнкции). Как видим из последнего представления, программный клоз - это логическая формула, имеющая форму продукции "ЕСЛИ- ТО", где часть "ЕСЛИ" соответствует телу клоза, а часть "ТО" - заголовку клоза.

Определение. Фактомназывается клоз без тела, т.е. ® А или еще проще: А.

Определение. Логическая программаесть множество программных клозов. Отметим, что логическое программирование можно рассматри­вать как исчисление продукций, каждая индивидуальная логическая программа являет собой продукционную модель знаний.

Определение. Цельюназывается клоз без заголовка:

B₁, B₂, ..., B_n®.

Предикатные формулы B₁, B₂, ..., B_nвходящие в цели, называются под­целями.

Программным представлением клозаявляется следующая форма, называемая правилом:

A(U₁, ..., U_nk):-

B₁ (X₁, ..., X_n1),

B₂ (Y₂, ..., Y_n2),

....

B_m (Z₁, ..., Z_nm),

где символ " :- " стоит вместо "", а символ запятая "," соответствует логической конъюнкции.

Выполнение правила заключается в доказательстве его заголовка (головного литерала). Этот процесс заканчивается в случае успеха нахождением подходящей интерпретации для правила. Для того чтобы доказать головную формулу. Пролог последовательно доказывает каждую формулу в теле правила. Так, чтобы доказать формулу A(U₁, ..., U_nk), последовательно доказываются формулы B₁(...), B₂(...), ..., B_m(...). Для каждой из этих формул B_i(...) в свою очередь имеется множество правил, где B_i(...) является заголовком.

Рассмотрим следующие правила

(1) площадь (X, Y) :-

фигура (X, Y),

write (²X=², X, ²Y=², Y).

(2) фигура (квадрат, ²сторона * сторона²).

(3) фигура (круг, ²p/2 * радиус * радиус²).

(4) фигура (треугольник, ²высота * основание * 1/2²).

(5) фигура (_, ²не известно²).

Пусть целью будет

площадь (круг, Z).

Такая цель означает, что нужно найти значение Z, соответст­вующее площади круга. Пролог пытается сначала нагой правило, в заголовке которого стоит литерал "площадь". В данном случае правило с заголовком указанного вида таково:

(1) площадь (Х, Y) - фигура (Х, Y).

Аргументы обеих формул в этом правиле совпадают и являются пе­ременными (которые принято записывать с заглавных букв). Первый шаг, выполняемый Прологом, это передача значений для X и Y из цели:

Х= круг, Y= Z.

В нашем случае X получает конкретное значение "круг", в то время как запись Y = Zпросто устанавливает факт равенства двух перемен­ных. Как только переменная Y получает значение, Z будет присвоено то же значение. Теперь правило (1) трансформировалось в правило сле­дующего вида:

(1’) площадь (круг, Y):- фигура (круг,Y).

Пролог обязан запомнить вид этого правила, которое равносильно следующей записи:

если (фигура(круг, Y)), то (площадь(круг, Y)).

Теперь Пролог формирует новую цель:

фигура (круг, Y).

Для этой новой цели он ищет подходящее правило. В нашей про­грамме таких правил 4 (правила (2) - (5)). Эти правила имеют усеченный вид: в структуре "если (...) то (...)", как видим, в них отсутствует часть "если (...)". С точки зрения логики это означает, что независимо от исходных условий, записываемых в части "если (...)", эти правила ут­верждают истинность частей "то (...)". Следовательно, доказывать такие правила не надо.

Итак, для цели "фигура (круг, Y)" выбирается правило

фигура (квадрат, "сторона * сторона'').

Как и на первом шаге, выполняется попытка передачи значений переменным. Иначе говоря, получается следующее:

круг = квадрат; Y = " сторона * сторона ".

Учитывая, что "круг" и "квадрат" не переменные (первый символ "к" - не заглавный). Пролог вместо присваивания сравнивает их. Ре­зультат сравнения - "ложь". Следовательно, правило (2) использовать нельзя. Однако, есть еще правила с заголовком "фигура". Поэтому Про­лог выбирает следующее по порядку:

(3) фигура (круг, "p /2*радиус*радиус").

Текущая цель такова:

фигура (круг, Y).

Результат присваивания значений:

круг = круг; Y = "p /2*радиус*раднус".

Цель доказана, поскольку доказывать правило (3) не надо, о чем было сказано выше. Поскольку выше было принято, что Y = Z, то Z ав­томатически получает значение Z = "л /2*радиус*радиус "

Стандартный предикат write выведет найденные значения, напеча­тав:

X = круг, Y = "p /2*радиус*радиус".

Из данного примера мы видим, что выбор подходящего правила для доказательства цели не всегда возможен из-за несоответствия зна­чений параметров.

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

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

Алгоритм интерпретатора Пролога заключается в следующем. Если список целей пуст - работа завершается успехом. Если список це­лей не пуст,' то интерпретатор продолжает работу, выполняя процедуру 'ПРОСМОТР'.

Процедура 'ПРОСМОТР'.Правила программы последовательно просмаливаются от начала к концу до обнаружения первого правила С, такого, что заголовок С сопоставим с первой целью G1. Если такого правила обнаружить не удается, то восстанавливается предыдущий спи­сок целей и для него выполняется процедура 'ПРОСМОТР', начищая с последнего испробованного правила С. Если список целей не пуст, а все правила для первом цели в самом первом списке целей проверены, то алгоритм завершается общей неудачей. Если С найдено и имеет вид

H:- B₁, ..., B_n,

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G₁, ..., G_m.

Пусть С' - это

Сопоставляется G1 с Н'. Пусть S - результирующая конкретизация переменных. В списке G₁, ..., G_m цель G₁ заменяется на список , что порождает новый список целей:

Заметим, что если С - факт, то из списка целей удаляется первая цель G1.

Переменные в новом списке целей устанавливаются согласно интерпретации S, что порождает новый список целей

Старый список L₀ = G₁, ..., G_m, сохраняется, а система переходит к доказательству нового списка L₁, т.е. осуществляет переход к процеду­ре 'ПРОСМОТР'.

Мы обратимся к рассмотрению средств языка Пролог для разработки механизмов СИИ во второй части книги. Читателю потребуется 6азовый набор сведений о системе TURBO-PROLOG 2.0, помещенный в Приложении 2. Чтение этого приложения может быть отложено до гла­вы, посвященной разработке базовых механизмов учебной СИИ во вто­рой части пособия.

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