Слайды The Next Mainstream Programming Language

The Next Mainstream Programming Language - это слайды Тима Свини (Tim Sweeney), основного разработчика движка Unreal. Тим размышляет о том, чтобы он хотел от языка программирования, говорит какие проблемы возникают при работе с C++. К сожалению, это только слайды, а не статья, поэтому все очень кратко и не все до конца понятно.

Просто красивая картинка оттуда

Поклонники Haskell'я будут довольны, Haskell упоминается не один раз, там даже есть раздел The Genius of Haskell. Правда, прямо за ним идет раздел Why Haskell is Not My Favorite Programming Language. :-)
По поводу этих слайдов на Lambda the Ultimate разгорелось большое обсуждение, в котором участвует и сам Тим. Много мнений высказывается по поводу сборки мусора в играх.
"Представьте, вы врываетесь в комнату. Повсюду монстры, у вас есть пара секунд, чтобы среагировать, прежде чем вас поджарят. Хотите ли вы, чтобы сейчас началась сборка мусора? Конечно же нет!"

Некоторые программы работают быстрее, если кликнуть на заголовок окна

"Такая ситуация возможна, если программа слишком много времени отводит на то, чтобы рапортовать о прогрессе, но недостаточно времени тратит собственно на работу." (Хех, я знаю людей, которые поступают так же :-) ). "Когда вы кликаете на заголовок окна и продолжаете удерживать клавишу мыши, менеджер окон ожидает следующее сообщение от мышки, чтобы понять - вы просто кликнули на заголовок окна или собираетесь окно куда-то тащить. Во время этого ожидания отрисовка окна приостанавливается.
Из-за этого программа начинает работать быстрее. Отсутствие перерисовок означает, что меньше CPU тратится на перерисовку того, что вы все равно бы не заметили."

Речь идет об ОС Windows, оригинал заметки тут: Why does my program run faster if I click and hold the caption bar?. Звучит как анекдот, но на блоге Реймонда Чена есть примеры программ, можно проверить.

Блог Дорона Холана о драйверах режима ядра

Дорон Холан (Doron Holan), программист из Микрософт, занимается программированием драйверов режима ядра под Windows уже более восьми лет. И ведет блог по этому поводу: A Hole In My Head. Я человек далекий от программирования драйверов, но почитать для общего развития было интересно.
Еще по теме, статья на microsoft.com: C++ for Kernel Mode Drivers: Pros and Cons. Хотя в статье говорится, что это просто статья без каких-либо намеков, стоит использовать для этих целей C++ или нет, но, по-моему, вывод из нее можно сделать только один: "Just don't". :-)

Библиотеки для отрисовки графов

Несмотря на то, что проблему с отрисовкой своего графа я решила с помощью GraphViz'а, я успела к тому моменту основательно порыться в Интернете в поисках библиотеки отрисовки графов, плюс сейчас порылась, освежила воспоминания и нашла кое-что новое.
Всегда приятно, когда есть хорошая библиотека для решения какого-либо класса задач. С открытыми исходниками, подробной документацией, живым форумом и прочими прелестями, которые есть у хороших библиотек. Сразу вспоминается Boost.
В Boost Graph library реализовано большое количество алгоритмов на графах, в том числе несколько алгоритмов отрисовки графов, но как-то маловато...

Самая достойная из бесплатных библиотек, что мне встретилась - это Lib tulip, на ней построена демонстрационная программа отрисовки графов Tulip. Документация несколько мутная, но есть. Есть форум, ну и конечно же есть исходники (C++). Умеет несколько двумерных раскладок, умеет рисовать трехмерные графы. Для отрисовки в 3D использует OpenGL.

Остальные бесплатные проекты, что я видела, либо полудохлые, либо им чего-то да не хватает. Привлекательно выглядит uDraw, раньше он назывался daVinci и под старым именем был довольно известен. Он без исходников, но есть дистрибутивы под большое количество платформ: под Windows, под разные Unix'ы...

