Ббк 32. 973-018 г рецензент канд физ мат наук, Ф. А. Мурзин

Расширение абстрактной машины для выполнения альтернатив ЛП

Команда	Пояснение
ALT	выбор подходящего варианта.
ESC	выход из тупиковой ситуации.

Таблица 34


Определение команд ЛП

Формат регистров	Результат
s e (ALT c1 c2 . c) d r	→ s e (c1 . c) (c . d) ((s e (c2 . c) d) . r)
s e (ESC) d Nil	→ Nil e (Esc) d Nil
s‟ e‟ (ESC) d‟ ((s e (c2 . c) d) . r)	→ s e (c2 . c) d r

2. 
   Основы
   

Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви, что по реализации напоминает вариантные записи или объединения в обычных ЯВУ. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном выборе.
Обычно понятие алгоритма и программы связывают с детерминированными процессами. Однако эти понятия не очень усложнятся, если допустить недетерминизм, ограниченный конечным числом вариантов, так что в каждый момент времени из них существует только один вариант.
В любом выражении можно выполнить разметку ветвей на нормальные и тупиковые. Тупики можно связать с различными тэгами и выставить ловушки на заданные тэги. При попадании в тупик формируется значение всей структуры, размещенной внутри ловушки.
Используя тупики и ловушки, можно организовать перебор вариантов до первого беступикового варианта или собрать все беступиковые варианты. Второе можно сделать, используя отображения (map), а первое допускает метод первого подходящего, чо можно реализовать как слегка модифицированный evcon с добавочной ловушкой на прерывание при достижении успеха.
Более сложно обеспечить равновероятность выбора вариантов. Наиболее серьезно возможность такой реализации рассматривалась в проекте языка SETL. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто
формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств атома в языке Lisp. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.

3. 
   Язык декларативного программирования Prolog
   

Prolog является наиболее известным языком логического программирования общего назначения, ассоциируемый с проблемами искусственного интеллекта и компьютерной лингвистики. Он базируется на логике первого порядка и в отличие от обычных языков программирования приоритетно использует декларативность. Логическая программа выражается в терминах отношений, представляемых как факты и правила. Применялся для автоматизации доказательств теорем и разработки экспертных систем, включая лингвистические процессоры для естественных языков. Выполнение логической программы понимается как ответ на запрос над системой отношений. Отношения и запросы конструируются из термов и клауз.
Язык программирования Prolog предложен в 1972 году А. Колмерауэром. (Alain Colmerauer), процедурную интерпретацию языка выполнил Р. Ковальский (Robert Kowalski) и дал еѐ описание в 1973 году, опубликованное в 1974 году. Практичность языка резко возросла благодаря созданию Д. Уорреном (David Warren) компилятора в 1977 году, что приблизило скорость символьной обработки к эффективности языка Lisp.
Существует Pure Prolog в качестве семантического базиса языка, удобного для изучения основных механизмов Prolog-машины.
Итеративные алгоритмы можно программировать как рекурсивные функции.
Prolog-машина ищет ответ на запрос в имеющейся системе отношений и, если находит, то сообщает его.
Опубликованы алгоритмы мета-интерпретатора для языка Pure Prolog, показывающие его самоприменимость и расширяемость.

Определение	Примечание
Factorial (N, F) Factorial (0, 1) Factorial (x+1, F) ← F := Factorial (x, y) * (x + 1)	Функция реализуется двумя клаузами: констатация, что от 0 – значение 1; декларация отношения между значениями функции на соседних числах

Пример 34. Вычисление факториала

Определение	Примечание