Математическая логика и теория алгоритмов

Пусть имеем выражение (Ъс.+л:1)4, в котором записаны после­ довательно ламбда-абстракция (Ъс.+х!) и аргумент 4. При замене х на 4 получим (+4 1). Это правило преобразования называется Э-преобразованием. Примеры Р-преобразований: (Ад:.+л:1)4->+4 1; (Ад:.+д:х)5->+5 5->10; (>а.3)5-^3; ihc.{'ky.lyx))2 6- ¥{Xy.ly2)6->6 2-4 (^/ уЗ)(Ъ:,+л:1)->(Ъ:,+л:1)3-Я-3 1->4, где (Ъс.+л:1) — аргумент для предьщущей ламбда-абстракции. , Кроме того, в ламбда-исчислении вводятся а-преобразование, •^-преобразование, рекурсии и т.д. Если выражение содержит несколько редексов, то возможно одновременное их оценивание, например, если имеем (+3 5) (- 5 2)), то можно представить это выражение в виде следующего графа (рис. 6.6). Посредством параллельной ре­ дукции всех редексов можно увеличить скорость вычислений. При этом появ­ ляется возможность параллельной об­ работки и имеются следующие преи­ мущества по сравнению с процедурны­ ми языками. (1) Графовая структ}'ра ламбда- исчисления позволяет выявить редексы для параллельной обработгси. (2) Нет необходимости в централизованном управлении опера­ циями редукции, которые нужно делать для процедурных языков. (3) Связь между редексами можно выполнить полностью уни­ фицировано. В процедурных языках задачи распараллеливания вычислений требуют специальных программ, в том числе и синхронизацию X t / \ 3 5 5 2 Рис. 6.6 2 6 2