Пожалуй самой известной библиотекой для отрисовки графов является LEDA, написана на С++. Это не только библиотека отрисовки графов, там много чего есть как касающегося графов, так и не касающегося. Но это платная библиотека, платная даже для вузов. И стоит она немеряно. Насколько мне известно, раньше она была бесплатной для учебных заведений и получила довольно-таки широкое распространение. И часто в форумах в обсуждениях отрисовки графов она упоминается. Но сейчас говорить о ней большого смысла нет. Соответственно, теряют смысл библиотеки, которые написаны на основе LEDA. Это AGD (Algorithms for Graph Drawing), GDT (Graph Drawing Toolkit).

В прошлом посте я упоминала yFiles, на базе которой построена бесплатная программи yEd. yFiles yаписана на Java, есть yFiles.NET. Стоит тоже неслабо.

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

В комментариях упоминались коллекции ссылок на проекты, посвященные отрисовке графов, приведу их здесь. Возможно кому-то удастся отыскать в них еще что-то полезное.
Graph Drawing в каталоге Google
Graph Drawing на dmoz.org

Это продолжение рассказа об отрисовке графов. Начало можно найти тут: Нарисовать граф красиво.

Программы для отрисовки графов

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

GraphViz

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

Прежде чем начать работать лучше почитать хелп, который лежит в директории GraphViz/doc. Интуитивно понятный интерфейс вас там не ждет. На самом деле GraphViz - это набор из нескольких программ, я пользовалась одной из них, dotty. dotty умеет считывать граф из текстового файла, где граф преставлен в несложном формате, и красиво выводит его на экран. Если что-то не понравится, узлы можно подвинуть, подправить самостоятельно. Здесь же можно добавить/удалить узлы, можно вообще здесь же граф нарисовать. Если зарыться в документацию, то можно узнать, что dotty делает иерархическую раскладку, а GraphViz умеет и другие, но можно в это и не вникать. Это идеальное решение, если хочешь просто нарисовать граф, не забивая себе голову деталями, раскладками и т.п.
У меня граф лежал в виде списка узлов и переходов в базе данных. Я написала небольшой скрипт, который вытягивал этот граф из базы и писал его в текстовый файл в формате, понятном dotty. Потом скармливала этот граф dotty. Мне вполне этого хватило.
Как написано у них на сайте, отрисованный граф можно экпортировать в графические форматы, SVG, Postscript. Экспортом я не пользовалась, мне надо было только распечатывать.
Есть варианты под Windows, пэкаджи для Линукса, разных Юниксов, MacOS. Есть исходники.

Следующими программами я не пользовалась, цитирую то, что написано у них на сайте.

yEd
yEd построена на базе java-библиотеки для отрисовки графов под названием yFiles. Библиотека не бесплатна, а вот программа yEd бесплатная. Интерфейс красивый, на сайте много скриншотов с отрисованными графами. Пользователей затравливают красивыми картинками.
Есть экспорт в форматы SVG, WMF, BMP, JPG и GIF.

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

Органическая раскладка

Ортогональная раскладка.

Примеры отрисовки больших графов.

Большая кластеризованная сеть	Большая сеть отрисована в круговой раскладке
Древовидная стукрура, 10000 узлов	Большая карта сети, отрисованная в органической раскладке

aiSee
Это уже за деньги, но есть 30-дневная урезанная триал-версия. Ее можно получить для некоммерческого использования, но некоммерческая версия тоже урезана.

Очень настаивают на том, что программа оптимизирована для отрисовки очень больших графов, до сотен тысяч узлов и работает с ними очень быстро. Для таких графов предусмотрен фолдинг (схлопывание групп узлов в один узел).

Что представляет собой особенный интерес - есть версия сайта на русском. И очень интересный пример графа я там откопала. Они перевели карту московского метрополитена в формат GDL (graph description language), в котором они хранят все графы, и отрисовали. То, что у них получилось, уж больно похоже на официальную карту метрополитена.

