Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Categories:

Представление HOF (High Order Functions) в C++

В С++ функции высших порядков представлены функторами, или объектами-функциями (function object). Объект-функция - это "все, к чему можно применить operator()()". Функции высшего порядка из STL (скажем, стандартные алгоритмы) принимают как раз объекты-функции. Объектами-функциями могут быть свободные функции, статические функции-члены, объекты, у которых определен operator()() и ссылки на такие объекты. Возможно, есть какие-то более экзотические сценарии, вроде переопределенных operator& и кастов (operator funptr()), но их редко пишут руками и в первом приближении можно не рассматривать.

С++ крайне непоследователен, поэтому нестатические методы объектами-функциями уже не являются, и их приходится оборачивать в объекты, фактически, для того, чтобы превратить this в явный аргумент.

На уровне представления в памяти в функцию высшего порядка из STL может передаться:

1) указатель на функцию (указатель типа "указатель на код")
2) указатель на объект (указатель типа "указатель на данные")
3) сам объект (данные переменного размера)

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

1) обычный косвенный вызов
2) вызов метода "operator()()" (чуть ли не дюжина вариантов кода, в зависимости от характера виртуальности!)
3) непосредственный вызов
4) ничего

Умножьте это на несколько вариантов управления памятью при входе-выходе в функцию STL.

При проектировании старались, чтобы у компилятора почаще была возможность генерировать "ничего", и производительность не падала, был "нулевой штраф за абстрактность" (zero abstraction penalty).

Причин такого безусловно кривого дизайна было много: неудачный механизм наследования (разрешение множественно наследовать реализацию), неудачная модель компоновки из объектных файлов (необходимая для обратной совместимости с си и взаимодействия с другими древними языками, но не допускающая WPO и template export), просто тот факт, что шаблонное метапрограммирование и языки с компактным синтаксисом в духе Haskell, Javascript и Python еще не были тогда изобретены.

В результате, оказалось что все варианты ФВП представлены разными типами, у которых нет общего супертипа. И параметры-функции в сигнатурах алгоритмов STL имеют тип просто T, т.е. по-научному forall t . t

Однако создатели С++ на этом не остановились, и добавили еще специализацию шаблонов, частичную специализацию, SFINAE и вывод шаблонных аргументов для шаблонных функций. Плюс перегрузку экзотических операторов, конструкторов и перегрузку функций.

Таким образом, разработчик на С++ по идее должен все эти факторы учитывать при выборе оптимального дизайна. Но на практике разработчики пишут на узком подмножестве С++, и ФВП с шаблонами используют крайне редко.

Поэтому при разработке компилятора, генерирующего человекообразный С++ из языка с ФВП, стоит много разных задач.

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

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

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

Конкретнее описать проблему и возможные пути решения я постараюсь в ближайших постах.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments