четверг, мая 29, 2008

Concepts, Techniques, and Models of Computer Programming

Вот я и стал счастливым обладателем CTM.

Володя, что это за книжка? — спросите вы.

Отвечаю: “Concepts, Techniques, and Models of Computer Programming” — пожалуй, самый полный набор самых полезных идей в программировании.

Все мы знаем, что есть функциональное программирование, логическое, объектно-ориентированное. Есть ленивые вычисления, строгие. Есть concurrency с message passing, есть с shared state. Бывает недетерминизм, бывает программирование в ограничениях, да чего только не бывает.

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

Вот для наведения порядка в голове и нужны такие книги.

Авторы поставили перед собой задачу последовательно, шаг за шагом, изложить самые распространенные и полезные концепции в программировании.

Начинают с декларативного программирования (в их варианте чуть больше, чем чисто функциональное или prolog без поиска), переходят к concurrency (сначала message passing), потом добавляют состояние, объекты, shared state concurrency, доходят до логического программирования, а дальше и до распределенного программирования и программирования в ограничениях. И все это только концепции (можете называть их парадигмами, хотя авторы предпочитают более строгое «вычислительная модель»). А к каждой концепции прилагается еще и куча техник.

В отличии от SICP, в CTM не дается реализация всех моделей с нуля, что несколько расстраивает, т.к. не достигается такой уровень понимания. В книге используется kernel language подход, где для объяснения очередной вычислительной модели выбирается минимальное подмножество языка и объясняется семантика этого подмножества. Из-за такого подхода иногда появляется ощущение, что читаешь лекционный материал, а не семинарский (как SICP). С другой стороны CTM — учебник для 2-го курса — тут надо не только кодить учить. А чтобы рассказать обо всех идеях, используя подход SICP (interpreter approach, по их классификации), пришлось бы раздуть 900 страниц (в формате 20х25 см) тысяч до 3-х.

В качестве языка авторы используют собственную разработку — язык Oz. Но как SICP не является учебником по Scheme, так и CTM — не учебник по Oz. Это книги по Программированию.

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

Пойду читать дальше, чего и вам желаю.

11 комментариев:

semka комментирует...

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

geniepro комментирует...

Авторы поставили перед собой задачу последовательно, шаг за шагом, изложить самые распространенные и полезные концепции в программировании.

А что Вы скажете об аналогичной книге:

Н.Н. Непейвода, И.Н. Скопин "Основания программирования" (Ижевск, 2002)
http://forum.oberoncore.ru/download/file.php?id=232

Vladimir Shabanov комментирует...

Не читал и отзывов не слышал. Так что сказать что-либо внятное не могу.

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

Также язык изложения кажется несколько сложноватым, что-ли. Названия некоторых терминов не очень понятные (сентенциальное программирование, например. есть подозрение, что это логическое программирование, но чуть другое).

В общем я бы пока читать не стал бы. Хотя может отдельные главы посмотрел бы.

А ты сам не читал? У тебя какое-нибудь мнение по этой книжке есть?

geniepro комментирует...

Выборочно читал, но полностью пока не осилил...
Эту книгу просто усиленно и восторженно рекламирует один из русских оберонщиков -- Илья Ермаков, может Вы о нём слышали?

Vladimir Shabanov комментирует...

Вирт (вроде он автор Оберона) плохо высказывался на тему ФП (что-то вроде "какой смысл писать функциональные программы на машинах, которые внутри императивны"). Соответственно все его языки наглухо императивны. А это прошлый век.

Чистое ФП (как в хаскеле) позволяет просто проводить очень нетривиальные оптимизации и получать в среднем код более быстрый, чем у обычной императивной программы. Т.е. ФП сейчас повторяет историю со сборкой мусора, когда все говорили, что оно тормозно, а в итоге оказалось быстрее чем ручное выделение памяти.

Т.е. недостатков производительности у ФП и GC уже нет. А вот достоинств масса.

Так что я не считаю сейчас использование паскаля, С и оберона оправданными. Максимум вставка на С (ни в коем случае не C++). По-этому обероном не интересуюсь. Не перспективно. Слишком низкий уровень.

geniepro комментирует...

> Вирт (вроде он автор Оберона) плохо высказывался на тему ФП (что-то вроде "какой смысл писать функциональные программы на машинах, которые внутри императивны"). Соответственно все его языки наглухо императивны. А это прошлый век.

Это было давно, и хотя сейчас Вирт всё ещё изобретает чисто-императивные языки для всяких PIC-контроллеров, но потихоньку меняет своё мнение об ФП. Вот его недавняя работа:
"On Programming Styles"

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

> Чистое ФП (как в хаскеле) позволяет просто проводить очень нетривиальные оптимизации и получать в среднем код более быстрый, чем у обычной императивной программы.

Это всё замечательно в теории, но на практике у компиляторостроителей пока руки не доходят до реализации таких оптимизаторов. Средняя программа на Хаскелле работает всё-таки медленнее, чем аналогичная на Си, и что бы они выровнялись, на Хаскелле придётся постараться...
Красота Хаскелла при этом теряется... :о(

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

Думаю, это сильно зависит от конкретного алгоритма.
Известно, что в тех же Оберонах сборщик мусора не высвобождает однажды занятую им область памяти, даже если уже не нуждается, так что если GC захватит памяти больше, чем есть свободной, то своппинг на каждой итерации сборки мусора быстро положит программу на лопатки... ;о)

> По-этому обероном не интересуюсь. Не перспективно. Слишком низкий уровень.

Ну, Оберон и был разработан как низкоуровневый язык, замена Си, для реализации операционной системы...

Vladimir Shabanov комментирует...

но на практике у компиляторостроителей пока руки не доходят до реализации таких оптимизаторов.

Вполне доходят. Все чаще и чаще попадаются в блогах упоминания о том как Хаскелл переплюнул С или окемл. И это только начало.

Средняя программа на Хаскелле работает всё-таки медленнее, чем аналогичная на Си, и что бы они выровнялись, на Хаскелле придётся постараться...

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

Красота Хаскелла при этом теряется... :о(

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

Думаю, это сильно зависит от конкретного алгоритма.

В том то и фишка, что поменять алгоритм в хаскеле проще, чем в С.

то своппинг на каждой итерации сборки мусора быстро положит программу на лопатки... ;о)

В ghc вроде вообще можно указать размер кучи. А свопится будут только неиспользуемые участки. Если программа занимает памяти больше доступной, то она и на С будет тупить.

Анонимный комментирует...

Curry не пробовали? Это функционально-логический язык, взято все лучшее из Haskell и Пролога. Такое ощущение, что программы получаются декларативнее и короче, чем на Haskell. Правда, процесс становления Curry еще не завершен, что затрудняет его использование.

Vladimir Shabanov комментирует...

Пробовал Curry несколько лет назад (я тогда очень constraint programming-ом интересовался).

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

Но вроде он уже тогда был подзаброшен, его развивают?

Анонимный комментирует...

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

Анонимный комментирует...

Есть электронный вариант (2004 года) на http://gen.lib.rus.ec/get?md5=010e3dfadd48d815ce185f9ffb8cde25
Качество вполне ничего