«Водопада» не существует

На прошлой неделе в нескольких «околоэлектронных» и «околопрограммистских» ЖЖ состоялся срачик по поводу ГОСТов в частности и стандартов вообще, а также про необходимость следовать им. Итоги подвел [info]hedgeov, заодно собравший ссылки на некоторые части дискуссии:

http://hedgeov.livejournal.com/337510.html

В этой записи я тоже хотел бы вспомнить про ГОСТы, конкретно — про серии 19 и 34, регламентирующие содержание документации на программы и автоматизированные системы соответственно. Их, разумеется, считают устаревшими — хотя из явных анахронизмов там можно назвать лишь необходимость распечатки текста программы (да и ее можно обойти). Более конструктивный аргумент — это то, что в ГОСТах 34 серии приведен список документов, которые сопровождают процесс разработки программы и якобы этот список вынуждает при разработке использовать «модель водопада».

Видимо, эти критики не видели ни одного титульного листа самого завалящего технического задания, составленного в соответствии с ГОСТ. Берусь утверждать, что эти ГОСТы определяют «итеративную модель» наподобие RUP или OpenUP, а «модель водопада» существует лишь в воспаленном бреду различных апологетов «внедрения RUP».

Аргументация будет очень простой. Во-первых, и в так называемой «модели водопада», и в RUP-подобных итеративных процессах, и в ГОСТ выделяются четыре стадии разработки, только называются они по-разному. У буржуев это Inception, Elaboration, Construction и Transition, в ГОСТах названий не приводится и обычно «стадии» называют по получающимся в конце документам («артефактам», в терминологии RUP): техническое задание, технический проект, рабочая документация (одновременно с ней разрабатывается и сама ИС) и ввод в действие. Конечно, апологеты RUP утверждают, что стадии RUP и стадии «водопада» — это «две большие разницы», но их настойчивость в этом убеждает в обратном.

Перейдем ко второму пункту. Я не зря упомянул про титульный лист. Дело в том, что он убивает все противопоставления «водопада» итеративным процессам. Фанаты последних утверждают, что в случае «водопада» ТЗ, проект и вообще все «требования» «спускают сверху». Так вот, на титульном листе всегда есть подписи двух сторон — заказчика и исполнителя. Всякое согласование документов само по себе и порождает итерации — и в «идеальном» случае порождает из ГОСТовской модели что-то похожее на OpenUP.

Разумеется, я не зря упомянул об «идеальном случае». Дело в том, что основная часть всех «методологий» — это здравый смысл и прочие Best Practices. А если на здравый смысл положили с большим прибором — то «от дурака» не спасет ни ГОСТ, ни RUP.

PS Типичная (к сожалению) ситуация, когда ТЗ согласуется на уровне какого-нибудь недостижимого начальства, а в патологическом случае — этим же впадающим в маразм начальством и пишется — на уровне RUPовского здравого смысла называется «неправильным определением заинтересованных лиц» и к ГОСТам отношения не имеет.

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

Программирование калечит мозг

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

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

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

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

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

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

800 страниц ни о чем

Я знал, что русские учебники по околокомпьютерным вопросам брать в руки не стоит. Сегодня не удержался, посмотрел книжку некоего А. Д. Хомоненко «Базы данных. Учебник для вузов». Талмуд объемом почти в 800 страниц можно сократить вчетверо без потери ущерба для содержания. Более-менее прилично написаны первые две сотни страниц, а весь остальной объем забит описанием конкретных СУБД (причем «неновых» уже на момент написания книги) и «публикацией БД в Интернете» — состоящей из руководств по настройке IIS, PWS и Apache в Windows и экспорту из Access в HTML.

Автор, судя по Яндексу, весьма талантлив и пишет подобные книги на все «актуальные» темы — от Microsoft Word 2003 до работы с базами данных в C++ Builder.

Математика, логика и программирование. Часть четвертая, логическое программирование

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

Обычно логическое программирование связывают с языком Prolog — но только потому, что он якобы «специально» для него предназначен. На самом деле тут применяется и Lisp, и «потомки» ML, и «самописные» движки типа Inform 7.

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

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

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

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

Правда, там, где от декларативных языков требуется производительность, и за эту производительность готовы платить — там все обстоит несколько лучше. Например, язык SQL является чисто декларативным — он описывает не процесс поиска данных, а то, какие данные удовлетворяют результату. Но в производительности СУБД заинтересованы люди с большими деньгами — и поэтому ведется постоянная работа по улучшению алгоритмов оптимизации запросов к БД.

Кстати, SQL построен на основе реляционной алгебры — предложенных Коддом в 1970 году операций для работы с «отношениями», то есть таблицами с записями. Тоже математическая теория, только про нее в популярных самоучителях типа «PHP и SQL за два дня» не пишут.

