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

Не следует путать с частичным применением.

Стратегии вычисления
Строгие вычисления
Аппликативный порядок Вызов по значению (call-by-value) Вызов по ссылке (call-by-reference) Вызов по адресу (call-by-address) Вызов по соиспользованию (call-by-sharing) Вызов по копированию — восстановлению (call-by-copy-restore)
Нестрогие вычисления
Нормальный порядок Вызов по имени (call-by-name) Вызов по необходимости (call-by-need) Ленивые вычисления (lazy evaluation) Оптимистичные вычисления Вызов по макрораскрытию
Недетерминированные стратегии
Полная β-редукция Вызов по преднамеченности (call-by-future) Оптимистичные вычисления
Другие
Частичные вычисления Удалённые вычисления Вычисления по короткой схеме

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

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

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

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

${\displaystyle prog:I_{\text{static}}\times I_{\text{dynamic}}\to O,}$

где ${\displaystyle I_{\text{static}}}$ — статические данные — представляет собой часть входных данных, известную во время компиляции.

Частичный вычислитель преобразует ${\displaystyle \langle prog,I_{\text{static}}\rangle }$ в ${\displaystyle prog^{*}:I_{\text{dynamic}}\to O}$ путем предварительного вычисления всех статических входных данных в время компиляции. ${\displaystyle prog^{*}}$ называется остаточной программой. Она должна работать более эффективно, чем исходная программа.

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

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

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

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

См. также

• Мемоизация
• Частичное применение
• Снижение стоимости операций
• Суперкомпиляция

Примечания

1. Климов Ю. А. Особенности применения метода частичных вычислений к специализации программ на объектно-ориентированных языках  (рус.). ИПМ им. М. В. Келдыша РАН (2008). Дата обращения: 26 марта 2023. Архивировано 29 января 2023 года.
2. Professor Yoshihiko Futamura (англ.). Дата обращения: 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:10.1007/3-540-11980-9_13.