Метка: программирование

В очередной раз прочитал в качестве определения «объектно-ориентированности» что-то типа «это структурки и код для работы с ними«. Удивительно, как популярная (но не единственная) реализация так повлияла на понимание термина. Речь идет прежде всего о том, как «объектно-ориентированность» реализована в C++.

Для начала — попытаемся понять, что же такое «объектно-ориентированность» в программировании. Мне очень нравится определение из SICP:

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

Таким образом, способ, которым мы организуем большую программу, в значительной степени диктуется нашим восприятием моделируемой системы. В этой главе (3 глава SICP) мы исследуем две важных организационных структуры, которые соответствуют двум достаточно различным взглядам на мир и структуру систем. Первая из них сосредотачивается на объектах (objects) и большая система рассматривается как собрание индивидуальных объектов, поведение которых может меняться со временем.

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

Эта модель в явной форме была реализована в языках типа Simula или Smalltalk. Из более современного можно назвать, например, VRML — это не просто «формат файлов» типа Autocad или 3D Studio, а практически полноценная реализация вышеназванного принципа. Из «настоящих» языков программирования — можно привести в качестве примера Objective C. Очень похожи на модель с обменом сообщениями «сигналы» и «слоты» библиотеки Qt — но в данном случае речь идет о диком смешении двух подходов к ООП, и вряд ли это стоит считать подходящим примером.

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

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

class A {
public:
	int x;
	int f(int y);
private:
	int z;
};

… и вот такой код, работающий с ним:

A a;
int b;
a.x = 2;
b = a.x;
b = a.f(3);

В С++ эти три строчки — принципиально разные операции. На самом деле все они могут быть рассмотрены, как частный случай «посылки сообщения» (а ее мы будем записывать в виде адресат.сообщение(аргументы)):

class A {
public:
	int get_x();
	void set_x(int new_x);
	int f(int y);
private:
	int x, z;
};

... 

A a;
int b;
a.set_x(2);
b = a.get_x();
b = a.f(3);

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

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

объект Формула {
методы:
	Число вычислить() - чисто виртуальный;
}

объект Сумма : Формула {
методы: 
	Число вычислить();
	задатьПервоеСлагаемое();	
	задатьВтороеСлагаемое();
переменные состояния:
	Формула первоеСлагаемое, второеСлагаемое;
}

объект Константа : Формула {
методы:
	Число вычислить();
	задатьЗначение(Число);
переменные состояния:
	Число значение;
}

Думаю, что реализации расписывать не надо? А вот как это можно использовать:

Константа к1, к2, к3;
Сумма с1, с2;
Число результат;
к1.задатьЗначение(1);
к2.задатьЗначение(2);
к3.задатьЗначение(3);
с1.задатьПервоеСлагаемое(к1);
с1.задатьВтороеСлагаемое(к2);
с2.задатьПервоеСлагаемое(с1);
с2.задатьВтороеСлагаемое(к3);
результат = с2.вычислить();

Естественно, что вышеописанное — это некоторое извращение, и все соответствующие объекты должны создаваться сразу, как только мы напишем результат = (1+2)+3;. «Метод» в нашей терминологии — это не более чем описание «формата» получаемого сообщения и реакции на него.

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

Жутким монстром на фоне этого всего выглядит Qt — где умудрились объединить и обмен сообщениями (в виде сигналов и слотов), и «объекты в стиле C++». Получилось что-то в духе чудовища Франкенштейна — хотя иногда и довольно удобное в использовании.

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

Так как «РосПил» действует искючительно в рамках 94-ФЗ, то внимание навальнят привлекло то, что выложенные в рамках соответствующих объявлений ТЗ неявно подразумевают выполнение заказа заранее определенным исполнителем. Естественно, это адская коррупция, безусловно плохо, и вообще, должно быть наказано. Берусь утверждать, что это — единственный способ действительно разработать пресловутую «автоматизированную систему», и отличить по этому критерию «нормальный» и «коррупционный» заказы не представляется возможным.