Умеет экспортировать в форматы SVG, PNG и HTML.
Есть версии для Windows, Linux, Solaris, и Mac OS X.


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

WilmaScope 3D

Walrus

Обе написаны на Java с использованием Java3D, у обеих исходники открытые.

Проектов по отрисовке графов огромное количество. Постоянно появляются новые, старые умирают. Вот несколько ссылок на проекты, которые не вошли в мой рассказ.
GVF - The Graph Visualization Framework
Graph Visualisation
uDraw(Graph)
Comp.compilers: tools for graph visualization - summary. Очень старое обсуждение программ для отрисовки графов.

Это продолжение рассказа об отрисовке графов. Начало можно найти тут: Нарисовать граф красиво.

Нарисовать граф красиво

visualcomplexity.com

Давным-давно передо мной стояла такая задача: в базе данных лежат несколько графов и хорошо бы их красиво вывести на печать. Чтобы и узлы друг на друга не залезали, чтобы прочитать названия узлов и переходов можно было и чтобы это все было оптимально размещено на листе формата А4. Вариант "двигать квадратики в Visio" и т.п. отметаем с негодованием.
Информации по этому поводу на русском языке очень мало. В основном натыкаешься на вопросы таких же страждущих. Что странно, потому что бывает весьма полезно представить в виде графа какие-нибудь данные, структуры, все сразу становится понятнее.

SequoiaView

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

Я в итоге старательно поспрашивала Google на английском и нашла очень много чего интересного.

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

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

2. Библиотеки для отрисовки графов.
Вы хотите, чтобы ваша программа рисовала граф унутри себя и вам для этого достаточно библиотеки, которая с этим всем справится.

3. Теория отрисовки графов (Graph Drawing Theory).
Вам интересна именно теория отрисовки графов с научной точки зрения. Здесь я расскажу все, что знаю про эту теорию, и дам ссылки на книги и ресурсы по этой теме.

Ссылки по теме:
visualcomplexity.com Коллекция ссылок на проекты, занимающиеся визуализацией сложных сетей.
Швейцарский нож, или Визуализация графов. Статья Андрея Зубинского.

О непростой жизни тараканов

Прежде чем начать свой рассказ, имею своим долгом предупредить. Речь пойдет о биороботах, в которых в качестве биологического материала используются тараканы. Возможно, вам будет неприятно это читать. Определенно не стоит продолжать чтение, если вы только что поели.

Биороботы бывают разные. Вот, человек над рыбками издевается, а проект Control and Communication in the Animal and the Machine - это робот, контролируемый Мадагаскарским тараканом. Таракан помещается в установку на шарик. Этот шарик он может крутить, это дает сигнал моторам, в итоге от кручения шарика движется вся конструкция. Изменить направление движения таракана заставляют с помощью света. Тараканы, как известно, свет не любят. И если включить свет с какой-либо стороны таракан стремится от него убежать в темное место, тем самым поворачивая чудо-машину.

Я привела маленькую фотографию, на официальном сайте проекта можно найти огромные, очень хорошего качества, с которых таракан размером во весь экран смотрит на вас грустными глазами.

На случай, если вы беспокоились: нет, тараканчику совсем не больно. В FAQ'е автор проекта говорит, что по некоторым косвенным признакам ему удалось распознать, что таракан совсем не против. Хм, ну сам таракан вряд ли станет опровергать его слова. В этом FAQ'е еще много чего интересного рассказывается, можно пополнить свои знания. Вот, например, интересный факт: таракан может некоторое время прожить без головы, после чего умирает с голода.

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

