Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

определяет функцию прибавления единицы к переменной х. Запись ка. показывает, что это выражение является ламбда-абстракцией, формальным параметром которой является х. Выражение, которое следует за точкой (в данном случае это +х1) является телом ламбда-абстракции. Рассмотрим следующее ламбда-выражение: (Ях.+ху)3. Здесь х считается связанной переменной, 3 - значением для х. Для оценки этого выражения необходимо, чтобы переменная у уже имела какое-либо значение. Обычно значение свободной переменной определяется во внешнем выражении, содержащем это выражение. (5 - преобразование Пусть имеем выражение (Ях.+х1)4, в котором записаны последовательно ламбда-абстракция (Ях.+х1) и аргумент 4. При замене х на 4 получим (+4 1). Это правило преобразования называется р - преобразованием. Примеры /3- преобразований: (Ях.+х1)4^+4 1 Ях. +XXjS S S— •^l О (Ях. 3)5^3 (Ях.(Лу./ух))2 6—>(Ху./у2)6—>6 2—>3 (Af.f3)(Ax.+xl)^(Ax.+xl)3^+3 1^4 где (Ах. +х1) - аргумент для предыдущей ламбда-абстракции. Кроме того, в ламбда-исчислении вводятся а - преобразование, г] - преобразование, рекурсии и т.д. Если выражение содержит несколько редексов, то возможно одновременное их оценивание, например, если имеем (х(+3 5) (- 5 2JJ, то можно представить это выражение в виде следующего графа, см. Рис. 5.6. Посредством параллельной редукции всех редексов можно увеличить скорость вычислений. При этом появляется возможность параллельной обработки, и имеются следующие преимущества по сравнению с процедурными языками. (1) Графовая структура ламбда-исчисления позволяет выявить редексы для параллельной обработки. (2) Пет необходимости в централизованном управлении операциями редукции, которые нужно делать для процедурных языков. (3) Связь между редексами можно выполнить полностью унифицировано. В процедурных языках задачи распараллеливания вычислений требуют специальных программ, в том числе и синхронизацию (по времени) этих 175 X л ^ 3 5 5 2 Рис. 5.6.