Редукция графика - Graph reduction

Эта статья посвящена термину информатики. Для использования теории графов см. переходная редукция.

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

Мотивация

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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 г. диссертация.^[1] Эту диссертацию цитировали Питер Хендерсон и Джеймс Х. Моррис-младший в статье 1976 года «Ленивый оценщик».^[2] это ввело понятие ленивого вычисления. В 1976 г. Дэвид Тернер включил ленивую оценку в SASL с использованием комбинаторов.^[3]SASL был ранним функциональным языком программирования, впервые разработанным Тернером в 1972 году.

Смотрите также

• Машина для редукции графа
• Машина SECD

Примечания

1. Худак, Пол (сентябрь 1989 г.). «Концепция, эволюция и применение языков функционального программирования». ACM Вычислительные опросы. 21 (3): 359–411. CiteSeerX  10.1.1.83.6505. Дои:10.1145/72551.72554.
2. Ленивый оценщик
3. Худак, Пол; Хьюз, Джон; Пейтон Джонс, Саймон; Вадлер, Филипп. «История Haskell: лень с классом». Конференция по истории языков программирования 2007.

Рекомендации

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

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

• Саймон Пейтон Джонс, Реализация языков функционального программирования, Prentice Hall, 1987. Полный текст онлайн.[1]