Реальные программы содержат значительное число абстракций. Про-
грамму следует преобразовать таким образом, чтобы она содержала
только суперкомбинаторы. Согласимся с тем, что имена суперкомби-
наторов будут начинаться с символа “$”, например:
$XY = [x].[y].− y x.
Для того, чтобы подчеркнуть особенности суперкомбинаторов, пе-
репишем это определение в виде:
$XY x y = − y x.
Избираемая стратегия заключается в преобразовании абстракции,
которую следует откомпилировать, в:
(i) совокупность суперкомбинаторных определений,
(ii) вычисляемое выражение.
Будем изображать это посредством:
Определения суперкомбинаторов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вычисляемое выражение
Пример 16.5 Выражение ([x].[y].− y x)3 4 представимо в виде:
$XY x y = − y x
_______________
$XY 3 4
Пример 16.6 Выражение ($XY 3)не является редексом и не может
быть вычислено. Таким образом, определения суперкомбинаторов
задаются в виде набора правил перезаписи. Редукция заключается в
перезаписи выражения, которое совпадает с левой частью правила,
заменяя его на выражение, стоящее в правой части. Такие системы
считаются системами перезаписи термов.
Упражнение 16.4 Можно ли вычислить выражения:
$XY 5, $XY 5 7, $XY 3 4 7 ?
|
Главная
Каталог файлов