Возьмем любое руководство по пресловутым «методологиям разработки» — за исключением разве что Getting Real (оно в случае хоть сколько-то «ответственных» систем неприменимо). Все RUP, Agile, Scrum и им подобные начинаются с критики мифической «модели водопада» — когда ТЗ на разработку спускается сверху, исполнитель отвечает — «Есть!» и с упорством идиота принимается воплощать что-то, изложенное заказчиком. В современных методологиях разработка ТЗ (где она есть) — первый этап, или стадия реализации проекта. Он включает работу с заказчиком, выявление его требований, согласование пожеланий заказчика с возможностями разработчиков и заканчивается в том числе и выпуском бумажки с заголовком «Техническое задание». В более «экстремистском» случае даже такой бумажки не предусмотрено — точнее, вместо фиксации требований упор делается на «управлении требованиями» и прочем непрерывном взаимодействии с заказчиком.

Сейчас практически общепринято, что заказчик неспособен самостоятельно написать хоть сколько-то грамотное техническое задание на автоматизированную систему — если он сам не является разработчиком таких систем. Соответственно, само по себе наличие ТЗ подразумевает, что разработка ИС уже начата. Подчеркну, что даже наши советские ГОСТы 19 и 34 серии предусматривают, что ТЗ согласуется между обеими сторонами — заказчиком и исполнителем. Процедура же «госзакупок» подразумевает, что исполнитель и заказчик взаимодействуют по принципу «Партия сказала — Надо! — Комсомол ответил — Есть!».

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

PS Опять же, перед тем, как писать что-то в комменты, предлагаю попытаться написать ТЗ на аналог Google Reader :)

Позволю себе цитату из vit_r:

The great wizard Yasha lives in the Magical World of IT. He discovers Rotten Code by smell and applies the mysterious Refactoring Spell. The software becomes better. At least this is what other great wizards and their magical books say.

И ее же перевод на человеческий язык:

Yasha reads some old source code, he finds dependencies, connections and logical errors which where unknown or overlooked in the time when this code was written, than Yasha simply updates the source code to the level of his current understanding.

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

На днях в комментариях был озвучен другой пример «волшебства». Для начала: что не так в этом коде (PHP, если кто не догадался)?

$name = isset($_GET['name']) ? $_GET['name'] : 1;
$link = new dbLink();
$list = new listWidget($link, "SELECT name, age, class 
                               FROM students 
                               WHERE name='%s';",
                              $name);
$list->show();

Ответ: пока мы не увидим конструктора listWidget и кода, строящего SQL-запрос, мы не можем говорить о корректности этого кода. Правда, комментаторы отчего-то решили, что конструктор listWidget — это что-то типа sprintf, и пришедшее извне $name вставляется в SQL-запрос безо всякой обработки. Более того, в ответ на комментарий, что все тут пучком, kettle безапелляционно заявил:

Данные надо проверять на входе, а не в середине.

Как только появляется такая вот безапелляционность — то надо задуматься, а не столкнулись ли мы с очередным шаманским рецептом? Сейчас я попытаюсь популярно объяснить, что как и любое шаманство, он проистекает из непонимания ситуации и некритического следования готовым решениям.

Для начала — обрисуем проблему. Если $_GET[‘name’] — это что-то нормальное, типа John или Jack — то при подстановке его вместо %s в шаблон запроса мы получим что-то типа

SELECT name, age, class 
FROM students 
WHERE name='John';

Что будет, если зловредные родители назовут своего ребенка каким-то экзотическим именем? Little Bobby Tables, говорят, ходит по нашей земле, и при подстановке простого американского имени Robert’; DROP TABLE students;— мы получим вот такую штуку:

SELECT name, age, class 
FROM students 
WHERE name='Robert'; DROP TABLE students;--';

Вместо одного запроса мы получаем два, второй из которых может содержать все, что угодно — например, как тут, удалять одну из таблиц в БД. Проблема эта довольно «популярная», обросшая большим количеством «доморощенных» решений, и очень неплохо освещенная, например, в презентации SQL Injection Myths and Fallacies.

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

SQL Injection не имеет ничего общего с «проверкой входных данных». И «John», и «O’Brien», и «<script type=text/javascript>alert(‘Pwned!’);</script>», и «Robert’; DROP TABLE students;—» — это прекрасные нерусские имена, которые могут и храниться в базе данных, и выводиться на страничку, и фигурировать в запросах пользователей. Задача программиста — сделать так, чтобы и в виде запроса от пользователя, и в БД, и на страничке, выводимой скриптом, они отображались одинаково. Как говорил В. И. Ленин, «величайшей ошибкой было бы думать», что примеры из книжки «PHP для начинающих» имеют какое-либо отношение к реальности. Использование одних и тех же данных безо всяких преобразований и в роли «ввода», и в запросах к БД, и для вывода — это чудовищный «антипаттерн», причем культивируемый во всех учебниках.