Математика, логика и программирование. Часть третья, доказательство теорем

В предудущей части я упоминал о том, что уже в 50-х появились первые попытки «научить компьютер думать», то есть доказывать математические утверждения. Программа, реализующая «традиционную» логику, получается довольно небольшой — я уже упоминал Logical Theorist — но при этом результат ее работы впечатляет. Например, будучи снабженной списком аксиом из книги Рассела и Уайтхеда «Основания математики», эта программа смогла за разумное время доказать 38 из 52 приведенных во второй главе книги теорем.

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

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

Правда, сегодня существует несколько смежных с доказательством теорем направлений. Есть несколько систем для автоматической проверки доказательств (например, Mizar), важный «побочный продукт» которых — сборники формализованных определений и доказательств. Другое популярное направление — поиск всех утверждений, которые можно доказать, в надежде на то, что среди них найдется что-то новое. По-английски это называется discovery system, «открывающая» система. Одной из первых таких систем стала Automated Mathematician, о «потомке» которой, программе Eurisko, стоит рассказать подробнее.

Automated Mathematician представлял собой программу на Lisp, умевшую по определенным правилам модифицировать другие программы на том же языке, которые интерпретировались, как определения математических понятий. В 1976 Дуглас Ленат выделил «ядро» этой системы — «язык» RRL-1 (Representation Representation Language) — фактически, набор правил логического вывода. Eurisko — система, применявшая эти правила, — была обобщением Automated Mathematician и могла применяться в различных областях знаний — от проектирования СБИС до… настольных стратегических игр.

Да, не смейтесь, в 1981 году правила настолки Traveller (посвященной сражениям в космосе) были формализованы и внесены в Eurisko, и программа выработала довольно парадоксальную, но стопроцентно выигрышную стратегию — удивившую всех, кто пытался применить там, скажем, «законы» военно-морской тактики. Это считалось очень интересной демонстрацией «искуственного интеллекта» и даже привело к изменению правил игры — правда, в 1982 году Eurisko снова «победила» на соревнованиях, найдя очередную лазейку в новых правилах. После этого, во-первых, применение «сгенерированных компьютером» стратегий на соревнованиях по Traveller было запрещено, а во-вторых — проектом заинтересовалось DARPA, агентство Пентагона по перспективным научным разработкам. Уж что у них там вышло — не знаю.

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

Математика, логика и программирование. Часть вторая, про Lisp и функциональное программирование

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

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

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

Своего рода «революцией» стал появившийся в 1958 (а разработка началась в 1954) язык FORTRAN, где предусматривалось преобразование чего-то похожего на математические выражения в машинный код. FORTRAN буквально означает FORmula TRANslator. Думаю, преимущества FORTRAN и более позднего ALGOL над ранними «языками программирования» очевидны, а дискуссия о применении оператора goto вместо конструкций ветвления или цикла все еще отражена в школьных учебниках программирования. Я бы не хотел подробно останавливаться на императивных языках, они всем хорошо известны, а хотел бы перейти к более интересным вещам.

В том же «Логико-философском трактате» (да, мне он очень нравится) содержится, видимо, общепринятая сегодня точка зрения о том, что язык ограничивает возможность выражения мыслей, причем очень интересно сформулированная:

Границы моего языка означают границы моего мира.

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

В математической логике довольно важную роль играет теория вычислимости, из результатов которой хотелось бы отметить построенное в 1941 году Черчем лямбда-исчисление. В середине 50-х появились первые попытки «научить» ЭВМ доказывать теоремы по геометрии, после работы Гильберта это казалось хорошей демонстрацией способности компьютера «думать», то есть пользоваться формальной логикой. В 1956 году Ньюэлом, Шоу и Саймоном была создана программа Logical Theorist, а в 1958 году МакКарти, работая в IBM над системой символьных вычислений, пришел к выводу, что комбинация FORTRAN c заложенными в Logical Theorist идеями (называлось это FLPL — FORTRAN List Processing Language, язык обработки списков на базе FORTRAN) окажется нежизнеспособна — и сделал лямбда-исчисление «теоретической базой» нового языка программирования, названного Lisp (от LISt Processor).

Программа на Lisp — это не записанная в каком-то порядке последовательность операций, а набор определений функций. Для того, чтобы вычислить функцию, необходимо вычислить сначала ее аргументы — и этот подход оказывается очень удобен. Уже на первых страницах учебников по Lisp объясняется рекурсивная программа вычисления факториала — и там это очень естественно. Кстати, понятие рекурсии происходит из теории вычислимости и лямбда-исчисления и прекрасно там разобрано еще до появления каких-либо компьютеров.

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

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

С другой стороны, Lisp оказался очень далек от реального аппаратного обеспечения. Более того, в 60-х считалось, что языки программирования делятся на две категории — Lisp и «все остальные». Это было правдой, «все остальные» языки программирования придерживались императивного подхода, в той или иной степени обобщавшего реальное устройство компьютера, то есть «машину фон Неймана». Lisp вообще никак не был привязан к свойствам оборудования, и считался очень неэффективным. Правда, в середине 70-х появились так называемые лисп-машины с аппаратной поддержкой некоторых свойств языка, но они были вытеснены быстро развивавшимися компьютерами общего назначения. «Обычным» применением для Lisp и его более современных диалектов (Scheme и Common Lisp) считается «искуственный интеллект» и связанные с ним задачи — например, представление знаний, машинное обучение, обработка естественных языков и тому подобные задачи. Правда, никто не мешает использовать Lisp и в более «стандартных» областях — например, на Lisp написан текстовый редактор Emacs, Scheme используется в некоторых системах информационной безопасности, на Common Lisp была написана одна из первых в мире систем интернет-магазинов.

Среди других функциональных языков стоит назвать РЕФАЛ (РЕкурсивных Функций АЛгоритмический язык), созданный Валентином Турчиным в 1966 году. Кстати, рекурсия впервые появилась именно в Lisp, и является для функциональных языков «естественной» — тогда как в императивных она оказывается чем-то сложным и чужеродным. Из более современных — ML (возникший, как часть системы доказательства теорем LCF), его «потомков» Caml и OСaml, Erlang — интересный тем, что сразу предназначался для «практического» программирования, Haskell — последний является интересным примером реализации «чистого» лямбда-исчисления, не допускающего побочных эффектов. В нем отсутствуют такие привычные «императивным» программистам понятия, как переменные и присваивания — а для «неминуемых» операций с побочными эффектами, вроде ввода-вывода, применяются так называемые «монады».

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

Математика, логика и программирование. Часть первая, про логику

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

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

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

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

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

Фактически, возникла проблема обоснования математики — то есть разрешения парадоксов теории множеств. Проблема действительно важная — потому что требовалось объяснить, «а чем это мы все тут занимаемся». Должна ли математика быть связана с реальным миром, или же математические объекты чисто умозрительны? А если они умозрительны — то почему же можно пользоваться математикой в расчетах? Можно ли «доверять» математическим рассуждениям? Эта проблема получила несколько решений, к сожалению, неудовлетворительных.

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

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

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

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

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

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

Напоминалка

Не забыть до 4 марта написать пост для предвыборной чистки френдленты.

И второе. У меня имеется черновик записи про функциональное и логическое программирование, но он довольно большой — почти 6 страниц А4. Резать на куски или так осилите?

Про пользу от философии

Пару месяцев назад я написал довольно обширный текст о том, что под логическое программирование можно подвести некую «философскую» базу. [info]nicka_startcev, разумеется, меня немного подкалывал — а вот сегодня закономерно впал в некую ересь. Читаем:

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

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

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

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

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

Сознайтесь, кодеры!

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

Говорят, что даже на Физтехе, на Факультете Управления и Прикладной Математики — цитата:

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

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

Так или иначе, многие «практикующие» программисты заканчивали отнюдь не ВМК или профильные факультеты МВТУ. А выпускники остальных ВУЗов нашей необъятной Родины, пытающиеся работать «программистами», скорее всего, никогда не сталкивались с тем, чтобы их «драли» за какие-то недоделки в программах в ходе обучения. Почему я делаю акцент на слове «драли»? Вовсе не из-за каких-то околофрейдистских комплексов, а из-за простого принципа — «за одного битого двух небитых дают». Программиста во время обучения не бьют — то есть не обращают внимания на ошибки, и свои шишки он набьет уже потом, в процессе работы. Просто так устроена сложившаяся система обучения.

А вот как учат будущих инженеров (из комментариев к ролику на Youtube — это БГТУ, зачет по курсу «Детали машин»):

Признавайтесь, программисты, докапывался ли кто-то до «уродств» в тех программах, которые вы писали в ВУЗе?

PS Меня макнули мордочкой в собственное дерьмо один (!) раз за все 2 (в школе) + 4 (в универе) года, и случилось это на втором курсе, когда В. В. Борисенко заболел, и его заменял А. И. Немытов. Я сдавал одну из задач по теме «Текстовый редактор«, преподаватель быстренько проверил, как у меня обрабатываются «граничные условия», продемонстрировал, что в этих случаях моя программа ведет себя некорректно, и объяснил, в чем суть ошибки. Больше я подобных случаев не помню.

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

У ребе [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 школе. Уже давно собираюсь написать некую «рвущую шаблон» вещь о ней. Писать или не надо?

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

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

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

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