ICFPC 2018

В этот раз мы писали программы для какого-то фантастического 3D-принтера, в котором печать производят летающие наноботы. Боты имеют какую-то систему команд, могут перемещаться по полю и превращать материю в энергию и обратно. Кроме того, присутствует некое "подпространственное поле", за счёт которого напечатанные куски модели могут висеть в воздухе, пока поле включено. Боты могут размножаться делением и потом опять соединяться. Каждая команда ботам стоит сколько-то энергии, и включение "антигравитации" тоже сколько-то стоит. Дан набор моделей, которые надо напечатать, надо написать соответствующие программы для ботов, тратящие как можно меньше энергии.

Задачи для ICFPC придумывают вроде бы люди из университетов, но при этом, похоже, эти люди имеют какой-то опыт промышленной разработки, так что процесс решения задач похож на "настоящее" программирование гораздо больше, чем, например, те же ACP ICPC. Начать с того, что сам процесс получения входных данных и формирования выходных каждый раз представляет собой целую небольшую задачу - то по REST надо разговаривать, то длинные рациональные числа парсить. В этот раз протокол был полностью бинарным: в командах координаты кодировались даже не байтами, а отдельными битами. Модели тоже были закодированы не совсем тривиально: по одному биту на воксель. Вероятно, как раз бинарный протокол стал причиной того, что в этот раз в контесте принимало участие гораздо меньше команд, чем в прошлые разы (всего 95 команд; в прошлом году, для сравнения, мы были 102-ми из 120).

Другой момент, делающий ICFPC похожим на "реальную жизнь" - не ограниченный размер команды. При ограниченном сроке (трое суток), очевидно, организовать эффективную работу большой команды над сложной задачей - целая большая управленческая проблема. Если у вас есть где-то чудо-ПМ, вы, теоретически, можете взять команду из 100 условных индусов и всех победить. Или вы можете взять двух-трёх хороших разработчиков без всякого ПМ-а и тоже всех победить. То есть, как и в реальных задачах, это соревнование не только по программированию, но и по управлению проектами.

И ещё один момент: условия задачи меняются и усложняются прямо во время разработки. Как знакомо. В этот раз, правда, усложнение было всего одно, зато какое... Так часто бывает на ICFPC: когда впервые читаешь задачу, появляется ощущение, что эту задачу решить нельзя никак, никакими силами и ни за какое время. Потом ты начинаешь что-то пилить, разбираться, у тебя начинает что-то получаться... А потом приходит усложнение задачи раз в пять.
Писали в этот раз опять на Haskell.

Пятница

Эту часть контеста Minoru охарактеризовал так:

1. Никто ничо не понял, но Портнов уже пилит базовые типы и тулинг.

С прошлых лет у меня так и осталось ощущение, что очень важно побыстрее выдать хоть что-то. Не для того, чтобы набрать очки (правила подсчёта очков в ICFPC обычно такие, что одним только кодингом на скорость ничего не добьёшься). А для того, чтобы у команды появилось ощущение "ну, что-то вроде можем, может быть эту задачу даже можно решить". Пока такого ощущения не появится, все находятся в некоторой фрустрации: "руки опускаются". А это просто потеря времени.
А для того, чтобы выдать хоть какой-то самый тривиальный алгоритм, надо написать некоторое количество обвязки: разбор файлов итд. Поэтому я нагуглил пакет bits и стал реализовывать кодирование команд ботам в заданный бинарный протокол. В чате в это время обсуждали общие подходы и усолвие задачи. А потом я пошёл спать.

Суббота

Краткое содержание от Minoru:

2. Появились какие-то базовые идеи, народ осваивает запиленный Портновым
   тулинг.
3. Идеи рождаются быстрее, чем пишется код, это всё выпрыскивается в чат (в
   этом году ещё и в трекер).

На самом деле, я ещё продолжал пилить обвязку. Дело в том, что в данной задаче, когда ботов больше одного, команды для разных ботов должны идти вперемешку. Точнее, исполнитель на каждом шаге смотрит, сколько сейчас живых ботов, читает из программы N команд и раздаёт их ботам. С учётом того, что алгоритм должен выдавать команды ботам согласованно, целую небольшую задачку составляет формирование общей программы из программ для отдельных ботов, с учётом их переменного количества. А ещё я сделал чтение файлов моделей при помощи библиотеки bitwise.
Потом я взялся писать "простой алгоритм", который включает антигравитацию и начинает печатать модель слой за слоем одним ботом. При этом мне приходилось по дороге допиливать обвязку.
Изначально у меня была мысль, что будет две отдельных сущности: Generator - набор API для формирования последовательности команд, и какой-нибудь Emulator - реализация описанной в спецификации модели, с подсчётом энергии, учётом закрашенных вокселей и т.д. И потом мы бы как-нибудь с использованием генератора создавали какие-нибудь программы, и сравнивали их при помощи эмулятора. Но потом постепенно как-то так получилось, что для написания хоть сколько-то полезных алгоритмов генератору на каждом шаге нужно (по крайней мере частично) знать состояние мира, в которое приводит сгенерированная последовательность команд. А эмулятор у нас так и не родился...
К вечеру самый простой алгоритм был готов, и мы даже надеялись что-то выдать в раммках lightning division, но не успели.

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

4. Выходит апдейт условий, все получают скачок адреналина, возможен регресс
   до второй фазы с целью перепилить тулинг. (Эта фаза может наступать
   несколько раз в зависимости от апдейта).

Теперь:

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

Для задач по разборке сразу появилась идея, что можно составить программу на сборку, а потом по определённым правилам "инвертировать" её. Да вот только до реализации этой идеи мы так и не дошли. Разборку мы делали так же, как сборку, просто с другими командами. А пересборку реализовали в лоб: сначала разобрать одно до нуля, а потом собрать другое.

Уже почти ночью мы всё-таки напоролись на "мифические" проблмы с производительностью из-за иммутабельности и ленивости (мифические, потому что по моему опыту на них наталкиваешься довольно редко). Решили кардинально, избавившись в этих местах и от ленивости, и от иммутабельности.
Ещё мы успели что-то залить, и оказались аж на 12м месте в лидерборде. Ну, просто потому, что только 15 команд к данному моменту успели хоть что-то выдать.

Воскресенье

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

Понедельник

В понедельник остались только мы с Minoru. Товарищи Akon32 и ForNeVer оставили нам по длинному описанию начатых, но не законченных идей в трекере.
С утра, увидев что мы сползли на 67е место из 78, я стал разбираться с ошибками, и к обеду залил исправленную версию.
Minoru начал писать скрипт, который бы с использованием evaluator выбрал лучший вариант решения для каждой задачи, из тех что мы отправляли за весь контест.
С какими-то ещё небольшими оптимизациями, мы поднялись на 48е место из 95. Не очень плохо, но бывало лучше...
А вскоре после обеда, лайвборд заморозили, и до вечера мы что-то ещё понемногу оптимизировали уже "вслепую": эмулятора-то не было, и мы до сих пор не знаем, чего в этих сабмишшенах было больше: оптимизаций или ошибок, и куда мы в итоге попадём. Примерно с равной вероятностью мы можем оказаться на 20м и на 80м месте.

5. В смысле конец контеста, у меня же ещё вот это, это и это не реализовано!

В общем

Некоторое количество замечаний в духе Капитана Очевидность:

• Надо лучше организовывать общение в команде. В частности, лучше документировать код, наверное. А то я несколько раз объянял товарищам, как работает мой Generator. И пару раз выяснялось, что два человека параллельно делают одно и то же.
• Не надо экономить на инфраструктуре. Если понятно, что вот это можно вынести в утилитную функцию, вот здесь для ясности ввести type synonym, то это надо делать, хотя это занимает время. При работе в одиночку, или даже в команде в том случае, когда ты один пишешь большой кусок кода, иногда имеет смысл на первом этапе сэконоить: написать побыстрее некоторое количество тупого кода, с копипастой и прочим, убедиться в его работоспособности, а потом отрефакторить и убрать копипасту. В случае тесной командной работы так делать не надо: инфраструктурный код должен сразу иметь простое, "красивое" api.
• Если какая-нибудь часть инфраструктурного кода очевидно нужна (например, эмулятор, или pathfinding, или визуализатор), то её очевидно нужно писать, а не "да ладно, давайте как-нибудь так".
• Вся команда должна хорошо владеть используемым языком и его библиотеками. У нас же чрезвычайно разношёрстная команда: когда мы после контеста решили выяснить пересечение множеств умеемых каждым из нас языков, оказалось, что это пересечение пусто.

Как можно участвовать в ICFPC (2016)

«Рядом с этой сокровищницей мысли, — неторопливо думал Васисуалий, — делаешься чище, как-то духовно растешь»

В этом году мы с товарищами (ForNever, Minoru, Hagane, grouzen) опять взялись участвовать в ICFPC. Если кто не в курсе, что это такое — см мой предыдущий пост или серию постов товарища adept.
В этот раз для разнообразия мы не писали AI для игрушки. Организаторы были из Японии, и поэтому мы весь уик-енд... складывали оригами. Кто-то из кода, а кто-то нет.
Задача состояла в том, чтобы из квадратного «листа бумаги» складывать разные (плоские) фигуры. В качестве задачи даётся описание нужной фигуры, а решение — набор складок на квадрате и описание, какие вершины в какие переходят при складывании. Первая сотня фигур была предложена организаторами, а дальше задачи могли отправлять участники, и за отправку задач тоже давали очки.
При этом, на самом деле, это было «не настоящее оригами». Были допустимы решения, невозможные с бумагой — части листа могли проходить друг через друга при складывании. При отправке решений чужих задач можно было даже «рвать бумагу» (при отправке своих задач — нельзя). Момент про разрешено ли разрезание мы уточняли долго и сложно.
Контест в этот раз проходил с утра пятницы по вечер воскресенья в моём часовом поясе.

В пятницу

с утра я «по-быстрому» написал скачивалку задач с сервера и закачивалку решений (на python, просто потому что там было REST API, а у меня уже был опыт использования для этого питоньей библиотеки requests). Ещё я написал парсер предложенного формата задач и рендерилку, которая рисует фигуры из задач в виде svg (на Haskell). Сразу пригодился хаскельный модуль Data.Ratio. Дело в том, что в задачах использовались координаты в виде рациональных чисел, причём размеры числителя и знаменателя не были ограничены. Так что быстро образовалась строчка type Number = Ratio Integer.
Потом я посмотрел на результаты рендера и увидел, что первые семь задач тривиальные (там просто квадрат, сдвинутый или повёрнутый, но не сложенный), решения для них легко написать вручную. Решил и залил.
Потом мы начали думать над задачей (я уже писал, у меня всегда так — сначала код, потом думать).
Когда нет ограничения на разрезание бумаги, задача сводится к тому, чтобы разрезать квадрат на эн многоугольников и сложить из них нужную фигуру. Насколько я знаю, подобные темы широко и глубоко изучены, но я не знаком с конкретными работами и алгоритмами. (в университете был даже какой-то спецкурс по оригами, как разделу геометрии, но я на него не попал). Поэтому я долго и упорно думал в эту сторону, но ничего не придумал.
В чате довольно быстро образовалось несколько идей:

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