Представим себе несколько извращенную и надуманную ситуацию. Предположим, что ввод от пользователя к нам приходит в кодировке КОИ-8, БД работает только с CP866, а для вывода мы должны использовать CP1251. Я думаю, любой русскоговорящий программист поймет, что здесь минимум в двух местах нужно осуществить соответствующие преобразования. Но ведь и в «обычном» случае мы имеем дело с такой ситуацией! «Алфавит» и «семантика» текста в $_GET, SQL-запросах и HTML-коде — совершенно разные, и похожи они лишь отдаленно. Собственно, игнорирование необходимости преобразования между ними — это причина самых распространенных ошибок в веб-программировании.

Кстати, предлагаю посмотреть, как устроены SQL-запросы с параметрами в «более других» драйверах для работы с БД в PHP:

http://bobby-tables.com/php.html

Как легко видеть, я просто «изобрел велосипед», практически заново переизобретя уже готовые решения. Не вижу в этом ничего дурного :)

Под заголовком «Functional C programming» чувак описывает «глючную, медленную и недокументированную» реализацию Lisp:

http://blog.charlescary.com/?p=95

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

Понял, что еще меня смущает в мысли о том, что

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

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

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

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

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

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

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

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

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

Я не сторонник подхода «а давайте везде использовать ООП/функции высших порядков/монады (манды?)/Haskell/чистый ассемблер/придумать-и-вписать-что-то-свое» — особенно когда объявляется, что только этот подход позволит избавиться от багов, ускорить десятикратно работу программистов, и главное — является единственно верным. Именно это заставило меня со скептицизмом отнестись к заявлению udpn о том, что Haskell — правильный язык для написания операционных систем, после чего я пообещал «посмотреть» на пресловутый House.

Разумеется, пообещав, я благополучно записал это обещание в свой импровизированный todo list, где оно и протерялось. Вспомнить про него меня заставил вчерашний срач, начатый на хабре силами vit_r и продолженный в ЖЖ metaclass.

Как известно, в любых компьютерных программах «волшебным образом» заводятся ошибки. С ними можно поступить тремя способами — грубо говоря, Abort, Retry и Ignore. За третий способ бьют морду уже в программистских ПТУ, так что речь пойдет о двух более принятых в приличном обществе стратегиях. Более подробно об этом можно почитать по ссылкам выше, а также найти в ЖЖ vit_r расширенный вариант хабровской записи. Я же вернусь к теме операционных систем.

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

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

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

Если верить адептам Haskell-ной веры, то в вопросе «налево пойдешь — коня потеряешь, направо пойдешь — сам пропадешь» «Abort или Retry?» имеется еще один вариант — якобы их истинно правильный язык программирования сам не дает допустить ошибку. В качестве примера такого применения Haskell и была приведена ОС House.

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

Вернемся непосредственно к House. Архитектура этой системы, согласно ее описанию, довольно проста. Это «микроядерная» операционная система, с явным разделением «политики» (реализованной на Haskell) и «механизма» (на C с ассемблерными вставками). Ядро ОС — это примерно 1200 тысячи строчек на Haskell и 750 строчек на C. На C реализованы некоторые компоненты, необходимые для работы Haskell-ного рантайма и «низкоуровневого» взаимодействия с «железом».

Сишная часть реализует в этой операционке специальную монаду H — от Hardware, позволяющую хаскелльному коду выполнять операции с такими штуками, как страницы памяти или обработчики прерываний. Кроме того, микроядро на Haskell умеет взаимодействовать с драйверами устройств — тоже написанными на Haskell, но выполняющимися не в Ring 0, а в нормальном «пользовательском» Ring 3. В общем, классическое микроядро, ничего особенного.

Правда, весь кайф обламывает вот какой момент. Ядро тащит с собой весь рантайм от GHC, который оценивается где-то в 50 тысяч строк кода на Си. Там, в этом рантайме, находится хаскельное расширение Concurrent Haskell — которое в этой ОС выполняет функции планировщика и менеджера процессов. Получается типичный пример «каши из топора» — с тем же успехом House можно называть «написанной на Си». Более того, trusted computing base оказывается просто громадной по сравнению, скажем, с Minix, где все ядро — это около 7 тысяч строк на Си с небольшими ассемблерными вставками.

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

