Interested Article - Частичные вычисления

Стратегии вычисления
Строгие вычисления
Нестрогие вычисления
Недетерминированные стратегии
Другие

Частичные вычисления ( англ. partial evaluation, PE ) в информатике стратегия вычислений , которая заключается в получении более эффективного кода на основе использования заданной информации о части аргументов и однократного выполнения той части кода, которая зависит только от известной части аргументов и не зависит от неизвестной части . Является разновидностью специализации , т. е. оптимизации программ на основе использования заданной информации о значении части переменных.

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

Самое простое применение частичных вычислений — создание новых программ, которые работают быстрее, чем исходные, и при этом гарантированно обладают таким же поведением.

Компьютерная программа prog рассматривается как преобразование входных данных в выходные данные:

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

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

Проекции Футамуры

Примером использования частичных вычислений является случай, когда prog интерпретатор языка программирования . Эта ситуация впервые была описана в 1970-х годах Ёсихико Футамурой . Если I static является исходным кодом на интерпретируемом языке, предназначенным для работы внутри интерпретатора prog , то специализация интерпретатора относительно него создает prog * — интерпретатор, запускающий только исходный код I static , не требующий его повторного написания и работающий быстрее, чем исходная комбинация интерпретатора prog и исходного кода I static . Фактически prog * является скомпилированной версией I static .

Эта техника известна как первая проекция Футамуры, которых существует три:

  1. Специализация интерпретатора для заданного исходного кода является исполняемым файлом .
  2. Специализация специализатора для интерпретатора из п. 1 является компилятором .
  3. Специализация специализатора из п. 2 для самого себя является генератором компиляторов, т. е. инструментом, который может преобразовать любой интерпретатор в соответствующий компилятор.

См. также

Примечания

  1. Климов Ю. А. . ИПМ им. М. В. Келдыша РАН (2008). Дата обращения: 26 марта 2023. 29 января 2023 года.
  2. (англ.) . Дата обращения: 26 марта 2023. 26 марта 2023 года.
  3. Futamura Y. Partial computation of programs // RIMS Symposia on Software Science and Engineering. — Springer, 1983. — Т. 147. — С. 1—35. — (Lecture Notes in Computer Science). — ISBN 3-540-11980-9 . — doi : .
Источник —

Same as Частичные вычисления