SICP, середина

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

Начну с плюсов. Как недавно заметил [info]infowatch, в «околокомпьютерных» областях достаточно велико количество самоучек, а «официальные» учебные планы зачастую неадекватны — следовательно, любой более-менее приличный «компьютерщик» в той или иной степени оказывается «самоучкой». Недостатки такого подхода очевидны — нет «систематичности» знаний и «единой картины мира».

Вообще, складывается такое впечатление, что отечественное программирование во многом представляет собой некий «карго-культ», копирующий внешние стороны такового в США. Кто-то рассказал про интервью при приеме на работу в Google и Microsoft — и все-все-все, включая распоследнюю «веб-студию», бросаются спрашивать про сортировку и красно-белые деревья. То, что когда-то эти вопросы позволяли Google и Microsoft набирать исключительно студентов-отличников ведущих американских ВУЗов — в расчет не принимается. Аналогичное впечатление производят и учебные планы — например, вопросы, связанные с индуктивными вычислениями и прочей рекурсией явно заимствованы из курсов с использованием Lisp наподобие SICP. На «традиционных» у нас C и Pascal они выглядят довольно дико. В общем, самоучки учат самоучек.

Что делать в такой ситуации? Наверное, лучше всего «забить» на попытки Рабиновича напеть Паваротти и «самоучиться» по первоисточникам — тем более, что ситуация с ними сегодня лучше, чем десяток лет назад. Например, SICP достаточно неплохо переведена, и теперь не придется вычленять «разумное, доброе, вечное» из кривого пересказа. Не надо «плеваться» от того, что эта книга — всего лишь «вводный курс» программирования. В свое время, например, кто-то обратил внимание на возраст присутствующих в аудитории на видеолекциях (в интернете выложены видеозаписи лекций по этому курсу) — и там было немало вполне взрослых людей, возможно даже и с опытом работы.

Более того, из-за особенностей применяемого диалекта Lisp, в SICP уже в конце первой главы переходят к вполне содержательным задачам — то есть демонстрирующим не какие-то конструкции языка, а различные подходы к программированию. Это отличает ее от других «вводных курсов», где берется какой-то язык программирования (раньше дико модным был Pascal), подробно изучаются его конструкции, а из «программирования» до обучающихся доводится лишь одна истина — что, оказывается, можно набрать на клавиатуре какой-то текст, затем нажать нужные кнопки и компьютер волшебным образом выполнит то, что хотел программист.

Что меня особенно удивило — я ни разу не видел более краткого описания ООП, чем один-единственный абзац в SICP (в начале 3 главы):

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

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

Разумеется, что все рассматриваемые в SICP подходы к программированию можно показать и с использованием других языков. Например, встречаются решения задач оттуда на Common Lisp (это, правда, не считается — так как он все равно достаточно близок к Scheme), Python, Javascript и даже на C# — в общем, «на чем угодно». Правда, ни один из этих языков (за исключением, разве что, Common Lisp) не подходит для того, чтобы продемонстрировать все эти подходы сразу.

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

Например, в главе 1.3.1 приводятся формулы численного интегрирования, и утверждается, что «определенный интеграл … можно численно оценить с помощью формулы» («the definite integral … can be approximated numerically using the formula «) — при этом не раскрывается ни законность этой оценки (что можно «простить»), ни ее точность. Правда, вычисляются два приближения для одного интеграла, меньшее значение переменной dx соответствует большей точности — и только! В упражнении 1.29 приводится формула Симпсона, утверждается, что она представляет собой «более точный метод численного интегрирования» (в чем эта точность заключается — не объясняется), а затем предлагается проинтегрировать с ее помощью кубический многочлен — якобы это должно «доказать», что она «более точна». Удивительно, но результат оказывается ближе к истинному значению — но это не сходимость, как в первом случае, а просто свойство формулы Симпсона — она дает точное значение при интегрировании кубических многочленов.

Чуть дальше появляются более «страшные» вольности. Например, в «определении» производной (оно необходимо для метода Ньютона) предлагается заменить стремящееся к 0 dx каким-то «очень малым» значением. Сказать, что это приближение, видимо, религия не позволяет.

В конце раздела 1.3 находим упражнение 1.45 — от которого я пришел в ужас. Сообщается, что метод Ньютона не работает для некоторых функций, например, для извлечения корня n-й степени. Предлагается использовать многократное «торможение усреднением» (average damping — этот термин я не встречал нигде, кроме SICP), а «кратность» его применения установить — держитесь — экспериментально! Да, читатель SICP, скорее всего, не сможет доказать полученное утверждение — но предложение «экспериментально» доказать математическое утверждение, согласно современным представлениям, дико само по себе. Может, не стоит вообще давать такие задачи?

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

