Lev Walkin (lionet) wrote,

Автор C++ о диспетчеризации по типам и о #Haskell

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3449.pdf

Open and Efficient Type Switch for C++

Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup


Автор C++, Страуструп сотоварищи, пишет в соавторстве статью о новой библиотеке для диспетчеризации по типам с помощью внешней интроспекции. Написано на шаблонах C++11 и оформлено в виде библиотеки. Называется Mach7. Выглядит в итоге как-то так:



Ну ничё так.

Теперь о том, что заинтересовало меня. В статье есть периодические отсылки к функциональному программированию.

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

struct Expr { virtual int eval () = 0; };
struct Value : Expr { ⋯ int eval (); int value ; };
struct Plus : Expr { ⋯ Expr& e1; Expr& e2; };


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

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

Насколько быстро теперь работает? Говорят, примерно как OCaml или Haskell:
Библиотека реализована как стандартный C++11 код с шаблонным мета-программированием и несколькими макросами. Оно работает примерно также быстро, как эквиваленты на OCaml или Haskell, и даже иногда приближается по быстродействию или даже становится быстрее написанного руками C++ кода, который использует Visitor дизайн-паттерн.

Ну это хорошо, что так быстро, как OCaml или Haskell. Вопрос, зачем при таком раскладе использовать C++, замнём для ясности.

Но дальше вообще прелесть идёт: критика паттерна Visitor!
Библиотека Mach7 и идеи в ней были мотивирована нашим неудовлетворительным опытом работы с различными C++-ными фронт-эндами и фреймворками для анализа программ. Проблема была не с самими фреймворками, но с фактом, что мы должны были использовать шаблон проектирования Visitor для того, чтобы смотреть, обходить и обогощать абстрактные синтаксические деревья целевых языков. Мы нашли Visitor-шаблоны неподходящими для прямого выражения логики приложения, удивительно сложными для обучения студентов, и часто более медленными, чем решения для обхода, написанные вручную. Вместо них, пользователи опирались на динамические приведения типов во многих местах, часто многоуровневые, таким образом предпочитая более короткий, более ясный, и более прямой код, нежели чем Visitor'ы. Соответствующий проигрыш в производительности был обычно незамечаем до более поздних стадий кодирования, когда уже было поздно что-то менять.

Ну можно поздравить C++, теперь можно на нём отдельные вещи писать почти так же коротко, ясно и почти так же быстро, как на OCaml.



Кроме функциональщины, в посте есть отсылка к лиспу, к Duff's device, и вообще, хорошая статья, надо студентам давать. C++ — это очень большой, огромный джип, и эта статья — неплохая иллюстрация.
Tags: c++, fp, ocaml, papers
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 35 comments