5: Сентенциальное программирование: Рефал

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

рефал  — предметно-эквациональный способ определения функций на свободном моноиде с дополнительной одноместной операцией.

 

(А. П. Бельтюков. Определение Рефала для чистых математиков.)

Рефал—замечательный язык!На нем можно запрограммировать все, что угодно, если, конечно, других языков не знать.

 

Студент УдГУ

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

действия глобальны, условия глобальны. (5.1)

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

В имеющихся сейчас двух наиболее развитых и альтернативных системах сентенциального программирования Prolog и Рефал при распознавании условий происходит еще и подготовка информации для применения перестройки. Эта особенность —

подготовка информации для действий в ходе распознавания условий, (5.2)

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

В настоящее время глобальная проверка условий в системах сентенциального программирования осуществляется путем обработкиметавыражений. Метавыражение отличается от выражения тем, что в нем встречаются переменные. Например, если маленькими буквами обозначаются постоянные, а большими -- переменные, то 1+а -- выражение, 1+X -- метавыражение. При проверке выясняется возможность отождествить некоторые метавыражения друг с другом или с данными и попутно вычисляется подстановка, т. е. функция, сопоставляющая переменным их значения. подстановка дает необходимую для выполнения шага работы программы информацию. В только что приведенном примере при отождествлении вместо X должно быть подставлено а.

Такой способ работы согласуется с формулировкой глобальных условий в логике и в теории алгоритмов, но его нельзя считать a prioriисчерпывающим. В дальнейшем могут появиться другие формы глобальной проверки данных.

Конкретизация

Язык Рефал был создан В. Ф. Турчиным для программирования символьных преобразований. Исходный толчок он получил от идеиалгорифмов Маркова (см., например, теоретическое приложение к книге [ 21 ] ), но эта идея была полностью пересмотрена в ходе работы по созданию языка. Идейный и математический уровень проработки языка исключительно высокий, но вопросы дизайна почти проигнорированы.

В основе языка лежит (другой по сравнению с языком PROLOG) частный случай операции отождествления: конкретизация метавыражения.

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

Язык Рефал определен через три компонента: структуру данных, Рефал -машину, обрабатывающую эти данные, и собственно конкретный синтаксис языка.

Структура данных

Данные, обрабатываемые языком Рефал, представляют собой последовательности атомов, структурированные несколькими согласованными между собою видами скобок. Например, в некотором конкретном синтаксисе такое выражение могло бы иметь вид {a+[b-(c+d)**2]/3}*(a+d). В поле памяти Рефал -машины задействованы два вида скобок: структурные и функциональные.

Выражения языка Рефал.

1. Атомы являются выражениями.
2. Любая последовательность выражений является выражением.
3. Выражение E, заключенное в структурные скобки, является выражением. Атомы и выражения в структурных скобках носят общее имятермов.
4. Если E — выражение, A — описанный в программе атом, AE, заключенное в функциональные скобки, является выражением (называемым функциональным выражением ). A называется детерминативом этого выражения.

В конкретном синтаксисе Рефала функциональные скобки обозначаются < >, структурные -- ( ). Атомы делятся на:

1. Символы (байты, простые символы).
2. Составные символы (имена, определенные в программе) представлены идентификаторами, начинающимися с большой буквы.
3. Целые числа без знака, меньшие 2³², например, 123456789.
4. Действительные числа, например, 123456789.E-5.

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

Дадим точные определения.

Объектное выражение — выражение, не содержащее функциональных скобок.

Минимальное функциональное выражение — выражение, имеющее вид <E>, где E — объектное выражение.

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

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

Детерминатив — первый символ в функциональной скобке.

Детерминатив интерпретируется как имя функции, обрабатывающей содержимое функциональных скобок. Эта функция должна определяться статически, поэтому в ходе вычислений не могут образовываться выражения вида < <e.1> e.2>. В подавляющем большинстве случаев детерминатив должен быть именем, но некоторые обычные символы, например +, также могут использоваться в качестве детерминативов.

Пример 5.2.3. Рассмотрим пример памяти Рефал -машины в ходе вычислений.

