-Редукция и проблема конфликта имен
Рассмотрим следующее выражение
x.y.xyy
Переменная х является связанной в данном выражении, т.к. оно содержит x. Или можно говорить: имеет место связанное вхождение переменной х в данное выражение.
Теперь рассмотрим тело самой внешней абстракции
y.xyy
Хотя х входит в данное выражение, это вхождение не является связанным, т.к. выражение не содержит x. Поэтому мы говорим, что х является свободной переменной в данном выражении. Однако переменнаяyпо-прежнему связана благодаряy. Если мы теперь рассмотрим тело самой внешней абстракции, т.е.xyy, то здесь как х, так иyявляются свободными.
-выражение Е, не содержащее свободных переменных называется замкнутым.
Используя представление о свободных и связанных переменных, мы можем формализовать определение -редукции.
-редукция – это такое правило преобразования (x.Е) А, которое дает модифицированную форму Е, где все вхождения свободной в Е переменной х заменены на А.
Существует проблема, связанная с -редукцией, которую можно проиллюстрировать на следующем примере:
x.((y.x.+xy)x) (**)
Это выражение содержит единственный редекс. Если мы попытаемся вычислить его, получим
x.(x.+xx)
Проблема состоит в том, что в том примере выражение аргумента содержит свободную переменную, имеющую одинаковое имя с одной из связанных переменных в теле абстракции, т.е.(( y.x.+x(связан)y)x(свободен).
Чтобы безопасно выполнить -редукцию, необходимо сначала модифицировать абстракцию так, чтобы сделать все имена связанных переменных уникальными по отношению к свободным переменным в выражении аргумента. Поэтому в нашем примере нужно переименовать связанную переменную х в теле абстракции, скажем на х’.
(y.x.+xy) (y.x’.+x’y)
Теперь выполнение -редукции безопасно
x.((y.x’.+x’y)x)
x.(x’.+x’x)
Этот процесс переименования называется -преобразованием или-подстановкой.
Он основан на той идее, что два таких выражения как x.xиy.y обозначают одну и ту же функцию, т.к. отличаются только именами связанных переменных, другими словами, являются алфавитно-эквивалентными. Мы говорим, что выражениеx.x-преобразовано вy.y, или чтоx.xиy.yявляются-преобразуемым и записываем
x.x = y.y
В общем случае выражение x.Е может быть преобразовано в выражениеx’.Е’, гдеE’ получается заменой всех вхождений свободной переменной х на х’, при условии, что х’ сама не является свободной переменной в Е. Например, следующее-преобразование корректно
x.fxyz.fzy
Пример неправильного -преобразования
x.fxyy.fyy
Проблема конфликта имен накладывает ограничение на -редукцию: мы можем безопасно выполнять-редукцию выражения Е1Е2, если только ни одно имя свободной в Е2 переменной не совпадает с именами связанных в Е1 переменных.
Переименование переменных в Е1 является трудоемкой операцией при ее реализации на компьютере. Далее мы рассмотрим решение этой проблемы.
Константы и константные функции
Рассмотрим -исчисление с предварительно определенным набором констант. Так как в чистом-исчислении отсутствуют константы, определим некоторый набор констант, который в общем случае может быть произвольным.
Константы |
Значения |
0, 1, -1, 2, -2, …. |
Множество целых чисел |
True, false |
Булевы константы |
+, -, *, / |
Арифметические операции |
= |
Булевы функции |
….. |
|
COND |
условная функция |
NIL |
конструктор списков |
NULL |
функция, проверяющая список на пустой список |
….. |
|