Редукция - граф
Cтраница 2
В предыдущей главе была рассмотрена вычислительная модель редукции графов в контексте - исчисления и показано, как редукция нормального порядка реализуется путем редуцирования самого левого из самых внешних редексов с помощью правил преобразования графов, соответствующих правилам редукции в Л - исчислении. Кроме этого была сформулирована проблема, затрагивающая эффективность данной схемы, которая возникает при наличии свободных переменных во вложенной - абстракции. Наличие свободных переменных означает, что каждое применение данной функции должно порождать копию тела этой функции, чтобы связать эти переменные с соответствующими значениями. [16]
Число компонент связности при транзитивном замыкании и при редукции графа не изменяется. [17]
 |
Обработка вершин-синонимов при сборке мусора. [18] |
Теперь мы опишем, как можно сконструировать функцию редукции графов для вычисления выражений нашего расширенного - исчисления, которое включает константы и примитивные функции. Однако один вопрос, который до сих пор подробно не рассматривался, - это вопрос о спуске по гребню при применении примитивной функции и о подъеме ( вверх по гребню), необходимом при вычислении аргументов примитивной функции для завершения ее применения. Одна из причин того, что мы опустили детали реализации спуска / подъема, заключается в том, что простой метод, основанный на использовании стека, хорошо работает в этом случае. [19]
Теперь надо сообразить, как должно выглядеть условие редукции графа. Так как проверку такого условия невозможно записать в виде выражения, содержащего только исходные операции алгола, мы организуем логическую процедуру-функцию ГРАФ НЕПОЛНЫЙ ( ге), где м-число вершин в графе, и работающую с графом U как с глобальным объектом, а заодно и вырабатывающую ( если граф V не полный) номера I и J склеиваемых вершин. Такая организация алгоритма тем более удобна, что процесс редукции и перекраски отделяется от способа определения нары склеиваемых вершин. [20]
Теперь мы покажем, как работает реверсирование указателей при редукции графов, обрисовав в общих чертах алгоритмы и дав два примера, иллюстрирующие их основные особенности. После этого нам будет просто расширить данный выше алгоритм редукции, чтобы включить в него реверсирование указателей. [21]
Применение правил редукции i-исчисления к графовому представлению Я выражений называется редукцией графов. [22]
Таким образом, разделение подграфов аргументов было введено для основного типа редукции графов, и поэтому из такой простой оптимизации правила редукции для 5 можно ожидать соответствующего увеличения эффективности. [23]
В этой главе будет рассмотрена комбинаторная реализация и, в частности, редукция графов комбинаторных выражений. В основе такого преобразования поэтому лежит функция, которая абстрагирует свободные переменные выражения, оставляя после этого цепочку применений комбинаторов. [24]
Поэтому существует прямое соответствие между принципами работы функционального потока данных и вычислительной модели редукции графов. Данное соответствие также распространяется на графовое представление выражений, хотя это может быть не очевидным с первого взгляда. [25]
Подобно другим вычислительным моделям, рассмотренным в этой книге, таким как SECD-машина и редукция графов, функциональная потоковая модель дает представление р-редук-ции и б-правил для поддерживаемых примитивных функций. Эти примитивные функции включают условные выражения, которые, хотя и выражаются с помощью вершин-переключателей и вершин слияния, могли бы точно так же рассматриваться в терминах только двух дополнительных примитивных функций и их дельта-правил. Более того, редекс такого применения можно рассматривать как перезаписываемый в том смысле, что входящие дуги его вершины применения перенаправляются в тело функции. [26]
Здесь мы ограничимся лишь изложением простого метода поиска контуров в графе, так как редукция графа сводится к стягиванию каждого контура графа в одну вершину. Эта операция представляет некоторые сложности в удобном представлении необходимой информации, а для дальнейшего содержания книги большого интереса не представляет. [27]
Другими словами, вычислительная модель определяется в терминах потока данных, а не потока управления или редукции графов, и программы на понятийном уровне представляются потоковыми графами. [28]
 |
Простое преобразование графа, представляющее Х - применение. [29] |
Таким образом, при графовом представлении разделение выражений представляется естественным образом без необходимости введения явного контекста, что делает редукцию графов жизнеспособной моделью для реализации функциональных языков. [30]
Страницы: 1 2 3 4