Продолжение, как говорится, следует.

SICP, середина: 12 комментариев

  1. >красно-белые деревья
    красно-чорные же.

    >как только речь заходит о математических вопросах – то начинается “тушите свет, сливайте воду”
    Думаю это потому что на Западе образование более-менее отражает рынок труда.
    Только единицы процентов разработчиков ПО пойдут разрабатывать шо-то наукоёмкое, где нужно знать дифференциальное исчисление и численные методы.
    Для этих единиц процентов наверняка есть куча спец.курсов по applied math.

    1. > Думаю это потому что на Западе образование более-менее отражает рынок труда.

      Почему же тогда в книжке не изучается Java?

      > Только единицы процентов разработчиков ПО пойдут разрабатывать шо-то наукоёмкое

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

      1. >в книжке не изучается Java?
        Потому шо из всего многообразия книжек, ты выбрал книжку 1996 года.
        Java стала играть значимую роль на рынке бизнес-софта только с версии 2, т.е. с 1998. До этого Java была для кофеварок (но не выстрелила, PIC дешевле, а для кофеварок решает именно стоимость экземпляра) и апплетов (тоже не фонтан, производительности не очень хватало, в то время IMO чаще писали native code в виде ActiveX, чем java applets).

        >ненаукоемкая задачка
        >тайловая электронная карта, известны координаты

        Задачка чо-то не особо характерна.

        Прикладной разработчик не будет её решать.
        Он вызовет у объекта «карта» метод [convertPoint:toCoordinateFromView:] или TryViewportPointToLocation.

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

        Лично я тоже бы не стал.
        Обычно правильный способ искать координаты, это таки инвертировать проекцию: и вычислительно намного дешевле чем тайлы перебирать, и точнее.

        По мне так «изобретать велосипеды» это в данном случае самому реализовывать хорошо известные методы интерполяции..

        1. Еще раз намекну, что это MIT и клали они на «специфику рынка труда» с большим прибором.

          Теперь про карту. Метод «toCoordinateFromView» как раз и надо реализовать. Проблема в том, что ГИС-ядро, которое знает параметры проекции, висит на веб-сервере, и спрашивать у него координаты на каждое движение мышки просто нельзя. При перезагрузке тайлов кидают координаты их углов — а дальше «ебитесь, как хотите».

          1. >ГИС-ядро, которое знает параметры проекции, висит на веб-сервере
            Мнда.
            Зачем серверу-то знать параметры проекции? Он же бедный сломается уже порядка при 10k одновременных пользователей.
            Не судьба что ль было посмотреть, как это сделано у google/bing/yandex/yahoo/OpenStreetMap/всех остальных, и повторить то же самое?

            Anyway.

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

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

            1. > Зачем серверу-то знать параметры проекции? Он же бедный сломается уже порядка при 10k одновременных пользователей.

              10k одновременных пользователей там не планировалось. А знать надо для того, чтобы отрисовывать карту. Тайлы по мере отрисовки (ну или заранее) кешируются. Параметров проекции никто, кроме ГИС-ядра, в общем случае не знает.

              > и повторить то же самое?

              Напомню, что проекция Меркатора — далеко не единственная. Она замечательна тем, что параллели и меридианы представляют собой прямоугольную сетку и пересчет «пиксельных» координат на экране в геодезические координаты происходит легко и непринужденно. Кроме интернетовских карт, используют ее только в морской навигации. Недостатков у нее полно, чего стоит одно искажение площадей — сравни хотя бы Гренландию с Южной Америкой на гугломапсе.

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

              Какие нах текстуры? Мне прислали нарезанную квадратиками карту — допустим, такую:

              http://egsc.usgs.gov/isb/pubs/MapProjections/graphics/bipolar.gif

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

              > не нужно почти ничего знать

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

  2. А может наоборот, предполагалось, что у слушателей имеется достаточная математическая подготовка? Когда курс создавался? В 80е?

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

      1. > все оценки сложности получаются чудовищно сложными методами

        Да, помнится был срач насчёт програзма и высшей математики. :-) Как раз приводились аргументы, что знание рядов и интегралов делает оценку сложностей алгоритмов простой и понятной. А иначе приходится изобретать велосипеды. И хорошо ещё, что с двумя квадратными колёсами, а не сложнее. :-)

Добавить комментарий для Шура Люберецкий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *