Кодирование семантики - Semantics encoding

А семантическое кодирование это перевод между формальные языки. Для программистов наиболее знакомой формой кодирования является компиляция языка программирования в машинный код или байт-код. Преобразование между форматами документов также является формой кодирования. Составление TeX или Латекс документы для PostScript также часто встречаются процессы кодирования. Некоторые препроцессоры высокого уровня, такие как OCaml с Camlp4 также включают кодирование одного языка программирования в другой.

Формально кодирование языка A в язык B - это отображение всех терминов A в язык B. Если существует удовлетворительно кодирование A в B, B считается по крайней мере такой же мощный (или же по крайней мере столь же выразительно) как.

Характеристики

Неформального понятия перевода недостаточно для определения выразительности языков, поскольку оно допускает тривиальные кодировки, такие как сопоставление всех элементов A с одним и тем же элементом B. Следовательно, необходимо определить определение «достаточно хорошей» кодировки. . Это понятие меняется в зависимости от приложения.

Обычно кодировка ${ displaystyle [ cdot]: A longrightarrow B}$ ожидается сохранение ряда свойств.

Сохранение композиций

прочность: Для каждого n-арного оператора ${ displaystyle op_ {A}}$ оператора A существует n-арный оператор ${ displaystyle op_ {B}}$ B такой, что; ${ displaystyle forall T_ {A} ^ {1}, T_ {A} ^ {2}, dots, T_ {A} ^ {n}, [op_ {A} (T_ {A} ^ {1}, T_ {A} ^ {2}, cdots, T_ {A} ^ {n})] = op_ {B} ([T_ {A} ^ {1}], [T_ {A} ^ {2}], cdots, [T_ {A} ^ {n}])}$
полнота: Для каждого n-арного оператора ${ displaystyle op_ {A}}$ оператора A существует n-арный оператор ${ displaystyle op_ {B}}$ B такой, что; ${ displaystyle forall T_ {B} ^ {1}, T_ {B} ^ {2}, dots, T_ {B} ^ {n}, exists T_ {A} ^ {1}, dots, T_ {A} ^ {n}, op_ {B} (T_ {B} ^ {1}, cdots, T_ {B} ^ {N}) = [op_ {A} (T_ {A} ^ {1}, T_ {A} ^ {2}, cdots, T_ {A} ^ {n})]}$

(Примечание: насколько известно автору, этот критерий полноты никогда не используется.)

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

Сохранение скидок

Это предполагает наличие понятия редукции как в языке A, так и в языке B. Обычно в случае языка программирования редукция - это отношение, моделирующее выполнение программы.

Мы пишем ${ displaystyle longrightarrow}$ на одну ступень редукции и ${ displaystyle longrightarrow ^ {*}}$ для любого количества ступеней редукции.

прочность: Для каждого срока ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ языка A, если ${ displaystyle T_ {A} ^ {1} longrightarrow ^ {*} T_ {A} ^ {2}}$ тогда ${ displaystyle [T_ {A} ^ {1}] longrightarrow ^ {*} [T_ {A} ^ {2}]}$ .
полнота: На каждый срок ${ displaystyle T_ {A} ^ {1}}$ языка A и всех терминов ${ displaystyle T_ {B} ^ {2}}$ языка B, если ${ displaystyle [T_ {A} ^ {1}] longrightarrow ^ {*} T_ {B} ^ {2}}$ тогда есть некоторые ${ displaystyle T_ {A} ^ {2}}$ такой, что ${ displaystyle T_ {B} ^ {2} = [T_ {A} ^ {2}]}$ .

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

Сохранение прекращения

Это также предполагает наличие понятия редукции как для языка A, так и для языка B.

прочность: на любой срок ${ displaystyle T_ {A}}$ , если все сокращения ${ displaystyle T_ {A}}$ сходятся, то все редукции ${ displaystyle [T_ {A}]}$ сходятся.
полнота: на любой срок ${ displaystyle [T_ {A}]}$ , если все сокращения ${ displaystyle [T_ {A}]}$ сходятся, то все редукции ${ displaystyle T_ {A}}$ сходятся.

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

Сохранение наблюдений