Товарищ grouzen произвёл обширные изыскания существующих научных работ на тему оригами и около, и обеспечил нас пейперами для чтения на всю неделю. К сожалению, применить их мы не смогли.
Потом начался как всегда разброд и шатание, каждый стал заниматься чем-то своим.
Я решил начать с написания какого-никакого «фреймворка» для дальнейшей работы — набора функций для разрезания многоугольников, объединения и т.п. Некоторые из геометрических алгоритмов тривиальны (отражение многоугольника относительно прямой), зато другие зубодробительны (объединение произвольных многоугольников). Для таких алгоритмов я стал гуглить существующие реализации, по возможности на Haskell (т.к. парсер задач уже был на Haskell). Нашёл только clipper. Это биндинги к одноимённой библиотеке на C++. Сразу обнаружилась особенность: Clipper работает с целочисленными координатами (видимо, в основном заточен на экранную графику) размером Int64. А у нас рациональные и просто целые очень большие числа. Так что при попытке засунуть в clipper одну из первых тривиальных задач сразу получили: Literal 1267650600228229401496703205376 is out of the Int64 range -9223372036854775808..9223372036854775807. Так что реализацию сложных алгоритмов отложили на потом (по факту объединение многоугольников у нас в итоге и не использовалось). Minoru взялся писать разрезание многоугольника прямой на два (это в любом случае бы понадобилось для складывания, а в clipper этого нет).
Дальше Minoru, Fornever и hagane начали обсуждать вариант с разворачиванием скелета. Я в эту идею особо не вникал, т.к. думал над представлением «фигуры» в процессе её сворачивания и реализацией «сворачивалки» в виде State ЧтоТо ().
К вечеру пятницы у меня был «солвер», который брал многоугольник и один раз сворачивал квадрат вдоль каждой грани этого многоугольника. И рисовал в svg что получилось. То есть он теоретически мог уже решать часть задач. Но при этом он принимал данные не в том виде, и выводил не в том. При этом там было ещё куча неуловленных багов.
Fornever к этому времени перегенерировал все иллюстрации к задачам, устранив баг в рендерилке.

В субботу

с утра я стал было дописывать алгоритм сворачивания выпуклых полигонов, но наткнулся на баги в методе разрезания многоугольника (где-то какое-то деление на ноль). Попытался разобраться в коде этого метода и не смог. Т.к. Minoru сильно в другом часовом поясе, я решился переписать этот код. Стал гуглить как это делается правильно, и нашёл зубодробительные алгоритмы разрезания произвольных многоугольников. После долгих попыток в них разобраться я внезапно понял, что нам нужно разрезать только выпуклые многоугольники (т.к. многоугольники, на которые бумагу могут разделить складки оригами, могут быть только выпуклыми), и быстро написал сравнительно простой метод разрезания выпуклых многоугольников.
Потом я стал писать форматирование решения в соответствии с форматом, прниимаемым сервером. В это время Fornever с Hagene что-то писали на тему «разворачивания скелетов». Hagane ещё и постил задачи для других участников, придуманные «вручную». Потом, чтобы не тратить клетчатую бумагу, Hagane c Fornever стали писать генератор случайных задач.
grouzen предложил написать графическое интерактивное приложение для разворачивания фигур вручную, но до реализации этой идеи как-то ни у кого не дошли руки.
К вечеру субботы у меня был солвер, который решал некоторую часть задач, и я его пачками натравливал на избранные простые задачи. На многих задачах при этом проявлялся баг в геометрических алгоритмах. Тут же написалась решалка тривиальных задач (которые просто квадрат без складываний). Ещё я написал вариант солвера, который складывает вместо требуемой фигуры её выпуклую оболочку — это, очевидно, даёт приближённые решения, но лучше чем ничего.
Потом оказалось, что у нас имеется три реализации геометрии — Minoru и моя на Haskell, Hagane на Racket и Fornever на F#; и две реализации форматирования вывода, обе на Haskell — моя и Hagane, отличающиеся по-моему только названиями функций. На этом месте я взвыл в чатик — мол, нет на нас ПМ-а или хотя бы тимлида.
До позднего вечера я искал баги в реализации геометрии, Fornever с Hagane писали генератор задач, а Minoru писал разворачивание скелетов.
Потом Hagane решил взять на себя функции лида и отправил меня спать. Правда, совсем перед тем как лечь, я нашёл баг в одной строчке (опечатка при копипасте) в реализации разрезания многоугольника, и поправил его, отчего все «волшебные» баги исчезли.

В воскресенье

с утра у меня образовалось несколько идей:

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

Я нарешал скриптом с исправленным солвером пару сотен простых задач и стал реализовывать перечисленные идеи. В итоге где-то к середине дня я реализовал перенос и для самых простых случаев поворот, доделал сворачивание выпуклых фигур, и оставалось только время от времени запускать скачивалку и решалку (ту, которая складывает выпуклую оболочку для всего подряд). Ещё я оставшееся время пробовал всякие улучшения и оптимизации.
В частности, в какой-то момент я вдруг решил попробовать сделать хоть какой-нибудь вариант генетического алгоритма для решения сложных задач. Для этого нужно иметь функцию оценки, а она в данном случае определяется через площади многоугольников. Какое-то время я боролся с функцией нахождения площади из clipper, но то ли я его не так готовил, то ли есть баги в биндингах, то ли в самом clipper — результаты оценки получались настолько неадекватными, что я на это плюнул. Писать собственный расчёт площади времени не осталось.
У моего солвера оставалась существенная проблема: он часто генерировал решения размером в десятки или сотни килобайт, при ограничении в 5000 байт. Вечером стали думать, как уменьшить размер решений. В итоге сделал:

• если многоугольник не выпуклый и мы всё равно будем делать приблизительное решение — округлить входные координаты до 10-12 знаков после запятой (уменьшает размер дробей на выходе);
• складывать не по всем подряд рёбрам многоугольника, а сначала только по чётным, потом только по нечётным. Не очень понимаю почему, но на некоторых задачах это помогло существенно.

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

В итоге

к моменту заморозки leaderboard мы оказались на 44м месте (из 293 команд всего, получивших ненулевое количество очков 201). Что есть необычно высокий результат по сравнению с нашими прошлыми попытками.
По моему личному впечатлению, в этот раз задача была заметно проще, чем в предыдущие (я не удивлюсь, если увижу разочарованные отзывы об этом icfpc от «аксакалов» — мол, слишком легко). Но, возможно, это такой perception bias из-за того, что в классической аналитической геометрии с линейной алгеброй худо-бедно разбираюсь, а во всяких AI почти никак не разбираюсь.
У нас, как всегда, были проблемы с организацией и коммуникацией (каждый писал что-то своё, иногда дублируя работу). По-моему, если бы мы физически находились в одном месте, результаты могли бы быть сильно лучше, хотя бы за счёт взаимной мотивации (говорят, психологически сложнее отлынивать, когда видишь как человек за соседним компом сосредоточенно пишет код) :) Как и в прошлые разы, были проблемы из-за того, что члены команды имели сильно разный опыт работы с выбранным языком.
Надеюсь, в следующем году мы как-нибудь сможем смягчить эти проблемы, и результат будет ещё лучше.

Как не надо участвовать в ICFPC (типа отчёт об ICFPC-2015)

Мы с несколькими товарищами (широко известными в узких кругах - ForNeVer, rexim, Minoru) уже который год подряд пытаемся участвовать в ICFPC. Если кто не в курсе, это такой своеобразный ежегодный контест по программированию, приуроченный к international conference for funcional programming (ICFP). Несмотря на название, программировать можно не только на функциональных языках, а на чём бог на душу положит. Более того, во многих случаях код организаторам передавать необязательно - контест организован так, что нужно отослать ответы на какие-то задачи. Т.е. теоретически можно вообще не программировать, а решить задачи на бумажке и отослать ответы. Просто очень сложно. Контест длится трое суток — в моём часовом поясе это от вечера пятницы до вечера понедельника. Темы заданий выбираются в целом довольно разнообразные, но последние годы заметен уклон в сторону всяческих AI. Например, вот задачи тех контестов, в которых я участвовал:

• 2014 - надо было написать AI для игры a la Pacman. Даны карты, а надо прислать программы на ассемблере выдуманных процессоров, играющие за основного персонажа и за призраков, набирая побольше очков.
• 2013 - угадывание формул. Даны значения переменных и результат вычисления, а также некоторая общая информация о выражении. Надо прислать угаданные выражения.
• 2012 - AI для игры наподобие Supalex.

