Как вы кодируете абстрактный алгоритм Лампинга, используя комбинаторы взаимодействия?

10

Комбинаторы взаимодействия были предложены в качестве цели компиляции для λ-исчисления ранее. Эта статья реализует полное λ-исчисление. Известно также, что можно оптимизировать кодировки сети взаимодействия λ-исчисления для подмножества λ-членов, которое можно типом EAL. Эта статья реализует это подмножество λ-исчисления, переводя λ-члены типа EAL в сети взаимодействия, которые, возможно, более сложны, чем комбинаторы взаимодействия, поскольку они используют бесконечный алфавит меток для группировки дупликаторов.

Интересно, можно ли объединить оба предложения? То есть, существует ли какая-либо кодировка для абстрактного алгоритма, т. Е. Λ-членов, которые могут быть EAL-типа, в качестве комбинаторов взаимодействия?

MaiaVictor
источник

Ответы:

6

Я не знаю о какой-либо реализации алгоритма Лампинга непосредственно в комбинаторах взаимодействия. Я знаю, что наличие целочисленных меток является необходимой особенностью алгоритма Лэмпинга, даже для термов типа EAL, потому что метки отражают вложение так называемых экспоненциальных блоков в сети доказательств, а алгоритм Лэмпинга по сути является выполнением сетей доказательства используя геометрию взаимодействия, как впервые наблюдали Гонтье, Абади и Леви . Таким образом, вопрос реализации алгоритма в комбинаторах взаимодействия сводится к представлению экспоненциальных блоков в сетях доказательств с использованием комбинаторов. По сути, это то, что Маки и Пинто сделали в своей статье.

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

Дамиано Мазза
источник