Это предполагает существование понятия наблюдения как на языке A, так и на языке B. В языках программирования типичные наблюдаемые являются результатами входных и выходных данных в противоположность чистым вычислениям. На языке описания, например HTML, типичная наблюдаемая - результат рендеринга страницы.

прочность: для каждого наблюдаемого ${ displaystyle obs_ {A}}$ на терминах A существует наблюдаемая ${ displaystyle obs_ {B}}$ членов B так, что для любого срока ${ displaystyle T_ {A}}$ с наблюдаемыми ${ displaystyle obs_ {A}}$ , ${ displaystyle [T_ {A}]}$ имеет наблюдаемый ${ displaystyle obs_ {B}}$ .
полнота: для каждого наблюдаемого ${ displaystyle obs_ {A}}$ на терминах A существует наблюдаемая ${ displaystyle obs_ {B}}$ на условиях B так, что для любого срока ${ displaystyle [T_ {A}]}$ с наблюдаемыми ${ displaystyle obs_ {B}}$ , ${ displaystyle T_ {A}}$ имеет наблюдаемый ${ displaystyle obs_ {A}}$ .

Сохранение симуляций

Это предполагает наличие понятия моделирования как на языке A, так и на языке B. В одном из языков программирования программа имитирует другую, если она может выполнять все те же (наблюдаемые) задачи и, возможно, некоторые другие. Моделирование обычно используется для описания оптимизаций во время компиляции.

прочность: для каждого срока ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ , если ${ displaystyle T_ {A} ^ {2}}$ имитирует ${ displaystyle T_ {A} ^ {1}}$ тогда ${ displaystyle [T_ {A} ^ {2}]}$ имитирует ${ displaystyle [T_ {A} ^ {1}]}$ .
полнота: для каждого срока ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ , если ${ displaystyle [T_ {A} ^ {2}]}$ имитирует ${ displaystyle [T_ {A} ^ {1}]}$ тогда ${ displaystyle T_ {A} ^ {2}}$ имитирует ${ displaystyle T_ {A} ^ {1}}$ .

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

Сохранение эквивалентностей

Это предполагает наличие понятия эквивалентности как для языка A, так и для языка B. Обычно это может быть понятие равенства структурированных данных или понятие синтаксически различных, но семантически идентичных программ, таких как структурное соответствие или структурная эквивалентность.

прочность: если два условия ${ displaystyle T_ {A} ^ {1}}$ и ${ displaystyle T_ {A} ^ {2}}$ эквивалентны в A, то ${ displaystyle [T_ {A} ^ {1}]}$ и ${ displaystyle [T_ {A} ^ {2}]}$ эквивалентны в B.
полнота: если два условия ${ displaystyle [T_ {A} ^ {1}]}$ и ${ displaystyle [T_ {A} ^ {2}]}$ эквивалентны в B, то ${ displaystyle T_ {A} ^ {1}}$ и ${ displaystyle T_ {A} ^ {2}}$ эквивалентны в A.

Сохранение распространения

Это предполагает наличие понятия распределения как на языке A, так и на языке B. Обычно для компиляции распределенных программ, написанных на Острый, JoCaml или E, это означает распределение процессов и данных между несколькими компьютерами или процессорами.

прочность: если срок ${ displaystyle T_ {A}}$ это композиция из двух агентов ${ displaystyle T_ {A} ^ {1} ~ | ~ T_ {A} ^ {2}}$ тогда ${ displaystyle [T_ {A}]}$ должен быть составом двух агентов ${ displaystyle [T_ {A} ^ {1}] ~ | ~ [T_ {A} ^ {2}]}$ .
полнота: если срок ${ displaystyle [T_ {A}]}$ это композиция из двух агентов ${ displaystyle T_ {B} ^ {1} ~ | ~ T_ {B} ^ {2}}$ тогда ${ displaystyle T_ {B}}$ должен быть составом двух агентов ${ displaystyle T_ {A} ^ {1} ~ | ~ T_ {A} ^ {2}}$ такой, что ${ displaystyle [T_ {A} ^ {1}] = T_ {B} ^ {1}}$ и ${ displaystyle [T_ {A} ^ {2}] = T_ {B} ^ {2}}$ .

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

внешняя ссылка

Вики по трансформации программ