Cтраница 3
Поскольку наиболее естественная реализация основана на редукции графов, модель вычислений является ленивой, а так как отсутствуют переменные, то нет необходимости рассматривать вопрос об их именах и контексте. К сожалению, даже очень простое Х - выражение имеет сложный эквивалент в КЛ и, хотя отсутствуют переменные, уменьшение накладных расходов из-за отсутствия контекста эффективно компенсируется необходимостью передавать выражения аргументов в качестве параметров. Таким образом, этот сырой подход не применим на практике без оптимизации с целью повышения эффективности. [31]
Здесь обеспечивается семантика нормального порядка, поскольку аргументы не вычисляются перед тем, как будут подставлены в тела функций, применяемых к ним, а нормальные формы ( СЗНФ) являются либо лямбда-абстракциями с конструктором lam, либо применением идентификатора с конструктором id к произвольному числу ( включая нуль) аргументов. Хотя выражение в аргументе не вычисляется до тех пор, пока его значение не потребуется в теле примененной лямбда-абстракции, оно будет вычисляться вновь и вновь для каждого его вхождения в тело абстракции. Однако если eval является ленивой мемо-функцией, то адрес и значение вычисленного выражения аргумента будут храниться в мемо-таблице и при необходимости значение просто отыскивается в этой таблице. Таким образом запоминание обеспечивает реализацию вызова по необходимости с помощью функционально определенного интерпретатора с семантикой вызова по имени. [32]
В качестве альтернативы АПР можем сначала подставить Е2 вместо х в El, что соответствует нормальному порядку редукций. Она поэтому соответствует понятию вызова по текстовой замене. Как мы уже видели, при этом может возникнуть конфликт имен и необходимость повторного вычисления выражений аргументов. Если мы обходим проблему конфликта имен ( например, выполнив - преобразование для каждого выражения аргумента или приводя выражение только к СЗНФ), тогда такой механизм соответствует вызову по имени. [33]
НИР в таких случаях эффективно откладывает вычисление любых редексов внутри выражения аргумента до тех пор, пока это возможно, в расчете на то, что такое вычисление может оказаться ненужным. Стратегия выбора самого левого из самых внешних редексов предписывает поэтому выполнять подстановку для х в Ку. В результате за один шаг получается нормальная форма Ку.у. АПР, с другой стороны, вычисляет выражение аргумента в первую очередь, что в данном случае приводит к зацикливанию. Хотя отсюда следует, что мы должны всегда выбирать нормальный порядок редукций, чтобы гарантировать, что вычисление закончится всякий раз, когда это возможно, АПР оказывается значительно более эффективным при реализации на обычных компьютерах, что мы и увидим далее в этой книге. [34]
Первое и наиболее очевидное изменение, которое необходимо сделать, касается правила для функции Eval, когда ее аргументом является применение функции. Мы по-прежнему требуем, чтобы функция была либо замыканием, либо примитивом, и нам, следовательно, по-прежнему необходимо вычислять выражение самой функции перед вызовом Apply. Мы можем просто передать выражение аргумента без изменений в функцию Apply, но это снова поставит перед нами проблему, связанную со ссылками на переменные в выражении аргумента. Следовательно, мы должны использовать структуру, подобную замыканию, чтобы запоминать как само выражение аргумента, так и контекст, содержащий корректные связи переменных этого выражения. Назовем эту структуру задержкой, чтобы отразить тот факт, что она представляет отложенное вычисление выражения, хотя ее часто называют также рецептом, отражая тот факт, что она представляет рецепт для вычисления значения. [35]
Заметим, однако, что если аргумент в теле функции встречается больше одного раза, то для каждого вхождения аргумента требуется вычисление задержки или применение соответствующего замыкания к пустому параметру. Таким образом, требуется повторное вычисление аргумента всякий раз, когда нам нужно получить его значение, и, следовательно, мы имеем вызов по имени. Чтобы реализовать ленивое вычисление, мы должны реализовать вызов по необходимости. Для этого требуется разделять не только выражения аргументов, но и результаты вычислений этих выражений. Механизмы, реализующие вызов по необходимости, рассмотрены в следующем подразделе. [36]
Один способ, гарантирующий, что аргумент никогда не будет вычисляться более одного раза, заключается в вычислении его перед выполнением р-редукции. Это соответствует аппли-кативному порядку редукций. Вместо подстановки аргумента в исходном виде выполняется подстановка значения аргумента, поэтому повторные вхождения связанной переменной не приводят к повторной редукции аргумента. В таком случае будем говорить, что выражение аргумента является разделяемым. [37]
Макрокоманда NEW требует от программ структур данных нового описания элемента. Аргумент NEW может быть использован для задания начального данного ( DATUM) элемента. Если аргумент есть идентификатор типа ARRAY, то копия соответствующего массива становится начальным данным. В противном случае начальное данное принимает значение выражения аргумента. [38]
Хотя этого совершенно достаточно, чтобы выразить правила преобразования лямбда-исчисления, мы указали некоторые проблемы, связанные с данным представлением, в частности то, что трудно в данном случае выразить разделение выражений аргументов. Две ссылки на одну и ту же переменную в этом случае приводят к тому, что из контекста дважды извлекается одна и та же связь, и нет необходимости в ее дублировании. Второй метод достижения разделения состоит в принятии графового представления выражений. При этом множественные ссылки на одно и то же выражение аргумента представляются множеством дуг, идущих к единственной разделяемой копии соответствующего графа аргумента. Как и в предыдущей главе, мы будем основывать наше обсуждение на лямбда-исчислении и будем полагать, что let - и let-rec - выражения были преобразованы в нашем промежуточном коде. Обработка рекурсивных определений отложена до следующей главы. [39]
В качестве альтернативы АПР можем сначала подставить Е2 вместо х в El, что соответствует нормальному порядку редукций. Она поэтому соответствует понятию вызова по текстовой замене. Как мы уже видели, при этом может возникнуть конфликт имен и необходимость повторного вычисления выражений аргументов. Если мы обходим проблему конфликта имен ( например, выполнив - преобразование для каждого выражения аргумента или приводя выражение только к СЗНФ), тогда такой механизм соответствует вызову по имени. [40]
Если мы реализуем нормальный порядок редукций и под - 1ерживаем разделение ( гарантируя, что аргументы вычисляются не более одного раза), тогда механизм редукции соответствует вызову по необходимости. В традиционных языках вызов по имени и вызов по необходимости отличаются, только если выражение аргумента дает побочные эффекты. В функциональном языке не существует побочных эффектов, и, следовательно, два этих механизма вызова дают всегда одинаковый результат. Вызов по необходимости поэтому можем охарактеризовать как нормальный порядок редукций, приводящий выражение к СЗНФ вместе с разделением выражений аргументов. Если соединим вызов по необходимости с ленивыми конструкторами, то получим ленивое вычисление, с которым уже встречались в гл. [41]
И) Если / - это замыкание [ VB E, то выражение тела ( В) вычисляется в контексте Е, дополненном связью V с а. Однако перед тем как сделать это, состояние машины нужно запомнить, чтобы можно было продолжить работу после того, как вычисление В закончится. Это состояние представляет собой текущее состояние машины ( кортеж из четырех элементов) с удаленными верхним элементом управляющей строки и двумя верхними элементами стека. Новый стек пуст, новый контекст представляет собой контекст применяемого замыкания, дополненный связью идентификатора связанной переменной с выражением аргумента, а новая управляющая строка состоит из единственного элемента. [42]
Первое и наиболее очевидное изменение, которое необходимо сделать, касается правила для функции Eval, когда ее аргументом является применение функции. Мы по-прежнему требуем, чтобы функция была либо замыканием, либо примитивом, и нам, следовательно, по-прежнему необходимо вычислять выражение самой функции перед вызовом Apply. Мы можем просто передать выражение аргумента без изменений в функцию Apply, но это снова поставит перед нами проблему, связанную со ссылками на переменные в выражении аргумента. Следовательно, мы должны использовать структуру, подобную замыканию, чтобы запоминать как само выражение аргумента, так и контекст, содержащий корректные связи переменных этого выражения. Назовем эту структуру задержкой, чтобы отразить тот факт, что она представляет отложенное вычисление выражения, хотя ее часто называют также рецептом, отражая тот факт, что она представляет рецепт для вычисления значения. [43]
Первое и наиболее очевидное изменение, которое необходимо сделать, касается правила для функции Eval, когда ее аргументом является применение функции. Мы по-прежнему требуем, чтобы функция была либо замыканием, либо примитивом, и нам, следовательно, по-прежнему необходимо вычислять выражение самой функции перед вызовом Apply. Мы можем просто передать выражение аргумента без изменений в функцию Apply, но это снова поставит перед нами проблему, связанную со ссылками на переменные в выражении аргумента. Следовательно, мы должны использовать структуру, подобную замыканию, чтобы запоминать как само выражение аргумента, так и контекст, содержащий корректные связи переменных этого выражения. Назовем эту структуру задержкой, чтобы отразить тот факт, что она представляет отложенное вычисление выражения, хотя ее часто называют также рецептом, отражая тот факт, что она представляет рецепт для вычисления значения. [44]
Другие приложения, которые различаются главным образом по времени, необходимом для их создания, включают в себя анализ высказываний и анализ сложности. Первый связан с определением того, какое из рекурсивных уравнений в описаниях функции потребуется при данном вызове этой функции. Это важно в компьютерах с параллельной архитектурой, в которых может быть необходим удаленный доступ к разделяемым кодам. Путем определения того, какие части этого кода необходимы ( высказывания), можно значительно сократить количество сообщений, которые эти высказывания пересылают. Анализ сложности также важен для параллельных машин, особенно для машин с улучшенными структурными элементами. Если выражение содержит подвыражение, которое может быть вычислено независимо, например аргументы применения функции или выражение, значением которого является функция и которое применяется к выражению аргумента, то независимые вычисления могут быть поручены ( разбросаны) различным процессорам для параллельного выполнения. Однако такое распределение приводит к дальнейшему росту обмена информацией, и если стоимость разделения вычислений преобладает над выигрышем по времени выполнения вычислений, то смысла увеличивать степень параллелизма таким образом нет. Задача, поэтому, заключается в том, чтобы заранее, на этапе компиляции, знать, как долго будет происходить вычисление подвыражений. Возможно, что на это будет указывать некая мера сложности, определенная для выражений, и если они были выражены в терминах некой нестандартной семантики и домена, то абстрактная интерпретация может стать формальной основой для подобного анализа. [45]