Delphi World - ИИ - Урок 5 - Язык Рефал
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
ИИ - Урок 5 - Язык Рефал

Автор: Сотник С.Л.

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

Разработчики языка Рефал делят алгоритмические языки на две группы. Первую группу образуют языки, которые называются языки операторного, или процедурного типа. Элемен-тарными единицами программы являются здесь операторы, т.е. приказы, выполнение которых сводится к четко оп¬ределенному изменению четко определенной части памяти машины. Ти¬пичным представителем этой группы является язык машины Поста. Сюда же относятся машин-ные языки конретных ЭВМ, а также массовые языки программирования типа Фортран, Алгол, ПЛ/1.

Языки второй группы называются языками сентенциального, или дек¬ларативного ти-па (sentence — высказывание, предложение). Программа на таком языке представляется в виде набора предложений (соотношений, правил, формул), которые машина, понимающая данный язык, умеет каким-то образом применять к обрабатываемой информации. Простей¬шим приме-ром сентенциального языка, созданного с теоретическими це¬лями является язык нормальных алгоритмов Маркова.

Можно указать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное накло¬нение (императив, приказание), для сентенциалышх - изъявительное нак¬лонение (описание, повествование). Обращаясь к естествен-ному языку, нетрудно заметить, что "изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное накло-нение предстает в виде некоторой специальной модификации". Таким образом, можно сделать вывод о том, что "относительный вес изъявительного наклонения является мерой развитос¬ти языка".

Язык РЕФАЛ является сентенциальным в своей основе, а вся информа¬ция в этом языке представляется в виде правил конкретизации. Каждое правило записывается в виде предложе-ния, которое представляет собой продукцию с определенными синтаксисом и семантикой. Пред-ложения в Рефал-программе отделяются друг от друга знаком § (параграф).

Каждое правило конкретизации определяет раскрытие смысла некото¬рого понятия через более элементарные. Операцию конкретизации можно также определить как переход от имени к значению. Введем два знака:

k и [], которые будем называть конкретизационными скобками, и кото¬рые будут содер-жать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то kx[]. (конкре-тизация х) будет изображать значе¬ние этой величины. Другой пример: объект k28 +7[] при пра-вильном опре¬делении операции сложения рано или поздно будет заменен на объект 35. Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке Рефал. Эту опера¬цию будет выполнять Рефал-машина (имеется в виду машина на логи¬ческом уровне, имитируемая соответствующим транс-лятором на уни¬версальной ЭВМ; возможно, разумеется, и построение реальной "физи¬ческой" Рефал-машины).

Поскольку правило конкретизации есть указание для замены одного объекта (слова в некотором алфавите) на другой, предложения языка Рефал должны состоять из левой части (за-меняемый объект) и правой части (объект, заменяющий левую часть). Для разделения правой и левой части мы будем использовать знак стрелки "[]".

Пример 3.5. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде

§kX[][]137.

Между знаком § и первым знаком k можно вставлять последовательность знаков, кото-рая будет служить номером предложения, или комментарием к нему, например:

§ l.l kX[][]137. (ф. 27)

Опишем теперь структуру Рефал-машины, которая, используя предло¬жения Рефал-программы, будет выполнять конкретизации. Будем считать, что объектом обработки является некоторое выражение (слово), которое находится в поле зрения машины. Работа машины осуще-ствляется по шагам, каждый из которых представляет выполнение одного акта, конкрети¬зации.

Пусть программа машины состоит из единственного предложения (ф. 27), а в поле зре-ния находится выражение kX[]. Тогда за один шаг машина заме¬нит содержимое поле зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет, и следовательно, делать ей больше нечего.

Так как Рефал-программа содержит, вообще говоря, набор (последова¬тельность) пред-ложений, может оказаться, что для выполнения данной кон¬кретизации пригодно не одно, а не-сколько предложений. Например, в поле памяти, кроме (ф. 27), может находиться еще предло-жение

