Преобразование закрытия и раздельная компиляция вызовов функции высшего порядка
Существует ли стандартный способ иметь дело со взаимодействием между раздельной компиляцией и различными видами преобразования закрытия при компиляции вызовов функции высшего порядка?
Я знаю о трех подобных функции конструкциях, которые отчетливо компилируются на большинстве языков программирования: закрытия, функции (верхнего уровня) и функциональные объекты в стиле С++. Синтаксически их называют тем же путем, но компилятор оптимально генерировал бы отчетливо сформированные сайты вызова:
Syntax: | clo(args) | func(args) | obj(args)
--------------------------------------------------------------------------------
Codegen: | clo.fnc(&clo.env, args) | func(args) | cls_call(&obj, args)
^ ^ ^ ^ ^
fn ptr | +--"top level" fn --+ |
+--- "extra" param, compared to source type -----+
(В C++, cls_call был бы T::operator() для objкласс T. C++ также позволяет виртуальные функторы, но это - по существу случай закрытия с дополнительной косвенностью.)
На данном этапе вызовы к map (x => x > 3) lst и map (x => x > y) lst должен вызвать отличающийся map функции, потому что первым является простой указатель функции после подъема и второго, являются закрытием.
Я могу думать о четырех способах заниматься этой проблемой:
C++ (98) подход, который вынуждает вызываемого к любому выбору форма сайта вызова (через тип формального параметра: виртуальный функтор, указатель функции или невиртуальный функтор) или раздельная компиляция отбрасывания при помощи шаблона, эффективно определяя решение № 2 ниже.
Перегрузка: компилятор мог сделать несколько инстанцирование
map, и все другие функции высшего порядка, с соответствующим искажением имени. В действительности существует отдельный внутренний функциональный тип на форму сайта вызова, и разрешение перегрузки выбирает правильный.Мандат a глобально форма сайта однородного вызова. Это означает, что все функции верхнего уровня берут явное
envаргумент, даже если им не нужен он, и что "дополнительные" закрытия должны быть представлены для обертывания аргументов незакрытия.Сохраните "естественную" подпись для функций верхнего уровня, но мандат что вся обработка функциональных параметрических усилителей высшего порядка быть сделанными посредством закрытий. "Дополнительные" закрытия для уже закрытых функций вызывают функцию батута обертки для отбрасывания неиспользованного
envпараметр. Это кажется более изящным, чем опция 3, но тяжелее реализовать эффективно. Или компилятор генерирует множество calling-convention-indepedent оберток, или он использует небольшое количество чувствительных к соглашению о вызовах преобразователей...
При наличии оптимизированного closure-conversion/lambda, на который походит подъем гибридной схемы, с выбором на функцию того, засунуть ли данный аргумент закрытия в ENV или список параметров, это сделало бы проблему более острой.
Так или иначе, вопросы:
- Эта проблема имеет явное имя в литературе?
- Есть ли другие подходы помимо четырех выше?
- Есть ли между подходами известные компромиссы?
1 ответ
Это довольно глубокий вопрос с множеством ответвлений, и я не хочу писать здесь научную статью. Я просто коснусь поверхности и укажу вам больше информации в другом месте. Я основываю свой ответ на личном опыте работы с Glorious Glasgow Haskell Compiler и Standard ML of New Jersey , а также на научных статьях, написанных об этих системах.
Ключевым отличием амбициозного компилятора является различие между известными вызовами и неизвестными вызовами. Для языков с функциями высшего порядка второстепенным, но все же важным различием является то, является ли вызов полностью насыщенным (что мы можем решить только на известном сайте вызова).
Известный вызов означает сайт вызова, где компилятор точно знает, какая функция вызывается и сколько параметров он ожидает.
Неизвестный вызов означает, что компилятор не может определить, какая функция может быть вызвана.
Известный вызов полностью насыщен , если вызываемая функция получает все ожидаемые параметры и сразу переходит в код.Если функция получает меньше аргументов, чем ожидает, функция частично применяется , и вызов приводит только к выделению замыкания
. Например, если я напишу функции Haskell
mapints :: (Integer -> a) -> [a]
mapints f = map f [1..]
, тогда вызов map известен и полностью насыщен .
Если я напишу
inclist :: [Integer] -> [Integer]
inclist = map (1+)
, то вызов map будет известен , а применяется частично .
Наконец, если я напишу
compose :: (b -> c) -> (a -> c) -> (a -> c)
compose f g x = f (g x)
, то вызовы f и g будут неизвестными .
Главное, что делают зрелые компиляторы, это оптимизируют известные вызовы . В приведенной выше классификации эта стратегия в основном подпадает под №2.
Если все сайты вызова функции известны, хороший компилятор создаст специальное соглашение о вызовах только для этой функции, например, передав аргументы только в правильные регистры, чтобы все работало хорошо. .
Если известны некоторые, но не все сайты вызовов функции, компилятор может решить, что стоит создать специальное соглашение о вызовах для известных вызовов, которые будут либо встроены, либо будут использовать специальное имя известно только компилятору. Функция, экспортированная под именем в исходном коде, будет использовать стандартное соглашение о вызовах , и ее реализация обычно представляет собой тонкий слой, который выполняет оптимизированный хвостовой вызов специализированной версии.
Если известный вызов не полностью насыщен, компилятор просто генерирует код, чтобы выделить закрытие прямо в вызывающей стороне.
Представление замыканий (или того, обрабатываются ли первоклассные функции каким-либо другим методом, например, лямбда-лифтинг или дефункционализация), в значительной степени ортогонально обработке известных и неизвестных вызовов.
(Возможно, стоит упомянуть альтернативный подход, используемый MLton : это компилятор всей программы; он может видеть весь исходный код;он сводит все функции к первому порядку, используя метод, который я забыл. Есть неизвестных вызовов, потому что общий анализ потока управления на языках более высокого порядка неразрешим.)
Относительно ваших последних вопросов:
Я думаю, что эта проблема является лишь одним из аспектов запутанной проблемы, называемой «как компилировать первоклассные функции». Я никогда не слышал специального названия только для этого выпуска.
Да, есть и другие подходы. Я набросал одно и упомянул другое.
Я не уверен, есть ли какие-нибудь обширные исследования компромиссов, но лучшее, что я знаю и которое я очень рекомендую, - это Создание быстрого карри: Push / Enter vs. Eval / Apply для языков высшего порядка Саймона Марлоу и Саймона Пейтона Джонса. Одна из многих замечательных особенностей этой статьи заключается в том, что она объясняет, почему тип функции , а не сообщает вам, является ли вызов этой функции полностью насыщенным.
Подводя итог пронумерованным альтернативам: номер 1 не запускается. Популярные компиляторы используют гибридную стратегию, связанную с номерами 2 и 3. Я никогда не слышал о чем-то похожем на номер 4; различие между известными и неизвестными вызовами кажется более полезным, чем различение функций верхнего уровня от аргументов типа функции.