Частичная оценка

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

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

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

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

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

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

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

Особенно интересный пример использования частичной оценки, впервые описанный в 1970-х годах Ёсихико Футамурой: это когда prog является интерпретатором языка программирования .

Если I _static — это исходный код, предназначенный для работы внутри этого интерпретатора, то частичная оценка интерпретатора по отношению к этим данным/программе создает prog * — версию интерпретатора, которая запускает только этот исходный код, написанную на языке реализации интерпретатора. интерпретатор, не требует повторной поставки исходного кода и работает быстрее, чем исходная комбинация интерпретатора и исходного кода. В этом случае prog * фактически является скомпилированной версией I _static .

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

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

Они были описаны Футамурой на японском языке в 1971 году. и на английском языке в 1983 году.

См. также

• Выполнение функции во время компиляции
• Мемоизация
• Частичное применение
• Специализация по алгоритмам времени выполнения
• s _mn Теорема
• Снижение прочности
• Template metaprogramming

Ссылки

Общие ссылки

• Футамура, Ю. (1999). «Частичная оценка вычислительного процесса — подход к компилятору-компилятору». Вычисления высшего порядка и символьные вычисления . 12 (4): 381–391. CiteSeerX   10.1.1.10.2747 . дои : 10.1023/А:1010095604496 . S2CID   12673078 .
• Консель, Чарльз; Дэнви, Оливье (1993). «Учебные заметки по частичной оценке». POPL '93: Материалы 20-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . Ассоциация вычислительной техники. стр. 493–501. CiteSeerX   10.1.1.114.7330 . дои : 10.1145/158511.158707 . ISBN  0897915607 . S2CID   698339 .

Внешние ссылки

• Джонс, Нил Д.; Гомар, Карстен К.; Сестофт, Питер (1993). Частичная оценка и автоматическая генерация программы . Прентис Холл. ISBN  9780130202499 .
• Дэнви, О., изд. (1999). «Частичная оценка и манипулирование программой на основе семантики PEPM'99» (PDF) . CiteSeerX   10.1.1.164.2284 .
• Вельдхейзен, Тодд Л. (1999). «Шаблоны C++ как частичная оценка». ПЭПМ'99 . стр. 15–. arXiv : cs/9810010 .
• Применение динамической частичной оценки к динамическим, рефлексивным языкам программирования