Поле памяти:

'aaxzACDE' <Sort < Perm 'G'1.5E5 > <Perm 115 'F'> <Perm 112 -2.0E-5>><Sort AllRight Sort Perm 'QRTS'>'XZ<(')

Поле зрения выделено в поле памяти жирным шрифтом. Заметим, что в поле памяти можно выделить данные, обработка которых уже завершена и которые не изменятся до конца исполнения программы (те, которые находятся вне программных скобок; в нашем случае'aaxzACDE' и 'XZ<('). У символов, представляющих скобки, есть 'обычные' двойники, не обязательно имеющие парные и не влияющие на структурирование выражения. Первый атом Perm стоит в позиции функции, а последний из атомов Perm стоит в позиции данных, так что имена функций могут формироваться³ динамически. При записи программы пробелы, если они не находятся внутри символьных констант, игнорируются, за исключением тех, которые отделяют один символ от другого (эти пробелы просто опускаются после того, как на этапе лексического анализа сыграли роль разделителей). И, наконец, еще одна тонкость. 123 — это один атом, '123' — три атома,-123.0 — опять один атом, -123 — два атома: символ '-', после которого стоит число.

Кроме основной части поля памяти, в ходе исполнения может появиться несколько стеков закопанных выражений, например:

Stack1 '=' 15  Stack2 '=' Perm B A
           21             Perm C2 C1
          -45             Perm 'X' 20
           60

В принципе, несколько стеков — избыточная конструкция. Но, поскольку здесь стеки рассматриваются как общие области памяти, лучше в каждом модуле иметь свой стек. К сожалению, явной связи между стеками и модулями в Рефал -программах нет.

Допустим, есть строка < AB(CD)(E)F>. Она во всех известных нам Рефал -системах представляется двунаправленным списком, изображенным на рис. 5.1. Этот формат представления стал общераспространенным для Рефал -систем, начиная с реализации, описанной в[ 25 ] . Однако он не является обязательным.

Рис. 5.1. Реализация структуры данных Рефала

При реализации языка Рефал В. Ф. Турчин задумался, как избежать слишком частых обращений к каким-то суррогатам возможностей традиционных языков. Он решил заранее описать алгоритм преобразования выражений и подобрать для него подходящую структуру данных. Описанный им алгоритм хорошо работает с целым классом случаев, включая те, которые заранее не предусматривались, — отличительный признак концептуально продуманного решения. В лекции, относящийся к языку PROLOG можно увидеть, что происходит, если структуру данных хорошо не продумать на ранних этапах, а тем более зафиксировать случайные промежуточные результаты как стандарт.

Более того, описанные Турчиным алгоритм и структуры данных являются отличной базой для точного определения семантики на базеабстрактного синтаксиса языка Рефал.

Преобразование выражений в формат для обработки делается один раз, при вводе информации либо при трансляции программы.

Рассмотрим конкретный синтаксис выражений.

Идентификатор — любая последовательность цифр и букв, начинающаяся с большой буквы. Об этом говорит сайт https://intellect.icu . Идентификатор является символьным литералом и представляет составной символ. Символы, заключенные в одинарные ' ' кавычки, являются символьными литералами, представляют сами себя. Дважды повторенная кавычка представляет кавычку. Двойные кавычки " " используются для ограничения имени составного символа, не обязательно являющегося идентификатором⁴. Если вне кавычек встречается символ, не являющийся скобкой, частью идентификатора или числа, это трактуется как ошибка.

Определение метавыражения Рефала получается из определения выражения добавлением еще одного базисного случая: переменная является метавыражением.Переменные не могут быть детерминативами.

Метавыражение называется образцом, если оно не содержит функциональных скобок.

В конкретном синтаксисе обозначение переменной включает тип и символ переменной, записываемые как тип.атом. В стандартномРефале имеются переменные трех типов: символьные ( s.First ), термовые ( t.Inner ) и общие ( e.Last ).

Значением символьной переменной служит атом, термовой — терм (символ или выражение в скобках), общей — произвольное (может быть, пустое) объектное выражение.

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

Модель вычислений и Рефал-программа

Основные два шага в Рефал -вычислениях — конкретизация переменных в образце в соответствии с областью зрения и подстановкаполученных значений в другое метавыражение. В языке рассматривается лишь частный случай конкретизации.

Конкретизация образца Me в объектное выражение E называется такая подстановка значений вместо переменных Me, что после применения данной подстановки Me совпадет с E .

Заметим, что одно и то же метавыражение может иметь много конкретизаций в одно и то же объектное выражение. Например, рассмотримметавыражение

e.Begin s.Middle e.End                 (5.3)

и объектное выражение

AhAhAh 'OhOhOh' (Ugu','Udgu) '(((' Basta'!'
                                       (5.4)

Имеется 11 вариантов конкретизации (5.3) в (5.4) (проверьте!).

Если у метавыражения Me есть много вариантов конкретизации в E, то они упорядочиваются по предпочтительности в следующем порядке.

Пусть Env1 и Env2 — два варианта конкретизации Me в P. Рассмотрим все вхождения переменных в Me. Если Env1 и Env2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной, которому Env1 и Env2 приписывают разные значения и сравним длину этих значений. Та из конкретизаций, в которой значение, приписываемое данному вхождению переменной, короче, предшествует другой и имеет приоритет перед ней.

Например, сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом e.1 (e.X s.A e.Y) e.2. В результате получится следующее множество вариантов сопоставления:

{e.1 = ,           eX = ,      sA = A1, eY = A2 A3, e.2 = (B1 B2) }
{e.1 = ,           eX = A1,    sA = A2, eY = A3,    e.2 = (B1 B2) }
{e.1 = ,           eX = A1 A2, sA = A3, eY = ,      e.2 = (B1 B2) }
{e.1 = (A1 A2 A3), eX = ,      sA = B1, eY = B2,    e.2 =         }
{e.1 = (A1 A2 A3), eX = B1,    sA = B2, eY = ,      e.2 =         }

Варианты сопоставления перечислены в соответствии с их приоритетами, т. е. самый первый вариант находится на первом месте и т. д. Описанный способ упорядочения вариантов сопоставления называется сопоставлением слева направо.

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

Алгоритм для сопоставления объектного выражения E с образцом P в Рефал-5.

Вхождения атомов, скобок и переменных будут называться элементами выражений. Пропуски между элементами будут называтьсяузлами. Сопоставление E: P определяется как процесс отображения, или проектирования, элементов и узлов образца P на элементы и узлы объектного выражения E. Графическое представление успешного сопоставления приведено на рис. 5.2. Здесь узлы представлены знаками o.

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

Общие требования к отображению P на E (сопоставлению E : P)

1. Если узел N2 расположен в P правее узла N1, то проекция N2 в E может либо совпадать с проекцией N1, либо располагаться справа от нее (линии проектирования не могут пересекаться).
2. Скобки и атомы должны совпадать со своими проекциями.
   

   
   Рис. 5.2. Сопоставление E : P является отображением P на E. Здесь объектным выражением E является 'A'((2'B'))'B', а образцом P является 'A'(e.1 t.2)s.3
    
3. Проекции переменных должны удовлетворять синтаксическим требованиям их значений; т. е., быть в соответствии с типом переменной атомами, термами или произвольными выражениями. Различные вхождения одной переменной должны иметь одинаковые проекции.

Предполагается, что в начале сопоставления граничные узлы P отображаются в граничные узлы E. Процесс отображения описывается при помощи следующих шести правил. На каждом шаге отображения правила 1–4 определяют следующий элемент, подлежащий отображению; таким образом, каждый элемент из P получает при отображении уникальный номер.

Правила отображения