Результаты у нашей команды обычно... э... ну, лучше чем последнее место, чо. С одной стороны, главное не победа. C другой...
Типичный «путь к успеху» таков. Команда географически сильно распределённая, покрывая несколько часовых поясов. Теоретически это могло бы даже быть преимуществом (непрерывный 24-часовой кодинг, как 24-часовая поддержка, а?). Но как-то не в нашем случае. О контесте вспоминаем за пару дней. Обсуждаем выбор языка программирования, особо не зацикливаясь на фиксации этого выбора. Типичное решение: «давайте попробуем haskell, а там если увидим что чото не то, возьмём C++». При том, что часть команды имеет очень мало опыта с Haskell, а другая часть — с C++. Во время контеста (он длится трое суток) у каждого что-нибудь случается, из разряда «зимой совершенно неожиданно выпал снег» — приезжают родственники, нужно на работу или ещё что-нибудь. Т.е. вещи, которые в принципе можно было предотвратить (отработать в другой день итд), если позаботиться об этом достаточно заранее. В этот раз соригинальничали. О контесте вспомнили аж за неделю. В качестве языка программирования выбрали Scala. При том, что двое из команды (я и Minoru) к этому моменту о ней только по наслышке знали. Я был в принципе не против, т.к. наслышан о языке был давно — почему бы и не изучить. За неделю скачал компилятор, среду разработки (hint: Idea community edition с плагинами для Scala и vim mode) и уехал на дачу. Где через напоминающий старые-добрые времена мобильный GPRS (ни дать ни взять диалап - не верещит на всю комнату, и только) стал изучать гугл на тему туториалов. Нашёл scala by example. Написав hello world, решил потренироваться на кошках и пошёл куда очень давно не ходил — на acm.timus.ru. Кстати, с удивлением обнаружил, что они теперь поддерживают и Scala, и Haskell. Тот факт, что я с институтских времён не занимался спортивным программированием, очень даже сказался — все мои программы упёрлись в time limit :) Не из-за «тормозной явы», конечно, а просто из-за плохих алгоритмов. В данном случае меня это не очень расстроило — в рамках ICFPC производительность нашего кода обычно мало важна. Общее впечатление от Scala, кстати — это скорее «пере-ява», чем «недо-хаскель» :)
У меня есть «особенность стиля разработки», по-моему, не очень удивительная. Я плохо умею придумывать алгоритмы и организацию кода отдельно от самого кода. Поэтому, приступая к чему-то новому, я обычно начинаю с написания сколь угодно плохого алгоритма на том, что под руку подвернётся (прототип в 15 строк, он может даже и вовсе не работать), а дальше уже думаю над алгоритмами и дизайном параллельно с изменением кода. Начало предыдущих ICFPC выглядело поэтому так. Пока народ в чате думает над задачей, над алгоритмами, обсуждает, лучше ли здесь Haskell или C++, я беру и начинаю что-то писать на haskell. К моменту, когда в чате появляются сообщения вида «ну ладно, давайте писать», оказывается, что в репозитории уже лежит мой код на haskell :) (хороший код или плохой — отдельный вопрос). И в итоге остальные, из соображения «экономии кода», чтобы не переписывать то же самое на другом языке, продолжают тоже на haskell. Когда опыта с ним мало, это иногда выливается в многочасовую борьбу с компилятором. Видимо как раз из-за того, что прошлые разы я таким образом «навязывал» остальным Haskell, в этот раз ForNeVer и предложил взять Scala :) Поэтому в этот раз в начале контеста я ждал, пока ForNeVer cоздаст заготовку проекта, а в это время пытался думать над задачей. Без кода думать получалось плохо.
Кстати, о задаче.
В этот раз опять нужно было написать AI для игры. Игра — нечто похожее на тетрис на гексагональной решётке. Основные отличия: вся последовательность фигур известна заранее; фигуры сами по себе вниз не падают, их надо падать отдельными командами; и их можно закреплять не только внизу, но и где-нибудь посередине, если упереть в стенку или в другую фигуру. И ещё: каждая команда может быть закодирована одной из нескольких букв. Поэтому из последовательностей команд можно составлять слова. Имеется некоторое количество «заклинаний», «phrases of power», или попросту чит-кодов. За использование их в последовательности команд дают отдельные очки. Одно заклинание (Ei!) сказали сразу, другие предложили найти «в задании, в твитах, в background leaterature и game artifacts». Бэкграундом были, видимо, произведения Лавкрафта. Организация получения задач и отправки решений такая: дано фиксированное количество «карт» — описаний игровых полей (они могут быть пустыми или на них изначально могут быть какие-то занятые клетки) и фигур, которые там могут выпадать. Надо для каждой карты прислать последовательность команд, которая наберёт по специфическим правилам этого «тетриса» как можно больше очков.
Я нарисовал одну из первых карт (они выдаются в виде json) на бумажке, и обнаружил, что там заполненными клетками написано «Ei!». Ага, значит на других картах могут быть другие заклинания. Только рисовать гексагональную решётку даже на клетчатой бумаге немного утомительно, так что явно нужна какая-то рисовалка карт, чтобы хотя бы на них посмотреть. Примерно к этому времени появилась заготовка проекта, и ForNeVer уже сделал загрузку карт из json. Тогда я написал рисовалку карт в виде ascii-art. Запустив её на имеющихся картах, узнали ещё парочку заклинаний.
В предыдущих ICFPC мы как-то умудрялись обходиться без визуализации действий наших ботов. В этот раз rexim для разнообразия взялся таки сделать визуализацию. Я в AI и родственных алгоритмах мало сведущ — в прошлом году апофигеем стало использование волнового алгоритма. Поэтому я взялся писать то, что особой изобретательности не требует, но при этом явно понадобится — эмулятор этого самого тетриса. Отдельный анекдот вышел вокруг представления игрового поля. Очевидно, нужно что-то наподобие двухмерного массива, с возможностью как-нибудь делать операции «вычёркивание строки» и «перемещение занятых клеток». При этом у меня был, с одной стороны, опыт ещё институтских игрушек, где это был сишный char[][]; с другой — опыт хаскеля предлагал использовать что-нибудь типа [[CellState]]. Опыт со scala не подсказывал пока ничего. Я спросил в чате, и мне предложили не заморачиваясь использовать Array[Array[CellState]] (если кто не в курсе — это мутабельный массив с произвольным доступом, в принципе аналогично сишному char[][]). Ну и ладно. Обернул его в класс, дополнив методами типа «проверить валидность координат», и вперёд. Таким образом, эмулятор вышел «мутабельным»: при обработке команды он изменяет своё состояние. А когда позже ForNeVer стал писать какой-никакой AI, ему понадобились методы типа «посмотреть что получится если выдать такую-то команду», не изменяющие состояния игрового поля. В результате пришлось переделывать эмулятор в частично иммутабельный. Народ потом возмущался — зачем у нас эмулятор мутабельный! в следующий раз никакой мутабельности! Я отвечал, что тогда непонятно, зачем взяли Scala — код без мутабельности естественнее писать на Haskell.
Ещё через некоторое время после начала контеста к нам присоединились grouzen и ulidtko. Ulidtko примерно одновременно с Minoru взялись решать специфическую геометрическую задачку: поворот фигур на гексагональной решётке. Причём каждый из них, кажется, пошёл своим путём. Я решил, что трёх человек на такую простую на первый взгляд задачу будет многовато, и решил этим не заниматься. В итоге большую часть времени я допиливал помаленьку эмулятор и... играл в тетрис. В наш эмулятор с визуализатором. Т.к. первый работоспособный AI у нас появился только где-то к вечеру воскресенья, до этого мы могли набирать очки только играя в наш «тетрис», набирая очки и записывая последовательности команд. А т.к. AI у нас получился бесхитростный, на некоторых задачах мои результаты так и остались лучшими. В воскресенье вечером мы залили всё что этот наш AI нарешал. В понедельник все кроме Minoru ушли на работу. Поэтому в понедельник Minoru ещё что-то допилил в AI и отправил решения по тем задачам, по которым их удалось улучшить.
Собственно, на этом и всё.
«А мораль сей басни... а не будет сегодня никакой морали, дети, идите сами думайте» (с) не помню откуда.

Настройка планшета Wacom Intuos Pro под Debian/Ubuntu и KDE 4/5

Чтобы не забыть, запишу куда-нибудь.
У wacom intuos pro есть четыре лампочки вокруг express ring. Подвиндами они показывают активность одного из четырёх режимов, в которых может работать express ring — это просто четыре варианта настроек. Переключаются режимы кнопкой в центре кольца.
Под линуксами планшет работает без проблем сразу после включения. Только express keys по дефолту ни на что не настроены, а express ring работает просто скроллом. Из четырёх лампочек горит всегда первая.
Express keys и express ring легко настраиваются из systemsettings в кедах (для гнома тоже есть конфигурялка, но специально на неё не смотрел). Но про переключение режимов и лампочек эта конфигурялка не знает. Точнее, у неё есть понятие профиля настроек, и даже можно настроить хоткей на их переключение, но с лампочками на планшете они не связаны.
Ядерный драйвер wacom умеет управлять этими лампочками. Для этого надо записать число от 0 до 3 в файлик /sys/bus/usb/devices/*/*/wacom_led/status_led0_select. Только вот этот файлик по дефолту доступен на запись только руту.
Отсюда возник вот такой набор костылей: https://github.com/portnov/wacom-intuos-pro-scripts.
Правила udev 99-local.rules запускают скрипт wacom-setup.sh, который запускает chmod, чтобы разрешить простым юзерам запись в тот файлик в /sys.
К кнопке посередине кольца средствами кед (или другими) привязывается какое-нибудь редкоиспользуемое сочетание клавиш. На это же сочетание средствами кед (или другими) вешается скрипт wacom-switch-mode.sh, который прибавляет единичку к значению в файлике (переключает лампочку) и вызывает скрипт wacom-ring-mode.sh, который вызывает xsetwacom, чтобы переназначить функции express ring.
В принципе, переключать настройки можно не через xsetwacom, а дёргая кде-шную конфигурялку через dbus, чтобы она переключала профили. Всё это красиво работает под 4ми кедами.
Ещё одна засада: в текущем состоянии в KDE5 конфигурялка вакомов не работает от слова совсем. Она вроде как портирована на KF5, но этот порт в дистрибутивы не включён. И в дебианах/убунтах он просто так не соберётся, потому что требует libxcb-xinput, которого под дебианами/убунтами нет, т.к. он самими разработчиками libxcb считается unstable и по дефолту с xcb не собирается. Если кому нечего делать, может попробовать собрать libxcb-xinput под дебиан или убунту.
Ситуация несколько облегчается тем фактом, что в kubuntu 15.04 похоже поставляется не чистокровные KDE5, а помесь из компонентов KDE 4 и 5. В частности, можно запустить конфигурялку вакомов от четвёртых кед: kcmshell4 kcm_wacomtablet. Но, модуль кедов, который собственно управляет планшетами, он тоже от четвёртой версии, и потому в пятой по дефолту не запускается. Чтобы настройки работали и применялись, надо в автозапуск кедов добавить запуск этого модуля командой qdbus org.kde.Wacom /kded loadModule wacomtablet. Только из systemsettings в пятых кедах сейчас есть баг, из-за которого скрипт в автозапуск добавить можно, но работать он не будет. Так что надо написать *.desktop-файл, который будет запускать скрипт, который будет запускать qdbus, и положить этот desktop-файл в ~/.config/autostart.

LiveMath IV

Дошли руки собрать очередную версию LiveMath.

LiveMath — это LiveDVD, содержащий большой набор свободного математического ПО. Предполагается для использования в основном в демонстрационных целях, но может также использоваться для постоянной работы.

Картинка для привлечения внимания:

(на картинке слева вверху FriCAS считает интегралы в специальных функциях, а справа R выводит графики по данным, включенным в поставку для примера).

В этот раз LiveMath основан на Ubuntu 12.10 (Quantal), плюс некоторое количество дополнительного софта. LiveMath IV содержит (среди прочего):

Системы компьютерной алгебры:

• Maxima 5.27 (http://maxima.sourceforge.net) - полнофункциональная система аналитических вычислений.
• Fricas 1.1.8 (http://fricas.sourceforge.net) и OpenAxiom 1.4.1 (http://open-axiom.org)  - обе актуальные версии мощной системы компьютерной алгебры Axiom.
• YaCas 1.3.2 (http://yacas.sourceforge.net) - еще одна система компьютерной алгебры.
• PARI/GP 2.5.1 (http://pari.math.u-bordeaux.fr/) - широко используемая компьютерно-алгебраическая система, разработанная для быстрых вычислений в теории чисел (факторизации, алгебраическая теория чисел, эллиптические кривые...).
• GAP 4r4p12 (http://www.gap-system.org/) - свободно распространяемый, открытый и расширяемый программный комплекс для применения в области вычислительной дискретной математики, в частности, теории групп.
• Mathomatic 15.8.2  (http://www.mathomatic.org/) - переносимая, универсальная программа, которая может решать, упрощать, группировать, дифференцировать, интегрировать и сравнивать алгебраические выражения.

Системы автоматизации доказательств:

• ACL2 4.3 (http://www.cs.utexas.edu/users/moore/acl2/) - язык программирования для моделирования компьютерных систем и средство, помогающее доказывать свойства этих моделей.
• Coq 8.3.pl4 (http://coq.inria.fr/) - система автоматизированного построения доказательств, с помощью которой, кроме всего прочего, была решена проблема четырех красок.
• Agda2 2.3.0 (http://wiki.portal.chalmers.se/agda/pmwiki.php) - язык программирования с зависимыми типами и система автоматизации доказательств.
•  Prover9/Mace4, Otter и пр.

Системы численных вычислений:

• SciLab 5.3.3  (http://www.scilab.org/) - пакет научных программ для численных вычислений, предоставляющий мощное открытое окружение для инженерных и научных расчетов.
• GNU Octave 3.6.2 (http://www.octave.org/) - язык высокого уровня, предназначенный для выполнения математических вычислений;
• FreeMat 4.0 (http://freemat.sourceforge.net/) - свободная среда для быстрой разработки, научного прототипирования и обработки данных, имеет интерфейс и синтаксис языка, подобные MatLab.
• Yorick 2.2.02 (http://yorick.sourceforge.net/) -специализированный С-подобный язык для создания симуляторов с упором на скорость вычислений.
•  Dynare 4.3.0 (http://www.dynare.org/).
  

Образовательные программы:

• Kig 4.9.2 (http://edu.kde.org/kig/), Geogebra 4.0.34.0 (http://geogebra.org), DrGeo 1.1.0  — интерактивная геометрия.
• KAlgebra 4.9.2
  
• KMPlot 4.9.2 — средство для построения графиков.

Обработка и визуализация данных:

• Gnuplot 4.6.0
• Mayavi2 4.1.0 (http://code.enthought.com/projects/mayavi/#Mayavi2) - открытый пакет научной 2D и 3D визуализации данных.
• OpenDX 4.4.4 (http://www.opendx.org/) - программное средство для анализа данных в графическом виде, визуализации научных данных.
• GGobi 2.1.10 (http://www.ggobi.org/) - среда визуализации многомерных данных;
• QtiPlot 0.9.8.8 - позиционируется как замена для Microcal Origin - программа для несложной статистической обработки данных, построения всяческих графиков.
• Grace 5.1.22 (http://plasma-gate.weizmann.ac.il/Grace/) - программа для подготовки двумерных графиков по численным данным.
• PAW 2.14.04 (http://cern.ch/paw/) - интерактивная программа анализа и графического представления результатов. Может применяться для анализа большого и очень большого объёма данных.
• ROOT 5.34.00 (http://cern.ch/root/) - наследник PAW, интерактивная система обработки и визуализации очень больших объёмов научных данных.
• GNU R 2.15.1 (http://r-project.org/) - мощный язык статистических вычислений, используемый профессиональными статистиками.
• GRETL 1.9.9 (http://gretl.sourceforge.net/) - система эконометрического анализа.
• Udav 0.7.1.2 (http://udav.sourceforge.net/) - инструмент визуализации данных.

Работа с графами

• Tulip 0.5.11
• GraphThing 1.3.2
• Cytoscape 2.8.3
• Rocs 1.7.2

Научные редакторы:

• TeXLive 2012.20120611 - полноценный дистрибутив TeX.
• TeXmacs 1.0.7.15  (http://texmacs.org) - текстовый редактор для набора математических и прочих научных текстов, также позволяет включать в документ сессии FriCAS, Maxima, Octave, SciLab и других систем компьютерной математики. Данная версия использует Qt, так что выглядит заметно приятнее старых, и работает несколько шустрее.
• Kile 2.1.2 (http://kile.sourceforge.net/) - интегрированная среда подготовки документов с помощью TeX.
• Texmaker 3.4 (http://www.xm1math.net/texmaker/) - интегрированная оболочка для LaTeX.
• TeXworks  0.5- лёгкая оболочка для LaTeX.
• LyX 2.0.3.

Также LiveMath IV содержит среду XFCE 4.10, LibreOffice 3.6.2. Для "больших" систем (ROOT, PAW, R, Octave) включена значительная часть имеющихся в репозиториях Ubuntu пакетов. Для многих изначально "консольных" систем включены GUI-обёртки, для некоторых по несколько, на выбор. К большинству программ есть документация. Возможна установка системы на жёсткий диск с помощью стандартного установщика Ubuntu.

Полный список установленных пакетов.

Загрузить образ ISO. (2 GB). Образ гибридный: можно записать на DVD или на флешку. Выложен образ на моём домашнем сервере, суперскоростей не обещаю.

Страница проекта.

К сожалению, у меня нет времени, чтобы тестировать все эти программы. То, что я протестировал - работает. Багрепорты принимаются в комментариях или на e-mail portnov at bk dot ru, но мгновенного исправления не обещаю.

LiveMath сделан с помощью Ubuntu Construction Kit (http://uck.sourceforge.net/), так что каждый, в принципе, может сделать себе нечто подобное. Вероятно, это окажется проще, чем качать моё изделие.

Домашняя бухгалтерия в командной строке, yet another

Сделал вот ещё одно приложение для «домашней бухгалтерии в командной строке», в стиле ledger или hledger, но лучше :)
Называется YaLedger (yet another ledger).
Код: https://gitorious.org/yaledger
README: https://gitorious.org/yaledger/yaledger/blobs/master/README.ru
Умеет:

• Автоматический выбор корреспондирующих счетов по настраиваемым правилам, так что в большинстве случаев достаточно записывать только одну половину проводки;
• Сверку балансов счетов — можно указать, что в данный момент на счёте такая-то сумма, и yaledger автоматически сделает проводку, чтобы его данные сходились с указанными;
• Шаблоны проводок; периодические проводки; автоматическое выполнение проводок при определённых условиях;
• Чтение проводок из нескольких файлов;
• Чтение проводок из форматов CSV и HTML (выписки из телебанков);
• Само собой, работу с разными валютами;
• Учёт курсовой разницы (из-за разницы между курсами купли/продажи)
• Загрузку курсов валют ЦБ РФ;
• Умную обработку дублирующихся записей;
• Несколько отчётов: балансы счетов, обороты по счетам итп.

Сделано на haskell, с учётом основных (моих) требований:

• Это приложение именно для домашней бухгалтерии, так что вести журнал проводок должно быть максимально просто (например, мне лень для каждой проводки указывать два счёта).
• Я хочу, чтобы приложение оперировало более-менее стандартными объектами бухгалтерского учёта. Ну, например, hledger не использует таких сущностей, как "дебет" или "кредит", он просто прибавляет к балансу число, которое может быть отрицательным и положительным; yaledger ведёт себя более похоже на "взрослые" системы, учитывая отдельно кредитовые и дебетовые полупроводки.
• Мне лень, да и некогда особенно, заниматься отладкой; поэтому максимально возможное количество проверок я переложил на систему типов, а там, где в компайл-тайме особенно ничего не проверишь — сделал так, чтобы система типов заставляла меня проверять всё что можно (например, невозможно кредитовать дебетовый счёт, не сойдутся типы; а если в данном случае неизвестно, кредитовый это счёт или дебетовый, компилятор заставит явно написать проверку).

Что-то вроде документации (неполной) тут:  http://redmine.iportnov.ru/projects/yaledger/wiki.

Эту штуку я использую в течение всего периода её разработки (чуть больше месяца :)). У меня работает, но баги, конечно, возможны.

Это пока что-то типа пре-релиза. На днях допишу документацию и выложу на hackage.

Введение в прикладное программирование под GNU/Linux

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

Аудитория

Эта статья расчитана на два вида читателей. Во-первых, это люди, имеющие опыт программирования под MS Windows, но не имеющие такого опыта под GNU/Linux. Во-вторых, это люди, не имеющие опыта программирования вовсе. Однако, я предполагаю, что читатель в общем знаком с общепринятой в программировании терминологией, и ему не нужно объяснять, например, что такое «программа», «функция», «компилятор» или «отладка».

Средства разработки

Я буду рассматривать разработку с использованием тех средств, которые являются наиболее «родными» для GNU/Linux. К ним относятся:

• Язык программирования C

• Командная оболочка bash

• Текстовые редакторы Vim и Emacs

• Компилятор GCC

• Отладчик GDB

• Утилита для сборки проекта GNU make

• Система управления версиями Git

• Оконная система X11

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

Языки программирования

Наиболее «родным» языком программирования для GNU/Linux является C. Это обусловлено следующими факторами:

• GNU/Linux заимствует многие идеи (практически, идеологию) операционной системы UNIX;

• Операционная система UNIX была написана на языке C (собственно, этот язык создавался именно для написания этой ОС);

• Соответственно, ядро Linux и системное окружение GNU написаны тоже на C.

Ниже я буду рассматривать разработку с использованием языка C. Однако, этот выбор не является догмой. Другими популярными при разработке под GNU/Linux языками являются C++, Python, Perl. Конечно, могут использоваться и любые другие языки.

Среда разработки

В течение последних двух десятилетий очень широкое распространение получили т.н. IDE — интегрированные среды разработки. Такая среда включает в себя текстовый редактор, компилятор, отладчик, средства сборки проекта и мн.др. Такие среды есть и под GNU/Linux (наиболее популярны Eclipse, NetBeans, IDEA, KDevelop, Anjuta). Однако, история разработки под UNIX-подобные системы показывает, что IDE не являются не только единственным, но и наиболее эффективным средством разработки. Практически, правильный ответ на вопрос «какая самая лучшая IDE под GNU/Linux» — это «GNU/Linux это и есть IDE».

Часто можно встретить мнение, что большой проект без IDE разрабатывать невозможно. Это мнение легко опровергается. Первые версии UNIX писались даже не в Vim (его тогда ещё не было), а в Ed. Это так называемый «построчный» текстовый редактор, в котором вы можете редактировать за раз только одну строку текста. Весь файл на экране не отображается. В случае с UNIX по-другому и быть не могло — у разработчиков не было никаких экранов, а общение с системой осуществлялось при помощи телетайпов. Современное ядро Linux пишется в основном в редакторах Emacs и Vim.

Многие утилиты UNIX вызывают «текстовый редактор по умолчанию». Команда, запускающая текстовый редактор по умолчанию, берётся из переменной окружения $EDITOR. Некоторые утилиты смотрят сначала в переменную $VISUAL, и, лишь если она не установлена, в переменную $EDITOR. Это исторически сложившееся поведение: к старым компьютерам зачастую не было подключено никакого дисплея, а только телетайп, поэтому запускать экранный (визуальный) редактор смысла не было. В современных дистрибутивах обычно по умолчанию оказывается EDITOR=vi или EDITOR=nano. Указать использование другого редактора для одной команды можно так:

EDITOR=emacs some-command

Чтобы использовать нужный редактор по умолчанию всегда, нужно добавить в файл ~/.profile строчку типа

export EDITOR=emacs

Исторически сложилось так, что «настоящими» текстовыми редакторами для программистов являются только Vim и Emacs (просто из-за того, что у них самая долгая история развития именно в качестве текстовых редакторов для программистов). Остальные редакторы находятся в положении догоняющих.

Командная оболочка

Командная оболочка (или командный интерпретатор) — это программа, принимающая команды от пользователя на некотором достаточно простом языке программирования и выполняющая их. Большинство команд запускают одноимённые программы. Отдельные команды представляют собой конструкции языка программирования оболочки.

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

ОС семейств DOS и Windows заимствовали некоторые функции командной оболочки из UNIX, однако их авторы пошли на существенные упрощения, из-за чего функционал COMMAND.COM и cmd.exe получился сильно урезанным. PowerShell вполне на уровне, но работает существенно по-другому.

В рамках этой статьи я ограничусь использованием командной оболочки bash (как наиболее распространённой и используемой по умолчанию в большинстве дистрибутивов) для запуска компилятора и других средств разработки. Хороший обзор использования командной оболочки можно найти, например, в известной книге [kernigan_pike].

Документация

Все средства разработки и библиотеки в GNU/Linux обычно довольно хорошо документированы. Традиционно для документации используется специальный формат и утилита для его просмотра — man. Документация в системе делится на несколько разделов:

1. Команды пользователя (например, ls, gcc или man)

2. Системные вызовы — API ядра ОС

3. Библиотечные функции

4. Драйвера и т.п

5. Форматы файлов

6. Игры и т.п

7. Различные обзоры подсистем

8. Команды, используемые для системного администрирования

Для вызова раздела документации по имени нужно указать это имя при вызове команды man (например, man ls). Иногда разделы с одинаковым названием есть сразу в нескольких разделах документации документации. Указать конкретный раздел можно при вызове man (например, man 3 printf).

Более подробную информацию о справочной системе man см. в man man.

Утилиты системного окружения GNU часто используют для документации формат info. См., например, info Coreutils.

Компилятор

Сейчас существует много компиляторов языка C, более-менее совместимых с различными стандартами. Тем не менее, пока что в среде GNU/Linux наиболее применимым остаётся компилятор C, входящий в комплект GNU Compilers Collection (GCC). Этот компилятор, кроме стандарта C, поддерживает некоторое количество расширений стандарта. Эти расширения, в частности, широко используются в исходных текстах ядра Linux. В последнее время появляются компиляторы, способные скомпилировать ядро Linux (например, llvm-clang, или EKO).

Компилятор GCC запускается из командной оболочки командой вида

gcc [OPTIONS] program.c

где program.c — имя входного файла. Кроме того, по стандарту POSIX, компилятор может быть запущен командой cc program.c (cc — от "C compiler").

При обычном запуске компилятор пытается создать исполняемый файл. По умолчанию, выходной файл называется a.out (такое название осталось от древних версий UNIX). Другое название можно задать с помощью опции компилятора -o, например,

gcc -o program program.c

При сборке программы из нескольких модулей компилятору можно подавать на вход несколько исходных файлов или файлов объектного кода, например,

gcc -o program main.c module1.o module2.o …

Чтобы только скомпилировать один исходный файл в объектный код (не пытаясь собрать исполняемый файл), нужно дать команду вида

gcc -c module.c

(имя выходного файла по умолчанию будет module.o).

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

Статическая библиотека в UNIX-подобных системах представляет собой архив (старинного формата ar), включающий набор объектных файлов. Такой архив создаётся командой вида

ar r libsomething.a module1.o module2.o …

Имена файлов библиотек традиционно начинаются с префикса lib.

Динамически загружаемая библиотека представляет собой объектный файл специального формата (расчитанного на динамическую загрузку). Такая библиотека создаётся командой вида

gcc -shared -o libsomething.so module1.c module2.c …

Для использования библиотеки при сборке программы её нужно указать компилятору при помощи опции -l, например

gcc -o program -lm program.c

(здесь будет использоваться файл библиотеки libm.so, префикс lib компилятор подставляет по умолчанию). По умолчанию компилятор собирает программу, использующую динамические библиотеки. Если нужно использовать статические версии библиотек, компилятору нужно указать опцию -static.

Подробную информацию об опциях gcc см. в man gcc.

Hello, world!

Считается, что традиция начинать изучение языка программирования с написания программы, выводящей строку "Hello, world!", пошла с книги Кернигана и Ричи "Язык C" [kernigan_richie]. В случае с языком C эта программа выглядит следующим образом:

#include <stdio.h>

int main(int argc, char* argv[]) {
printf("Hello world!\n");
return 0; 
}

Чтобы запустить эту программу, этот текст нужно записать в файл с именем, скажем, hello.c, и из директории, в которой расположен этот файл, дать команду вида

gcc -o hello hello.c

Впрочем, в случае такой простой программы достаточно дать команду

make hello

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

./hello

Порядок сборки

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

На входе компилятор имеет в общем случае набор файлов с исходными текстами. Перед началом собственно компиляции эти файлы обрабатываются т.н. препроцессором (программа cpp). Главная функция этой программы — выполнение директив вида #include . Встретив такую директиву, препроцессор вставляет содержимое указанного файла (в данном случае, stdio.h) на место этой директивы. Препроцессор понимает ещё некоторые директивы, но сейчас на них останавливаться я не буду.

После препроцессора выполняется собственно компиляция. Из исходных файлов на этом этапе получаются т.н. объектные файлы. Это файлы, содержащие исполняемый машинный код, но ещё не готовые для запуска. Главное, чего в них недостаёт — это адреса вызываемых библиотечных функций. Например, код функции printf() содержится в библиотеке libc. А в объектном файле содержится только имя этой функции. Кроме того, объектный файл содержит имена всех объявленных в нём функций.

Объектные файлы, а также используемые библиотеки подаются на вход компоновщику (программа ld). Компоновщик ищет все вызываемые из различных объектных файлов функции (по именам) в объектных файлах и в библиотеках. Если все функции найдены, то компоновщик собирает собственно исполняемый файл. При этом имена вызываемых функций заменяются на конкретные адреса памяти. В случае использования динамической библиотеки имя используемой функции остаётся, и к нему добавляется имя файла динамической библиотеки, в которой при запуске программы нужно будет искать эту функцию.

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

Второй пример: решение квадратных уравнений

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

#include <stdio.h>
#include <math.h>

/* solve: calculate roots of square equation.
* a, b, c are coefficients in equation.
* Roots would be stored at x1, x2.
* Return value: count of real roots.
*/
int solve(double a, double b, double c,
        double* x1, double* x2) {
double D = b*b - 4*a*c;
double sqrtD;

if (D > 0) {
  sqrtD = sqrt(D);
  *x1 = (-b - sqrtD)/(2.0 * a);
  *x2 = (-b + sqrtD)/(2.0 * a);
  return 2;
} else if (D < 0)
  return 0;
  else {
    *x1 = -b/(2.0*a);
    return 1;
  }
}

int main (int argc, char* argv[]) {
double a,b,c;
double x1, x2;
int roots_count;

// Input coefficients
printf("A: ");
scanf("%lf", &a);
printf("B: ");
scanf("%lf", &b);
printf("C: ");
scanf("%lf", &c);

// Solve the equation
roots_count = solve(a,b,c, &x1, &x2);

// Output results
switch (roots_count) {
  case 0:
    printf("No (real) roots.\n");
    break;
  case 1:
    printf("One root: %0.4lf\n", x1);
    break;
  case 2:
    printf("Two roots: %0.4lf and %0.4lf\n",
           x1, x2);
    break;
}

return 0;
}

По аналогии с предыдущим примером, запишем этот текст в файл square.c и попытаемся скомпилировать его командой

gcc -o square square.c

Но на этот раз мы получим ошибку примерно такого вида:

/tmp/cc6RNFIi.o: In function `solve': square.c:(.text+0x6d): undefined reference to `sqrt' collect2: ld returned 1 exit status

В чём здесь дело? Ясно, что компилятору почему-то не понравился вызов функции sqrt(). Причём, он жалуется уже не на файл исходного кода, а на объектный файл (вот этот cc6RNFIi.o). Это означает, что исходный файл благополучно скомпилировался, а проблемы возникли на стадии компоновки (что можно видеть и по упоминанию в тексте ошибки программы ld — это стандартный в GNU/Linux компоновщик). Компоновщик не смог найти функцию sqrt(). В данном случае, это произошло из-за того, что эта функция содержится в библиотеке libm, а мы не просили компилятор использовать её. Чтобы избавиться от этой ошибки, нам нужно изменить команду компиляции на следующую:

gcc -o square -lm square.c

Такая команда должна отработать без ошибок и создать исполняемый файл square.

При сборке любой достаточно сложной программы нам придётся использовать несколько библиотек, и, возможно, понадобится указывать ещё какие-то опции компилятору. Команда может получиться довольно длинная. Что же, каждый раз набирать её вручную? Нет. Один из принципов философии UNIX гласит: «Всё, что может быть автоматизировано, должно быть автоматизировано». Здесь нам пригодится одна из древнейших UNIX-утилит — программа make. Чтобы воспользоваться ею, нужно написать файл с именем Makefile (в той же директории, что и наш исходный файл) со следующим содержимым:

square: square.c         $(CC) -o $@ -lm $<

Теперь собрать исполняемый файл можно просто дав команду make. Как это работает?

Make

Утилита make предназначена для сборки программ (хотя может использоваться для автоматизации многих других похожих задач). Она читает файл с именем Makefile и видит в нём набор правил. Каждое правило определяет три вещи: цель (goal, т.е. то, что нужно собрать), список исходных файлов и набор команд, которые нужно выполнить, чтобы собрать цель из исходных файлов. В примере выше, square — это имя цели, square.c — единственный в данном случае исходный файл (если их несколько, они перечисляются через пробел), а вторая строчка — команда. В команде могут использоваться переменные. Некоторые из переменных имеют специальное значение. В частности, в любом правиле $@ обозначает имя цели, а $< — первый исходный файл. Переменная $(CC) указывает на компилятор C, используемый в системе по умолчанию (в большинстве случаев это gcc, но бывает и что-нибудь другое).

В имени цели и списке исходных файлов может использоваться подстановочный символ %. Например, такое правило:

%.o: %.c   $(CC) -c $<

обозначает, что файлы с именем, заканчивающимся на .o, нужно собирать из соответствующих файлов с суффиксом .c.

Кроме того, make заранее знает некоторое количество правил по умолчанию. Среди них есть упомянутое в последнем примере, а также правило

%: %.c   $(CC) -o $@ $<

Благодаря этому правилу, в примере с «Hello, world!» просто команда make hello запускала cc -o hello hello.c.

По набору правил make составляет граф зависимостей целей друг от друга и от исходных файлов, и выполняет только те команды, которые нужны для сборки цели, указанной в командной строке. Если не указано никаких целей, то собирается первая цель, описанная в Makefile.

Более подробную информацию об этой утилите см., например, в man make.

Управление версиями

Для управления версиями исходного кода может использоваться любая VCS. Однако, раз уж мы говорим о GNU/Linux, рассмотрим вкратце систему, используемую для разработки ядра Linux: git. По git существует довольно обширная документация, в т.ч. и на русском языке. См. например, мою статью [vcs_git] или известную серию статей [los-t_git].

Для начала использования git нужно создать репозиторий — хранилище для версий файлов. Это делается командой

git init

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

*.o square hello

Теперь команда

git add .

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

git commit

По этой команде откроется текстовый редактор по умолчанию. Тут нужно будет написать комментарий к коммиту. В данном случае достаточно строчки типа «Initial commit».

Отладка

Для отладки в Linux используется отладчик gdb. Но сначала, для того, чтобы программу было удобно отлаживать, её нужно скомпилировать с опцией -g. Сейчас нам достаточно изменить Makefile, приведя его к виду

square: square.c         $(CC) -o $@ -lm -g $<

и пересобрать программу.

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

Отладка запускается командой вида

gdb ./square

Если отлаживаемой программе нужно передать какие-то опции командной строки, их можно указать здесь же:

gdb ./some-program -a -b

При запуске отладчика появляется приглашение командной строки вида:

GNU gdb (GDB) 7.2-ubuntu Copyright (C) 2010 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later  This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law.  Type "show copying" and "show warranty" for details. This GDB was configured as "i686-linux-gnu". For bug reporting instructions, please see: ... Reading symbols from /home/portnov/LUG/src/square...done. (gdb)

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

К наиболее часто используемым командам относятся:

list

Напечатать очередной кусок исходника (печатается 10 строк). Можно указать конкретные номера строк после имени команды, например l 10,15.

run

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

break

Установить точку останова. Номер строки, на которой нужно установить точку останова, указывается после имени команды.

next

Выполнить одну строку программы.

print

Вычислить и напечатать выражение. Выражение указывается после команды. Таким образом можно, например, однократно посмотреть значение какой-нибудь переменной.

display

Добавить выражение к списку постоянно отображаемых. Значения этих выражений будут показываться после исполнения каждой команды. Рядом с каждым выражением печатается его номер в списке. Удалить выражение из списка можно командой undisplay с номером выражения.

quit

Выход из отладчика.

Более подробную информацию по GDB см. в man gdb.

Оконная система X11

Исторически в UNIX не было и не могло быть никакой графической среды, потому что не было графических дисплеев. Графическая среда для UNIX появилась примерно тогда, когда появились распространённые графические дисплеи: в 1984. Сначала она называлась W (от Window), затем её усовершенствовали и назвали следующей буквой алфавита — X, следующая версия называлась X2… Сейчас имеем X11.

X11 представляет собой, прежде всего, сетевой протокол поверх TCP/IP и UDP/IP. У протокола есть клиент и есть сервер. Клиент посылает последовательность запросов вида «нарисуй мне окошко», «нарисуй на нём кнопочку», а сервер их исполняет. Один из главных принципов X11 — «определять механизмы, а не политики». Протокол предоставляет возможность, скажем, рисовать окошки, а как именно они будут отображаться — не определяет.

Наиболее распространённым X-сервером сейчас является Xorg (http://x.org); всё ещё жив XFree86; под Windows актуален Xming; выпускаются аппаратные X-серверы — комплекты «монитор + клавиатура + мышка», в которых поддержка серверной функциональности X11 реализована аппаратно — такие комплекты используются в качестве графических терминалов.

Протокол X11, в отличие от, скажем, HTTP, является бинарным, а не текстовым — это сделано из соображений экономии пропускной способности сетевого соединения и простоты разбора запросов сервером. Но это усложняет создание клиентов этого протокола: собирать замысловатые бинарные X11-запросы заведомо сложнее, чем, например, текстовые HTTP-запросы. Поэтому для написания X-клиентов используются специальные библиотеки функций, формирующих и отправляющих серверу X-запросы. Наиболее распространена библиотека libX11. Более современным вариантом является libxcb.

Запросы X11 весьма низкоуровневые. Например, чтобы реализовать функциональность кнопки, нужно нарисовать в окне прямоугольник, написать в нём текст, ждать в цикле нажатия кнопки мыши, и при каждом нажатии проверять, где щёлкнули — внутри прямоугольника или вне него. Поэтому стали появляться так называемые тулкиты — библиотеки, являющиеся высокоуровневыми обёртками над libX11.

Исторически первым тулкитом был Athena3D. Потом были Motif и Tk. Сейчас наиболее распространены GTK+ и Qt (Qt, строго говоря, представляет собой не X11-тулкит, а многоцелевой кроссплатформенный набор библиотек, который может использоваться в качестве X11-тулкита).

Hello, world на GTK+

В качестве примера рассмотрим следующую программу. Она показывает окно с одной кнопкой. При нажатии на эту кнопку появляется сообщение «Hello, world».

#include <gtk/gtk.h>

// This function displays message dialog.
// main_window parameter should be set to parent window of the dialog.
void message_box (GtkWindow* main_window, gchar *message) {
  GtkWidget *dialog, *label, *content_area;
 
  // Create a dialog
  dialog = gtk_dialog_new_with_buttons ("Message",
                                        main_window,
                                        GTK_DIALOG_DESTROY_WITH_PARENT,
                                        GTK_STOCK_OK,
                                        GTK_RESPONSE_NONE,
                                        NULL);
  // Create a label
  content_area = gtk_dialog_get_content_area (GTK_DIALOG (dialog));
  label = gtk_label_new (message);
 
  // On "response" signal (it's called when user clicks a button in
  // the dialog), destroy the dialog.
  g_signal_connect_swapped (dialog,
                            "response",
                            G_CALLBACK (gtk_widget_destroy),
                            dialog);
 
  // Add a label
  gtk_container_add (GTK_CONTAINER (content_area), label);
  // Show the dialog
  gtk_widget_show_all (dialog);
}

// Callback for delete-event signal
static gboolean delete_event( GtkWidget *widget,
                             GdkEvent  *event,
                             gpointer   data )
{
 // If return TRUE, window will not be closed.
 // This may be used to preven closing window in some situations.
   return FALSE;
}

// Callback for destroy signal
static void destroy( GtkWidget *widget,
                    gpointer   data )
{
 // End main GTK+ event loop
   gtk_main_quit ();
}

// Callback for button click
static void hello ( GtkWidget *widget,
                   gpointer  data )
{
 // "data" parameter represents main window here
 message_box(GTK_WINDOW(data), "Hello, world!");
}

int main( int   argc,
         char *argv[] )
{
   GtkWidget *window;
   GtkWidget *button;
  
   // Init GTK+
   gtk_init (&argc, &argv);
  
   // Create main window
   window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
  
   // Set up callbacks for some signals
   g_signal_connect (window, "delete-event",
        G_CALLBACK (delete_event), NULL);
  
   g_signal_connect (window, "destroy",
        G_CALLBACK (destroy), NULL);
  
   // Set window borders width
   gtk_container_set_border_width (GTK_CONTAINER (window), 10);
  
   // Create labeled button
   button = gtk_button_new_with_label ("Hello World");
  
   // Set up callback for "clicked" signal of the button.
   // Pass main window as second parameter.
   g_signal_connect (button, "clicked", G_CALLBACK (hello), (gpointer)window);
  
   // Pack the button into window
   gtk_container_add (GTK_CONTAINER (window), button);
  
   // Show the button
   gtk_widget_show (button);
  
   // Show the window
   gtk_widget_show (window);
  
   // Run main GTK+ event loop.
   gtk_main ();
  
   return 0;
}

Собирается эта программа командой вида

gcc -o gtk-hello $(pkg-config --cflags gtk+-2.0) $(pkg-config --libs gtk+-2.0) gtk-hello.c

GTK+ — довольно сложно устроенный набор библиотек, поэтому, чтобы не указывать все нужные библиотеки и опции компилятора вручную, мы используем здесь программу pkg-config, которая печатает опции компилятора, нужные для использования GTK+.

Дополнительная литература

[raymond] Реймонд, Эрик С. Искусство программирования для UNIX. — Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 544с., ил.

[kernigan_pike] Керниган Б., Пайк Р. UNIX. Программное окружене. — Пер с англ. — СПб: Символ-Плюс, 2003. — 416с., ил.

[kernigan_richie] Керниган Б., Ритчи Д. Язык программирования C. — Пер. с англ. — Москва: Вильямс, 2006. — 304 с.

[vcs_git] Портнов И. Системы контроля версий. Git. URL: http://iportnov.blogspot.com/2008/06/git.html

[los-t_git] Los-t. Git guts (серия статей в ЖЖ). URL: http://los-t.livejournal.com/tags/git+guts

Изготовление презентаций из Asciidoc с помощью Beamer

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

Схема такая:

Сначала из Asciidoc делаем DocBook. Это можно сделать командой вида asciidoc -b docbook input.txt. Только вот по такой команде получится файл в формате DocBook 4.5, а моя XSL-таблица понимает только DocBook 5.0+. Поэтому берём конфигурационные файлы asciidoc для изготовления DocBook 5.0, например, отсюда, и даём команду вида

asciidoc -b topic input.txt

Получается файл input.xml. Теперь берём XSL-таблицу, преобразующую DocBook 5.0+ в TeX-овский исходник, например, здесь (эта таблица заведомо не полная, но для моих задач хватает; кому не хватит — добавляйте туда свои шаблоны :)), и даём команду вида

xsltproc beamer.xsl input.xml > presentation.tex

Ну а теперь компилируем этот исходник командой вида

xelatex presentation.tex

(может понадобиться запустить эту команду несколько раз, чтобы проставились все ссылки и т.п).

Таким образом сделана, в частности, упомянутая в одном из предыдущих постов презентация (из вот такого исходника).

Об изготовлении EPUB из DocBook

Тут не так давно я уже упоминал, что из DocBook можно делать, в том числе, и EPUB. Однако процесс не вполне тривиальный; мне кажется, его стоит расписать несколько подробнее.

Вот тут в IBM DeveloperWorks описан такой процесс. Однако изготовленный по этому рецепту файл будет обладать парой недостатков:

• Это будет файл устаревшего формата «Open Epub»;

• В нём не будет внедрённых шрифтов.

Такой файл благополучно открывается чем-нибудь типа Okular. Однако AdobeViewer на читалках типа PocketBook 301+ в таких файлах показывает русские буквы вопросиками. Это происходит из-за того, что встроенного шрифта в файле нет, AdobeViewer пытается использовать шрифт по умолчанию, а в нём нет русских букв.

Так что будем делать «более правильный» EPUB. «Нормальный» EPUB-файл — это zip-архив, в котором содержатся следующие вещи:

• Файл с именем «mimetype»; этот файл обязательно должен идти первым в архиве, не должен быть сжат, и его содержимым должна быть строка «application/epub+zip» (без символа новой строки в конце).

• Директория с именем «META-INF»; в ней — файл container.xml. Примеры содержимого этого файла можно нагуглить, главное что в нём должно быть прописано — ссылка на файл contents.opf (OPS/contents.opf).

• Директория с именем «OPS»; В ней — HTML-файлы с собственно содержимым книги, картинки к ним, шрифты (файлы *.ttf), и файл contents.opf и таблица стилей CSS.

Для того, чтобы сделать такой файл из имеющегося DocBook-файла book.xml, нужно проделать следующее:

1. Выполнить команду вида:

   xsltproc --stringparam epub.oebps.dir OPS/ \
          --stringparam epub.embedded.font Ubuntu-R.ttf \
          --stringparam html.stylesheet style.css /usr/share/xml/docbook/stylesheet/docbook-xsl/epub/docbook.xsl \
          book.xml

   Здесь вместо «Ubuntu-R.ttf» можете указать какое-нибудь другое имя шрифтового файла. Путь к epub/docbook.xsl на вашей системе может быть и другим, подставьте ваш. Эта команда создаст директори META-INF и OPS в текущей директории.

2. Скопировать откуда-нибудь или написать таблицу стилей OPS/style.css. Стили можно настраивать на ваш вкус, но надо учитывать следующее:

   • Если вы предполагаете, что документ будут читать на E-Ink устройстве, то не делайте слишком сложную цветовую гамму; экран мало того что чёрно-белый, так ещё не очень хорошо показывает тонкие оттенки. Идеально было бы обойтись 4мя или 8ю оттенками серого (включая чёрный и белый).

   • В таблице должны быть правила, указывающие конкретные шрифты, наподобие следующих:

     @font-face {
       font-family: "Ubuntu";
       font-style: normal;
       font-weight: normal;
       src: url(Ubuntu-R.ttf)
     }
     
     @font-face {
       font-family: "Ubuntu";
       font-style: normal;
       font-weight: bold;
       src: url(Ubuntu-B.ttf)
     }
     
     @font-face {
       font-family: "Ubuntu";
       font-style: italic;
       font-weight: normal;
       src: url(Ubuntu-I.ttf)
     }
     
     @font-face {
       font-family: "Ubuntu";
       font-style: italic;
       font-weight: bold;
       src: url(Ubuntu-BI.ttf)
     }
     
     @font-face {
       font-family: "DroidSansMono", monospace;
       font-style: normal;
       font-weight: normal;
       src: url(DroidSansMono.ttf)
     }
     
     pre {
     white-space: pre-wrap;
     font-family: "DroidSansMono", monospace;
     font-size: 85%;
     }

     (имена шрифтов, конечно, укажите ваши).

3. Скопировать откуда-нибудь файлы шрифтов (*.ttf) в директорию OPS/.

4. Исправить файл OPS/content.opf, добавив туда ссылки на шрифты. Это делается строчками вида:

   
   

   
   <item id="font2" href="Ubuntu-I.ttf" type="application/x-font-ttf"/>
   

   в разделе для каждого файла шрифта. Значения параметра id ни на что не влияют и могут быть любыми, лишь бы не повторялись.

5. Собрать собственно EPUB-файл командами вида

   $ echo "application/epub+zip" > mimetype
   $ zip -0Xq  my-book.epub mimetype
   $ zip -Xr9D my-book.epub META-INF OPS

6. (Опционально) Проверить получившийся файл при помощи программы epubcheck командой вида

   java -jar epubcheck.jar my-book.epub

Получившийся файл my-book.epub должен нормально читаться как на компьютере, так и на книгочиталках.

Небольшое разъяснение по комментариям

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

Подготовка технической документации с использованием asciidoc и DocBook

Это мой конспект для выступления на семинаре, проводившемся нашей LUG. См. также презентацию к докладу.

Глава 1. Актуальность, цели и задачи

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

Целью разработки документации к программному продукту является предоставление пользователю достаточно полной информации о продукте в том виде, в котором это удобно пользователю. Отсюда вытекают следующие задачи:

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

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

Глава 2. Обзор технологий

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

• MS Word и подобные системы;

• Системы «единого источника»:

  • Help&Manual и аналоги;
  • DocBook;
  • DITA;
  • и другие.

Рассмотрим некоторые из этих технологий несколько подробнее.

Глава 3. Help&Manual

Главным плюсом этой системы часто является то, что она уже внедрена и работает. Также несомненный плюс — это система единого источника, т.е. из одного текста можно получить документ в разных форматах. Особенность этой программы и аналогов: это WISIWYG-системы. Насчёт того, является ли эта особенность плюсом или минусом, по сей день не утихают споры. Плюс WISIWYG-технологий очевиден, он заложен в названии: можно сразу видеть, как будет выглядеть текст в результате. К минусам WISIWYG относят следующие пункты:

• Есть такое высказывание: если система предоставляет возможность что-нибудь настраивать, она, фактически, заставляет вас это настраивать. В данном случае это относится к тому, что автор тратит время не только на написание текста, но и на его оформление, хотя это, по идее, не его задача.
• Такие системы склонны порождать совершенно дикую и нечитаемую разметку при конвертировании в HTML, LaTeX и другие подобные форматы. Например, легко можно получить разметку наподобие: разметка. Это сказывается, как только появляется необходимость поправить такую разметку «руками».
• При работе в таких системах люди склонны использовать не логическую, а физическую разметку (например, помечать кусок текста жирным шрифтом, вместо того чтобы отмечать этот текст как заголовок). Что интересно, большинство таких систем предоставляют возможность использования логической разметки, иногда даже удобную, но по каким-то психологическим соображениям люди не склонны её использовать. Это приводит к проблемам при изменении общего стиля оформления документа, а также зачастую при конвертировании в другие форматы.

В связи с последним пунктом можно упомянуть системы с похожим девизом — WISIWYM (What You See Is What You Mind). Таких систем значительно меньше. К ним относится, например, LyX (http://www.lyx.org). Такие системы вобще не позволяют использовать физическую разметку. LyX, например, не позволит вам поставить два пробела или два разрыва строки подряд.

Известные минусы H&M и аналогов:

• Закрытый бинарный формат файлов; впрочем, это исправляется в новой версии H&M, где используется XML-формат;
• Следствие: для просмотра и редактирования нужна сама программа H& M;
• Все эти системы платные;
• Нет средств для управления версиями документации;
• Нет средств для обеспечения одновременной работы нескольких человек над одним документом.

Наш отдел документации, видимо, сравнительно небольшой. Важнее, на самом деле, что над одним документом у нас работает 1-2 человека - писатель и переводчик. Поэтому пока что отсутствие средств для управления версиями нам не слишком мешает.

Глава 4. DocBook

DocBook — это формат для ведения технической документации, основанный на XML. Разработка DocBook началась в 1991 году и, в разное время, развивался и поддерживался этот формат различными организациями:

• 1991—1994: HaL Computer Systems и O’Reilly & Associates (+ большое влияние Novell и Digital);
• 1994—1998: Davenport Group (+ большое влияние Novell и Sun);
• 1998—2007: OASIS. DocBook XML v4.5;
• 2 Aug 2008: OASIS. DocBook XML v5.0.

Раньше поддерживалась версия DocBook, основанная на SGML вместо XML (DocBook/SGML). SGML более «дружелюбен», более приспособлен к написанию человеком. Например, некоторые теги можно не закрывать, некоторые можно даже и не открывать. Это свойство досталось в наследство от SGML в HTML. Если в HTML-файле написать

Привет мир! <a href=http://site.com/>site.com</a>

(это полное содержимое файла), то браузер обязан интерпретировать это так же, как код

<html>
<header></header>
<body>
<p>Привет мир! <a href="http://site.com/">site.com</a></p>
</body>
</html>

Сразу видно, что это позволяет значительно упростить разметку. Однако это делает программы для обработки SGML гораздо более сложными и неустойчивыми в работе. До сих пор не существует программ, разбирающих любую разновидность SGML!

Так что сейчас DocBook/SGML не поддерживается, поддерживается только DocBook/XML.

К плюсам этой технологии можно отнести:

• Не только открытый, но и стандартный формат, широко используемый как в OpenSource, так и в коммерческих компаниях;
• Существующие инструменты позволяют преобразовывать DocBook во все распространённые форматы (HTML, CHM, PDF итп);
• За счёт открытости и стандартности возможно реализовать преобразование в любой другой формат;
• Формат очень полный; в спецификации предусмотрены, например, специальные теги для сочетаний клавиш, для пунктов меню, и т.п;
• Формат можно расширять, дописывая собственные DTD;
• Это XML, а для работы с XML существует огромное количество инструментов и технологий;
• Т.к. исходные файлы текстовые, их можно держать под управлением системы контроля версий.

К минусам я бы отнёс:

• Высокий порог вхождения; нужно знать XML и саму спецификацию DocBook;
• Нетривиальная настройка вывода в HTML, PDF и т.п; Например, для вывода в PDF используется либо промежуточный вывод в TeX (так что для настройки нужно знать TeX), либо промежуточный вывод в XSL-FO (так что для настройки нужно знать XSL-FO);
• Системы контроля версий не так уж хорошо приспособлены к хранению XML-файлов.

Менее очевидным минусом является малое количество WISYWIG-программ для редактирования DocBook (но они есть, из бесплантых — Serna, разрабатываемая нашими соотечественниками).

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

Глава 5. DITA

Некоторыми (особенно в США) формат DocBook рассматривается как устаревающий. На смену ему приходит технология DITA. Это также формат, основанный на XML. Однако базовый формат определяет только основные теги, которые используются в любом документе. Все более специфичные теги определяются в так называемых специализациях DITA с помощью деклараций DTD. Существует несколько стандартных специализаций. Предполагается, что каждый пишет специализацию для своих нужд.

DITA содержит следующие нетривиальные идеи:

1. Текст пишется во многих небольших файлах, называемых топиками (topics). Каждый топик — это логически завершённый кусок документа.
2. Эти топики объединяются в выходной документ согласно содержимому других файлов — карт документа. Таким образом, получается, что текст отделён от структуры документации, текст и структуру можно менять независимо.
3. Каждый топик имеет определённый тип (doctype в смысле DTD), и структура топика определяется его типом. Стандартные типы — Задача, Концепция и Справочник. Например, топик типа Задача описывает последовательность шагов, необходимых для выполнения задачи. Топик типа Справочник содержит перечень элементов и их описаний, и т.д. Благодаря специализации всегда можно добавить свои типы топиков.

Плюсы:

• БОльшая, даже по сравнению с DocBook, гибкость формата;
• И все плюсы DocBook.

Минусы:

• По сравнению с DITA Docbook рассматривается как формат для чайников; Как минимум, здесь надо знать не только XML, а ещё и DTD;
• Т.к. формат ещё относительно новый, он пока слабее поддерживается;
• Тот же минус, что у DocBook: не лучшая поддержка XML со стороны систем контроля версий;
• Тот же минус, что у DocBook: сложность настройки вывода в PDF, по тем же причинам.

Про бесплатные WISIWYG-редакторы для DITA я ещё вобще не слышал.

Глава 6. Wiki-подобные разметки

Чтобы не писать в XML, широко используются различные Wiki-подобные разметки. Их очень много. Практически каждый wiki-движок предлагает свой язык разметки. Наиболее известны разметки MediaWiki (используется википедией) и dokuwiki.

Не все wiki-разметки поддерживают все средства форматирования, многие ограничены. Разметка MediaWiki поддерживает практически любое форматирование, но выглядит такая разметка страшновато. Dokuwiki выглядит более читаемо, но не поддерживает некоторое сложное форматирование.

Среди таких разметок известна ещё разметка Asciidoc. asciidoc - это скрипт на python, преобразующий соответствующую разметку в несколько выходных форматов. Есть возможность определить «бэкенды» для вывода в какие-нибудь ещё форматы. Достаточно хорошо поддерживаются выходные форматы HTML и DocBook. DocBook, в свою очередь, можно преобразовать практически во что угодно.

Существует программа (и библиотека) pandoc, предназначенная для конвертации различных форматов разметки. Например, с помощью этой программы можно преобразовать RST в Markdown, HTML или MediaWiki, или HTML в Markdown, и т.п. Эта библиотека достаточно гибкая, к ней можно писать фильтры — readers и writers. Я поддерживаю reader и writer для Asciidoc.

Плюсы такой технологии:

• Меньший порог вхождения, чем у XML-технологий;
• Системы контроля версий лучше всего работают как раз с plain text файлами;
• При использовании DocBook в качестве промежуточного формата получаем все плюсы технологии DocBook;
• В принципе, можно использовать DITA вместо DocBook в качестве промежуточного формата;
• За счёт наличия конвертеров всегда есть возможность уйти с этой технологии на какую-то другую.

Минусы:

• Порог вхождения всё-таки есть, хоть и небольшой;
• Из-за использования DocBook в качестве промежуточного формата получаем минус DocBook — сложность настройки вывода в PDF.

Глава 7. Применение для совместной работы

В основном здесь рассматривается использование web-интерфейса для работы с документами. Однако надо заметить, что это, не единственный вариант. Как минимум не стоит забывать про возможность использования систем контроля версий для совместной работы над документами.

Сначала я стал рассматривать возможность использования уже имеющейся веб-платформы — Confluence. Её, в принципе, можно использовать для разработки документации, но:

• Своеобразная разметка; это тоже wiki-разметка, но уникальная, никто кроме confluence её не поддерживает;
• Слабая поддержка импорта: практически есть возможность только импортировать doc-файлы;
• Слабая поддержка экспорта: confluence может экспортировать pdf, но так, что этот вариант не многим лучше распечатки веб-страницы на pdf-принтере; другие форматы вывода не поддерживаются;
• Сами тексты хранятся в БД, и в случае, если придётся переходить на другую технологию, тексты придётся как-то нетривиально добывать из БД.

Я давно использую Asciidoc, поэтому стал искать wiki-движки, которые бы поддерживали asciidoc. Как оказалось, среди огромного количества вики-движков только единицы поддерживают больше одного формата разметки. Единственный движок, поддерживающий Asciidoc — это Gitit, и как раз за счёт использования библиотеки pandoc. Кроме того, Gitit хранит тексты не в БД, а в текстовых файлах. Для контроля версий может использоваться одна из нескольких систем контроля версий (Git, Mercurial, Darcs). Так что если открыть доступ к этому репозиторию по сети, то получаем возможность редактирования содержимого вики с локального компьютера, любимым текстовым редактором, без веб-форм и вообще без соединения по сети (сеть нужна только чтобы взять содержимое и положить его обратно).

Gitit использует для обеспечения совместного редактирования достаточно простую модель. Предположим, один человек (A) начал редактировать страницу, затем (не дожидаясь пока A закончит) её начал редактировать Б. В таком случае, если изменения, внесённые двумя людьми, не пересекаются (например, они редактировали разные части страницы), будут применены все изменения. Иначе тому, кто закончит последним, будет предложено разрешить конфликты вручную.

Системы контроля версий используют примерно ту же модель, но могут обеспечивать бОльшую гибкость: см., например, git merge vs git rebase.

Глава 8. Об импорте и экспорте

Собственно, об экспорте я кратко уже упомянул. Программа pandoc позволяет конвертировать документы в разметке asciidoc в несколько распространённых форматов, включая docbook. В свою очередь, docbook можно сконвертировать во что угодно, даже в xml-формат последней версии H&M.

В случае необходимости можно преобразовать имеющиеся документы в формат asciidoc. В случае с исходными документами в формате H&M используемой, 4й версии, для этого придётся:

• Конвертировать исходный hmx файл в xml-формат новой версии H&M, используя конвертер, поставляемый с этой новой версией;
• С помощью небольшого скрипта и XSL-таблицы преобразовать полученный набор xml-файлов в один xml-файл docbook;
• С помощью ещё одной XSL-таблицы преобразовать docbook в asciidoc.

При этом возникают мелкие недочёты, связанные с особенностями работы H&M. Например, в его xml-файлах встречается разметка вида:

слово слово<strong> выделено </strong>текст...

или даже

слово <strong></strong> дальше текст...

Такая разметка, конечно, превращается в не вполне корректную asciidoc-разметку. Но это, вообще говоря, мелочи, и исправляется "поиском и заменой" в текстовом редакторе.

Глава 9. Улучшение поддержки DocBook

Для обеспечения более полной поддержки DocBook я определил в своём конфигурационном файле Asciidoc дополнительные макросы:

• icon:image.png[] для вставки иконок;
• button:button.png[Текст кнопки] для упоминаний кнопок;
• label:[Текст] для заголовков элементов управления;
• screenshot::screen.png[] для больших скриншотов.

Глава 10. Настройка вывода в PDF

Существует несколько способов преобразовать DocBook в PDF. Наиболее распространены два:

• С использованием XSL-FO в качестве промежуточного формата;
• С использованием LaTeX в качестве промежуточного формата.

XSL-FO — это ещё один XML-формат для представления форматированного текста. В отличие от DocBook, этот формат ориентирован на низкоуровневую физическую разметку. Преобразовать DocBook в XSL-FO несложно, для этого есть свободно доступные XSL-таблицы. Преобразованием XSL-FO в PDF занимаются специальные программы, называемые XSL-FO Processors. Их существует несколько:

• Apache FOP (бесплатный, но не поддерживает некоторых возможностей и имеет некоторые сложности с настройкой русскоязычного вывода);
• JadeTeX (специальная версия TeX, настроенная так, что понимает xml на входе);
• PassiveTeX (что-то из той же серии);
• XEP (коммерческий продукт, полностью функциональный, но опять же есть сложности с русским языком).

Собственно, различные сложности с русским языком есть у всех этих вариантов (они всегда решаемы, но это требует времени). Разработка JadeTeX и PassiveTeX, к тому же, на данный момент заморожена.

Другой вариант преобразования — использовать в качестве промежуточного формата TeX. Для преобразования DocBook в TeX используется программа dblatex, представляющая собой скрипт на Python и набор XSL-таблиц. Полученный TeX-файл, в зависимости от настроек dblatex, должен быть затем обработан LaTeX, PDFLaTeX или XeLaTeX. Я использую XeLaTeX. Он имеет следующие преимущества:

• Полная поддержка Unicode (те, кто работал с «традиционными» версиями TeX, знают, что поддержка Unicode в них реализована с помощью хитроумных хаков);
• XeLaTeX использует шрифтовую подсистему операционной системы (GDI на Windows, Freetype на Linux) вместо специфической и местами устаревшей шрифтовой подсистемы TeX. В частности, доступны все установленные в системе шрифты;
• Формат вывода по умолчанию — PDF.

Сгенерированные dblatex документы используют специальный стиль, поставляемый в комплекте dblatex. Его, конечно, можно модифицировать. XSL-таблицы из комплекта тоже можно настроить под свои задачи.

Глава 11. Вывод в CHM

Вывод в CHM поддерживается «стандартным» набором DocBook-XSL. Правда, для полноценной поддержки русского языка надо добавить следующие параметры к xsltproc:

xsltproc -stringparam chunker.output.encoding windows-1251 \
  -stringparam htmlhelp.encoding windows-1251 -stringparam chunker.output.indent yes

и в получившемся файле htmlhelp.hhp указать русский язык:

sed -i -e 's/0x0409.*/0x0419 Russian (RUSSIA)/' chm/htmlhelp.hhp

Компилятор CHM (hhc.exe) из комплекта MS HTML Help Workshop благополучно запускается под Wine, достаточно «подсунуть» ему windows-библиотеки mfc40.dll и itss.dll.

Глава 12. Поддержка составных документов

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

Другой вариант — использовать XInclude уже после преобразования документов в DocBook/XML. Этот вариант более гибкий и удобный. Например, можно включать не весь файл целиком, а только нужные секции. Для этого пишется ещё один XML-файл, называемый мастер-документом, в котором указана мета-информация (заголовок и т.п.), а также структура документа и набор тегов , включающих нужные разделы других документов. Но такой XML содержит мало полезной информации и много служебной разметки. Чтобы не писать мастер-файл в XML руками, я использую небольшой скрипт, делающий этот файл из YAML-файла вида

title:  Заголовок составного документа
author: Ilya V. Portnov
date:   September 2010
contents:                                 # Содержание
- programmer:                           # Здесь будут включены разделы из файла programmer.xml
- used_abbrevs                        # \
- add_docs                            #  }- Список разделов из programmer.xml
- sys_reqs                            # /
- part:                                 # Здесь будет сформирована часть документа
Концепция:                            # с заголовком part
- concept:                            # Внутрь этой части будут помещены разделы из concept.xml
- concept_goals                     # ...
- concept_components
- technologies
- concept_features
# Здесь включаются все главы, являющиеся дочерними
# по отношению к элементу 'general_descr'
- part:
Руководство программиста. общее описание:
- programmer: [ xpointer(id('general_descr')/chapter) ]
- part:
...
Руководство администратора:
- admin:
- _radixware_starter
- _radixware_server
- _radixware_manager
- user: [ _radixware_explorer ]

Таким образом получается подход, близкий к подходу DITA. Текст хранится в отдельных топиках и объединяется согласно картам документов (в формате YAML). При этом получаем даже дополнительную гибкость по сравнению с DITA, т.к. в YAML-карте документа упоминаются не только имена страниц, а и идентификаторы конкретных секций. Благодаря этому можно, например, переставить разделы в выходном документе, не меняя страниц, а меняя только карту документа.

Глава 13. Профилирование

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

DocBook предусматривает атрибуты тегов для профилирования изначально. Их поддержка в asciidoc добавляется редактированием конфигурационного файла. Например, чтобы пометить абзац как относящийся только к ОС Windows, нужно перед абзацем поместить строку [os="windows"].

Обычно для каждой задачи требуется профилирование сразу по нескольким переменным. Например, у данного заказчика OS Linux, архитектура процессора x86_64, и т.п. Чтобы не указывать каждый раз все параметры вручную, я пишу файл profiles.yaml вида

me:
os: any
audience: author
review:
os: any
audience: reviewer
some_customer:
os: linux
arch: x86_64

Здесь каждой цели профилирования сопоставлен набор пар (имя, значение), по которым должно производиться профилирование. Скрипту нужно только указать цель профилирования в качестве аргумента командной строки.

Кроме того, поддерживаются «профили по умолчанию» для отдельных документов. Эти профили указываются в файле *.ymap. Параметры профилирования, заданные при сборке, перекрывают параметры, заданные для документа по умолчанию.

Глава 14. История изменений

Часто регламент требует, чтобы в начале документа присутствовала таблица, описывающая историю версий документа. Ведение такой таблицы автоматизируется благодаря тому, что для хранения документации используется git. Специальный python-скрипт анализирует вывод команды git log для каждой страницы и ищет сообщениях коммитов пометку [MAJOR] (таким образом, в сводную таблицу попадут только действительно важные изменения). Этот же скрипт пытается получить из таких сообщений версию продукта, к которой относится изменение (ищет сразу после пометки [MAJOR] строку вида PRODUCT: TXRBS-1.1.1.6). Затем другой скрипт сводит таблицы изменений для отдельных страниц в одну таблицу для всего документа и для каждого изменения указывает список изменившихся разделов.

Глава 15. Внешние ссылки

Обычно комплект документации состоит не из одного документа, а из нескольких. И появляется необходимость делать ссылки между документами. Главная тонкость тут в том, что при разных вариантах сборки документации одна и та же страница может оказаться в разных документах, поэтому нужны какие-то действия, чтобы определять, на какой файл ставить ссылку в выходном документе.

Эта задача у меня решается следующим образом. Во всех ссылках указываются только идентификаторы целей. При сборке xsl-стили автоматически делают внешними те ссылки, которые ссылаются на идентификаторы, определённые не в собираемом документе. В случае, когда все связанные документы описаны в одном ymap-файле, на этом этапе сборки все документы существуют в виде одного большого xml-документа (правда, он целиком никогда не формируется в виде файла, а только передаётся между скриптами через unix pipes). В такой ситуации не составляет труда с помощью xsl выяснить, какой идентификатор в каком документе определён.

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

    <externs>
<document name="another_document">
 <title>Руководство администратора</title>
 <pointer target="target1"/>
 <pointer target="target2"/>
 ...
</pointer>
<document name="another_document_2">
 ...
</document>
</externs>

Таким образом, в xml-документе опять же оказывается определено, какие идентификаторы в каких документах определены, и xsl-стиль может правильно расставить внешние ссылки.

Глава 16 Полная схема сборки