Cтраница 2
Приведенные четыре примера должны продемонстрировать особенности одного из стилей программирования на базе функциональных языков, в данном случае - Норе, названного систематической дефиницией функций, определенных на типах данных. Структура задачи моментально подсказывает структуру решения, а структура типа данных - структуру каждой функции. Однако на базе функциональных языков существуют и другие стили программирования. Наиболее важные из них включают в себя использования функций высшего порядка и ленивого вычисления. Эти особенности языка Норе будут рассмотрены в последних двух главах. [16]
Если мы реализуем нормальный порядок редукций и под - 1ерживаем разделение ( гарантируя, что аргументы вычисляются не более одного раза), тогда механизм редукции соответствует вызову по необходимости. В традиционных языках вызов по имени и вызов по необходимости отличаются, только если выражение аргумента дает побочные эффекты. В функциональном языке не существует побочных эффектов, и, следовательно, два этих механизма вызова дают всегда одинаковый результат. Вызов по необходимости поэтому можем охарактеризовать как нормальный порядок редукций, приводящий выражение к СЗНФ вместе с разделением выражений аргументов. Если соединим вызов по необходимости с ленивыми конструкторами, то получим ленивое вычисление, с которым уже встречались в гл. [17]
В предыдущей главе была рассмотрена основанная на использовании стеков абстрактная машина для вычисления функциональных выражений, написанных в соответствии с нотацией А-исчисления. Как мы видели, эта машина наиболее удобна для реализации вычислений аппликативного порядка, соответствующих вызовам по значению Расширение области применения машины с целью поддерживать вызовы по необходимости требует введения дополнительных структур для явного представления задержек В этой главе будет рассмотрен совсем другой подход к вычислению лямбда-выражений, при котором мы допускаем представление выражений в виде графов, а не в виде линейных текстовых строк. Результирующая модель вычислений по очевидным причинам называется редукцией графов. Одно очевидное преимущество заключается в том, что в графовом представлении легко выразить разделение; нам не нужна дополнительная структура, такая, как контекст, для запоминания связей ( разделяемых) переменных, поскольку на ( разделяемый) подграф можно ссылаться любое число раз с помощью указателей. Второе преимущество данного представления в том, чю вычисление нормального порядка в этом случае легко представляется и относительно эффективно реализуется. Все это делает редукцию графов особенно естественным инструментом Для поддержки вызовов по необходимости и, следовательно, ленивого вычисления в функциональных языках. [18]
Здесь обеспечивается семантика нормального порядка, поскольку аргументы не вычисляются перед тем, как будут подставлены в тела функций, применяемых к ним, а нормальные формы ( СЗНФ) являются либо лямбда-абстракциями с конструктором lam, либо применением идентификатора с конструктором id к произвольному числу ( включая нуль) аргументов. Хотя выражение в аргументе не вычисляется до тех пор, пока его значение не потребуется в теле примененной лямбда-абстракции, оно будет вычисляться вновь и вновь для каждого его вхождения в тело абстракции. Однако если eval является ленивой мемо-функцией, то адрес и значение вычисленного выражения аргумента будут храниться в мемо-таблице и при необходимости значение просто отыскивается в этой таблице. Таким образом запоминание обеспечивает реализацию вызова по необходимости с помощью функционально определенного интерпретатора с семантикой вызова по имени. Здесь, однако, мы обнаружили, что ленивое запоминание автоматически обеспечивает эту эффективность, модулируя обычные механизмы ленивых вычислений; разделение происходит косвенным образом через мемо-таблицу с эффективностью, несколько превышающей эффективность разрушающего присваивания. [19]
Несмотря на свою непривычную, а поэтому озадачивающую форму, в отличие от большинства программ программа ММ, описывает существенные операции умножения матриц без чрезмерно жесткого определения процесса или затемнения его частей. Для компьютеров фон Неймана эта программа неэффективна па самой своей природе ( в отношении использования памяти), но V: из нее можно вывести эффективные модификации, и можно i; представить себе реализации систем ФП, которые позволили iV бы выполнять ММ без расточительного использования памяти, , предполагаемого приведенной здесь ее формой. Вопросы эффек - тивности выходят за рамки проблематики этой статьи. Я позво - Vf лю себе только заметить, что поскольку язык прост и не пред - С. У рым, то, возможно, лучше было бы, если бы система оказалась, способной выполнять некий вид ленивого вычисления 19, 10 ] / иИ контролировать управление данными более эффективно, чем. ЭТО удается в системах, основанных на лямбда-исчислении. [20]