Редукция - граф
Cтраница 3
Отсюда следует, что если мы выбираем вершину-редекс PR для редукции первой, то метод копирования, не требующий каких-либо изменений алгоритма редукции графов, является наилучшим. Однако метод побочных вершин также может ис пользовать изменение порядка выбора редексов, поскольку если PR редуцируется первой, то в момент замены РА будет уже известно, является ли PR вершиной-синонимом. [31]
Существуют также более сложные методы, например использование суперкомбинаторов [46], и мы рассмотрим подходы, основанные на использовании комбинаторов, с целью найти эффективные реализации редукции графов в следующих двух главах. Дополнительная выгода решения проблемы свободных переменных этим путем заключается в устранении ненужного копирования и дублирования редукций, что придает реализации свойство так называемой полной ленивости. [32]
К настоящему моменту мы рассмотрели множество реализаций функциональных языков, интерпретационный и компиля-ционный подходы, языки со строгой и ленивой семантикой, основанные на вычислительных моделях, которые используют определенный контекст, редукцию графов и комбинаторы различных форм. В каждом случае возникает возможность повышения производительности выполнения программы и по времени выполнения, и по объему занимаемой памяти. Последний вид повышения производительности относится и к вопросу сборки мусора, рассмотренному в предыдущей главе, но подобный способ разрешения проблемы несколько похож на запирание конюшни после побега лошадей, поскольку в действительности хотелось бы прежде всего сократить потребность в какой-либо сборке мусора до минимума. Аналогично можно отметить определенную локальную оптимизацию, которая возникла в некоторых связанных в основном с компилятором МФО-реализациях, таких как компиляция авторекурсии в циклах. [33]
Мы могли бы, конечно, ввести новый тип вершин для let - выражений этого вида, но это не является необходимым и привело бы только к затуманиванию той простоты, которая присуща механизму редукции графов. [34]
Выбор именно этих двух примеров обусловлен тем, что они представляют две крайности в области приложения функциональных языков, а именно - использование строгих языков, основанных на оптимизированной SECD-машине, и использование ленивых языков на основе оптимизированной редукции графов. Обсуждение этих вопросов содержится в разд. [35]
Привлекательность комбинаторных реализаций в том, что в этом случае все вычисляемые выражения находятся в чисто апшшкативной форме, фактически в константной аппликатив-ной форме ( КАФ), означающей аппликативную форму без переменных. Так, при редукции комбинаторных графов имеют место только два типа преобразований, представляющих применение комбинатора или примитивной функции к подвыражению, которое также находится в КАФ. Каждый комбинатор является поэтому чистой функцией в том смысле, что его применение зависит исключительно от значений его аргументов и не зависит от значений любых свободных переменных его тела. [36]
Итак, все что нам нужно сделать - это определить правила преобразования графов, соответствующие применениям 5, К. Как и в случае редукции графов, в результате будет получена реализация, которая естественным образом является ленивой в том, что в качестве очередного редекса для упрощения всегда выбирается самый левый из самых внешних редексов. [37]
Один из способов сделать это состоит в представлении выражений в виде графов. Это приводит нас к идее редукции графов, которая будет детально описана в гл. [38]
Каковы преимущества и недостатки специального представления tuple - З, предложенного в разд. Предложите, как можно модифицировать алгоритм редукции графов, описанный в разд, 11.3, чтобы реализовать вычисление аппликативного порядка. [39]
Хотя параллельная редукция графов находится в детском возрасте, она представляет очень интересный новый подход к параллельным вычислениям. Во время написания этой книги исследования по параллельной редукции графов и разработке машины такой редукции активно проводились несколькими группами во всем мире Машины, описанные в [27, 44, 54] и [71], все являются или машинами чистой редукции графов, или основываются в своих операциях во многом на принципах редукции графов. [40]
И, рекурсию можно представить в вычислительной модели ленивой редукции графов с помощью непосредственного применения У-комбинатора, который является совершенно правильным Я-выражением. Сложность результирующего выражения чрезмерно велика даже для представления, основанного на расширенном фиксированном наборе комбинаторов, хотя при немногим более эффективном подходе У выражается с помощью комбинатора W Kh. Этот подход рассматривается в упражнении в конце главы. Один из них использует У-комбинатор в качестве примитива, вводя дополнительное правило преобразования графов, включающее цикл. [41]
Простейшее преобразование данного типа называется Я-уда-лением и заключается в удалении свободных переменных из каждого Я-тела, в результате чего получается один новый комбинатор. Однако такое решение не дает максимально возможной эффективности, поскольку число применений в результирующих выражениях ( и, следовательно, число редукций графов, требуемых в процессе вычисления этих выражений) можно уменьшить, а размер структурных элементов комбинаторов - увеличить. Еще более серьезный недостаток состоит в том, что полная ленивость может быть утрачена, и при этом возникает вероятность, что в процессе вычисления выражения одно и то же подвыражение будет вычислено более одного раза. [42]
Каждое из последующих разделяемых применений element 2 будет использовать эти значения, поэтому исходные подвыражения не требуется вычислять заново. Отличие этого подхода от - удаления заключается в том, что здесь разделяемые подвыражения рассматриваются в качестве аргументов, а они естественным образом разделяются в редукции графов. [43]
 |
Слова состояния и указатели кучи. [44] |
Для определения того, какие ячейки активны, необходимо проанилизировать состояние процесса вычислений. Это состояние может быть представлено как стеком вычислений ( как в SECD-машине), так и единственным указателем на высокоуровневую ячейку графа вычислений ( как при использовании редукции графов) либо каким-нибудь иным образом. [45]
Страницы: 1 2 3 4