You are viewing lionet

Previous Entry | Next Entry


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:

Comments

( 35 comments — Leave a comment )
levgem
Sep. 26th, 2012 09:34 am (UTC)
Чудесная статья, спасибо.

Насколько я выступаю за С в образовании, настолько же я против С++ =)
lionet
Sep. 26th, 2012 09:35 am (UTC)
Та же фигня.
alll
Sep. 26th, 2012 09:58 am (UTC)
> зачем при таком раскладе использовать C++, замнём для ясности

Ну типа некритичный кусок кода на C++ (работающий так же быстро, как хаскель) не надо подключать к критичному куску кода на C++ же (работающему так же быстро, как C) через анус автогеном, что уже можно рассматривать как положительный результат. ;) Но по большому счёту скрипач не нужен, да.
_adept_
Sep. 26th, 2012 10:09 am (UTC)
C++ - это большой летающий танк :)

"Here’s the metaphor I like to use: assembly coding is infantry: as fine-grained as one could want to be, but slow (to write), lumbering along at 3.1 miles per hour. C is a tank. It’s robust, it’s powerful, and it’s extremely impressive and well-designed, but it moves at ground speeds: about 50 miles per hour. That’s what it’s designed to do. Languages like Python and Ocaml are airplanes– very fast, from a development perspective, but not fine-grained at all. C++ exists because someone had a fever dream in which these two classes of vehicles got mixed up and thought, “I’m going to put wings on a fucking tank”. The drag and awkwardness imposed by the wings made it terrible as a tank, but it doesn’t fly well either. Java was invented after a few horrible tank-plane crashes, the realization being that the things are too powerful and fly too fast. It’s a similarly ridiculous “tank-icopter”. It’s not as fast as the tank-plane, and few people enjoy flying them, but it’s less likely to kill people."

