WikiDer > Редукция графика

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

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

Мотивация

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

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

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

Представлен как дерево, приведенное выше выражение выглядит так:

Expression Tree.svg

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

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

Выражение Graph.svg

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

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

Выражение Graph Reduction.svg

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

Редукция комбинаторного графа

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

История

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

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

Примечания

  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]