Ленивая версия SECD-машины

Мы реализовали энергичную SECD-машину. Возникает естественный вопрос: что нужно изменить в нашей программе, чтобы поведение SECDмашины изменилось и стало соответствовать ленивой схеме вычисления выражений? Очевидно, что для этого, прежде всего, необходимо изменить реализацию вызова функции, чтобы вычислять значение ее аргумента лишь при первом обращении к нему. Конечно, такие же изменения следует внести и в реализацию вычисления блоков. Поскольку все наши вычисления основаны на хранении значений в контексте, то все, что для этого требуется, — это задержать вычисление значения при помещении его в контекст. Теперь в тот момент, когда значение, хранящееся в контексте, понадобится в качестве аргумента строгой функции, нужно будет произвести вычисление и заменить в контексте значение переменной вычисленным значением. Для этого опять потребуется применение функции, подобной функции replace.

Мы введем понятие задержки — это новый тип выражения, который содержит команду (выражение, подлежащее вычислению) и контекст, в котором это вычисление следует производить. Заметим, что задержка по своей структуре напоминает замыкание, с помощью которого ранее мы представляли функциональные значения. Такое сходство не случайно, поскольку фактически задержки представляют собой функции без аргументов, которые требуется вычислять при обращении к ним. В нашем описании типа WHNF появится определение нового конструктора для реализации понятия задержки: data WHNF =.

… I.

Delay Command Context.

а команда применения функции будет теперь выполняться таким образом, чтобы задержать вычисление аргумента: evaluate (s, е, (Application f а):с, d) =.

evaluate ((Delay a e):s, e, f: Apply:c, d).

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

Аналогичным образом следует организовать и передачу аргументов встроенным функциям. Конечно, аргумент задерживать фактически не нужно, если у примитивной функции этот аргумент — строгий, но в общем случае неизвестно, какие из передаваемых аргументов действительно строгие, так что уравнение для реализации 8-редукции изменим следующим образом.

evaluate ((Section n f args):arg:s, e, Applyic, d).

| n == 1 = evaluate ((intrinsic f newArgs):s, e, c, d).

| otherwise = evaluate ((Section (n-1) f newArgs):s, e, c, d) where newArgs = args ++ [Delay arg e].

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

Однако для адекватной реализации механизма ленивых вычислений необходимо, чтобы вычисление выражения происходило не более одного раза. С помощью чисто функциональных средств легко можно реализовать работу SECD-машины, при которой задержанное выражение вычисляется каждый раз, когда происходит обращение к нему, но в этом случае можно говорить не о ленивых вычислениях, а, скорее, о передаче аргументов «по наименованию», как это описывалось в начале гл. 7. Для реализации ленивых вычислений вычисление выражения один раз при первом обращении требует хранения результата вычислений на том же месте, которое раньше занимала задержка. Таким образом, необходимо выполнять присваивания, которые в чисто функциональном виде представить невозможно.

Для реализации передачи аргументов «по наименованию» достаточно организовать вычисление задержанных выражений в тот момент, когда строгая функция применяется к задержанному аргументу. В нашей реализации строгие аргументы будут у большинства примитивных функций, так что соответствующие изменения следует внести в уравнения, определяющие работу функции intrinsic, ответственной за применение примитивных функций. В предыдущем параграфе мы не описывали уравнения для функции intrinsic, считая, что ее работа организована точно так же, как и в случае eval/apply-интерпретатора. Это действительно так, при условии, что конструкторы для образования константных значений были строгими по своим аргументам. В случае реализации ленивой модели вычислений аргументами примитивных функций могут оказаться задержки, так что может потребоваться вычислять их значения перед собственно выполнением 5-редукции.

Уравнения для функции intrinsic ранее выглядели примерно так: intrinsic «ADD» [Integral a, Integral b] = Integral (a + b).

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

Integral. Теперь это уже не так, и модифицированные уравнения будут выглядеть следующим образом:

intrinsic «ADD» [а@(Delay _ _), b] = intrinsic «ADD» [strict a, b] intrinsic «ADD» [a, b@(Delay _ _) ] = intrinsic «ADD» [a, strict b] intrinsic «ADD» [Integral a, Integral b] = Integral (a + b) где функция strict осуществляет вычисление задержанного выражения.

Оно происходит практически так же, как и применение замыкания функции к аргументу. Разница состоит только в том, что задержки не требуют никакого аргумента, так что контекст для вычисления задержки берется непосредственно из самой задержки: strict (Delay cmd ctx) = result.

where (result:s, _) = evaluate ([], ctx, [cmd], []).

Заметим, что результатом вычисления задержки опять может быть задержка, в этом случае функция strict будет применена повторно.

Это все, что нужно сделать для реализации передачи аргументов «но наименованию». Но чтобы реализовать ленивые вычисления в полном объеме, необходимо обеспечить механизм, который позволил бы один раз вычисленное значение задержки в дальнейшем использовать, не проводя те же вычисления повторно. Для этого средств функционального программирования недостаточно, так как требуется выполнять «присваивание» вычисленного значения на место, где до этого хранилась задержка.

Можно представлять себе, что фактически задержки помещаются в некоторую специально выделенную область памяти, а в регистрах SECDмашины содержатся ссылки на эти задержки. При вычислении значения задержки в эту область памяти помещается вычисленное выражение, так что при последующих обращениях к ним новых вычислений делать уже не нужно.

Такой подход к реализации приводит нас к концепции помеченного выражения — выражения в СЗНФ, которое содержит «прозрачную» ссылку на область памяти, содержащую либо задержку, либо уже вычисленное выражение, которое задержкой не является. Такое помеченное выражение играет роль обычного выражения в СЗНФ, но в тех случаях, когда требуется его значение, фактически происходит обращение к значению в той области памяти, на которое указывает ссылка. В том случае, когда значение требуется для вычисления значения строгой примитивной функции, может происходить вычисление задержанного выражения, при этом результат вычисления помещается на место задержки, так что при последующих обращениях вычисления заново не производятся.

Мы не будем изменять нашу реализацию в соответствии с описанным поведением, для адекватного описания подобной модели вычислений гораздо лучше подходит механизм, описанный далее, в гл. 14.

Сделаем еще несколько замечаний. Во-первых, заметим, что при ленивых вычислениях фактически нет разницы между простым и рекурсивным блоками, поскольку вычисление значений определяемых переменных все равно задерживается до момента первого обращения к ним из тела блока. Конструктор простого блока Let вообще можно исключить из списка команд. При реализации рекурсивного блока теперь нет необходимости в формировании фиктивного контекста, в формируемый для вычисления значения блока контекст можно сразу же поместить задержки или «помеченные» выражения.

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

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

intrinsic «IF» [cond@ (Delay _ _), t, e] =.

intrinsic «IF» [strict cond, t, e] intrinsic «IF» [Logical True, t, _] = t intrinsic «IF» [Logical False, _, e] = e.