В вычислительной технике частичная оценка — это метод для нескольких различных типов оптимизации программ по специализации . Наиболее простым применением является создание новых программ, которые работают быстрее оригиналов, при этом гарантированно ведут себя так же.
Компьютерная программа prog рассматривается как отображение входных данных в выходные данные:
где статические данные — это часть входных данных, известная во время компиляции.
Частичный оценщик преобразуется в , предварительно вычисляя все статические входные данные во время компиляции. называется «остаточной программой» и должна работать эффективнее исходной программы. Говорят, что действие частичной оценки «приводит к остаточному» состоянию .
Проекции Футамуры
Особенно интересным примером использования частичной оценки, впервые описанным в 1970-х годах Ёсихико Футамурой [1] , является случай, когда prog является интерпретатором языка программирования .
Если I static — это исходный код, предназначенный для запуска внутри этого интерпретатора, то частичная оценка интерпретатора относительно этих данных/программы производит prog *, версию интерпретатора, которая запускает только этот исходный код, написана на языке реализации интерпретатора, не требует повторной поставки исходного кода и работает быстрее, чем исходная комбинация интерпретатора и источника. В этом случае prog * фактически является скомпилированной версией I static .
Эта техника известна как первая проекция Футамуры, всего их три:
Специализация интерпретатора для заданного исходного кода, приводящая к созданию исполняемого файла.
Специализация специализатора для интерпретатора (как применено в п. 1) приводит к получению компилятора.
Специализируем специализатор для самого себя (как в п. 2), получая инструмент, который может преобразовать любой интерпретатор в эквивалентный компилятор.
Они были описаны Футамурой на японском языке в 1971 году [2] и на английском языке в 1983 году [3].
^ «Частичная оценка процесса вычисления — подход к компилятору-компилятору», Труды Института инженеров электроники и связи Японии , 54-C : 721–728, 1971
^ Futamura, Y. (1983). "Частичное вычисление программ". Симпозиумы RIMS по программной науке и инженерии . Конспект лекций по компьютерной науке. Том 147. Springer. С. 1–35. doi :10.1007/3-540-11980-9_13. hdl :2433/103401. ISBN3-540-11980-9.
Общие ссылки
Футамура, И. (1999). «Частичная оценка процесса вычисления — подход к компилятору-компилятору». Вычисления высшего порядка и символьные вычисления . 12 (4): 381–391. CiteSeerX 10.1.1.10.2747 . doi :10.1023/A:1010095604496. S2CID 12673078.
Консель, Чарльз; Дэнви, Оливье (1993). «Учебные заметки по частичной оценке». POPL '93: Труды 20-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . Ассоциация вычислительной техники. стр. 493–501. CiteSeerX 10.1.1.114.7330 . doi :10.1145/158511.158707. ISBN0897915607. S2CID 698339.
Внешние ссылки
Джонс, Нил Д.; Гомард, Карстен К.; Сестофт, Питер (1993). Частичная оценка и автоматическая генерация программ. Prentice Hall. ISBN9780130202499.
Дэнви, О., ред. (1999). "Частичная оценка и семантическая обработка программ PEPM'99" (PDF) . CiteSeerX 10.1.1.164.2284 .
Вельдхёйзен, Тодд Л. (1999). «Шаблоны C++ как частичная оценка». PEPM'99 . стр. 15–. arXiv : cs/9810010 .
Применение динамической частичной оценки к динамическим, рефлексивным языкам программирования