От математики к обобщенному программированию

Если ваш опыт программирования от года и больше, если вам доводилось писать программы больше, скажем, 3000 строк исходного кода, то вы, безусловно, найдете в книге много полезного и занимательного (поверьте, математика не обязана быть скучной!).

Если ваш опыт программирования от года и больше, если вам доводилось писать программы больше, скажем, 3000 строк исходного кода, то вы, безусловно, найдете в книге много полезного и занимательного (поверьте, математика не обязана быть скучной!).

• Степанов А.А., Роуз Д.
• ISBN: 978-5-97060-289-8
• Издательство «ДМК Пресс», 2015
• http://dmkpress.com/catalog/computer/978-5-97060-289-8

Честное слово, я и не подозревал, что вот уже более сорока лет говорю прозой. Большое вам спасибо, что сказали.

Жан-Батист Мольер «Мещанин во дворянстве»

Для большинства программистов, знакомых с такими языками как C++ или Java, понятие обобщенного программирования (англ. generic programming), вынесенное в оригинальное название книги, означает, прежде всего, языковые конструкции, позволяющие специфицировать типы данных, хранимые в коллекциях. Типичными примерами (на Java) являются, например, следующие:

// Список строк

ArrayList <String> = new ArrayList <> ();

// Карта (соответствие «ключ:значение»)

Map <String, MyType> table = new TreeMap <> ();

Опытные программисты, безусловно, хорошо знакомы с подобным синтаксисом и знают, что таким образом можно создавать весьма сложные типы данных, «упакованных» в компактные и обозримые структуры. Одним словом, generic-ки это удобный, продуктивный и надежный способ создания новых типов данных.

Перевод самого термина «generic» весьма не однозначен и зависит от контекста (напомним, например, что «дженериками» называют лекарственные средства, которые производятся как заменители патентованных препаратов по лицензиям их правообладателей). В программировании под generic-ами часто понимаются т.н. обобщенные и параметризованные типы данных (см.примеры выше), что, в общем, правильно, но на мой взгляд, не столько проясняет, сколько затемняет смысл понятия. Я не буду вдаваться в этимологические тонкости, а скажу только, что авторы рассматриваемой книги под generic programming понимают «некоторый подход к программированию, концентрирующийся на проектировании алгоритмов и структур данных таким образом, чтобы они функционировали в самом широком окружении без потери эффективности» (перевод мой).

Согласитесь, что такое определение в силу его общности не слишком информативно. Но давайте не будем спешить, а обратимся к книге и, прежде всего, к ее оглавлению.

Первое, что обращает на себя внимание – то, что авторы избрали способ изложения, который принято называть «генетическим»: проблемы ставятся и рассматриваются в историческом контексте. Такой способ изложения весьма распространен в книгах по математике (см. например, «Последняя теорема Ферма. Генетическое введение в алгебраическую теорию чисел» Г.Эдвардс, М.: Мир, 1980) и позволяет аккуратно ввести читателя в круг рассматриваемых проблем. Генетический способ изложения концентрируется не только на математической составляющей той или иной проблемы, но и на истории появления самой проблемы и предпринятых способов ее решения. Читатель не столько читает, сколько погружается в ту или иную область; он ощущает себя не пассивным субъектом, а активным участником интеллектуального действа.

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

После этого в значительной степени вводного материала (гл. 1 ... 5) авторы обсуждают понятия, которые – увы – большинству программистов (если только они не имеют математического образования) неизвестны: группы, моноиды, кольца, поля и пр. Это – уже элементы абстрактной алгебры. Но не стоит заранее пугаться только потому, что раньше вы всего этого не знали. Прочтите-ка еще разок эпиграф к этому обзору.

Думаю, что я не ошибусь, если скажу, что со многим из этого – и группами, и кольцами, и полями – вы, скорее всего, неоднократно сталкивались, но только, возможно, не знали, что они так называются.

Эти три главы (с 6-й по 8-ю), посвященные абстрактной алгебре и алгебраическим структурам, могут показаться достаточно сложными, но я спешу успокоить тех, кто сомневается в своих математических способностях – не так страшен черт, как его малюют. Конечно, сам материал этих глав достаточно непривычен, но он отнюдь не так сложен, как может показаться. Вспомните, как вы осваивали велосипед или учились кататься на коньках – были и падения, и ушибы, но, в конце концов, вы научились. Так же и в математике – первые шаги в новой области будут непростыми. Но преодолимыми, поскольку нет людей, не способных к математике; есть только лень и необоснованные сомнения.

Безусловно, вы вправе спросить «Ну, и зачем мне нужны все эти кольца, группы или какая-то теорема Лагранжа?». На это я могу ответить одно – чтобы понять вкус кофе, надо пить кофе; чтобы стать знатоком музыки – надо слушать музыку. Можно, конечно, сразу же решить, что абстрактная алгебра с ее непривычным аппаратом и понятиями вам не нужны,– это, конечно, ваше право. Но тогда вы и не поймете, чего лишились. Не спорю, возможно, все эти алгебраические премудрости лично вам и не нужны, но как можно быть в этом уверенным, если вы с ними даже не познакомились? Так что я прошу вас не спешить и не делать поспешных выводов.

Еще несколько слов в «защиту» алгебры (в чем, она, конечно, не нуждается). Вспомните определение generic programming, приведенное в начале этой заметки; ключевое в нем – функционирование алгоритмов и структур данных в самом широком окружении. Так вот, алгебра и изучает, и предоставляет нам – программистам - это «самое широкое окружение». Более того, вся современная математика постепенно алгебраизуется, т.е. воспринимает понятия и методы, исходящие из алгебры. А программирование – как ни крути – это именно математика.

Оставшиеся главы книги посвящены заметкам о математике как об области знаний (гл.9), фундаментальным концепциям программирования в контексте ранее изложенных математических понятий (гл.10), а также рассмотрению ряда алгоритмов (гл. 11 ... 13). Разумеется, изложение ведется с точки зрения обобщенного программирования с опорой на концепции, введенные в предыдущих главах.

Кроме того, в книгу включены три небольших приложения, последнее из которых описывает некоторые особенности C++ для тех, кто не знаком с этим языком программирования.

В целом, книгу можно рекомендовать всем думающим программистам (хочется верить, что таких, все же, не так мало по сравнению с необозримой армией поденщиков от программирования). Если ваш опыт программирования от года и больше, если вам доводилось писать программы больше, скажем, 3000 строк исходного кода, то вы, безусловно, найдете в книге много полезного и занимательного (поверьте, математика не обязана быть скучной!). Важно даже не то, какие именно математические факты вы узнаете из этой книги, а то, что вы расширите свой кругозор и увидите, какие фантастические возможности таятся в сплаве «сухой» математики и практического программирования.

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

И, напоследок, следует напомнить, что один из авторов книги – Александр Степанов – заслуженно относится к числу самых выдающихся программистов современности. Он стоял у истоков generic programming и, безусловно, является первоисточником и авторитетом в понимании смысла и содержания этого понятия. Для программистов С++ позволю себе еще напомнить, что библиотека STL (обобщенные алгоритмы, контейнеры и средства доступа к ним) – творение А.Степанова