В компьютерных науках сокращение графа реализует эффективную версию нестрогой оценки, стратегии оценки , при которой аргументы функции не оцениваются немедленно. Эта форма нестрогих вычислений также известна как ленивые вычисления и используется в функциональных языках программирования . Метод был впервые разработан Крисом Уодсвортом в 1971 году.
Приведенная выше последовательность редукции использует стратегию, известную как редукция самого внешнего дерева . То же выражение можно вычислить с помощью редукции самого внутреннего дерева , что даст последовательность редукции:
Обратите внимание, что порядок сокращения делается явным добавлением круглых скобок. Это выражение также можно было бы просто вычислить справа налево, потому что сложение является ассоциативной операцией.
Отсюда и происходит термин сокращение дерева. При представлении в виде дерева мы можем думать, что самая внутренняя редукция работает снизу вверх, а самая внешняя — сверху вниз.
Выражение также может быть представлено в виде ориентированного ациклического графа , позволяющего совместно использовать подвыражения:
Что касается деревьев, то к графам применяется также самая внешняя и самая внутренняя редукция. Следовательно, у нас есть редукция графа .