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

Методика оптимизации программ

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

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

п г о г : я статический × я динамический О , {\displaystyle prog:I_{\text{static}}\times I_{\text{dynamic}}\to O,}

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ Сайт Ёсихико Футамуры.
  2. ^ «Частичная оценка процесса вычисления — подход к компилятору-компилятору», Труды Института инженеров электроники и связи Японии , 54-C : 721–728, 1971
  3. ^ Futamura, Y. (1983). "Частичное вычисление программ". Симпозиумы RIMS по программной науке и инженерии . Конспект лекций по компьютерной науке. Том 147. Springer. С. 1–35. doi :10.1007/3-540-11980-9_13. hdl :2433/103401. ISBN 3-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. ISBN 0897915607. S2CID  698339.
  • Джонс, Нил Д.; Гомард, Карстен К.; Сестофт, Питер (1993). Частичная оценка и автоматическая генерация программ. Prentice Hall. ISBN 9780130202499.
  • Дэнви, О., ред. (1999). "Частичная оценка и семантическая обработка программ PEPM'99" (PDF) . CiteSeerX  10.1.1.164.2284 .
  • Вельдхёйзен, Тодд Л. (1999). «Шаблоны C++ как частичная оценка». PEPM'99 . стр. 15–. arXiv : cs/9810010 .
  • Применение динамической частичной оценки к динамическим, рефлексивным языкам программирования
Взято с "https://en.wikipedia.org/w/index.php?title=Частичная_оценка&oldid=1234631160"