Про любительский подход

У ребе [info]metaclass обсуждают три простых тезиса про выбор языка программирования. Тезисы звучат так: «работает — не трогай!».

А сегодня я в процессе обАСУчивания некоего объекта был свидетелем интересного разговора. Обсуждались некие «общеинженерные» и «организационные» вопросы — и я поймал себя на том, что обсуждаемые этапы проекта прекрасно ложатся в выделяемые в разнообразных RUP-подобных процессах «фазы». Интересно, переводил ли кто-то «методологии» разработки ПО на ГОСТовский язык? Я знаю только попытку провести параллели между терминами из RUP и ГОСТ в учебном пособии М. И. Кумскова «Базы данных» и его одноименном курсе на мехмате — а все нагугливаемое по RUP и подобным «методологиям» использует исключительно англоязычные термины или кальки с них.

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

Нет, я не имею ничего против программистов-фанатиков (сам такой). Но все холивары «на каком языке писать» пахнут «кружком юных радиолюбителей«, как сегодня обозвали наш НИИ Говна и Торфа (вполне заслуженно, надо сказать). Чем инженер отличается от «юного радиолюбителя»? Как раз тем, что понимает разницу между самим проектом и непосредственной реализацией (программированием, монтажом оборудования, etc).

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

А вот, кстати, вспомнилось

В педивикии наткнулся на статью про MathML. Если вкратце, то это такой мертворожденный язык набора математических формул на основе XML. Полюбуйтесь сами:

 <mrow>
  <mi>x</mi>
  <mo>=</mo>
  <mfrac>
    <mrow>
      <mrow>
        <mo>-</mo>
        <mi>b</mi>
      </mrow>
      <mo>±</mo>
      <msqrt>
        <mrow>
          <msup>
            <mi>b</mi>
            <mn>2</mn>
          </msup>
          <mo>-</mo>
          <mrow>
            <mn>4</mn>
            <mo>⁢</mo>
            <mi>a</mi>
            <mo>⁢</mo>
            <mi>c</mi>
          </mrow>
        </mrow>
      </msqrt>
    </mrow>
    <mrow>
      <mn>2</mn>
      <mo>⁢</mo>
      <mi>a</mi>
    </mrow>
  </mfrac>
 </mrow>

Правда, очень просто и понятно? Сомневаюсь, что человек сможет «увидеть» здесь формулу для корней квадратного уравнения. Для сравнения, в TeX она записывается так:

x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}

…и получается вот такая красота:

root2

В ФАКе по MathML действительно, упоминают про «избыточность» формата — но сами посудите, почему нельзя сделать MathML чуть поумнее? В формулах буквы, цифры и значки обычно имеют вполне определенный смысл и изображаются вполне определенными шрифтами — в TeX просто заранее определены классы символов и правила их изображения (например, значки бинарных операторов вроде ‘+’ обычно имеют «отбивки» слева и справа, а буквы пишутся курсивом). В MathML это приходится задавать вручную — то есть снабжать каждую букву тегом <mi>, а числа — <mn>. Вряд ли можно назвать такой формат и human-readable (а уж про writable говорить не приходится).

Это, кстати, не скрывается. В том же ФАКе пишут, что желательно пользоваться программами-генераторами для создания документов MathML (кстати, такой генератор есть в Windows 7, называется «Панель математического ввода», здорово умеет распознавать всякие каракули).

В общем, про что это я? А про то, что применение XML-подобных языков зачастую просто усложняет задачу. Иногда просто нельзя понять, зачем где-то применен XML и какие он имеет преимущества перед, скажем, ini-файлом. Итак, загибаем пальцы.

— human-readable/writeable — нужно далеко не всегда, а в сложных приложениях совершенно теряется.
— универсальность — в большинстве случаев нафиг не нужна, да и понимается она очень по-разному. W3C, например, «рекламируя» форматы на основе XML, утверждает, что и для XHTML, и для MathML, и для какого-нибудь SVG подойдет один и тот же «универсальный» XML-парсер. Но вот если нам не надо работать с десятью разными типами XML-документов, зачем заморачиваться такой «универсальностью»?
— «самодокументируемость» — без комментариев. Конечно, вот такое еще можно понять, но как разобраться в том же MathML без специального руководства?

custom-dll-definition

— текстовый формат — в свете написанного выше не совсем понятно, зачем это нужно. Человеку читать и писать XML надо не всегда, а для парсера все эти текстовые теги совершенно безразличны и только создают избыточность, которой, кстати, парсер пользоваться не имеет права, например, при обнаружении ошибок — в этом случае он должен сказать, что документ не является синтаксически корректным. Какое счастье, что многие XML-парсеры пытаются хоть как-то обработать даже не вполне корректные документы!

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

Через десяток-другой сообщений американцы были ознакомлены с теорией «золотого миллиарда», XML я обозвал технологией, придуманной по принципу «с жиру бесятся», а уж сжатие XML вообще не нужно.

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

Об одном терминологическом заблуждении

Несколько лет назад я проходил собеседование в одной фирмочке, занимающейся разработкой софта. «Собеседование» — громко сказано, заключалось оно в рассказе потенциального работодателя о прелестях их фирмы, озвучивании предложения по зарплате (19 тыр на испытательный срок, затем 25) и нескольких вопросах ко мне. Вопросы были такие: чем отличается функция от процедуры, как я себе представляю процесс разработки ПО и какую последнюю книгу по программированию я читал.

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

Разумеется, «отличник», заучивший определение, должен ответить что-то типа «В Бейсике и Паскале функция возвращает значение, а процедура не возвращает, в Си различия между функциями и процедурами нет, функция, которая не возвращает значение, имеет специальный тип void». Тем более удивительно, что я так и ответил, даже зная наизусть то определение функции, которое на мехмате давал А. Г. Кушниренко (в курсе «Программирование и работа на ЭВМ», как это не странно). Почему-то функция в математике и функция в программировании были для меня разнородными понятиями, просто вторая была отдаленно похожа на первую.

Вообще, история понятия функции довольно интересна. Впервые его ввел еще Лейбниц, понимая под функцией «нечто», задаваемое формулой. Функции отождествлялись с графиками, затем к середине XIX века появилось более-менее современное определение числовых функций — как правила, сопоставляющего одному числу (аргументу) другое (значение). Кроме того, это понятие обобщалось на случай функций многих переменных, вектор-функций, многозначных функций и прочих подобных понятий. Наконец, в самом начале XX века было дано современное определение функции — как тройки из множества определения X, множества значений Y и подмножества f из их декартова произведения X*Y, такого, что для любого x из X существует единственный элемент <x, y> из f, где y — некоторый элемент Y. Это определение начисто выносит мозг первокурсникам, пришедшим на первую лекцию по математическому анализу — ведь многие искренне считают, что функция — это правило, по которому одному числу ставится в соответствие другое — так написано в старых школьных учебниках для шестого класса. В более новых учебниках приведено в смягченной форме мозгоразрывающее определение — там X и Y — обязательно числовые множества, а вместо «подмножества декартова произведения» говорится просто — «правило, ставящее в соответствие».

