3. Выражения, функции, отождествление.
B этом и последующих параграфах мы опишем строго те понятия, с которыми уже познакомились на примере из п.2. Все определения будут иллюстрироваться программой example1.ref.
Выражения. Выражение может быть объектным выражением, типовым выражением, рабочим выражением, общим выражением.
С понятием объектного выражения мы уже познакомились в п. 1. В отличие от объектного выражения, типовое выражение задает, вообще говоря, не одно конкретное выражение, а некоторое множество выражений.
Типовое выражение - это выражение, состоящее из символов, левых и правых структурных скобок и переменных одного из трех типов - символа, выражения и терма.
В частности, любое объектное выражение является также и типовым (не содержащим переменных).
Определения переменных даны в п.1.
В одном типовом выражении переменные разного типа не могут иметь одинаковых индексов, но переменные одного типа с одинаковыми индексами могут несколько раз встречаться в одном типовом выражении.
Примерами типовых выражений являются левые части предложений функций (до знака "=")
Придавая переменным в типовом выражении различные значения, которые они могут принимать, мы получаем множество объектных выражений, которое задает данное типовое выражение.
Про объектное выражение, которое входит в множество, задаваемое некоторым типовым выражением, будем говорить, что оно отождествляется с этим типовым выражением.
Примеры типовых выражений:
s.X s.X - типовое выражение, которое задает множество всех объектных выражений, состоящее из двух одинаковых символов.
'М' s.2 s.3 'A' - типовое выражение, которое задает множество всех объектных выражений, состоящих из четырех символов, первым из которых является символ "М", а последним - символ "А". Например, 'МАМА' , 'МАША' , 'МИША'.
(e.1) e.2 - типовое выражение, которое задает множество всех объектных выражений, состоящих из двух частей, первая из которых заключена в структурные скобки.
'if' ( e.1 ) 'go to ' e.2 - типовое выражение, которое задает некоторое множество условных операторов.
Рабочее выражение - это выражение, содержащее обращения к функциям, так называемые функциональные термы. Рабочее выражение может быть вычислено.
Рабочее выражение состоит из символов, левых и правых структурных скобок, а также из левых и правых функциональных скобок - знаков "<" и ">" . Естественно, что структурные и функциональные скобки в совокупности должны образовывать правильную скобочную структуру.
Примерами рабочих выражений является поле зрения на каждом шаге работы рефал-программы.
Способ вычисления рабочего выражения описан ниже в п.4.
Пример вычисления рабочего выражения <Go > приведен в п.2.
Общее выражение - это выражение самого общего вида. Оно может состоять из символов, структурных скобок, переменных и функциональных скобок.
Примерами общих выражений являются правые части (после знака "=" ) предложений функций.
Функции
Функция - это набор правил, которые задают способ вычисления функциональных термов. У каждой функции есть свое имя (детерминатив). Функция задает правила вычислений тех функциональных термов, внутренность которых начинается с составного символа-метки с именем данной функции.
Описание функции заключается в фигурные скобки и состоит из нескольких предложений.
Каждое предложение имеет вид:
- левая часть предложения - некоторое типовое выражение,
- знак "=", разделяющий левую и правую части предложения,
- правая часть предложения - некоторое общее выражение.
- знак ";" (точка с запятой).
Все переменные, входящие в правую часть предложения, должны входить и в левую часть предложения.
Теперь определим точно способ вычисления функционального терма, который начинается с составного символа-метки с именем функции, заданной некоторыми предложениями. Вычисление происходит следующим образом:
1. Начинаем с первого предложения.
2. Проверяем, отождествляется ли внутренность функционального терма (не включая составного символа-метки с именем функции, а также без знаков "<" и ">") с левой частью очередного предложения.
3. Если отождествляется, то в этом случае все переменные левой части предложения, принимают некоторые значения. Эти значения подставляются в правую часть предложения, после чего получается некоторое рабочее выражение. Это рабочее выражение заменяет исходный функциональный терм (включая знаки "<" и ">"). На этом вычисление функционального терма заканчивается.
4. Если не отождествляется, то берется следующее предложение и повторяется проверка.
5. Если предложений больше нет, то вычисление данного функционального терма невозможно. Такая ситуация называется "отождествление невозможно".
В вышеприведенном описании процесса вычислений может возникнуть неоднозначность присвоения значений переменным из левой части предложения. Интуитивно, при отождествлении выбирается "первый подходящий вариант отождествления при просмотре слева направо".
Для придания точного смысла интуитивному понятию отождествления, упорядочим все переменные в том порядке, в котором они встречаются в типовом выражении при просмотре слева направо. Теперь из всех вариантов отождествления выберем те, у которых значение первой переменной самое короткое. Если получилось несколько вариантов, то оставим те, у которых значение второй переменной самое короткое, и так далее. Подобная процедура всегда приводит к однозначности.
Выбор подходящего варианта отождествления происходит не просто перебором. Программа предварительно обрабатывается компилятором, основная работа которого и состоит в том, чтобы определить наиболее быстрый для каждой левой части предложения способ отождествления с ней объектных выражений.