Что интересно — от ошибок не спасает даже Haskell. В более поздней статье с описанием этой операционки приводится пример типичной ошибки с «граничными условиями» — вместо 4096 байт менеджер памяти пытался обнулить 4097, правда, с оговорочкой — мол, если бы мы аккуратно использовали вывод типов, то этой ошибки и не возникло бы. Так используйте, кто мешает?

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

В качестве картинки для привлечения внимания — фотография «Дети из Революционных училищ и дошкольники получили от Ким Чен Ына в подарок деликатесные виды рыб» из сегодняшней записи juche_songun.

А сама запись будет посвящена еще одной дискуссии на тему, «что лучше — рыба или удочка», в которой я поучаствовал в Твиттере. Речь шла про язык программирования Prolog и его изучение. Я посоветовал не тратить время на изучение конкретного инструмента, а посмотреть какие-нибудь хорошие книги по Good Old-Fashioned AI, то есть всяким экспертным системам и тому подобным вещам. Почему? Лично я считаю Prolog попыткой сделать универсальный язык для тех задач, которые относили к «искуственному интеллекту» в 80-х годах. Основа Prolog — это система логического вывода, которая в том или ином виде присутствует во всех системах доказательства теорем, экспертных системах, системах поддержки принятия решений и всей остальной чуши, которую считали AI в 70-х годах.

Казалось бы, решение простое и логичное — если логический вывод присутствует во всех подобных системах, то почему бы не сделать один универсальный язык, позволяющий описывать утверждения и правила вывода? Как мне кажется, такой «абсолютно универсальный» язык — это страшный overkill. Если для решения какой-то задачи так уж необходим логический вывод, то реализация «своей» аналогичной системы не так уж и сложна — например, в SICP в одной из глав рассматривается простой интерпретатор прологоподобного языка. Еще более простые примеры приведены в Principles of Artificial Intelligence Programming Питера Норвига. С моей точки зрения, гораздо более полезным оказывается умение делать такие интерпретаторы, чем использование «данного свыше» готового Prolog.

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

Как пример такого «индивидуального подхода» могу привести одну задачу, с которой я недавно столкнулся. Для одной геоинформационной системы потребовалось выводить на карту зоны, в которых необходимо предпринять какие-то действия, описанные в ведомственных инструкциях. Инструкции примерно такие: «если уровень радиации превысил 38 попугаев, то тут зона безвозратных потерь, всем присвоить ГСС посмертно». Логическое программирование — это общепринятый способ для машинного представления подобного рода инструкций. В чем же проблема? Речь идет не об отдельных точках, а об областях на карте. Ни одна готовая система не предполагает работы с картографическими данными, особенно если речь идет о разработках на ГИС-ядре нашего, родного, исконно-посконного КБ «Панорама».

Что же можно сделать в данном случае? В книжке Норвига описана система EMYCIN, в которой допускается работа с «неточными» данными. Каждому утверждению присваивается «показатель уверенности» (confidence factor, CF) — число от 1 до -1. 1 соответствует полной уверенности в истинности утверждения, -1 — уверенности в его ложности, 0 — «не знаю». Дробные значения — это утверждения, относительно истинности которых имеются сомнения. Операциям «И» и «ИЛИ» над утверждениями соответствуют операции с показателями уверенности, которые позволяют приписать такой же показатель и логическим следствиям исходных утверждений. На самом деле все довольно просто и понятно, если кто-то этим интересуется, то очень советую скачать книжку, поставить интерпретатор Common Lisp и погонять примеры.

Естественно, что в роли CF могут выступать не только числа. В описанной выше задаче в их качестве оказалось удобно взять области на карте. Операции «И» соответствует объединение областей, «ИЛИ» — пересечение. В результате получилась система, в которой всякому утверждению обязательно соответствует область на карте, где оно выполнено — и на запрос «А где уже получилась безжизненная пустыня?» система радостно закрасит на карте нужную область.

На этой, можно сказать, оптимистической ноте я бы хотел пригласить в комменты желающих убедить меня в том, что использование Prolog быстрее приближает ядерный апокалипсис :)

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

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

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

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

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

