Cтраница 1
Аппликативный порядок редукций1 ( АПР), который предписывает вначале преобразовывать самый левый из самых внутренних редексов. [1]
Это является источником теоретических возражений против интерпретаторов аппликативного порядка. [2]
Ниже мы рассмотрим два метода обработки рекурсии в SECD-машине аппликативного порядка: метод использования У-комбинатора и метод помеченных выражений. Заманчиво использовать У обычным образом для удаления явной рекурсии из выражения, включающего рекурсивную функцию. После этого полученное Х - выражение просто передается для обработки в SECD-машину, которая в конце концов специально построена так, чтобы иметь возможность обрабатывать такие выражения. [3]
Будет замечено, что эти правила преобразования реализуют вычисление аппликативного порядка, при котором аргументы функции вычисляются до ее применения. Однако это сделано исключительно ради эффективности и не является неотъемлемым свойством лежащей в основе теории. [4]
Это стандартный прием, который можно использовать для обеспечения семантики нормального порядка для выражений, которые должны иметь аппликативный порядок вычисления. [5]
Наиболее естественная потоковая реализация дли функциональных языков - это машина, управляемая данными. Она имеет семайтику аппликативного порядка, и именно эту модель вычислений мы рассмотрим в первую очередь. [6]
Когда есть возможность выбрать редекс для преобразования, выбор определяется порядком редукций. Двумя альтернативными стратегиями выбора являются аппликативный порядок редукций и нормальный порядок редукций, тесно связанные с энергичным вычислением и ленивым вычислением соответственно. [7]
Поэтому такой управляемый данными режим выполнения реализует редукцию аппликативного порядка, соответствующую правилу вызова по значению Чтобы получить семантику нормального порядка, применение функции должно выполняться, только когда его результат явным образом запрошен. Этот запрос должен быть размножен в случае, когда вычисление запрошенного применения требует результат другого Применения. Результирующий режим реализации называется потоком данных, управляемым запросами, и в этом разделе мы опишем модификации, необходимые, чтобы из версии, управляемой данными, получить версию, управляемую запросами. [8]
В предыдущей главе была рассмотрена основанная на использовании стеков абстрактная машина для вычисления функциональных выражений, написанных в соответствии с нотацией А-исчисления. Как мы видели, эта машина наиболее удобна для реализации вычислений аппликативного порядка, соответствующих вызовам по значению Расширение области применения машины с целью поддерживать вызовы по необходимости требует введения дополнительных структур для явного представления задержек В этой главе будет рассмотрен совсем другой подход к вычислению лямбда-выражений, при котором мы допускаем представление выражений в виде графов, а не в виде линейных текстовых строк. Результирующая модель вычислений по очевидным причинам называется редукцией графов. Одно очевидное преимущество заключается в том, что в графовом представлении легко выразить разделение; нам не нужна дополнительная структура, такая, как контекст, для запоминания связей ( разделяемых) переменных, поскольку на ( разделяемый) подграф можно ссылаться любое число раз с помощью указателей. Второе преимущество данного представления в том, чю вычисление нормального порядка в этом случае легко представляется и относительно эффективно реализуется. Все это делает редукцию графов особенно естественным инструментом Для поддержки вызовов по необходимости и, следовательно, ленивого вычисления в функциональных языках. [9]
Каковы преимущества и недостатки специального представления tuple - З, предложенного в разд. Предложите, как можно модифицировать алгоритм редукции графов, описанный в разд, 11.3, чтобы реализовать вычисление аппликативного порядка. [10]
Если теперь вместо У использовать У, самоприменение вычисляется, только когда оно само применяется к аргументу, соответствующему переменной у, например к целому аргументу функции / ас. Если применение функции, соответствующей h, например / ас, к этому значению аргумента не включает рекурсивный вызов, самоприменение не будет вычислено. Следует заметить, что этот метод, позволяющий обходить зацикливание в вычислении аппликативного порядка, использует совершенно такой же подход, как описанный нами в гл. Конечно, не возникает проблемы при использовании нормального У-комбинатора в ленивой SECD-машине, которая без необходимости не будет пытаться вычислить самоприменение. [11]
Работа машины описывается в терминах переходов из одного состояния в другое. Переходы мы определим с помощью функции переходов из одного состояния в другое в следующем разделе. Эта функция может быть использована для формального определения операционной семантики реализации и дана для случая аппликативного порядка вычислений. [12]
Стоимость таких проверок высока, а выполняться они должны при каждом вызове мемо-функции, возможно, несколько раз по мере роста мемо-таблицы. Проблема усугубляется тем, что применение сложных методов для обработки составных структур затруднительно, например использование хэширования для оптимизации поиска в мемо-таблицах или для формирования этих таблиц в виде упорядоченных деревьев. В любом случае получение необходимой и уникальной характеризации структуры данных требует создания рекурсивной функции. Другим недостатком этого вида запоминания является то, что при проверке на равенство необходимо полное вычисление всех аргументов, и поэтому мы ограничены вычислениями аппликативного порядка. [13]