Жестокость людей в приведенных проектах не идет ни в какое сравнение с жестокостью осы под названием Ampulex compressa. Сложные у них всех названия, буду называть ее просто "оса". Итак, она может напасть на таракана и ввести свое жало прямо ему в мозг. Насколько я знаю, то, что есть у тараканов, нельзя назвать мозгом в строгом смысле этого слова, но неважно. После этого оса может контролировать движения таракана и она ведет его к себе в нору.
Это еще не все, самое интересное впереди. Разумеется, оса ведет таракана к себе в нору не просто так. Личинка осы заползет в него и будет питаться внутренностями таракана, а когда вырастет большой, выберется из него на манер Чужих.

Фотографию этого безобразия я, пожалуй, приводить не буду. В оригинале статьи есть фотографии и захватывающие подробности: The Wisdom of Parasites.

Updated: 04.05.2007
На YouTube есть захватывающий ролик про робототракана

Триграфы и альтернативные символы

The addition of trigraphs has made it easier to make programs hard to read. It was a dark and stormy night for C when the ANSI C committee added trigraphs to the standard.

Это фраза из старых правил конкурса Obfuscated C, конкурса на самый запутанный код на языке C.
Вообще триграфы были придуманы для терминалов, в которых некоторых символов не хватает. В итоге вместо #define можно написать ??=define. Триграфы подменяются на нужные символы в самом начале, поэтому эти записи эквивалентны. Вместо { можно написать ??< , вместо } использовать ??> .

Триграф	Что заменяет
??=	#
??(	[
??/	\
??)	]
??’	^
??<	{
??!	|
??>	}
??-	~

Кроме триграфов есть еще альтернативные символы. Например вместо тильды ~ можно использовать compl, решетку # можно заменить на %: .
Альтернативные символы, которые не являются словами, известны как диграфы. Даже несмотря на то, что есть диграф, состоящий из четырех символов.

Диграф	Что заменяет
<%	{
%>	}
<:	[
:>	]
%:	#
%:%:	##

С триграфами связан один неприятный момент: можно опечататься и получить весьма странное поведение программы. Классический пример опечатки, которая превращается в тригаф, приведен у Герба Саттера. GotW #86: Slight Typos? Graphic Language and Other Curiosities

// What will the next line do? Increment???????????/
++x;

Символы '?' и '/' находятся на одной кнопке и опечататься так несложно. Но последовательность ??/ - это триграф, который заменяется на '\', что означает конкатенацию строк. Код превращается в

// What will the next line do? Increment?????????++x;

В gcc неприятностей от триграфов меньше, потому что там надо указать опцию -trigraphs для обработки триграфов. Кстати, в мануале к одной из старых версий gcc об опции -trigraphs сказано "You don't want to know about this brain-damage". :-)
А вот в Visual С++ никаких опций для триграфов указывать не надо, хотя для альтернативных символов - надо...

Триграфы будут заменены везде в коде, например внутри текстовых строк. И вот такой код

printf( "??-I wonder!\n" ); 

Выдаст на печать

~I wonder! 

Так как триграф ??- будет заменен на тильду. Для получения желаемого вывода придется использовать обратные слэши.

printf( "\?\?-I wonder!\n" ); 

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

??<z=compl(compl x??!y);%>

На конкурсе Obfuscated C в 90-м году победил как раз код, активно использующий триграфы. Но сейчас на этом конкурсе тригафы использовать не рекомендуется.

Изуродовать код до неузнаваемости можно не только с помощью триграфов и диграфов. Если лгать в комментариях, придумывать дурацкие названия переменным и в усмерть все задефайнить, то код будет очень сложно читать и поддерживать. О чем очень убедительно рассказывается на сайте Unmaintainable code, причем не только про C/С++, там есть правила, применимые к любым языкам программирования, есть правила по отдельным языкам. За примерами совершенно невообразимого кода лучше сходить на сайт упомянутого уже конкурса Obfuscated C или на страничку The Daily WTF, где ежедневно публикуются реальные примеры кода, вызывающие ужас и отвращение.

Ссылки по теме:
comp.lang.c++.moderated printf() question
Obfuscated C
The Daily WTF