§ 1.2 kX[][]274.

Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это приня-то в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что Рефал-машина сле-дует идеологии этих алгоритмов): машина просматривает предложения в том порядке, в котором они рас¬положены в Рефал-программе, и применяет первое из них, которое окажет¬ся подходя-щим.

Поле зрения может содержать сколько угодно конкретизационных скобок, причем они могут быть как угодно вложены друг в друга. В этом случае Рефал-машина начинает процесс конкретизации с первого из зна¬ков k, в области действия которого (т.е. в последовательности знаков до парной скобки []) нет ни одного знака k. Выражение, находящееся в об¬ласти этого знака k, последовательно. сравнивается с левыми частями предложений Рефал-программы. Най-дя подходящее предложение, машина выполняет в поле зрения необходимую замену и перехо-дит к следующе¬му шагу конкретизации.

Пример. Пусть Рефал-программа имеет вид

kX[][]137
kX[][]274
kY[][]2
k137+2[][]139,

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

kkX[]+kY[][].

На первом шаге замене подлежит подвыражение kX[] — получим в поле зрения kl37 + kY[][]. Теперь в первую очередь конкретизируется kY[] — получим в результате применения третьего предложения k137 +2[] и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов рабо¬ты машины [21]).

Чтобы иметь возможность представлять обобщенные предложения, ис¬пользуются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В про-стейшем случае переменные записы¬ваются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — пере¬менные, пробегающие в качестве значений выражения. Выражением в язы¬ке Рефал называется последовательность знаков, правильно построенная в соответствеии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкрети-зационных скобках. Выражения строятся из термов.

Пример. Предположим, требуется написать программу, кото¬рая выполняет раскрытие скобок в алгебраических выражениях, построен¬ных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выра¬жение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия ско¬бок надо: раскрыть скоб-ки в e1, раскрыть скобки в е2, полученные резуль¬таты сложить. Эту мысль в компактном, но в то же время и наглядном ви¬де выражает предложение:

§ 2.1 ke1 +e2[][] ke1[] +ke2[]

Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:

— хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),

— ни одно из выражений е1 или е2 не представимо в виде суммы (на¬пример, е = (А * В) * (С * Л)).

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

§ 2.2ke1 * (e2 +e3) [][]ke1 * e2[] +ke1*e3[],
§ 2.3k(e1 +e2) * e3[][]ke1 * e3[] + ke2*e3[] ,
§ 2.4ke1 * (e2 + e3) * e4 [] [] k(e1 * е2 + e1 * e3) * e4[].

Во втором случае по аналогии со сложением имеем

§ 2.5ke1 * е2[] [] ke1[]* ke2[].

Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терми-нальности" символов, что определяют предложения:

§ 2.6k(e) [] [] ke[],
§ 2.7ks[] [] s

(буквы не подлежат конкретизации).

Приведенные семь предложений § 2.1 - § 2.7 решают задачу. Рассмот¬рим как эта про-грамма обрабатывает выражение

k(A +B) * (С +D) []. Последовательно получим в результате работы программы (для удобства слева указыва-ем номер правила, которое непосредственно привело к дан¬ному выражению):

§2.2 k(A +В)*С[]. + k(A +B)*D[],
§2.3 kA *C[] +kB*C[] + k(A+B)*D[],
§2.3 kA *C[] + kB*C[] + kA *D[] + kB*D[].

Далее ограничимся рассмотрением первого слагаемого:

§ 2.5 kA[] * kC[] + ...,
§2.7 A * kC[] + ...,
§ 2.7 А * С + ... .

После аналогичной обработки остальных слагаемых получим искомое выражение

А*С+D*С+А * D + В * D.

Если на вход поступит выражение

kA + (B + С) [],

то получим последовательно:

§ 2.1 kA[] + k(B + С) [],
§ 2.7 А + k (Д + С) [],
§ 2.6 А + kB + C[],
§2.1, 2.7 A + B + С.

Обратите внимание, что если расположить правило § 2.5 перед правила¬ми § 2.2 и § 2.3, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования