Закрытие преобразования и отдельная компиляция вызовов функций более высокого порядка - PullRequest
Новая
       26

Закрытие преобразования и отдельная компиляция вызовов функций более высокого порядка

9 голосов
/ 20 февраля 2010

Существует ли стандартный способ взаимодействия между отдельной компиляцией и различными видами преобразования замыканий при компиляции вызовов функций более высокого порядка?

Мне известны три функционально-подобные конструкции, которые отчетливо компилируются в большинстве языков программирования: замыкания, функции (верхнего уровня) и объекты функций в стиле C ++. Синтаксически они вызываются одинаково, но компилятор оптимально генерирует сайты вызовов определенной формы: 

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, поскольку первая - это простой указатель функции после подъема, а вторая - замыкание.

Я могу придумать четыре способа решения этой проблемы:

  1. Подход C ++ (98), который заставляет вызываемого пользователя либо выбирать форму сайта вызова (через формальный тип параметра: виртуальный функтор, указатель функции или не виртуальный функтор), либо отбрасывать отдельную компиляцию с использованием шаблон, эффективно определяющий решение № 2 ниже.

  2. Перегрузка: компилятор может выполнить несколько экземпляров map и всех других функций более высокого порядка с соответствующим изменением имени. В сущности, для каждой формы вызова существует отдельный тип внутренней функции, и разрешение перегрузки выбирает правильное.

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

  4. Сохраните «естественную» сигнатуру для функций верхнего уровня, но предписывайте, чтобы вся обработка параметров функций высшего порядка осуществлялась через замыкания. «Дополнительные» замыкания для уже закрытых функций вызывают функцию-батут обертки, чтобы отбросить неиспользуемый параметр env. Это кажется более элегантным, чем вариант 3, но сложнее реализовать эффективно. Либо компилятор генерирует множество независимых от соглашения о вызовах оболочек, либо он использует небольшое количество thunks, чувствительных к соглашению о вызовах ...

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

В любом случае, вопросы:

  • Имеет ли эта проблема явное название в литературе?
  • Есть ли другие подходы, кроме четырех выше?
  • Есть ли общеизвестные компромиссы между подходами?

1 Ответ

17 голосов
/ 20 февраля 2010

Это довольно глубокий вопрос с множеством разветвлений, и я не хочу писать научную статью здесь. Я просто поцарапаю поверхность и укажу вам больше информации в другом месте. Я основываю свой ответ на личном опыте с Glasious Glasgow Haskell и Standard ML из Нью-Джерси , а также на научных работах, написанных об этих системах.

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

  • A известный вызов означает сайт вызова, где компилятор точно знает, какая функция вызывается и сколько параметров он ожидает.

  • неизвестный вызов означает, что компилятор не может выяснить, какую функцию можно вызвать.

  • Известный вызов полностью насыщен , если вызываемая функция получает все ожидаемые параметры и переходит прямо к коду. Если функция получает меньше аргументов, чем ожидает, функция применяется частично , и вызов приводит только к выделению замыкания

Например, если я напишу функции 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 против Eval / Подать заявку на языки высшего порядка Саймон Марлоу и Саймон Пейтон Джонс. Одна из многих замечательных особенностей этой статьи заключается в том, что она объясняет, почему тип функции не сообщает вам, является ли вызов этой функции полностью насыщенным.

Чтобы подвести итоги пронумерованных альтернатив: номер 1 не является стартером. Популярные компиляторы используют гибридную стратегию, связанную с номерами 2 и 3. Я никогда не слышал о чем-то похожем на номер 4; Различие между известными и неизвестными вызовами кажется более полезным, чем разграничение функций верхнего уровня от аргументов типа функции.

...