Сокращение графа

Эта статья о термине информатики. Чтобы узнать об использовании теории графов, см. транзитивную редукцию .

В информатике при сокращение графа реализует эффективную версию нестрогой оценки, стратегию оценки, которой аргументы функции не оцениваются немедленно. Эта форма нестрогой оценки также известна как ленивая оценка и используется в языках функционального программирования . Эту технику впервые разработал Крис Уодсворт в 1971 году.

Мотивация

Ниже приведен простой пример вычисления арифметического выражения:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}$

Вышеупомянутая последовательность сокращения использует стратегию, известную как сокращение внешнего дерева . То же выражение можно вычислить с помощью сокращения внутреннего дерева , что даст последовательность сокращения:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}$

Обратите внимание, что порядок сокращения определяется добавлением круглых скобок. Это выражение также можно было бы просто вычислить справа налево, поскольку сложение — это ассоциативная операция.

Представленное в виде дерева выражение выше выглядит следующим образом:

Отсюда и появился термин «сокращение деревьев». Если представить его в виде дерева, мы можем представить себе, что самая внутренняя редукция работает снизу вверх, а самая внешняя — сверху вниз.

Выражение также можно представить в виде направленного ациклического графа , позволяющего совместно использовать подвыражения:

Что касается деревьев, то к графам также применима внешняя и самая внутренняя редукция. Следовательно, мы имеем сокращение графа .

Теперь оценка с внешним сокращением графа может выполняться следующим образом:

Обратите внимание, что оценка теперь требует всего четырех шагов. Сокращение внешнего графа называется ленивым вычислением , а сокращение самого внутреннего графа называется нетерпеливым вычислением .

Сокращение графа комбинатора

Сокращение графа комбинатора - это фундаментальный метод реализации языков функционального программирования , в котором программа преобразуется в представление комбинатора , которое отображается в ориентированного графа структуру данных в памяти компьютера, а выполнение программы затем состоит из перезаписи частей этого графа («сокращение «это), чтобы двигаться к полезным результатам.

История

Концепция сокращения графа, позволяющая обмениваться оцененными значениями, была впервые разработана Крисом Уодсвортом в его докторской диссертации 1971 года. диссертация. Эту диссертацию цитировали Питер Хендерсон и Джеймс Х. Моррис-младший в статье 1976 года «Ленивый оценщик». это ввело понятие ленивых вычислений. В 1976 году Дэвид Тернер включил ленивые вычисления в SASL с помощью комбинаторов. SASL — ранний язык функционального программирования, разработанный Тернером в 1972 году.

См. также

• Машина сокращения графов
• SECD-машина

Ссылки

• Берд, Ричард (1998). Введение в функциональное программирование с использованием Haskell . Прентис Холл. ISBN  0-13-484346-0 .

Дальнейшее чтение

• Пейтон Джонс, Саймон Л. (1987). Реализация языков функционального программирования . Прентис Холл. ISBN  013453333X . LCCN   86020535 . Проверено 15 апреля 2022 г.