Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; 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 решают задачу.