1. После того как отображена скобка, следующей подлежит отображению парная ей скобка.
2. Если в результате предыдущих шагов оба конца вхождения некоторой переменной для выражений уже отображены, но эта переменная еще не имеет значения (ни одно другое ее вхождение не было отображено), то эта переменная отображается следующей. Такие вхождения называются закрытыми e-переменными. Две закрытые e-переменные могут появиться одновременно; в этом случае та, что слева, отображается первой.
3. Вхождение переменной, которая уже получила значение, является повторным. Скобки, атомы, символьные и термовые переменные и повторные вхождения переменных для выражений в P являются жесткими элементами. Если один из концов жесткого элемента отображен, проекция второго конца определена однозначно. Если Правила 1 и 2 неприменимы, и имеется несколько жестких элементов с одним спроектированным концом, то из них выбирается самый левый. Если возможно отобразить этот элемент, не вступая в противоречие с общими требованиями 1–3, приведенными выше, тогда он отображается, и процесс продолжается дальше. В противном случае объявляется тупиковая ситуация.
4. Если Правила 1–3 неприменимы и имеются несколько переменных для выражений с отображенным левым концом, то выбирается самая левая из них.Она называется открытой e-переменной. Первоначально она получает пустое значение, т. е. ее правый конец проектируется на тот же узел, что и левый. Другие значения могут присваиваться открытым переменным через удлинение (см. Правило 6).
5. Если все элементы P отображены, это значит, что процесс сопоставления успешно завершен.
6. В тупиковой ситуации процесс возвращается назад к последней открытой e-переменной (т. е. к той, что имеет максимальный номер проекции), и ее значение удлиняется; т. е. проекция ее правого конца в E продвигается на один терм вправо. После этого процесс возобновляется. Если переменную нельзя удлинить (из-за Общих требований 1–3), удлиняется предшествующая открытая переменная, и т. д. Если не имеется подлежащих удлинению открытых переменных, процесс сопоставления не удался.

На рис. 5.2 сопоставление производится следующим образом. Вначале имеется два жестких элемента с одним отображенным концом: 'A'и s.3. В соответствии с Правилом 3 отображается 'A', и этот элемент получает при отображении номер 1.Номера 2 и 3 будут назначены левой и правой скобкам согласно Правилам 3 и 1. Внутри скобок начинается перемещение справа налево, так как t.2 является жестким элементом, который может быть отображен, в то время как значение e.1 еще не может быть определено. На следующем шаге обнаруживается, что e.1 является закрытой переменной, чью проекцию не требуется обозревать для того, чтобы присвоить ей значение; что бы ни было между двумя узлами, это годится для присвоения (на самом деле, значение e.1 оказывается пустым). Отображение s.3завершает сопоставление. Расположение отображающих номеров над элементами образца дает наглядное представление описанного алгоритма:

1  2  5   4  3  6
'A' ( e.1 t.2 ) s.3

Этот сложный алгоритм упрятан в простые программные конструкции.

Программа на Рефале является последовательностью определений функций. Каждое описание функции в Рефале имеет вид

Имя функции {Последовательность сопоставлений}

Каждое сопоставление имеет вид

Образец = Метавыражение;

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

Пример 5.3.2. Рассмотрим пример Рефал -программы.

Pre_alph {
*1. Отношение рефлексивно
    s.1 s.1 = T;
*2. Если буквы различны, проверить, входит ли
* первая из них в алфавит до второй
    s.1 s.2 = <Before s.1 s.2 In <Alphabet>>; }
Before {
    s.1 s.2 In e.A s.1 e.B s.2 e.C = T;
    e.Z = F; }
Alphabet {
    = 'abcdefghijklmnopqrstuvwxyz'; }

Строки, начинающиеся с *, служат комментариями. Последняя из функций Alphabet введена для технологичности, чтобы определение алфавита было в одном месте и его легко было изменять. Так что функция с пустым образцом может пониматься как константное выражение. In является атомом-разделителем, заведомо не встречающимся в алфавите.

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

Если взаимное расположение функций никакой роли не играет, то внутри функции расположение сопоставлений важно. Сначала применяется первое из сопоставлений, при неудаче переходят ко второму и так далее до последнего.