Все это можно разбить где-то на 40 «семестровых», по 150-200 часов, «курсов» (собственно, трехсеместровые тут только физра и матан, да и тот, по-хорошему, нужно сократить до «левого предмета уровня МИСиСа» в один-два семестра). Набор курсов достаточно адекватный и в принципе, покрывает всякие «что должен знать программист 6 разряда» — но заметно шире этих списков, прежде всего, благодаря «гуманитарным» и «общеинженерным» дисциплинам. Тут я согласен с ailev, который объявил «computer science» лишь одной четвертой частью «верхнего образования инженеров-программистов«.

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

Итак, первый семестр. Включим в него следующие предметы:

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

В этом семестре ничего удивительного, матан должен будет «выстрелить» в следующем, при оценке сложности алгоритмов, а линейная алгебра позволит нормально поговорить об одном из наиболее интересных циклов задач из второй главы SICP. «Вводный курс» на основе MIT-овского учебника, кроме того, поставит в равное положении как «нулевого школьника», так и «самоучку» с «ПТУшником», учившихся по программе ребе theiced :)

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

В каждом из «компьютерных» предметов вводим новые языки программирования. От Scheme и нескольких DSL на ее основе в первом семестре — к, скажем, Паскалю в курсе алгоритмов и VHDL — в практических работах по «организации ЭВМ».

Те же тенденции продолжим и в третьем семестре, добавив, скажем Matlab и C:
— матан-3 (на этом закончим)
— вычислительная математика (с «практикумом» — то есть действительно «вычислительная»)
— английский (да и его пора «убрать»)
— безопасность жизнедеятельности (надо же с ней когда-то разделаться?)
— физра
— операционные системы (разработка и реализация — короче, книжка Таненбаума, See MIPS run Linux и что-то подобное)

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

В четвертом семестре предлагаю все же вспомнить, что математика — это отнюдь не «наше все». Например, сделаем так:
— философия (с упором на «прикладную философию» — то есть онтологию и теорию познания)
— математическая логика и теория алгоритмов (всякие машины Тьюринга, лямбда-исчисление и т. п.)
— физра (на этом все)
— технология разработки ПО (прежде всего методологии — разнообразные RUP, SCRUM, Getting Real и прочие buzzwords, ГОСТы 19 и 34)
— функциональное и логическое программирование (остатки SICP, PAIP Питера Норвига и прочие классические учебники по AI)
— правоведение (как источник «знаний» для логического программирования, и для галочки :) )

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

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

«Программирования» тут, как такового, нет — хотя никто не мешает, скажем, изучать TCP/IP на примере работающего стека из какой-нибудь ОС.

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

Здесь вспоминаем «прикладную философию» из четвертого семестра. «Программирование» вытаскиваем в курс машинной графики.

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

«Программирование» здесь превращается в «производство средств производства» — но Dragon book прочитать когда-то все же надо.

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

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

Теперь — о том, как этот «курс» соотносится, скажем с «все, что должен знать программист» за авторством sharpc, или с программой ailev, или же с программой theiced.

Из первого списка он, в идеале, должен в достаточной степени полно покрывать пункты 2, 3, 4, 5, 6, 7, 8, 9, частично 10, 11, 12, 13, 14 — хотя бы на уровне понимания «что к чему», 15, 16, 19, 23, 25, 26, 28, 31, 33. Пункты типа 18, 20, 21 должны осваиваться за счет «жестких» требований к коду во время обучения. Грубо говоря, если код нечитаем, то практическое задание не принимается. Кроме того, в «нашем» курсе есть гуманитарные и «общеинженерные» дисциплины — от философии (которую я рассматриваю как почти прикладную науку) до основ управления производством. Инженер-программист (в отличие от ПТУшника, то есть техника-программиста) должен не только уметь «кодить», но и более глубоко понимать процесс разработки ПО в его «гуманитарных» аспектах (так как может выполнять и «организационные» работы).

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

У theiced наблюдаем тот же недостаток, что и у sharpc — отсутствие «общеинженерных» дисциплин, плюс — повышенное внимание к таким вещам, как разнообразные конкретные инструменты. Еще из недостатков, с моей точки зрения — явная изначальная ориентированность на императивное программирование. Да, на практике оно используется куда чаще, но черт его знает, что там случится через 5 лет — так что ставить функциональщину в положение редкой экзотики определенно не надо. Другое достоинство айседовской программы — огромное количество «производственной практики» — но и готовить он предлагает не инженеров, а «адовых метаклассов» — то есть скорее техников-программистов 6 разряда :)

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

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

