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

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

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

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

${ displaystyle prog: I _ { text {static}} times I _ { text {dynamic}} to O,}$

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

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

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

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

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

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

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

Более того, применение инструмента в # 3 к самому себе дает сам инструмент, так что это Куайн.

Впервые они были описаны Футамурой в 1983 году.^[2]

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

• Выполнение функции во время компиляции
• Мемоизация
• Частичное применение
• Специализация алгоритма времени выполнения
• s_мин теорема
• Снижение силы
• Метапрограммирование шаблона

использованная литература

Общие ссылки

• Ёсихико Футамура, https://web.archive.org/web/20110629171734/http://www.brics.dk/~hosc/local/HOSC-12-4-pp381-391.pdf Частичная оценка вычислительного процесса - подход к компилятору-компилятору
• Чарльз Консель и Оливье Данви (1993). «Учебные заметки по частичной оценке». Материалы двадцатого ежегодного симпозиума ACM по принципам языков программирования: 493–501.

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

• Нил Д. Джонс, Карстен К. Гомард и Питер Сестофт: Частичная оценка и автоматическое создание программы (1993) Книга, полный текст доступен онлайн.
• 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
• C ++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
• Шаблоны C ++ как частичная оценка другая версия, включая Catat (pdf)
• Применение динамической частичной оценки к динамическим, рефлексивным языкам программирования