Заметим, что в языке Рефал отсутствие сопоставления, конкретизацией которого является текущая область зрения, означает аварийный останов программы с выдачей текущего поля памяти и закопанных данных. Пожалуй, это достаточно технологичное решение, поскольку для тех, кто сам желает обрабатывать ошибки, всегда имеется возможность поместить последней строкой в определение функции правило видаe.A=Обработка ошибки ;

Имеются также встроенные функции, в частности, функции работы с числами <'+' s.Number1 s.Number2> и подобные ей.

Рассмотрим связь между языком и программным окружением.

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

<Go >

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

$ENTRY Go { =<Prog <Open 'r' 1 'data.txt'><Get 1> >}

<Br e.N '=' e.Е >

<Dg e.N>

<Put s.Channel e.Expression>

<Putout s.Channel e.Expression>

<Input s.Channel> или <Input e.File-name>
<Xxin e.File-name> или <Xxin s.Channel>
<Xxout s.Channel e.Expr> или 
    <Xxout (e.File-name)e.Expr>

$EXTRN F1,F2,F3;

refgo prog1+functions+reflib

Mu { s.F e.X = <s.F e.X> },

$ENTRY Upd {e.X = <Mu e.X>;}

<Alphabet>

'abcdefghijklmnopqrstuvwxyz'

$ENTRY Go{=<Init>;}
$EXTRN Xxout;
* Инициализация поля зрения и констант
Init{=<Open 'r' 1 'Input.txt'><Trans <Acquire(<Get 1>)";}
Acquire {
  e.Got ()= e.Got;
* Конец ввода - пустая строка
  e.Got (e.New)=<Acquire e.Got e.New (<Get 1>)>;
}
Brackets {=('()')('[]')('')('<>');}
Trans {
  e.A =<Result <Pairing () e.A > >;
}
Pairing {
* В первой скобке содержится последовательность всех незакрытых
* скобок вместе с сегментами данных, подлежащими помещению
* в даннуюпару скобок;
* каждый сегмент данных также заключен в скобки
  (e.Unclosed (e.LastUn)(s.Lbrack e.Middle)) s.Rbrack e.Last,
     <Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =
*    Встретилась правая скобка, парная последней незакрытой;
*    выбрасываем отработанный сегмент из поля зрения
     <Pairing (e.Unclosed (e.LastUn (s.Lbrack e.Middle s.Rbrack))) e.Last>;
  ((s.Lbrack e.Middle)) s.Rbrack e.Last,
     <Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =
*    Парная незакрытой, находящейся внутри другой незакрытой
  (s.Lbrack e.Middle s.Rbrack) <Pairing () e.Last>;
  (e.Unclosed (e.LastUn)(s.Lbrack e.Middle)) s.Rbrack e.Last,
     <Brackets>: e.A(s.Lbrack1 s.Rbrack ) e.B =
*    Непарные скобки
       <Prout "Brackets Mismatch!"> Error;
  (e.Unclosed ) s.Lbrack1 e.Last,
     <Brackets>: e.A(s.Lbrack1 s.Rbrack ) e.B =
*    Еще одна открывающая скобка; создаем новую группу данных
       <Pairing (e.Unclosed (s.Lbrack1)) e.Last>;
  () s.Lbrack e.Last,
     <Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =
*    Первая открывающая скобка
       <Pairing ((s.Lbrack)) e.Last>;
  () s.Rbrack e.Last,
     <Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =
*    Первая скобка - закрывающая
       <Prout "Extra right bracket"> Error;
*    Нейтральный символ вне скобок
  () s.Other e.Last = s.Other <Pairing () e.Last>;
*    Выражение и скобки исчерпаны - успех
  () =;
*    Выражение исчерпано, а скобки - нет
  (e.Unclosed (e.Lastun))=<Prout "Not all brackets are closed" Error;
*    Нейтральный символ в очередной скобке
  (e.Unclosed (e.Lastun))s.Other e.Last=
     <Pairing (e.Unclosed(e.Lastun s.Other)) e.Last>;
}
Result {
* Если была ошибка, выйти
e.A Error=;
* Иначе вывести результат для дальнейшего использования
e.A =<Xxout ('output.rdt') e.A>;
}

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.