Упорядочивание параметров

Пусть имеется некоторое λ-выражение:

(…(λxz.+y(*xz))…)

Выносим у как экстра-параметр:

1-ый способ: _{↓подставляем у}

λxz.+y(*xz) = λx.((λx.λу.λz.+y(*xz))xy) = λx.$Sxy = (λy.λx.$Sxy)y = $Ty

┌─────┐ _{Самая внутренняя λ-абстракция.}

λx.[λz.+(*xz)]^.

Обозначим $Sxyz = +y(*xz) (1)

λx.$Sxy - это не суперкомбинатор.

$Tyx = $Sxy (2)

$Ty - вычисляемое выражение.

2-ой способ:

λxz.+y(*xz) = (λy.λxz.+y(*xz)))y = λx.$yx = $Ty

$Syxz = +y(*xz)

Необходимо упорядочивать свободные переменные $Tyx = $Syx так, чтобы уже связанные переменные стояли последними в списке параметров.

$T = λy.λx.$Syx

$T = $Sизбыток. Возможность оптимизации суперкомбинатора.

λx.λу.+ху

х имеет глубину связывания 1 между х и его абстрагированием

у имеет глубину связывания 0 стоит 1 символ λ в дереве разбора

Сначала надо абстрагировать переменные с минимальной глубиной связывания.

Предполагается, что каждая переменная где-либо связана.

Дата добавления: 2014-01-11