Кстати, нельзя начинать определение функции с «правила». Правило, то есть подмножество декартова произведения, стоит лишь на третьем месте. Для начала надо определить множества, где функция определена, и какие значения она принимает.

Так вот, мозгосносящее определение адски сильно — так как X и Y могут быть чем угодно. Например, пусть X — это множество текстовых строк, а Y — множество неотрицательных 32-битных чисел. Тогда strlen прекрасно описывается в этих терминах. Декартовым произведением X и Y будет множество пар из текстовой строки и числа, а «выделить» их следует так, чтобы текстовой строке соответствовала ее длина. Можно сделать областью определения множество пар 32-битных чисел с плавающей запятой, а областью значений — двухэлементное множество значений типа bool — а функция будет просто сравнивать эти числа. В общем, вы поняли.

На этом месте любой программист должен возмутиться — как же так, ведь функция обычно должна что-то делать, а возвращаемое значение зачастую никому и не нужно, возьмем хоть тот же printf. Это чудовищное заблуждение тех, кто видел только процедурные языки программирования, вроде Паскаля. «Что-то полезное» не зря называют «побочным эффектом» — у «настоящей» функции побочных эффектов быть не должно.

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

Для чего это может быть нужно? «Настоящая» функция зависит только от своих аргументов, не изменяет ничего лишнего, а единственным результатом ее работы является вычисленное значение. Это позволяет, например, легко распараллелить программу, написанную в функциональном стиле (то есть в том, который я описал, как присущий Лиспу). Попробуйте «распараллелить» длинную цепочку каких-нибудь присваиваний, уверен, что это потребует ручной работы. А «функциональная» программа паралеллится легко и непринужденно. Кроме того, не содержащая присваиваний функциональная программа потокобезопасна, а для «обычных» программ потокобезопасность — это темный лес и страшное вуду. Я почти не шучу, буквально месяц назад читал откровения эмбеддеров по поводу того, как надо использовать слово volatile.

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

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

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

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

Необычное программирование

Этнограф сидит напротив шамана и думает: «Бедный, невежественный дикарь! Неужели он правда считает, что в мире духов действительно существует такой же Енисей, такая же тайга и такие же олени? Вот примитивная какая религия!»
Шаман сидит напротив этнографа и думает: «Вот блин, как же мне объяснить этому доброму, но бедному и невежественному дикарю, что сакральный топос отличается от профанного субстанциально, а не экзистенциально? О! Скажу-ка я ему, что в мире духов существует такой же Енисей, такая же тайга и такие же олени — авось хоть что-то поймет».

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

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

Есть некое хорошо известное высказывание — «вся европейская философия — это комментарии к Платону и Аристотелю». У него есть менее известное «добавление» — «до Витгенштейна». Платон и Аристотель предполагали первичным существование вещей — Витгенштейн же утверждает следующее:

<…>
1.1. Мир есть совокупность фактов, а не вещей.
1.11. Мир определен фактами и тем, что это все факты.
1.12. Потому что совокупность всех фактов определяет как все то, что имеет место, так и все то, что не имеет места.
<…>
2. То, что имеет место, что является фактом, — это существование атомарных фактов.
2.01. Атомарный факт есть соединение объектов (вещей, предметов).
<…>
2.012. В логике нет ничего случайного: если предмет может входить в атомарный факт, то возможность этого атомарного факта должна предрешаться уже в предмете.
<…>
2.013. Каждая вещь существует как бы в пространстве возможных атомарных фактов. Это пространство я могу мыслить пустым, но не могу мыслить предмет без пространства.
<…>
2.0141. Возможность вхождения объекта в атомарные факты есть его форма.

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

Какое отношение это может иметь к программированию? Действительно, «обычное», то есть в современных реалиях — объектно-ориентированное программирование, изначально оперирует предметами. Но в том же «Логико-философском трактате» содержится очень интересная мысль о том, что «естественный язык» может ограничивать способности к познанию. В нашем случае «естественным» языком будет что-нибудь вроде C++ или Java — и они, разумеется, ограничивают нас тем, что требуют описывать объекты, а не факты.

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

Один из способов решения этой задачки — небольшое количество кода на Lisp, позволяющее описать, скажем, формулу, связывающую температуру по Цельсию и Фаренгейту 9C = 5(F — 32) следующим образом:

(define (celsius-fahrenheit-converter c f)
   (let ((u (make-connector))
         (v (make-connector))
         (w (make-connector))
         (x (make-connector))
         (y (make-connector)))
     (multiplier c w u)
     (multiplier v x u)
     (adder v y f)
     (constant 9 w)
     (constant 5 x)
     (constant 32 y)
     'ok))

Выражения с multiplier, adder и constant описывают следующие взаимоотношения между переменными:

c * w = u
v * x = u
v + y = f
w = 9
x = 5
y = 32

Если упростить эти формулы, то получим уравнение 9c = 5(f — 32) — как раз то, что мы хотели получить. При этом наше описание оказывается (благодаря определениям «простейших» примитивов) таким, что может вычислять выражение в «обе стороны» (про использование этой «системы» читайте в SICP по ссылке). Возможно, этот пример окажется не совсем корректным — все-таки мы начинаем с определения «объектов» в выражении присваивания (let), но он довольно прост для понимания. Кстати, попробуйте реализовать что-то подобное «объектно-ориентированным» способом — окажется, что явно выделить «объекты» в этой задаче не совсем просто, а часть из них будет явно излишней.

Давайте пойдем дальше. А именно, попробуем сделать игру в жанре «текстовый квест». В качестве «движка» выберем Inform 7, позволяющий компилировать вот такие описания:

"Hello Deductible" by "I.F. Author"

The story headline is "An Interactive Example".

The Living Room is a room. "A comfortably furnished living room."
The Kitchen is north of the Living Room.
The Front Door is south of the Living Room.
The Front Door is a door. The Front Door is closed and locked.

The insurance salesman is a man in the Living Room. "An insurance salesman in a tacky polyester suit. He seems eager to speak to you." Understand "man" as the insurance salesman.

A briefcase is carried by the insurance salesman. The description is "A slightly worn, black briefcase." Understand "case" as the briefcase.

The insurance paperwork is in the briefcase. The description is "Page after page of small legalese." Understand "papers" or "documents" or "forms" as the paperwork.

Instead of listening to the insurance salesman for the first time:
say "The salesman bores you with a discussion of life insurance policies. From his briefcase he pulls some paperwork which he hands to you."; move the insurance paperwork to the player.

Система программирования не знает заранее смысл терминов «insurance salesman», «briefcase» и «paperwork» — но способна анализировать грамматику «упрощенного» английского языка и исходя из этого анализа — делать выводы о том, что в этом описании является объектами и что с этими объектами можно сделать — то есть строит описание объектов из описания их отношений.

Фактически, мы уже вплотную подошли к так называемым «экспертным системам» и «искуственному интеллекту». Вообще, очень популярным в этих системах был язык Lisp, позволявший сравнительно просто (смотри выше ссылку на SICP) описывать новые синтаксические конструкции и в зависимости от библиотеки «становиться чем угодно». Lisp превращается и в объектно-ориентированный язык с помощью, например, Common Lisp Object System, и в гораздо более интересные вещи. Например, существует проект Cyc («цик», от encyclopedia), ставящий своей целью описать «все» знания. Основным языком программирования в Cyc является CycL — фактически, «очень ограниченный» диалект Lisp.

Например, фраза «Билл Клинтон — президент США» может быть записана следующим образом (с помощью предиката Is A — «является»):

(#$isa #$BillClinton #$UnitedStatesPresident)

А вот другой стандартный предикат — Generalises, «обобщает»:

(#$genls #$Tree-ThePlant #$Plant)

«Всякое дерево является растением».

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

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

Про ООП

Снова услышал такую точку зрения на объектно-ориентированное программирование (цитирую другое ее изложение):

С++ и обжектпаскаль — это приятный синтаксический сахар, что-то типа процедур. Что-то типа — в том смысле, что мы «инкапсулируем» некий функционал в более или менее закрытые кирпичики, у которых все потроха внутри и попортить их сложнее.

сиплюсявые Классы — чуть хитрее. Это структурки и код работы с ними, плюс некие странные механизмы наследования.

В общем, утверждается, что ООП — это некое расширение обычного процедурного программирования, делающее более удобным объединение структур данных и работающего с ними кода. Из этого очень часто делается вывод, что, допустим, C++ — это не более, чем ненужная надстройка над обычным C. Этому способствует, скажем, изучение библиотек WinAPI и MFC — так как вторая является «объектно-ориентированной оберткой» над первой, формируется представление, что ООП мало чем отличается от процедурного программирования.

Так ли это? Действительно ли повсеместное использование ООП — это дань моде? Хотелось бы думать, что нет. И сразу же обращу внимание на то, что библиотека WinAPI на самом деле спроектирована с использованием принципов объектно-ориентированного программирования — именно поэтому при сравнении WinAPI и MFC кажется, что «объекты» во второй дублируют «необъектные» понятия первой. ООП — это не замена записи вида f(h, a, b, c) на h.f(a, b, c), это совсем другое. Как определяет его Гради Буч (в книге «Объектно-ориентированный анализ и проектирование»),

Объектно-ориентированное программирование — это методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования.

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

«Странные механизмы наследования», в частности, позволяют выразить отношение «A является B» — говоря другими словами, «классы образуют иерархию наследования». Дело не в механизмах (хотя их реализация — крайне интересная штука), а в том, что они выражают. Апологеты ООП утверждают, что «объектно-ориентированное» мышление изначально присуще человеку. Изначально или нет — судить не нам, но вся средневековая философия была как раз «объектно-ориентированной», а началось это все еще с Платона. А именно, Платон считал, что существует «мир идей» и «мир вещей»:

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

Говоря в терминах программирования, существуют описания классов («тождественная идея … отданная на попечение мысли») и их экземпляры («нечто подобное этой идее»). Но труды Платона развивались и дальше. В частности, для средневекового католического богословия важное значение имела так называемая «проблема универсалий» — то есть проблема существования общих, родовых и видовых понятий. Грубо говоря, существуют ли объективно такие понятия, как «человек», общее для всех людей, или же это — просто созданная разумом абстракция? Для богословия был особенно интересен частный случай этого вопроса — если Бог един в трех лицах (Троица), то существует ли он реально и в каком виде? Переводя на язык современного программирования — есть ли «суперкласс» «Бог», для которого «Бог-отец», «Бог-сын» и «Святой Дух» являются «подклассами»? Вообще, философия Платона, Аристотеля и неоплатоников очень здорово излагается в терминах «абстракция-наследование-полиморфизм».

Так или иначе, человеку свойственно видеть вокруг себя объекты и выделять в них что-то общее. Возможно, поэтому ООП оказалось доступно даже для самых тупых «недопрограммистов». Дело не в том, что C++ или Java — «приятный синтаксический сахар», дело в том, что они позволяют стандартными средствами выражать некоторые простые отношения (типа «А является Б») — которые как минимум для «европеизированного» мышления кажутся естественными.

Считайтэ это «вступительной частью» к следующей записи, где я попытаюсь продемонстрировать, как выглядит программирование, «стыкующееся» с другой «философской» основой — а именно, с идеями Л. Витгенштейна о том, что мир состоит из фактов, а не из объектов.

PS На самом деле я это уже демонстрировал, правда, далеко не в «идеально чистом» виде.

Пионерский подход

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

bpla

Такой подход к разработке техники можно назвать «пионерско-партизанским». Звучит он обычно так: давайте возьмем десяток студентов, они на Дошираке и Роллтоне гораздо круче наваяют! А заканчивается он обычно такими вот «открытыми письмами«.

Лично я недавно «щупал» такую «студенчески-самодеятельную» конструкцию. Сразу скажу, что именно из-за впечатлений от нее я написал пост про «Фобос-Грунт«. Документации на это «чудо» практически нет, а та, что есть — реальному положению дел не соответствует. Разработчики — вчерашние студенты, других в НПО имени лавочника не держат. Самое «ужасное» — это то, для чего планировалось использовать девайс уровня сайта cxem.net. Нет, в космос не запускали, но близко к этому.

Если кто-то читал книжку Брукса «Мифический человеко-месяц», то должен помнить приведенное там сравнение программы, программного продукта и программного комплекса. По Бруксу, продукт, то есть программа, предназначенная для использования не только разработчиком, «стоит» в 3 раза дороже «простой» программы. Аналогично, элемент программного комплекса, то есть программа, взаимодействующая с другими компонентами, стоит тоже в 3 раза дороже. Наконец, то, что в переводе названо (видимо, не вполне точно) «Системным программным продуктом», объединяющим в себе свойства программного продукта и элемента комплекса, стоит в 9 раз дороже написанной пионерами на коленке «программы».

В свое время «прорывом» было осознание того, что в программировании можно применять «инженерные» подходы, позволяющие получать результат вне зависимости от разнообразных субъективных факторов. Программист из «Творца» превратился в рабочего на конвейере, выпускающем программные продукты гарантированно приемлемого качества — не шедевры, но вполне пригодные для использования. Почему-то азбучные истины Software Engineering при возврате в ту область, откуда они пришли, вызывают, мягко говоря, недоумение. Любой программист знает, что «достаточно качественная» программа на порядок «дороже» и «сложнее» наколенной поделки, но вот в то, что мелкосерийный БПЛА будет стоить в те же 10 раз дороже собранного юными техниками — почему-то не верит.

Пятничное

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

Вопрос: как делать?

Интересна даже не столько сама задачка, сколько намечающаяся дискуссия в комментах.

http://nicka-startcev.livejournal.com/1298310.html

Умер Деннис Ритчи

ИЧСХ, ни один журналюга об этом даже не заикнулся — а ведь язык программирования C и операционная система UNIX изменили мир сильнее, чем все айфоны с айпадами вместе взятые.

Натаскать к экзамену

[info]knutov затронул, на мой взгляд, крайне интересную тему. На хабре рассказывают о том, как правильно отвечать на вопросы, которые могут задать программисту при устройстве на работу. Грубо говоря, «что надо вызубрить, чтобы обмануть будущего работодателя». У меня неподалеку лежит книга «Deep C Secrets: Expert C Programming» за авторством Peter van der Linden’а, вышедшая в далеком уже 1994 году. В ней одно из приложений посвящено тем вопросам, которые задают на собеседованиях в «лучших фирмах» Silicon Valley. Тогда это было неким откровением, сегодня — те же вопросы задают в любой говноконторке, возомнившей себя «лучшей в мире» — благодаря руководствам типа Joel’овского.

Так вот, вспомнилась мне одна история. Как известно многим, и в чем я не раз признавался, я закончил маткласс 57-й школы г. Москвы. Как пишут на сайте школы, прием в математические классы сопровождается некими вступительными «собеседованиями». На этих собеседованиях предлагается решать задачи типа таких (взято из одного сборника, эти задачи предлагались в 2001 году — «свои» листочки я не нашел, видимо, далеко запрятал):

1. Отрезок [0, 1] разделили на 215 равных частей (от 0 до 1/215, от 1/215 до 2/215 и так далее). В каком отношении число 1/5 делит ту из них, в которую попадает (считая слева направо)?

2. На доске написано 100 чисел: одна единица и 99 нулей. За один шаг разрешается уравнять любые два числа, заменив каждое из них на их полусумму. Мы хотим, чтобы все числа стали равными. Докажите, что это невозможно.

3. Имеются слова: ДУМА, КАМА, КЕША, ДАША, КАША, ДАМА, КУМА. Сколькими способами можно выписать слова в столбик так, чтобы каждое следующее слово получалось из предыдущего заменой одной буквы (остальные остаются на своих местах)?

4. Из фанеры выпилен прямоугольный треугольник с катетами 4 и 5. Он лежит на дне неподвижного прямоугольного ящика 6 х 7. Можно ли его повернуть на 360 градусов, не отрывая от дна ящика?

5 (продолжение) Какова наименьшая возможная площадь прямоугольника, внутри которого можно повернуть этот треугольник?

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

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

В общем, как мне кажется, сегодня типовые вопросы про структуры данных могут годиться лишь для отсева редкостно ленивых кандидатов, не удосужившихся прочитать хотя бы такой FAQ. К «фундаментальному образованию», о котором говорит [info]knutov, эти вопросы отношения уже не имеют.

PS Кстати, к вопросу о 57 школе. Уже давно собираюсь написать некую «рвущую шаблон» вещь о ней. Писать или не надо?

Вдогонку про конфигурационные файлы

Все-таки я забыл один нюанс.

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

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

Линуксы — это хорошо

# apt-get build-dep nginx
Reading package lists... Done
Building dependency tree
Reading state information... Done
Note, selecting 'liblua5.1-0-dev' instead of 'liblua5.1-dev'
The following packages will be REMOVED:
libgd2-xpm php5-gd

(c) [info]alexkuklin

Правильные конфигурационные файлы

Несколько соображений относительно того, как должны быть устроены конфигурационные файлы.

Во-первых, обязательно надо использовать xml-подобный синтаксис. Желательно глотать не любой файл с расширением xml, а только в одной из юникодных кодировок с добавлением трех «нечитаемых» байт в начале (это называется BOM, Byte Order Mark) — чтобы его нельзя было редактировать простыми текстовыми редакторами.

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

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

Я ничего не забыл?

Собираем toolchain для MIPS

Как конченый китаефоб, я попросту не доверяю тем toolchain-ам, которые можно скачать с сайта Ingenic. А как вымирающий миниксовод, просто-таки обязан использовать для разработки Minix.

На самом деле, правда, я решил использовать ноутбук с миниксом как машину для разработки по одной простой причине — Minix 3 сейчас представляет собой довольно странную систему с точки зрения набора средств разработки. Например, make в миниксе — это вариация на темы BSD make, а входящий в Cygwin (под которым я хотел работать сначала) GNU make не понимает «позаимствованные» из NetBSD makefile-ы ядра Minix. Собрать BSD make в Cygwin у меня не получилось, там есть какие-то нюансы, так что я решил портированием миникса заниматься на нем самом.

Естественно, что фирма Ingenic не подозревает о существовании такой ОС и «готовый» toolchain для него не выкладывает. Тем хуже для них, потому как компилятор и утилиты для MIPS ничего особо страшного не представляют. Я решил действовать по инструкции с linux-mips.org. Пока что я собрал только binutils и GCC, перспективы использования отладчика пока туманные (так что все дальнейшее превращается в некую авантюру). Успокаиваю себя тем, что в Minix 3 приличного отладчика тоже никогда не было, и ничего, живут люди.

Итак, для начала скачиваем рекомендованные на сайте версии binutils (2-16.1) и GCC (3.4.4). Думаю, что binutils можно и посвежее, а вот с выбором GCC лучше не торопиться. То, что другие называют «бета-версией», разработчики компилятора GNU считают самостоятельным релизом. Например, в магистерской работе Ингмара Альтинга про портирование Minix 3 на PowerPC специально обращается внимание, что GCC 3.4.6 нормально компилирует MinixPPC, а 4 версия (4.x.x) жестко косячит.

Перед сборкой определим некоторые переменные окружения.

export WDIR=/tmp
export TARGET=mipsel-unknown-linux-gnu
export PREFIX=/usr/local/mipseltools
export PATH="${PATH}":${PREFIX}/bin

Говорят, что в качестве $TARGET можно безболезненно использовать сокращенную запись того же самого — а именно, mipsel-linux, но я не проверял. Вообще, эта строка строится по правилу архитектура-компания-ядро-ОС или иногда — архитектура-компания-ОС, например, mips-sgi-irix6.

Для начала собираем binutils. Тут все без сюрпризов. Распаковываем, конфигурируем, собираем, устанавливаем.

tar xjf binutils-2.16.1.tar.bz2
mkdir build-binutils && cd build-binutils
../binutils-2.16.1/configure --target=$TARGET --prefix=$PREFIX
gmake
gmake install
cd ..

Обращу внимание, что вместо make надо вызывать gmake, в случае с binutils все прокатывает, а с gcc возможны ошибки из-за различия синтаксиса Makefile-ов.

C gcc придется немного повозиться. Во-первых, configure неверно определяет возможности системы, во-вторых, встроенные типы Minix конфликтуют с некоторыми локальными для gcc определениями. Итак, распаковываем и конфигурируем.

tar xjf gcc-3.4.4.tar.bz2
mkdir build-gcc-bootstrap && cd build-gcc-bootstrap
../gcc-3.4.4/configure --target=$TARGET --prefix=$PREFIX --enable-languages=c --without-headers --with-gnu-ld --with-gnu-as --disable-shared --disable-threads

В файле gcc/auto-host.h убираем определения HAVE_GETRLIMIT и HAVE_MMAP_FILE. Кроме того, надо временно закомментировать в файле /usr/include/minix/types.h определение типа block_t. В одном из модулей gcc определяется собственный тип с таким же названием, не имеющий никакого отношения к блокам файловой системы Minix. После этого —

gmake
gmake install
cd ..

Работоспособность всей получившейся хрени можно проверить, собрав u-boot. Все очень просто — скачиваем его с VoGeeky (а можно, кстати, поставить git). Правда, придется поправить Makefile. Вместо конструкции

ifeq ($(ARCH),mips)
CROSS_COMPILE = mipsel-linux-
endif

пишем

ifeq ($(ARCH),mips)
CROSS_COMPILE = mipsel-unknown-linux-gnu-
endif

Теперь можно собирать (естественно, не забыв, что путь к тулчейну был добавлен в $PATH):

gmake volans_nand_config
gmake

После этого компилятор поработает-поработает и выплюнет вполне работоспособный загрузчик. Правда, придется перекинуть его на другую машину, чтобы засунуть в плату — дело в том, что в Minix то ли нет поддержки USB, то ли она в зачаточном состоянии. Соответственно, jzboot запустить не удастся. Ну а как перекидывать файлы — прекрасно написано в руководстве по сетевым возможностям Minix 3.

Про хаброидов

На днях видел на хабре две записи, можно либо смеяться, либо плакать.

Первая — «как правильно писать на Javascript». Первый же совет звучал примерно так:

Никогда-никогда не используйте eval()! Даже если очень надо — все равно не используйте! eval() позволяет порождать код, а это очень-очень нехорошо! Так делать нельзя, потому что так делать нельзя никогда!

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

Доводя это до абсурда, скажу, что самые true-программисты никогда не используют операторы цикла, а обходятся только goto и if в виде

if(condition) goto somewhere;

Всякие бесполезные циклы нарушают логику работы программы, привычную тем, кто всю жизнь писал на FORTRAN-77.

Вторая — чувак для понтов реализовал в C++ вычисления, как он сам сказал, «с плавающей точкой» на этапе компиляции (с использованием шаблонов, разумеется). Я не буду придираться к тому, что на постсоветском пространстве вместо точки «плавает» запятая, потому как заголовок неправильный с самого начала. Число с плавающей запятой — это представление числа в виде мантиссы с фиксированным количеством знаков и порядка. У автора реализовано представление в виде отношения двух целых чисел, это несколько другое «решение». Обычно в программировании это называют «рациональными числами», не заботясь, правда, о полной корректности этой формулировки. Подходы эти принципиально разные и путать одно с другим не надо.

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

Российского образования псто

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

Как я уже говорил, описаний «делай раз, делай два» для триангуляции Делоне в Интернете практически нет. Есть книга А. В. Скворцова, есть несколько разной подробности описаний на сайтах американских университетов, например, из курса CS 294-5 Университета Беркли. Но я пишу этот пост не оттого, что хочу пожаловаться на жизнь — изобретателю велосипедов так делать нельзя, он сам себе злобный Буратино. Я хочу предложить уважаемой публике сравнить программу курса в Беркли с «Практикумом по компьютерной геометрии«, который с 2009 года включен в программу мехмата МГУ.

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

Итак, на первом курсе сей предмет называется «Программирование и работа на ЭВМ» и предполагает сдачу двух зачетов — в осеннем и весеннем семестрах. Твердо установленной программы нет, все зависит от преподавателя, но подразумевается, что два сданных зачета доказывают умение студента писать программы на языке Си. Говорят, что иногда разрешают писать чуть ли не на Паскале. Занятия проходят попеременно в виде занятий за компьютерами и «обычных» семинаров, где препод рассказывает о том, что считает нужным. Например, А. Г. Кушниренко рассказывал про индуктивные функции, про некоторые нюансы языка Си типа арифметики указателей и правильного хранения двумерных матриц, а также — про своих (разумеется, тупых) американских студентов. Кроме того, он пугал нас тем, что на госэкзаменах мы забудем, что такое функция. К сожалению, мне на госах такой вопрос не задали, а я готовился :) Для получения зачета достаточно сдать три-четыре задачи из некоего списка (после этого преподаватель обычно убежден в том, что и остальные задачи студент сдаст, и больше не докапывается). Задачи простые (вот, например, список чего-то подобного), при минимальном знании Си решаются за полчаса каждая (и то время взято с большим запасом). У меня, например, от этого сложилось ложное впечатление, что и дальше все будет так просто.

На втором курсе было уже что-то похожее на вводный курс по Computer Science (с экзаменом в весеннем семестре и все тем же названием). Как всегда, было намешано все и сразу. В два семестра «у нас» запихнули четыре «американских» семестровых курса (вводный курс по C++, алгоритмы и структуры данных, формальные языки и грамматики, и понемногу, для общего знакомства — из курсов по операционным системам и компьютерным сетям). Все это прочитать за указанное время невозможно, поэтому реально программа несколько сокращается. Из лекций (их у нас читал В. В. Борисенко) я помню рассказ про машинную арифметику и стандарт IEEE 754, немного — про вызов функций с передачей параметров через стек в языке Си и ему подобных, было что-то про Register Transfer Language компилятора gcc, про «классические» алгоритмы и структуры данных, типа сортировок, разнообразных стеков, очередей и деревьев, кроме того, студентов развлекали байками о том, как горят в грозу сетевые карточки, и как отличить толстый Ethernet от тонкого. Формально для получения оценки нужно уметь решать задачи из опубликованного в Интернете списка и уметь отвечать на вопросы по программе, реально — надо решить по одной-две задачи из каждой темы или, допустим, найти ошибку в классе, реализующем арифметику произвольной точности (это приравнивается к решению соответствующей задачи). Этого достаточно для того, чтобы получить «пятерку» досрочно, а что происходит на основном экзамене — я не знаю. Говорят, что безбожно списывают, и положительные оценки получают даже полные «нули» по предмету.

В самом начале 2000-х на втором курсе пытались преподавать Java, но в итоге поимели кучу жалоб от студентов, от которых на третьем курсе внезапно потребовали знания Си или Фортрана. Борисенко говорил, что ничего «такого», что есть только в Си, использоваться не будет (а общее подмножество Java, Си и Фортрана осваивается в режиме «не приходя в сознание» за пять минут), но отечественный студент прекрасно умеет пользоваться фразой «а нас этому не учили!«.

Кстати, нельзя не упомянуть матчасть. Нет, это уже не старенький VAX, которому даже посвящен специальный сайт, сейчас мехмат полностью перешел на относительно современные персоналки. Ничего старше Pentium III я уже не застал. Гораздо интереснее софт. Стараниями К. Ю. Богачева на этих компьютерах стоит хитро настроенный Linux, запортить который студенты не могут. Чтобы жизнь малиной не казалась, задачи надо сдавать, используя хитро настроенный gcc (его еще называют «компилятор Богачева»). Там включена опция -Werror, приравнивающая предупреждения компилятора к ошибкам. В результате те, кто пишет дома в более лояльно настроенных компиляторах, сталкиваются с тем, что их программы просто не работают (в частности, компилятор матерно ругается на отсутствие пустой строки в конце файла, или на функцию main, возвращающую нецелое значение).

На третьем курсе начинается «Практикум на ЭВМ». Когда-то давно надо было писать на Фортране под СМ-4. Теперь, когда СМ сдана на цветмет, люди пишут на Си на тех же персоналках. Правда, говорят, что некоторые преподаватели принимают задачи и на Фортране. Не знаю, у нас этого никто не пробовал. Сей практикум растянут на четыре семестра, обо всем по порядку.

Третий курс в основном посвящен реализации алгоритмов из книжки «Методы решения линейных систем и нахождения собственных значений» все того же К. Ю. Богачева. В первом семестре надо написать две программы по 300-400 строк. В первой надо обратить матрицу размера около 1000×1000 (или решить аналогичных размеров линейную систему, это задачи равноценные), во второй — найти собственные значения той же матрицы. Пишутся они совершенно бездумно, простым переписыванием из книжки. Кстати, с точки зрения «справочника рецептов», написана она очень неплохо. Если преподаватель — не К. Ю. Богачев, то этого будет достаточно. Богачев требует несколько большего — а именно, ускорения этих методов в два-три раза. Правда, он еще и объясняет, как это сделать. После того, как сдана «практическая» часть — следует «теоретический» зачет. Всех студентов, сдавших программы, загоняют в аудиторию 14-08 и раздают письменное задание. Необходимо изложить три-четыре метода из книжки, если не полностью — то хотя бы в устраивающем Богачева объеме. Второй семестр — примерно то же самое, только книжка другая. На этот раз — «Методы приближения функций».

Я не буду говорить ничего про Н. Н. Ченцову, которая вела у нас эти занятия, желающие могут составить представление о ее методах обучения, почитав один из околомехматовских форумов.

Четвертый курс несколько забавнее. Например, такого исчерпывающего руководства по всем вопросам, как методички Богачева, больше нет. Кроме того, надо написать не только программу, но и отчет — связный текст на 5-6 страниц, описывающий метод решения и убеждающий преподавателя в его правильности. Конкретные задачи зависят от «препода». Например, кто-то вычисляет интегралы всякими там «методами трапеций» или решает методом Ньютона нелинейные уравнения. У И. С. Григорьева задачи поинтереснее — решение дифференциальных уравнений методом Рунге-Кутта с автоматическим выбором шага и применение принципа максимума Понтрягина в задачах оптимизации (то есть сведение задачи оптимизации, которую человечество в целом решать не умеет, к «решабельной» системе дифференциальных уравнений). Сам Илья Сергеевич регулярно выигрывает некие международные соревнования по решению задач оптимизации и вообще, любит эту тему. Правда, с точки зрения программирования тут все довольно просто и «концептуально» не отличается от, скажем, метода Ньютона решения тех же дифференциальных уравнений. Если имеется «рыба» отчета, то программа вместе с отчетом пишутся за 5-6 часов (а их надо две штуки). Эта простота развращает, но благодаря ей я все-таки увидел Е. А. Лапшина, которого «надо бояться«.

Во втором семестре так же незамысловато решаются уравнения в частных производных. Все еще проще. Собственно, происходящее на третьем и четвертом курсах не имеет никакого отношения к тому, что на Западе называют Computer Science. Это просто практикум по численным методам, но, надо сказать, неплохой — если повезет с преподавателем. У вышеназванной Ченцовой, например, интересных задач не будет — зато будет много геморроя со сдачей отчета. Сегодня она не хочет брать его в руки, потому как «жалко, такой чистый», а завтра будет — «противно, такой грязный». На программу она даже не смотрит, кое-кто даже сомневается в том, что она знает Си.

Кстати, четвертый курс занимается в так называемом «классе Эйч-Пи» (я специально не пишу HP, чтобы не путали с русскими буквами). Это аудитория во «Втором гуманитарном корпусе» (хотя гуманитарность его ставится под сомнение наличием там ВМК и оккупацией мехматом нескольких этажей), где когда-то давно стоял миникомпьютер HP-810 (возможно, название неправильное, так его обозвали на страничке «Компьютеры, которые выбираем не мы«) с пятнадцатью терминалами. Сейчас там стоят обычные персоналки с Windows XP производства, кажется, того же Hewlett-Packard. Так как студенты таскают программы на дискетках, перед тем, как засунуть что-то в компьютер, надо это что-то дать на проверку специально обученной тетеньке, сидящей у входа в класс и умеющей пользоваться Dr. Web с безбожно устаревшими базами и пасьянсом «Косынка». Как нетрудно догадаться, вся зараза первым делом попадает на компьютер с антивирусом, откуда разносится по классу. Систему там переустанавливают по три-четыре раза за семестр. Впрочем, пора бы заканчивать с ностальгическими воспоминаниями.

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

Я уже упоминал, почему в американских ВУЗах программа курса строится не по принципу «меньше тройки не получишь», а исходя из того, что может/хочет рассказать преподаватель. Они могут позволить себе такую роскошь, как заваливающие экзамен 3/4 слушателей, у нас этого просто не поймут. Зато троечникам напрягаться не надо.

UPD http://shura.luberetsky.ru/2011/08/05/neobkhodimye-poyasneniya/ — я отвечаю на некоторые вопросы.

Про рельеф

В продолжение вот этой задачки:

http://shura.luberetsky.ru/2011/07/19/algoritmicheskaya-zadacha/

Я реализовал алгоритм выбора точек, описанный в статье Systematic selection of Very Important Points from Digital Terrain Model for constructing Triangular Irregular Network без каких-либо изменений. Особо не заморачиваясь с производительностью, я добился того, что из миллиарда точек выбиралось порядка миллиона «очень важных» где-то минут за 40. Такое время меня вполне устраивало. Думаю, при желании можно сократить его в два-три раза, но делать этого я не буду, и вот почему.

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

Во-вторых, чудес не бывает. Более-менее адекватное количество «важных точек» можно выбрать тогда, когда их количество меньше общего количества точек где-то на два порядка. Итого миллиард точек исходника даст 10 миллионов точек TIN, или около 20 миллионов треугольников. Это много.

Если «сложить» эти пункты, то можно преобразовать исходный миллиард точек в 10 миллионов (с которых все и началось), а затем сделать из них 100 000 «важных точек» — около 200 тысяч треугольников, сущая ерунда по нынешним временам.

Кстати, хочу поплакаться на жизнь. Пол-пятницы искал нормальное описание того, как алгоритмически сделать триангуляцию Делоне. В интернетах встречается описание алгоритма со сложностью O(N2) — последовательно добавляем точки к существующей триангуляции, при необходимости перестраивая ее. Каждый шаг в худшем случае требует перестроения всех треугольников, и это мне не нравится. Иногда в довольно общих чертах описывают алгоритм типа «divide and conquer» — разбиваем множество точек надвое, строим для подмножеств триангуляции, а затем объединяем их. Сложность, как можно показать, асимптотически оптимальная, O(N ln N). Описание того, как именно надо объединять, обычно отсутствует. В книге Препараты и Шеймоса подробно разбирается задача построения диаграммы Вороного — графа, двойственного триангуляции Делоне, и вскользь делается упоминание о том, что построив диаграмму Вороного за асимптотически оптимальное время O(N ln N), можно преобразовать ее в триангуляцию. Этот подход тоже мне не нравится, так как для построения диаграммы Вороного требуется выполнять несколько более сложные операции.

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

Алгоритмическая задача

Дано: есть матрица высот, то есть (грубо говоря) равномерная сетка точек на поверхности Земли, для каждой из которых приведена ее высота. Точек много, порядка миллиарда. Нужно построить TIN-модель (triangular irregular network), то есть сетку из треугольников с «абы где» расположенными вершинами, «похожую» на исходную матрицу высот. Треугольников должно быть много меньше — несколько десятков тысяч это максимум.

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

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

Легко понять, что функция f, выбирающая из последовательности x0, …, xn M максимальных элементов, является индуктивной, то есть f(x0, …, xn) зависит только от f(x0, …, xn-1) и xn. Можно записать это следующим образом: f(x0, …, xn) = F(f(x0, …, xn-1), xn). Индуктивная функция от последовательности длины N вычисляется за N шагов очень простым циклом, надо знать лишь значение f на пустой или одноэлементной последовательности и функцию F.

Очень просто написать функцию, находящую M «наибольших» элементов в N-элементной последовательности за O(N*M) с расходом памяти O(M) — выбранные элементы хранятся в массиве, каждый новый элемент сравнивается со всеми выбранными до этого. Если включить мозг, то можно улучшить оценку до O(N*log M) с той же оценкой расхода памяти (храним выбранные M элементов в самобалансирующемся дереве). А можно ли сделать это еще быстрее, возможно, отказавшись от подхода с индуктивными функциями? Я ответа пока что не знаю.

Vogue, U-Boot и дисплей

Сумел добавить поддержку дисплея в U-Boot для вогоплеера. Подробности потом, а пока объясните, как пользоваться git :)

Кстати, оценил то, как написан U-Boot и китайские дополнения к нему. Разобраться с тем, что и как наворотили наши узкоглазые друзья — еще та задачка.

Нашел багу

Немного поковырял китайский U-Boot, адаптированный для процессоров Ingenic. Помните, я писал, что там некорректно отрабатывает утилита bmp_logo?

Так вот, дело — в типично китайском коде. Как вы думаете, что напечатает программа?

int main(void){
    int l;
    FILE *in;
/* skipped some code */
    fread(&l, sizeof(uint16_t), 1, in);
    printf("l = %d\n", l);
/* skipped some code */
    return 0;
}

Естественно, что на всех более-менее современных машинах sizeof(int) > sizeof(uint16_t), то есть переменная l окажется просто неопределена — проинициализируются только первые два байта. На little-endian системах программа будет «корректно» работать, если l «автоматически» инициализируется нулем.

Несмотря на то, что в стандарте C ничего не сказано про инициализацию нулем локальных переменных, иногда такое происходит. Когда ОС выделяет память для новой программы, назначенные для нее страницы обнуляются — чтобы никакие вирусы-трояны не искали там логины-пароли. Как бы не было больно знатокам стандарта языка C, main — далеко не та функция, с которой начинается выполнение программы. Сначала вызывается библиотечная функция _start или аналогичная ей по назначению, специфичная для каждого компилятора и инициализирующая необходимые для работы стандартной библиотеки вещи (подумайте, например, как будет работать без инициализации malloc()).

Так вот, в Linux-системах можно надеяться на то, что локальные для main переменные окажутся на еще нетронутой части стека. Происходящее в Windows — гораздо более неясно, но там локальные переменные main «инициализируются» чем-то непонятным.

Кто виноват — ясно. А что делать? Нет, не надо писать int l = 0;. Хочу лишний раз напомнить о существовании big-endian систем. В них после вызова fread() шестнадцатибитное значение запишется не в два младших, а в два старших байта — и нетрудно догадаться, что мы хотели несколько другого.

К сожалению, описанные у Кернигана и Ритчи типы int, short и long имеют нерегламентированную длину. Гарантируются какие-то минимальные значения, и ничего более. int может запросто оказаться двух-, четырех- и даже восьмибайтовым. И как тут жить? Керниган и Ритчи придумали один возможный подход. Например, во всех Unix-системах принято, что «время» — это 32-битовое целое без знака. В time.h с помощью typedef определяется тип time_t, который в реальности может быть int (на 32-битных машинах) или long (на 16-битных). На 64-битной экзотике он вполне может оказаться и short. Определено несколько таких «стандартных типов» — и все.

Естественно, если подходить таким образом, то очень скоро мы начнем определять типы наподобие bmp_file_data_length_t — целое, соответствующее тому типу, в который помещается «длина данных» из bmp-файла. Не очень весело, правда? В современных реализациях C, стандарте C99 и C++0x предусмотрен заголовочный файл stdint.h, в котором определяются целые типы фиксированного размера. Например, uint16_t — это 16-битное беззнаковое целое.

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

В общем, если бы безвестный китаец знал про типы фиксированного размера, он не стал бы использовать четырехбайтный int для хранения 16-битного значения и все были бы счастливы.

PS А вот еще вопрос. Что произойдет, если l объявить не в теле функции main(), а вне нее, как глобальную для данного файла?

Айпадное

Кстати, по случаю недорого приобрел Apple iPad (первый — владелец решил поменять его на мало чем отличающуюся новую модель). И если честно — единственной моей реакцией было: «Как, за ЭТО люди готовы платить по 25 тысяч рублей?» Я так и не понял, чем же настолько замечателен этот девайс, и считаю 12 тысяч за слегка подержанный аппарат вполне нормальной ценой.

Начну по порядку. Читать книжки (для чего девайс покупался) на подобного рода девайсе (основное, для чего он покупался) не совсем удобно. iTunes навязывает свои алгоритмы работы, которые идут вразрез с выработанной годами привычкой «закинуть файлы на плеер дрыг-энд-дропом». Яблочники решили, что нормальная файловая система пользователям (тем самым пользователям, которые, если заставить, писали программы для ДВК или осваивали DOS по книжке Фигурнова) не нужна, а нужны «библиотеки», свои для каждой программы. iBooks не может читать файлы Stanza, Stanza не видит файлы iBooks’а. Разумеется, все должно быть честно куплено, а не скачано из торрентов под названием «Самая большая русскоязычная библиотека». Кстати, нормальной читалки djvu я не нашел — а это очень важно лично для меня.

Софту для iOS далеко до своих аналогов с «настольных» компьютеров, как до Китая пешком. В тутошнем Safari нет выбора кодировки, который иногда ну очень нужен на страничках десятилетней давности. Да, я понимаю, что «пользователю» до фонаря все эти КОИ-7 и прочие болгарские кодировки, но засуньте эту штуку в какую-нибудь задницу, а не убирайте совсем! Отсутствует поиск по страничке — ну кому он вообще нужен, когда можно прикольно масштабировать страничку двумя пальцами?

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

— простое перемещение
— клик любой кнопкой, double-click любой кнопкой
— drag-and-drop с любой из нажатых кнопок
— прокрутка колесом

Итого — 11 различных «жестов». Пользователь с минимальными навыками, умеющий играть в пасьянс «Косынка» и «Сапер», владеет минимум 5-6 из них. Тачскрин любого типа поддерживает только двойной и одиночный щелчки и drag-and-drop, мультитач добавляет «многопальцевые жесты» — жалкий заменитель колеса прокрутки. В общем, впечатление такое, что количество привычных действий сократили вдвое. Более того, оказывается, что тачскрин жутко неудобен в играх. На экране в более-менее сложных игрушках, типа стрелялок и слешеров, возникает целых два «виртуальных джойстика» (по поведению они больше похожи на трекбол), причем жутко неудобных — возить пальцем по гладкому экрану даже более гнусно, чем пользоваться ноутбучным тачпадом. IBM-овский clit mouse, несмотря на то, что является вещью компромиссной во всех отношениях, в разы лучше.

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

Кстати, как-то обсудали с [info]golergka эргономику тачскринов. Я ругался на то, что точность позиционирования курсора мышью и пальцем просто несравнима. Макс отвечал на это «убойным» аргументом — мол, программа с правильным интерфейсом для тачкрина не будет использовать кнопочки размером 5×5 пикселей. Конечно, мерить размеры экранных элементов управления в пикселях неправильно, правильнее использовать либо миллиметры (чтобы сравнивать экраны с разным dpi) или даже градусы-минуты-секунды, чтобы измерять угловые размеры элемента при нормальном расстоянии до экрана. В любом случае, размер элемента управления не должен быть сильно меньше размера «пятна контакта» курсора — для мыши это, согласно разнообразным HIG, порядка 16×16 пикселей — т. е. около 3-4 мм на обычном экране. У пальца — не меньше, чем 10×10 мм. Так вот, программа с неправильным интерфейсом входит в стандартную поставку iPod и называется Safari. Достаточно зайти в профиль ЖЖ или на хорошо викифицированную википедическую страничку, чтобы убедиться в том, что комфортный при чтении размер шрифта делает из гиперссылок в тексте крайне неудобные «элементы управления».

Немного про клавиатуру. Она просто неудобна. Держа девайс двумя руками в вертикальном положении, я еще могу набирать что-то большими пальцами, но во-первых, у меня ладони большие, а во-вторых, это все равно неудобно. В горизонтальном положении никаких рук не хватит тянуться. Маленькая аппаратная клавиатура, как у HTC TyTN или Qtek 9100, в разы удобнее, даже несмотря на то, что набор большими пальцами — это извращение. Красивой экранной клавитауры айпада хватает разве что на написание адреса в браузере. Кроме того, абсолютно нелогичен набор кнопок со знаками препинания. Помнится, Лебедев ругался по поводу якобы неправильного расположения запятой. На экранной клавиатуре iPad неправильно расположено абсолютно все! Наверное, еще больше ненависти к айпадовской клавиатуре сгенерировал Каганов.

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

Вернусь к софту. В нашей Папуасии уже давным-давно считается, что самые навороченные программы стоят 70 рублей на лотке с дисками. Вызывает искреннее недоумение жадность, например, самой распоследней дурацкой игры. Хочешь пройти уровень? Гони 99 центов! Чисто гостиница «Экономическая» из сказки про Незнайку. Все-таки Джобс придумал гениальный способ «доить» пользователей. Якобы «бесплатный» софт оказывается демо-версией, просящей деньги или показывающей рекламу. Freeware как таковое на iOS, по-моему, отсутствует. Джобсу со всего этого, разумеется, капает процентик.

Непонятки возникают с «многозадачностью». Как я понимаю, для пользовательских приложений она отсутствует. Выполняющиеся «в фоне» программы — редкость, исключение — разве что iTunes. Яблофанаты говорят, что для обычного пользователя понятие «многозадачности» чуждо и непонятно. При этом у них одновременно висят аська, скайп, недоделанный документ в ворде и окошко браузера с башоргом. У самых продвинутых крутится винамп.

Кстати, в том же Safari возникли непонятки с табами. Например, «вконтактный» плеер нормально играет музыку, находясь в неактивной закладке. Youtube в неактивных закладках почему-то не работает. Еще убивает перезагрузка страничек при активном переключении среди двух-трех табов по непонятным причинам. Мало памяти?

Совершенно отвратителен редактор текста в Safari (а тексты в вебе не ограничиваются 140 символами для Твиттера). Набрать 140 букв в Твиттере или приличную запись в блог — это очень разные вещи, и второе требует возможности перемещения по тексту и вообще «нормального» редактирования. Тыканье пальцем в экран — это не заменитель курсорных клавиш. Кстати говоря, курсорные клавиши были, скажем, на клавиатурных коммуникаторах Qtek 9100, HTC TyTN и им подобных (а с поименованными я просто неплохо знаком), несмотря на наличие тачскрина. Просто пользоваться ими намного удобнее, чем пытаться попасть пальцем или стилусом в промежуток между теми самыми буквами.

В целом, впечатление не самое приятное. Те же коммуникаторы на Windows Mobile 6.0 «старались казаться» маленькими компьютерами, с маленькими Word и Excel. Конечно, трудно найти маньяка, который делал бы что-то осмысленное в этих программах, но факт остается фактом. iOS явно разработана исключительно для мобильных устройств, основное применение которых — игры, проигрывание музыки и видео, немножечко — серфинг по интернету или чтение честно купленных электронных книжек. Если от устройства на WM6 оставалось впечатление «компьютера-недомерка», то iPad — это «айфон-переросток», такая дорогая игрушка.

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