Кто-нибудь использовал полиморфную дефункционализацию Поттье и Готье в модульном компиляторе?

15

Дефункционализация - это программная трансформация, которая преобразует программы высшего порядка в программы первого порядка. Идея состоит в том, что для данной программы существует только конечное число лямбда-абстракций, поэтому вы можете заменить каждую лямбду идентификатором, а каждое приложение функции - вызовом процедуры apply, которая разветвляется на этот идентификатор. Это иногда используется в компиляторов для функциональных языков, но его применение ограничено тем , что утрата функции является преобразование целого программа (вы должны статически знать все функции в программе), и поэтому только целого программы компиляторы делают использование Это.

Тем не менее, у Поттье и Готье есть заданный алгоритм дефункционализации с полиморфной типизацией, использующий более сложную типизацию с использованием GADT. Теперь, учитывая их кодировку, можно добавить универсальный случай к их лямбда-типу данных, который не является тегом, но содержит функцию более высокого порядка. Это означает, что должна быть возможность использовать их кодирование для дефункциональной работы на основе модуля к модулю.

Кто-нибудь сделал это, и указывают мне на компилятор, использующий эту идею? (Игрушечные компиляторы в порядке, и на самом деле предпочтительнее.)

Нил Кришнасвами
источник

Ответы:

6

Один подход описывается

Георгиос Фуртунис и Николаос С. Папаспиру. 2013. Поддержка отдельной компиляции в неработающем компиляторе. SLATE 2013.

Как @gasche упоминает:

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

ni0<i<nni

Blaisorblade
источник
4

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

Не могли бы вы подробнее рассказать о том, что вы здесь имеете в виду? Я не понимаю, как добавление базового случая (это будет к типу данных, к сопоставлению с образцом диспетчерской функции или к обоим?) Помогает модульности, как вы описали; кстати, почему вы имеете в виду именно «модуль за модулем»?

Я могу представить себе «базовый случай», который используется внутри данного модуля / программы для выборочной дефункционализации: у вас будет дополнительный конструктор для вашего типа функции reified, который не является тегом, а просто встраивает все 'a -> 'bфункции, чтобы упаковать функцию в этом конструкторе, вместо присвоения ему тега reified, будет предотвращаться его нефункционализация.

Другой подход к решению этой проблемы состоит в том, чтобы учесть, что каждый модуль может определять свой собственный тип «нефункционализированных функций» и диспетчер / обработчик. Функции из модуля M1должны иметь тип M1.arrowи применяться с использованием M1.applyи т. Д. Хотя это хорошо работает для использования функций первого порядка, я не совсем понимаю, как можно расширить его до функции более высокого порядка (которая не должна знать, откуда берутся их функциональные аргументы): если вы связываете функцию с ее диспетчером, вы снова входите в область косвенных вызовов функций.

Наконец, в статье вы упомянули краткое упоминание о программном и модульном подходе, но я не понимаю, как это связано с вашим предложением. То, что они описывают, выражается в терминах «открытых расширений» как функций, так и типов данных (функций и типов, которые могут быть определены в нескольких независимых модулях). В основном это ML-способ описать тот факт, что вы можете отложить комбинацию анализа / преобразования независимых модулей во время соединения, ослабляя необходимость преобразования всей программы.

gasche
источник