В общем, отвечая на вынесенный в заголовок вопрос, можно констатировать, что сами по себе существующие «образовательные стандарты» в области подготовки программистов вполне адекватны, и такое развлечение многих ЖЖ-юзеров, как составление «учебных планов» для мега-программистов, в целом лишено смысла — разве что позволяет понять, нужно ли автору высшее образование или же он пять лет протирал штаны в институте и мечтал о ПТУ :) Проблема же существования выпускников ВУЗов, владеющих исключительно PHP и Delphi, возникает не из-за учебных планов самих по себе, а из-за их реализации конкретными учебными заведениями.

Наткнулся на обсуждение очередной программы «высшего программистского образования», предложенной белорусским раввинатом.

http://belnetmon.livejournal.com/2097200.html
http://theiced.livejournal.com/199711.html

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

Изучаю тут последние веяния в преподавании так называемой информатики. Например, в небезызвестной 179 школе Денис Кириенко использует для обучения матшкольников Python.

http://server.179.ru/wiki/?page=DenisKirienko/Python

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

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

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

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

http://www.functionx.com/cpp/examples/returnpointer.htm

double * GetSalary()
{
 double salary = 26.48;
 return &salary;
}


Это они серьезно так пишут.

ailev написал интересную запись, где объявил так называемую Computer Science лишь частью более обширной «информатики», а также заявил о непустом пересечении последней с философией.

http://ailev.livejournal.com/1008054.html

Крайне рекомендую ознакомиться.

А вот вопросец созрел. Допустим, хочется мне какой-то «рабочий» проект реализовать на лиспообразном языке — в порядке «использования самых маргинальных технологий«, по терминологии минского раввината. Для начала — что выбрать, Common Lisp или Scheme? Common Lisp мне сразу резко «не понравился» — хотя бы из-за объема документации и кучи малопонятных вещей категории «так сложилось исторически», типа неочевидных различий между set, setq и setf. Scheme выглядит попроще, да и SICP я прочитал где-то до половины — в общем, там все достаточно знакомо.

Что мне не нравится в Scheme? Нет какой-то «эталонной» реализации. MIT/GNU Scheme поддерживает «устаревший» стандарт R5RS (с некоторыми незначительными отклонениями), в четвертом издании TSPL описывается R6RS. Этот вариант реализован в Chez Scheme и Racket, остальные реализации мне не нравятся «организационно» — один-единственный «незаменимый» разработчик — это «несерьезный» подход. Вообще, огромное количество реализаций Scheme мне представляется следствием наличия упражнений 5.51 и 5.52 в SICP.

Более того, все пригодные для использования реализации предлагают свои ни с чем не совместимые расширения. Исключение — разве что MIT/GNU Scheme, где расширений относительно «стандарта» практически нет. Эти «несовместимые расширения» тоже напрягают — а вдруг выбранная реализация окажется по каким-то причинам некошерной, и что тогда?

Наконец, хочется нормальной «современной» IDE с возможностями отладки. Emacs не предлагать, он отвратителен (сугубое ИМХО). Edwin из MIT/GNU Scheme — те же яйца, только в профиль — какое-то тяжкое наследие из 70-х. Похоже, что это пожелание сужает выбор до Racket.

Теперь — про Common Lisp. Тут попроще с реализациями. Основных — всего три: SBCL, CMUCL и CLISP (коммерческие я не рассматриваю, тут начинаются те же проблемы с несовместимыми расширениями и прочий vendor lock-in). IDE, кроме Emacs, отсуствуют. Сам язык мне не очень нравится. Из-за совместимости с древними диалектами Лиспа в Common Lisp воткнули таких «костылей», что иногда создается впечатления — а не Фортран ли это вперемешку с Алголом и синтаксисом Лиспа?

Чего мне от всего этого счастья хочется? Во-первых, простого развертывания. Насколько я понимаю, «сделать экзешник» в Лиспах непросто. Хочется хотя бы возможности установить работающую систему «двумя нажатиями мышки», а с этим возникают некоторые проблемы.

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

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