(http://michaelochurch.wordpress.com/2012/04/13/java-shop-politics/)
palm_mute
Sep. 26th, 2012 10:34 am (UTC)
прекрасно
cottidianus
Sep. 26th, 2012 11:17 am (UTC)
браво
v_l_a_d
Sep. 26th, 2012 10:11 am (UTC)
>Но дальше вообще прелесть идёт: критика паттерна Visitor!

А что в этом такого удивительного?
lionet
Sep. 26th, 2012 10:19 am (UTC)
Для cognizanti — ничего удивительного. Но я же на молодёжь вещаю тоже. Которые иной раз за GoF леса не видят.

Edited at 2012-09-26 10:20 am (UTC)
oleg_taykalo
Sep. 26th, 2012 10:51 am (UTC)
Надо бы выпустить редакцию GoFа со старыми знакомыми паттернами, а в реализацию понапихать всяких монадоборазных штук.

Ну к примеру обсервер сделать не просто обсервером а async monad, стратегии - через ФВП ну и всякое такое..
lionet
Sep. 26th, 2012 10:55 am (UTC)
Периодически FP community порывается сделать что-то такое.
udpn
Sep. 26th, 2012 12:22 pm (UTC)
А ссылочки не найдётся?

Когда-то видел статью, где всего GoF перевели на ФП. С тех пор нигде не видел.
lionet
Sep. 26th, 2012 12:10 pm (UTC)
Близко, но проблему не решает. Проблема такая: познакомить тех, кто только начинает присматриваться к функциональной парадигме, к факту развитости экосистемы ФП до уровня наличия признанных и надёжных шаблонов проектирования. Ситуация примерно такая: "Ну понятно, что на хаскеле факториал можно написать. Но на C++ написано столько кода, что уже понятно, как из этого кода конструировать более высокоуровневые, надёжные конструкции. Есть фольклор, есть best practices. Есть ли такое в ФП, или это просто занятная игрушка синтаксического, а не инженерного уровня?" Задачу ознакомления с подобными практиками в ФП не решишь простым перечислением, вроде: "ну вот мы X реализуем через HOF". Нужно же ещё познакомить человека с HOF, кратко хотя бы. И предоставить вариант на каком-нибудь C++ и рядом на Haskell, с использованием соответствующих шаблонов.

Вот такого введения пока я не видел.
zyxman
Sep. 28th, 2012 10:47 pm (UTC)
Purely function data structures не оно?
lionet
Sep. 29th, 2012 02:03 am (UTC)
Нет, не оно. Это структуры данных. Аналогия примерно такая, как если бы GoF паттернам учили путём разбора устройства и асимптотики хэшей и двоичных деревьев.
udpn
Sep. 26th, 2012 11:23 am (UTC)
Это затянувшийся пост-ссылка или статья? Если второе, то проясни, пожалуйста, вывод. Сам так и не нашёл.

На самом деле, вот так на классах нельзя ваять более-менее интересные ADT, например с параметром. Банальный пример это Maybe. Там нужно унаследовать Nothing от счётного количества классов.
lionet
Sep. 26th, 2012 11:29 am (UTC)
У меня под тэгом papers идут впечатления от некоторых прочитанных мной статей. Кто хочет — читает мои впечатления. Кто заинтересовался темой глубже — могут почитать статью саму по себе.
katresv
Sep. 26th, 2012 04:49 pm (UTC)
Я за то, чтобы таки вспомнить, что программист есть инженер. И чтобы давать хороший математический бэкграунд. Потому что не может быть сложно человеку с хорошим мат.бэкграундом переключаться между различными парадигмами. Математика приучает оперировать абстракциями. А начинать CS надо с ассемблера и архитектуры процессора параллельно с математикой. А там все равно что - хоть с++, хоть паскаль.
lionet
Sep. 26th, 2012 05:11 pm (UTC)
Подавляющее большинство времени у подавляющего большинства программистов в их практике тратится не на математику, а именно что на инженерию. А зачастую даже просто аморфное творчество, базирующееся на интуитивном представлении об семантике того или иного языка программирования. Так вот, функциональные языки программирования, хотя и не сложны сами по себе, и даже очень просты (например, денотационная семантика языка Haskell формализована и лаконично записана, как часть его стандарта! если есть математика в голове, через неё понять Haskell проще, чем C++, для которого этой семантики в таком виде нет), но не являются чем-то, что усваивается программистом сходу и сразу. Он не может "переключиться" в FP, пока не узнает об FP. Он не может использовать FP, пока не загрузит в "правое полушарие" интуитивное представление о семантике языка. Это требует тренировки и какого-то времени на довольно глубокое погружение. Можно утверждать, что любой програмист может за час пофиксить небольшую, ординарную проблему в незнакомом ему языке из списка {C, C++, Java, PHP, Python, Ruby, Perl}, при условии, что он знает любой другой из этих языков. Это не так, если мы берём функциональную парадигму. Нужно предварительное обучение, прежде чем начать переключаться.

А если он не знает FP, то он и не будет думать про FP как про мощный инструмент, даже когда он будет начинать делать задачу, которая идеально ложится на FP. Именно в этом проблема.

Что я могу сделать для этого? Ну вот пост написал, например, который показывает, как создатели языка C++ изобрели синтаксис и семантику, похожие на OCaml/Haskell, потому что они видятся им удобнее, чем то, что было доступно в C++ до этого. Хорошая опорная точка для того, чтобы внимательно присмотреться к парадигме FP, особенно для тех, кто сейчас варится ближе к program analysis и вообще, работе с AST.

Edited at 2012-09-26 05:15 pm (UTC)
katresv
Sep. 26th, 2012 05:47 pm (UTC)
У меня ощущение, что отличный программист, архитектор, вроде Вас, даже не понимает, сколько математики у него в голове. Не осознает, но вполне себе ею пользуется. Асимптотические оценки - математика, а Вы сходу оцениваете асимптотическую сложность представленного Вам алгоритма. Лично я наблюдала результаты аморфного творчества, которые заключались в том, что человек просто не понимал концепции областей видимости, почему при выходе из процедуры у него нигде не сохраняются локальные переменные, javascript замыкания просто свели бы его с ума. Когда на больших объемах данных даже не делается попытка поискать решение O(NlogN), а берется O(n^2) - а что, интуитивно же! log - это тоже, кстати, математика, хоть и школьный курс. Возьмем хоть ФП и банальное понятие функции как бинарного отношения, отображающего одно множество на другое, что суть математика. Инженерии нет без математики, вот я о чем.
zamotivator
Oct. 3rd, 2012 02:40 am (UTC)
Возможно, я избалован, но вы рассказываете про уровень квалификации... точнее, какой там квалификации, её отсутствия.

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

Большинство задач завязано не на математику, а на портфель банальных well-known знаний и моделей - flat memory model, turing machine, адресной арифметикой, булевой алгеброй... блин, да этим оно и исчерпывается.

Между математиками и разработчиками софта разница очень существенная.
И да, математики работающие в айти обычно очень хреновые разработчики, таково моё нескромное мнение.
ironcat_vlg
Oct. 5th, 2012 10:07 pm (UTC)
За последние 10 лет вся математика, которую приходилось использовать укладывалась в рамки арифметики.
А все потому, что я занимался автоматизацией бизнес-процесов. Там все алгоритмы давно зашиты в библиотеки, а понимание какой когда использовать вполне укладывается в правила типа "экономим память используем алгоритм А, экономим время - алгоритм Б". Я, из врожденного любопытсва, разбирал эти алгоритмы и пониал почему оно так или иначе, но в работе это совершенно не обязательно. Зато предменая область стоит перед нами во всей красе.

Я это к чему. Все зависит от задач. Кому математика мать родна, а кому учет амортизации и дебет/кредит.
iamjaph
Sep. 26th, 2012 07:27 pm (UTC)
А почему ФП преподноситься как нечто особенное? Или в ВУЗах калечат программистов? Ведь же еще в школе учат оперировать функциями.
lionet
Sep. 26th, 2012 07:37 pm (UTC)
На практике, мозг студента в российском институте не созрел даже для того, чтобы осознать, для чего он учится. Уж не говоря о том, чтобы понять, зачем ему сдался очередной Пролог или Лисп, который таки дают почти везде. Давать-то дают, но он после универа неизменно воспринимается как "да знаю я эти все ваши штучки, с прологом пришлось ещё в студенчестве потрахаться". Как FP влияет на построение больших систем, на облегчение работы в команде человек не сможет понять ещё долго, пока ему не придётся самостоятельно делать нетривиальную архитектуру. Непременно, нужно не раз и не два наесться кактусов с императивной лапшой и задуматься, а как можно ограничить, упростить, разделить и завластвовать.

Вот тогда его и нужно подхватить и научить FP. До этого момента всё почти без толку. Некоторые студенты всерьёз чувствуют себя программистами, выучив HTML и оператор for в PHP.

То же самое, я считаю, должно быть и при поступлении в вузы — поступать должны те, кто поработал уже на настоящей работе несколько лет, и понял, каких именно знаний им не хватает. И пришёл уже бы вуз конкретно за этими знаниями, а не для того, чтобы отсидеть.

Это всё очень схожие вещи.
__hedin
Sep. 27th, 2012 01:46 pm (UTC)
Есть программисты, "вышедшие" из психологов, учителей, художников, биологов. Кодить можно не только математику. Можно написать отвратительное решение с точки зрение математики, но оно хотя бы будет существовать.
Я всячески за появление авторитетного дока, в котором функциональщики бы последовательно описали видимый профит от перехода между привычным методом думать и записывать, и своим мироощущением. Для всех тех, кто не желает тратить 15 лет в пещере на постижение дзена.
katresv
Sep. 26th, 2012 05:55 pm (UTC)
Вот, кстати, на курсе "вероятностные графические модели" было много студентов, которые не знали азов комбинаторики. Я не утверждаю, что любому инженеру надо поместить в голову все мат.дисциплины мех-мата МГУ, но математический базис необходим.
francis_drake
Sep. 26th, 2012 07:46 pm (UTC)
Возьмётесь составить список?
esil0x
Sep. 26th, 2012 08:44 pm (UTC)
> Вопрос, зачем при таком раскладе использовать C++

Так я не понял, а как реализуется ихний "open type switch" на том же haskell или ocaml? Насколько я помню в ихних алгебраических типах нет чего-то аналогичного наследованию.
love5an
Sep. 26th, 2012 09:17 pm (UTC)
Я не понимаю, зачем C++ так уродуют и дальше?
Это всё(ровно как и другие высокоуровневые конструкции) не взлетит, пока в языке нет как минимум GC и вменяемой информации о типах в рантайме.

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

Ну то есть, ок, я еще мог держать в голове ручное управление памятью, деструкторы, исключения, "совместимость с Си", шаблоны и RTTI, и как-то пытаться совмещать их, хотя и то, это где-то на пределе возможностей, и я постоянно делал кучу ошибок(огромную кучу), а некоторые из знакомых даже этого просто не выдерживали, и отказывались работать с C++. Но если в язык так и будут пихать всё что придумают, я вот, честно, из принципа не пойду ни на одну вакансию, связанную с плюсам - на этом же просто невозможно будет писать.
Vitaly Mayatskikh
Sep. 27th, 2012 03:28 am (UTC)
А кто сказал, что плюсовые вакансии требуют весь фарш? Пишут в том виде, который смогли освоить, т.е. обычно за пределы си с классами, stl, да shared_ptr не выходят.
Игорь Петров
Sep. 27th, 2012 09:29 am (UTC)
Для адекватного сравнения производительности с хаскелем у авторов статьи квалификации не хватило:
www.reddit.com/r/haskell/comments/10i859/does_stroustroup_have_some_fp_envy_this_is_a/c6dqupe
не удивлюсь, если и в случае сравнения с окамлом ситуация аналогичная. Так что говорить о "почти так же быстро", думаю, преждевременно.
rssh
Sep. 27th, 2012 12:42 pm (UTC)
дяденьки, только на костре не сжигайте, но в реалтаймовую игрушку на С++ разбор AST деревьев можно сравнительно легко вставить (как в OCAML), а вот наоборот - пока значительно сложнее
migmit
Sep. 27th, 2012 02:40 pm (UTC)
Вставить в разбор AST-деревьев риалтаймовую игрушку на C++? Жжоте.
max630
Sep. 27th, 2012 04:50 pm (UTC)
вопрос - с каким ocaml они сравнивали производительность, если с простым матчем по типу - это одно, а если с гардами да вложенными паттернами (а это как раз "динамические приведения типов ... часто многоуровневые"), которые линейно перебираются - совсем другое
( 35 comments — Leave a comment )

Profile

lionet
Lev Walkin
Website

Latest Month

July 2014
S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
Powered by LiveJournal.com
Designed by yoksel