Неспящий

C++ 0x

2009-05-24T14:25:00.000-07:00

Поставил себе gcc 4.5 из лямбда бранча. Поиграюсь пока с тем, что успели реализовать из С++0x.
Заодно на виртуальную машину поставил windows7 + msvs 2010beta. Там тоже частично реализован C++0x (lambda, auto, static_assert).
Интересно сравнить подоходы реализации тех же лямбд и замыканий у микрософта и gcc.

Пока что нашёл баг в студии.
В таком коде
auto a = []() { return [](){return 0.0f;}; };

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

gcc на этой строчке вообще умирает с sigsegv

upd.
Ещё баг в gcc нашёл.
Такой вот код:


function Foo::GetEventHandler()
{
   return  [=](){this->onSomeEvent();};
}

при попытке вызова функтора получим sigsegv, так как this почему-то в лямбду захватывается нулевой.

если написать вот так:

return [this](){this->onSomeEvent();};
то всё ок.

в vc10 корректно работают оба варианта

2009-03-02T07:47:00.000-08:00

http://www.trumphurst.com/cpplibs/cpplibs.php
Довольно полезный сайт, содержащий базу различных С++ библиотек и небольшое описание к ним. Как я понял, база постоянно обновляется.

Подборка документов.

2009-01-16T09:19:00.000-08:00

Ужас не писал сюда почти год. Буду исправляться.

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

списки и кортежи

2008-04-21T19:47:00.000-07:00

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

Linux комментарии

2008-04-16T17:05:00.000-07:00

Тема конечно не новая, но просто стало интересно. Ввёл вот эту комманду в директории с исходниками линукса
grep fuck -Rn ./*

вот результат её

./arch/mips/kernel/irixelf.c:795:#if 0 /* XXX No fucking way dude... */
./arch/mips/kernel/irixioctl.c:2: * irixioctl.c: A fucking mess...
./arch/mips/pci/ops-bridge.c:43: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:63: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:72: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:105: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:126: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:135: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:176: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:200: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:207: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:244: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:268: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:275: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/sgi-ip22/ip22-setup.c:44: * fucking with the memory controller because it needs to know the
./arch/ppc/syslib/ppc405_pci.c:71: * the kernel try to remap our BAR #1 and fuck up bus
./arch/sparc/kernel/process.c:582: /* fuck me plenty */
./arch/sparc/kernel/sunos_ioctl.c:62: /* Binary compatibility is good American knowhow fuckin' up. */
./arch/x86/kernel/cpu/cpufreq/powernow-k7.c:577: * Some Athlon laptops have really fucked PST tables.
./arch/x86/kernel/cpu/mtrr/generic.c:141:/* Some BIOS's are fucked and don't set all MTRRs the same! */
./Documentation/DocBook/kernel-locking.tmpl:1408: If you don't see why, please stay the fuck away from my code.
./drivers/ide/pci/cmd640.c:16: * These chips are basically fucked by design, and getting this driver
./drivers/media/video/bt819.c:204: BUG? Why does turning the chroma comb on fuck up color?
./drivers/mtd/mtd_blkdevs.c:351: registered, to prevent the link/init ordering from fucking
./drivers/net/sunhme.c:1000:/* Only Sun can take such nice parts and fuck up the programming interface
./drivers/net/sunhme.c:2077: /* This card is _fucking_ hot... */
./drivers/scsi/NCR53C9x.c:1771: * how bad the target and/or ESP fucks things up.
./drivers/scsi/NCR53C9x.c:2691: /* Be careful, we could really get fucked during synchronous
./drivers/scsi/qlogicpti.h:64:/* Am I fucking pedantic or what? */
./drivers/watchdog/shwdt.c:116: * brain-damage, it's managed to fuck things up one step further..
./include/asm-cris/arch-v32/spinlock.h:109: * writers) in interrupt handlers someone fucked up and we'd dead-lock
./include/asm-m68k/sun3ints.h:30:/* master list of VME vectors -- don't fuck with this */
./include/asm-sparc64/system.h:195: /* If you fuck with this, update ret_from_syscall code too. */ \
./include/linux/netfilter/xt_limit.h:18: /* Ugly, ugly fucker. */
./lib/vsprintf.c:9: * Wirzenius wrote this portably, Torvalds fucked it up :-)
./net/ipv4/netfilter/nf_nat_snmp_basic.c:1015: * (And this is the fucking 'basic' method).
./net/netfilter/nf_queue.c:158: /* James M doesn't say fuck enough. */
./sound/oss/opl3.c:833: * What the fuck is going on here? We leave junk in the beginning

Линукс всё же народная ось :)

полезные инструменты

2008-03-02T15:07:00.001-08:00

Оказалось, мне тут передали эстафету в одном интересном флешмобе. Чтож, придётся поучаствовать.

1. Yakuake. Очень удобная консоль, которая выезжает сверху как в продвинутых играх. Позволяет экономить место и время на мелких операциях в консоли. Но если нужно что-то сложное делать, типа подебажить в gdb, то предпочитаю полноэкранную konsole, благо у меня два монитора и я могу себе это позволить.

2. Subversion. Система контроля версий нужна не только команде разработчиков, но и одному человеку. Можно смело удалять большие куски кода и вносить значительные изменения, не волнуясь, что что-то сломаешь. Ведь всегда можно посмотреть на то, что было раньше. Также удобно использовать эту систему не только для своих больших проектов, но и для мелких наработок, вроде полезных скриптов, документации, тестов, демок и т.д.
Так как база данных SVN легко бекапится, то легко обеспечить сохранность всей своей интеллектуальной собственности, не боясь что твой хард диск полетит. Можно перенести все свои наработки на другую машину\платформу. Или выложить на сервер и иметь доступ к ним с любого другого места.

3. locate. Индексирует файловую систему и позволяет осуществлять быстрый поиск файлов в своей базе данных. Это очень удобно. В среднем на моих 500+ гигабайтах дискового пространства поиск конкретного файла занимает менее 1 секунды. Раньше пользовался для этих целей утилитой find, но locate позволяет сократить время на несколько порядков. Ну и find всё-таки довольно сложная утилита. Для простого поиска файла по имени надо написать find / -name 'blabla', куда лаконичнее писать locate 'blabla'

4. vixie-cron. Как я жил без шедулера раньше - не представляю. Теперь мой компьютер делает 80% рутинных действий за меня. Он и создаёт бекапы SVN репозитория с записью на болванки раз в 2 недели, и индексирует базу для locate каждый день в 12 часов ночи, и синхронизирует portage для gentoo каждое воскресенье. Вообщем, если у вас есть какой-то набор действий, которые вам надо повторять периодечески, лучше их прописать в крон и тем самым сэкономить своё время и силы.

5. gVim. vim, как оказалось, очень мощный и удобный редактор. Да, порог вхождения в него весьма высок. Сначала надо читать туториалы и мануалы, запоминать многочисленные клавиатурные комбинации. Но зато потом эффективность работы с текстом повышается на порядки. После vim`а работать в Microsoft Visual Studio это всё равно, что рубить деревья топором, после того, как ты это делал бензопилой.

6. bash, find, grep, sed, wget, etc. жизнь свою без этого уже не представляю. unix way работы с системой очень удобен и комфортен, особенно для программиста. Вместо того, что бы тыкать мышкой в ограниченное по функциональности гуи, я просто пишу то, что мне надо сделать и система это делает.

Шрифты

2008-02-19T00:36:00.000-08:00

Наткнулся на очень интересную статью Максима Шемарёва, автора замечательной библиотеки двухмерной растеризации antigrain.

В ней автор раскрывает вопросы различия субпиксельной растеризации шрифтов у MS, Apple и под линуксом.

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

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

У Apple дела обстоят получше. У них есть субпиксельная точность. Поэтому шрифты обладают масштабируются. Но они излишне размываются, что даёт некий дискомфорт.

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

Хотелось бы всё же, что бы MS встали на путь истинный и начали бы поддерживать нормальную масштабируемость шрифтов и элементов GUI. Но в висте пока этого нет
Если пипл хавает помои, то зачем его кормить деликатесами? Стандартный подход монополиста.

MotionX приготовление к релизу.

2008-02-12T02:37:00.000-08:00

Вообщем написание библиотеки MotionX на текущий момент закончено. Проект на sf.net зарегистрирован. В ближайшие выходные буду комментировать интерфейсы в формате doxygen и генерировать документацию. Настрою системы сборки, к текущей Scons добавлю CMake. Проведу серию тестов, что бы выявить стабильность системы, утечки памяти и прочие ошибки. И если всё будет благополучно, то выложу первый релиз на sf.net.

Кстати, оказалось, что xmmintrin.h это не только MS-specific, оно есть и под GCC на x86 платформе. А значит и под линуксом библиотека сможет использовать SSE.

Я вчера запустил анимацию 50 персонажей, с 50-ти костями на каждом. С SSE фпс было в районе 700, а без SSE - 30.
То есть SSE даёт, в моём случае, более чем двадцати кратное увеличение производительности! Я сам такого не ожидал.
Так что польза от этой технологии иногда может быть весьма ощутимой.
Хотя отключить применение SSE всегда можно флагами компиляции.

рефакторинг в motionx

2008-02-03T12:47:00.000-08:00

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

Было:

template<>
    motionx::FrameSetCPtr   Create<motionx::FrameSet>(const std::string& file)
    {
        motionx::FrameSetPtr    anim(new motionx::FrameSet);
        std::ifstream   in;
        in.open(file.c_str(), std::ios_base::in | std::ios_base::binary);

        if (io::get<int>(in) != anim_file_magic_number)
            throw   motionx::bad_resource("Wrong file type.", file);
        if (io::get<int>(in) != anim_file_version)
            throw   motionx::bad_resource("Wrong file version.", file);

        int frames_count = io::get<int>(in);
        int frame_size   = io::get<int>(in);

        for (int i = 0; i < frames_count; ++i)
        {
            float   time = io::get<float>(in);
            motionx::Frame  frame;
            frame.resize(frame_size);
            frame.Pivot = io::get<mtl::rigid_tm>(in);
            std::generate(frame.begin(), frame.end(), boost::bind(io::get<mtl::rigid_tm>, boost::ref(in)));
            anim->AddFrame(frame, time);
        }

        return  anim;
    }Syhi-подсветка кода

Стало:

Animation*  LoadBinaryAnimation(MotionXLib* lib, const char* filename)
    {            
        IFileSystem*   fs = lib->FileSystem();
        AutoFileHandle f = (fs->Open(filename, "r+b"), fs);
        if (!f)
        {
            OnError(IOError(filename));
            return;
        }

        size_t  fileSize = fs->Size(f);
        int magicNumber = 0;
        int version     = 0;
        fs->Read(f, (char*)&magicNumber, 4);
        fs->Read(f, (char*)&version, 4);

        if (magicNumber != anim_file_magic_number || version != anim_file_version)
        {
            OnError(BadResource(filename));
            return;
        }

        InplaceAnimation* animData = AllocateMemory(fileSize - 8);
        fs->Read(f, animData, fileSize - 8);
        return new Animation(animData);
    }Syhi-подсветка кода

В результате вместо N+1 аллокаций памяти на один файл анимации, получил всего лишь 2.
Где N - количество кадров. Учитывая то, что анимации могут занимать весьма ощутимое количество памяти, это неплохой выигрышь. Причём тут куда важнее не скорость загрузки, хотя и она сильно возрасла, а то, что память меньше фрагментируется таким образом.

топологическая сортировка

2008-01-07T18:40:00.000-08:00

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

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

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

Допустим есть следующие модули: filesystem, logging, render, audio, scene manager, game

filesystem не зависит ни от какого модуля
logging зависит от filesystem
render -> filesystem, logging
audio -> filesystem, logging
scene manager -> filesystem, logging, render, audio
game -> scene manager, filesystem, logging

Тут мы имеем сложный граф зависимостей. Который не является деревом. Этот граф надо преобразовать в список, проходя по которому можно будет последовательно запустить или остановить модули.
Например вот такой: filesystem -> logging -> audio -> render -> scene manager -> game
Хотя различных списков может быть много.
Также надо как-то проверять наличие циклов в графе зависимостей, иначе построить такой список будет невозможно.

Вообщем, я уже почти сам построил нужный алгоритм, как нашёл у себя в сундуке древний манускрипт, называется он "C++ Boost Graph Library", открыв его я узнал, что моя проблема является довольно тривиальной и очень общей. Мне просто надо пройти граф зависимостей по алгоритму depth first search, а построение списков зависимостей является, так называемой, топологической сортировкой. Ну в принципе я тоже самое и придумал, только не знал как называть.

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

#include    <iostream>
#include    <utility>
#include    <algorithm>
#include    <list>
#include    <vector>
#include    <boost/graph/vector_as_graph.hpp>
#include    <boost/graph/topological_sort.hpp>

using   namespace   boost;
int main()
{
    const char* modules[] = {
        "render",
        "filesystem",     
        "scene manager",
        "game",
        "audio",
        "physics"
    };
    const int nModules = sizeof(modules)/sizeof(char*);

    std::vector<std::list<int> >    modulesGraph(nModules);
    modulesGraph[0].push_back(1); // render -> filesystem

    modulesGraph[2].push_back(0); // scene manager -> render
    modulesGraph[2].push_back(1); // scene manager -> filesystem
    modulesGraph[2].push_back(4); // scene manager -> audio
    modulesGraph[2].push_back(5); // scene manager -> physics

    modulesGraph[3].push_back(2); // game -> scene manager
    modulesGraph[3].push_back(1); // game -> filesystem
    modulesGraph[3].push_back(0); // game -> render

    modulesGraph[4].push_back(1); // audio -> filesystem
    modulesGraph[5].push_back(1); // physics -> filesystem

    std::vector<int>    modulesOrder;
    topological_sort(modulesGraph, std::back_inserter(modulesOrder), vertex_index_map(identity_property_map()));

    for (std::vector<int>::iterator it = modulesOrder.begin(); it != modulesOrder.end(); ++it)
        std::cout << modules[*it] << std::endl;
    return  EXIT_SUCCESS;
}Syhi-подсветка кода

на выходе получим следующее:
filesystem
render
audio
physics
scene manager
game

XNE

2008-01-07T14:58:00.000-08:00

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

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

Проект будет кроссплатформенным, но без фанатизма. Пока ориентация только на POSIX и Windows. Графический API - OpenGL. Мультиапи не планируется.

Сейчас мне интересно, в первую очередь, разработка правильной фундаментальной архитектуры. Что такое правильная архитектура? Для меня такая архитектура должна быть простой и расширяемой. Что бы работа с системой не вызывала головной боли.
В качестве основы я взял паттерн microkernel.
Конечно там будут и layers, и subsystems, и pipes и много чего другого. Вообще хочу поэкспериментировать с паттернами. Но это уже будет в деталях. Сейчас пока сконцентрируюсь на построении модульной архитектуры с микроядром.

Так же вплотную займусь организацией проекта. Документация, системы сборки, вспомогательные утилиты, code standart и т.д. Это у меня слабое место. Из-за отсутствии чёткой организации всё никак не могу выпустить свою анимационную библиотеку. Надо практиковаться в этом.

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

Проект будет c открытыми исходниками, лицензия, скорее всего, BSD или другая либеральная. А может быть и GPL. Я пока не определился окончательно.

Называется он XNE, расшифровывается как "XNE is Not Engine". Люблю акронимы :)

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

раскодировка

2007-12-12T14:44:00.000-08:00

Допустим вам пришло сообщение "äîïóñòèì âàì ïğèøëî ñîîáùåíèå". И ваш зоркий глаз в нём сразу же увидел кодировку cp1251 набранную символами западноевропейской кодировки iso8859-9
Казалось бы дело за малым. Первое, что хочется сделать это скопировать текст сообщения в файл(жалко нет устройства /dev/clipboard) и выполнить над ним операцию iconv -f iso8859-9 -t cp1251.
Но почему-то iconv вежливо ругнётся, указав на ошибки в последовательности. Ну конечно же. Ведь тех символов, которые мы видим в сообщении, нет и в помине в кодировке cp1251.
Важно понять, iconv не делает текстовой конвертации, как это получается в редакторах или браузере при смене кодировки. Он делает бинарную конвертацию, оставляя сами симвы, меня лишь их двоичное представление.

В данном случае нам нужна двухступенчатая конвертация. Зашифрованное сообщение мы видим в системной кодировке(у меня это utf8). Из неё нужно получить двоичное представление в однобайтовой кодировке. Поэтому делаем iconv -f utf8 -t iso8859-9. Выход этой комнады и является исходным сообщением, но уже в кодировке cp1251. Которую мы преобразуем в системную, что бы увидеть текст.
Вся операция расшифровки будет выглядеть следующим образом:

echo äîïóñòèì âàì ïğèøëî ñîîáùåíèå | iconv -t iso8859-9 | iconv -f cp1251

password generator

2007-12-06T08:45:00.000-08:00

генерируем пароли подручными средствами в линуксе

tr -cd [:alnum:] < /dev/urandom | head -c16

на выходе получаем строки такого типа
LngOnPEW3zJbUCFD
Mtx5PGf923omiaUD
mq40bfdIdY23LihM

количество символов пароля определяется параметром в head

vim

2007-11-21T16:03:00.000-08:00

В последнее время пытаюсь освоить Vim. Редактор очень мощный и интересный. Прочитал кучу доков и мануалов и с нетерпением хочу начать его использовать... Но, к сожалению, наткнулся на одну проблему, которую решить не могу и которая нигде не описывается.
Мне не понятно, как в этом редакторе поменять текущий путь. !cd -- не помогает. shell/cd также не помогает. После выхода из командного режима путь остаётся прежним.
Обидно. Проблема настолько тривиальная, видимо, что никто не стал её описывать. А с этим ни программу сбилдить, ни теги построить, да и вообще работать нельзя.

Приходится пока оставаться в KDevelop

Деликатес

2007-11-16T06:47:00.000-08:00

Создал себе аккаунт на деликатесе - http://del.icio.us/cyberzx
Буду туда добавлять ссылки IT тематики. Удобная штука, как оказалось.

О кошерном

2007-11-05T05:20:00.000-08:00

* Messages for package sys-libs/glibc-2.6.1:

* You still haven't deleted //etc/locales.build.
* Do so now after making sure //etc/locale.gen is kosher.

Хаха. Юмор оценил :)

былое

2007-11-03T10:08:00.000-07:00

Вот разгребал я тут старые программы свои. Эдак готов 2002-2005го. На некоторый код смотрю и думаю: "OMG!!! Что за ламер писал такой ужасный код!?". На другие же программки наоборот вызывают мысль: "ну ничего себе, неужели это я такое сделал? круто!".
Ну это уже ближе к нашему времени.

Вообще полезно. Смотришь как ты рос в профессиональном плане, как менялись твои навыки, философия программирования и, даже, мировоззрение. Это очень полезно.

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

Реализация

2007-11-02T23:20:00.000-07:00

Вот написал реализации калькуляторов к прошлому посту.
на Хаскелле и на С

Сейчас ещё напишу его на питоне. Ну а потом, если будет настроение, сделаю это на С++ без буста. Хотя это мне не особо интересно, так как С++ мой родной язык.

upd:
http://pastebin.com/f2e155cae - программа на петоне.
http://pastebin.com/f356d13b0 - реализация на хаскелле от VoidEx. с использованием монад.

Об ассоциативностях

2007-11-02T11:50:00.000-07:00

Вообщем, почитал я немного Книгу Дракона. Думал, что это нечто страшное типа "Искусства Программирования" Кнута. Оказалось, что совсем не так, книга написа довольно внятным языком и легка для восприятия, жалею что раньше не прочитал её.

Я понял, почему мне так не удалось сходу написать калькулятор. Проблема, как я и думал, лежала в математической области. О ней и хочу поговорить. Но обо всём по порядку. Начну я с ассоциативности.

И так, что такое ассоциативность и зачем она нам нужна?

Пусть есть некоторая бинарная операция @
Значит некоторой сущности x мы можем поставить в соответсвие y @ z
x = y @ z

Но y и z сами могут быть результатами выполнения операции @.

y = a @ b

x = (a @ b) @ z

или

z = b @ c

x = y @ (b @ c)

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

Назовём операцию @ лево-ассоциативной, если запись a @ b @ c эквивалентна выражению (a @ b) @ c. Если же a @ b @ c эквивалентно выражению a @ (b @ c), то операция @ является право-ассоциативной.

Можно запомнить, что если оператор стоит слева от терминального операнда(того, который нельзя разбить на под-выражения), то операция — лево-ассоциативная, иначе она право-ассоциативная. То есть, с какой стороны операция прилепливается к терминальному операнду, такая и ассоциативность у неё.

Пример.
Во многих языках программирования операция присваивания является право-ассоциативной. То есть a = b = c => a = (b = c). Это вполне резонно, так как вычесление операндов идёт справа и в конечном итоге доходит до самого левого.

Но арифметические операции являются лево-ассоциативными.

a - b - c => (a - b) - c.

Тут вычесление идет начиная с самого левого операнда.

Перейдёт к собственно проблеме.

Вот как выглядят грамматики для выражений с операторами с разной ассоциативностью.

expr -> term op expr — право-ассоциативная операция

expr -> expr op term — лево-ассоциативная операция

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

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

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

Так что делать? Неужели для такой простой задачки, как разбор арифмитических выражений придётся писать сложный bottom-up парсер с бэктрейсингом? Ну уж нет. Я так просто не сдамся!

Тут нам на помощь приходит математика. Оказывается есть простой способ избавления от левой рекурсии путём добавления новых нетреминальных символов в грамматику.

Если есть грамматика вида

A -> Aa | Ab | c

то мы можем трансформировать её в грамматику с правой рекурсией

A -> cR

R -> aR | bR | eps

Вот пример:

expr -> expr + term |

expr - term |

term

заменяется на

expr -> term rest

rest -> +term rest |

-term rest |

eps

А эта грамматика очень легко парсится на predictive parser.

Ну и приведу полную грамматика для арифметических выражений.

expr -> term rest_e

rest_e -> (+ | -) term rest_e | eps

term -> factor rest_t

rest_t -> (* | / | ^) factor rest_t | eps

factor -> -factor | +factor | (expr) | function | number

function -> unary_func_name (expr) |

binary_func_name(expr, expr)

Очень маленькая, простенькая и без левых рекурсий!

Калькулятор на Хаскеле

2007-10-26T22:59:00.001-07:00

Решил в рамках укрепления навыков работы с Хаскеллем написать простенький калькулятор.
При этом без предаврительного лексического разбора и перевода в обратную польскую нотацию. Задача получилось интересной.
Но так я до конца её не решил, так как при таком подходе не получается сделать функции сложения и вычитания левоассоциативными. То есть выражение 1 - 3 +2 у меня считается как 1 - (3+2).
Что-то я туплю, знаю что решение есть у этой задачи. Но найти его не могу.

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

Вот код с грамматикой:


module Calculator where

-- epxression grammar 
--                        
-- expression  ::= <addsub_expr> | <muldiv_expr> | <term> 
-- addsub_expr ::= <term2> + <expression> | <term2> - <expression>
-- muldiv_expr ::= <term> * <term2> | <term> / <term2>
-- term2       ::= <muldiv_expr> | <term>
-- term        ::= -<term>  | (<expression>) | unary_func | binary_func | <number> | const
-- unary_func  ::= (ln | exp | sin | cos | ...) (<expression>)
-- binary_func ::= (pow| add | sub | mul | div | ...) (<expression>, <expression>)
-- const       :: = pi | e | ...


type ExprParser = String -> (Float, String, Bool)

-- external functions tables
unary_functions = [("ln",log), ("exp", exp), ("sin", sin), ("cos", cos), ("inc", (+) 1)]
binary_functions= [("pow", (**)), ("add", (+)), ("sub",(-)), ("mul", (*)), ("div",(/))]
constants      = [("pi", pi), ("e", exp 1)]

-- syntax parsers
expr            :: ExprParser
parentheses     :: ExprParser
number          :: ExprParser
muldiv_expr     :: ExprParser
addsub_expr     :: ExprParser
minus_term      :: ExprParser
term            :: ExprParser
term2           :: ExprParser
const_p         :: ExprParser
unary_func      :: ExprParser
binary_func     :: ExprParser

-- entry function
calc :: String -> Float

-- useful functions
find_table_element :: String -> [(String, a)] -> a -> (a, String, Bool)

failParse s = (0, s, False)
isSucceed (val, s, res) = res
getVal (val, s, res) = val
getEndStr (val, s, res) = s

check_str :: String -> String -> (Bool, String)
check_str [] s2 = (True, s2)
check_str s1 [] = (False, [])
check_str s1 s2 = if (head(s1) == head(s2) ) then check_str (tail s1) (tail s2)
                        else (False, s2)
                        
-- parsers selection
infixr 4 >|
(>|) :: ExprParser -> ExprParser -> ExprParser
(p1 >| p2) s = if isSucceed (p1 s) then p1 s else p2 s

------------------------------------------------------------
calc s = getVal (expr (filter (\x-> x /= ' ') s))

------------------------------------------------------------
expr s = (addsub_expr >| term2) s
                
------------------------------------------------------------
number s = case readsPrec 10 s of
                x:xs -> (fst x, snd x, True)
                [] -> failParse s

------------------------------------------------------------
parentheses s@(x:xs) = if (x /= '(') then failParse s
                       else case expr xs of
                        (_, fs, False) -> failParse fs
                        (val, xr:sr, True) -> if (xr == ')') then (val, sr, True) else error "parse error: incorent parentheses"
                        (_, [], _) -> error "parse error: expression parsing failed"                                                
                                
------------------------------------------------------------
minus_term s@(x:xs) = if (x == '-') then
                        if isSucceed (term xs) then
                            ((-1.0)*getVal(term xs), getEndStr(term xs), True)
                        else error ("parse error: expression parsing failed " ++ getEndStr(term xs))
                    else failParse s                           
                                                               
------------------------------------------------------------
term [] = failParse []
term s  = (minus_term >| parentheses >| unary_func >| binary_func >| number >| const_p) s
          
------------------------------------------------------------
term2 s = if isSucceed (muldiv_expr s) then muldiv_expr s
            else term s
        
------------------------------------------------------------
muldiv_expr s = let (v1, s1, r1) = term s
                    (v2, s2, r2) = term2 (drop 1 s1)
                in if r1 && r2 
                        then case head s1 of
                                '*' -> (v1*v2, s2, True)
                                '/' -> (v1/v2, s2, True)
                                otherwise -> failParse s1
                        else if r1 then failParse s2 else failParse s1
                        
------------------------------------------------------------               
addsub_expr s = let (v1, s1, r1) = term2 s
                    (v2, s2, r2) = expr (drop 1 s1)
                in if r1 && r2
                        then case head s1 of
                                '+' -> (v1 + v2, s2, True)
                                '-' -> (v1 - v2, s2, True)
                                otherwise -> failParse s1
                        else if r1 then failParse s2 else failParse s1
                        
------------------------------------------------------------
find_table_element s table df = let sl = map (\x -> (x, check_str (fst x) s)) table
                                    found = filter (fst.snd) sl
                                        in case found of
                                        [] -> (df, [], False)
                                        otherwise -> ((snd.fst.head) found, (snd.snd.head) found, True)
                                        
------------------------------------------------------------
const_p s = find_table_element s constants 0.0
                                        
------------------------------------------------------------
get_unary_func s = find_table_element s unary_functions (\_->0)
get_binary_func s = find_table_element s binary_functions (\_ _->0)
                                                                                        
------------------------------------------------------------                                                   
unary_func s = let (f, s1, r) = get_unary_func s
                   (var, s2, r2) = expr (drop 1 s1) 
                in if r && r2 && head s1 == '(' && head s2 == ')' 
                        then (f(var), drop 1 s2, True)
                        else failParse s1
                
                
binary_func s = let (f, s1, r) = get_binary_func s
                    (var1, s2, r2) = expr (drop 1 s1)
                    (var2, s3, r3) = expr (drop 1 s2) 
                in if r && r2 && r3 && head s1 == '(' && head s2 == ',' && head s3 == ')' 
                        then (f var1 var2, drop 1 s3, True)
                        else failParse s1

Intel STM

2007-10-19T04:21:00.000-07:00

Интересная новость. Интел разрабатывает С++ компилятор, который поддерживает технологию Software Transaction Memory(STM). Эта технология используется для синхронизации доступа к общей памяти конкурирующих задач без использования блокировок.
Что должно увеличить общую производительность параллельных программ и упростить их разработку.

Intel® C++ STM Compiler, Prototype Edition

linux shed

2007-10-10T05:28:00.000-07:00

Тут интересная статья с обзором патча реального времени для ядра Linux.

Хороший обзор устройства стандартного планировщика процессов в Linux.

Man страничка с описанием некоторых политик планирования задач в POSIX-системах. FIFO и RR политики, насколько я понимаю, являются стандартными, но мне кажется реально они редко используются. Надо бы провести на эту тему research.

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

Debating the Linux Process Scheduler - тоже может быть интересно.

Ну и до кучи What every programmer should know about memory via Семён

Кстати, интересно бы было посмотреть на алгоритм планирования задач в под windows. Но в гугле я что-то так ничего по этой теме не нашёл.

haskell monads

2007-10-08T09:02:00.000-07:00

Вот тут довольно интересная аналогия касательно монад в хаскелле. Монады представляются в виде сборочной линии.
Очень понятно описывается логика их работы и применения.

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

gcc defines

2007-09-28T08:02:00.000-07:00

Небольшой хинт. Для того, что бы посмотреть список всех внутрених дефайнов компилятора GCC, надо запустить следующую команду
gcc -dM -E - < /dev/null

ну или gcc -dM -E empty.c если в вашей системе нет устройства /dev/null

баг с поиском в VS2003/2005

2007-03-29T16:47:00.000-07:00

Если у кого-то сломался поиск в файлах в этих средах разработки. И на любой запрос студия выдаёт "No files were found to look in". То достаточно нажать ctrl + scroll lock, и поиск снова заработает.
Странно, что этот весьма известный баг перекочевал из 2003-ей студии в 2005-ую.
За столько лет могли бы и пофиксить.

memory

2007-01-01T21:43:00.000-08:00

Что-то меня CRT-шный аллокатор памяти совсем не устраивает по функциональности. _aligned_malloc/_alligned_free, которые мне так необходимы, не являются ANSI функциями. Стандартного способа узнать количества выделенного блока памяти не существует.
Слабенько как-то... Написать что ли свой?

ANSI C

2006-12-07T12:41:00.000-08:00

попытался написать конвертор мешей на ANSI C.
Такой извращёный язык! Я на нём совершенно не умею писать :(

dsound note

2006-11-20T06:51:00.000-08:00

Как менять громкость звука в DirectSound линейно, а не экспоненциально? Очень просто!

void SetVolume(double vol)
{
double dbVol = 20 * log10(clamp(vol, 1e-3f, 1.0f));
pSndBuffer->SetVolume(dbVol * 100);
}

Таким образом, меняя vol от 0 до 1, получаем линейное изменение громкости звука.

functional style

2006-11-09T13:14:00.000-08:00

Люблю функциональный стиль кода и рекурсию. Надоели мне for/while циклы. Ну их :)

Короче, вот как у меня создаётся гео-сфера. Всего несколько строчек кода.

//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
MeshCPtr SmoothGeoSphere(GLuint iter, MeshCPtr in)
{
if (!iter)
return in;
return SmoothGeoSpehre(--iter, SphereNormalize(Subdivide(in)));
}

//--------------------------------------------------------------------------------------
MeshCPtr CreateGeoSphere(GLuint iterations)
{
return SmoothGeoSphere(iterations, CreateIcosahedron());
}

MotionX release

2006-11-02T16:53:00.000-08:00

Вот и наступил момент, когда я вполне удовлетворен качеством библиотеки MotionX. Она опробывана, так сказать, в боевых условиях, то есть в коммерческом проекте. И все мелкие косяки и глюки, которые в ней были, я вроде устранил.
Библиотека обладает достаточной функциональностью, но пока не все, что я задумал, реализовано.
Но есть всё, что необходимо для внедрения в игру скелетной покадровой анимации, в том числе и экспортёр из 3dsmax.
Но главное - положить начало публичной жизни библиотеки, дальше будет проще. Я думаю.
Осталось написать небольшую демку c использыванием glut и sdl.
И написать туториал по экспорту анимации. И документацию...
Вот в этом вся проблема. Придется писать много текста на английском. А в этом я никогда не практиковался. Хотя читать могу абсолютно любые тексты.
Ну ладно. Главное начать, что-то делать в этом направлении. Возможно излагать свои мысли на английском не так уж и сложно, как это кажеться.

И еще надо определиться с выбором лицензии. Сначала подумывал об LGPL, но слишком уж сильные ограничения она накладывает. Не хочу никого ни в чём ограничивать. Надо что-нибудь либеральнее.

floating point

2006-10-31T09:30:00.000-08:00

Думаю написать статью по теме работы с floating point числами в графических и физических real-time приложениях.
Из чего должна состоять статья? Вот набросал несколько пунктов.

- Краткое описание формата чисел с плавающей точкой стандарта IEEE 754
- Погрешности. какие бывают и как их расчитывать.
- Расчёт погрешностей для базовых математических операций. Сложения, вычитания, умножения и деления.
- Расчёт погрешностей для векторных операций. Сложение, вычитание векторов. Нормализация. Матричное перемножение(в том числе и умножение матрицы на вектор).
- Стабильность по численным погрешностям некоторых алгоритмов. Пока в голову пришли алгоритмы интегрирования. Вот думаю, для каких алгоритмов еще надо провести research?

Вот пока всё.
Но гложет меня сомнения о нужности подобной статьи. Может быть таких уже десятки и я их пропустил? Не хотелось бы заниматься ненужной работой.

upd:
сюда буду добавлять линки на статьи, по данной тематике которые мне удалось найти.

What Every Computer Scientist Should Know About Floating-Point Arithmetic

gDEBugger

2006-10-30T16:43:00.000-08:00

Помоему это ужасная не справедливость. То что под проприетарный D3DX есть такие удобные и бесплатные утилиты для отладки как NVPerfHUD. А для свободного OpenGL мы имеем в наличии лишь корявенький и платный gDEBugger. Причем NV распространяет его со своим SDK, что значит не стоит надеятся на выход аналогичной NVPerfHUD утилиты для OGL.
Это ли не саботаж разработчиков на OGL? Ну что стоит NV выпустить удобную и бесплатную утилиту для отладки OGL графики?

MotionX

2006-08-27T14:03:00.000-07:00

За две недели полностью, то есть абсолютно с нуля переписал свою систему анимации. Очень долго выбирал как называть библиотеку. Решил не оригинальничать и назвал ее MotionX :)

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

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

- Есть возможность анимировать разные части скелета персонажа в разных потоках. Например на ногах у нас стоит walk, а для верхней части туловища можно переключать различные анимации(attack, shoot, walk и т.д.). Ну и вообще дает большую гибкость в анимировании объектов.

- Модульная архитектура библиотеки. Помимо покадрового контролёра, можно подлючать другие контроллёры управления положением объектов. Например всё возможные варианты инвресной кинематики. Правда я пока не реализовал ни одного IK контролёра, но добавить их можно очень просто.

- Легкость в сериализации. Описание контроллёров, списки анимаций и связи между ними(время блендинга) находятся в xml файлах. Сами кейфреймовые анимации лежат в бинарном представлении. Есть экспортёр анимации из 3дмакса. Планирую написать экспорт из коллады. Таким образом можно будет охватить и Маю и XSI и другие пакеты моделирования.

- Мультиплатформенность. Библиотека компилируется под vc7.1, vc8.0 и gcc3.4 другие компиляторы пока не тестировал. Привязка к ОС или графическому API отсутсвует. Библиотеку тестировал под линуксом всё работает как надо. Если надо будет сделать поддержку других платформ, то займусь и этим.

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

Через пару недель планирую все это дело выложить на sourceforge. Лицензию пока не выбрал, но вряд ли это будет GPL. Выберу что-нибудь по-мягче.

Lua

2006-06-07T21:44:00.000-07:00

Уф... похоже битва с Lua и luabind закончилась моей победой.
Сначала я сбилдил lua.lib через msys, просто под mingw. Но в таком варианте там тольео билдинг dll, что вообщем-то мне не надо, не хочу плодить дллки. Тогда сбилдил либу вроде под posix, получил заветный liblua.a, переименовал её в lua.lib и подключил к своему проекту.
Вот зачто я испытываю нежные чувства к языку Си, являясь адептом С++, так за то, что можно сбилдить либу на одном компиляторе, а слинковать совсем на другом. Главное что бы формат объектников совпадал, к счатью и mingw и vc используют coff формат, во всём остальном ABI у них идентичный.
Всё было бы замечательно, если бы не одно но. В отладочной конфигурации у меня проект собирался без проблем и луа работала как надо. Но стоило сбилдить его в релизе, как начинались непонятные глюки. Линкер ругался, что отсутсвуют функции из lua.lib, причем имена функций начинались без подчеркиваний, что не соответсвует cdecl конвенции. Я так не разобрался, что это значит, но по-моему, такие имена у функций в либах, которые указывают на dll. Потом к ним прибавляется префкис __imp_. Так вот, как бы я не менял конфигурации проекта, сколько бы не копался в его настройках, но в релизе из под студии линковаться он у меня отказывался. При этом у меня вместо экзешника появлялись .lib и .exp файлы. Откуда? Я так и не понял.
Удивительнее всего оказалось то, что билдинг релиза используя boost.build работал без проблем. Чудеса да и только.
Совсем отчаявшись, я подумал что придется руками собирать библиотеку Луа в студии. Но вместо этого скомпилировал её в ansi конфигурации. И в моём проекта она вполне корректно слинковалась! Видимо я напоролся на какой-то баг линкера, который присутсвует как в VC7.1, так и в VC8.0.

С компиляцией lualib у меня проблем тоже вроде не было. Хоть это и С++ библиотека, но она использует boost.build для сблорки, а я с ним вполне так дружу :). Слинковалась библиотека с моим проектом тоже без проблем. Но вот работать отказывалась. Падала с совсем непонятными ошибками, в совершенно неожиданных местах. То есть там, где по логике вообще падать не должно. И еще все тесты оказались проваленными.
Тут я тоже промучался несколько часов, пока не заметил, что у меня путь к бусту в project-root.jam прописан не совсем правильно. У меня использывался буст из CVS репозитория, а он там очень корявый лежит. Исправил проблему, прописав путь к дистрибутиву 1.33.1 и всё заработало. Хотя под vc8.0 несколько тестов всё же провалилось, а в vc7.1 все прошли успешно. Странно как-то.
Кстати, версия luabind из sourceforge не работает с последней версией lua5.1, надо забирать luabind из CVS. Тоже весьма неприятный момент.

Но к счастью, весь этот секс остался позади. И теперь у меня открылись новые архитектурные возможности. Например используя скрипты будет проще наладить взаимодействие между потоком, обрабатывающим GUI и основным потоком приложения. Так как задавать отложенные скрипты всё же лаконичнее, чем задавать отложенные функции. Хотя второе и удобно благодоря boost::lambda, но всё же С++, к сожалению, не функциональный язык и boost::lambda не может придать ему всех свойств ФЯ.

Проблемы с WTL

2006-05-07T05:39:00.000-07:00

Поставил сегодня себе Visual C++ Express Edition и Microsoft Platform SDK. Думал что мой проект скомпилируется без проблем. Ха! Наивный.
Проблема в том, что мой проект использует WTL 7.5, он конечно же лежит отдельно и не входит в Platform SDK. Но требует наличия файла atlbase.h, который уже являются частью Platform SDK.
Все было бы хорошо, но atlbase.h инклюдит файл shlwapi.h, которого у меня в наличии не оказалось.
После блужданий по сети, я нашел информацию о том, что этот файл появится после установки компонента Microsoft Web Workshop(IE) SDK.
Какая логическая связь между этим компонентом и ATL я так и не понял. Ну ладно, поставил его, у меня появился shlwapi.h.
Все было бы хорошо, но у меня появилась новая проблема. При линковке проект требует библиотеку atlthunk.lib, которой опять же не оказалось в Platform SDK.

Опять поиск в сети очень помог мне. Оказалось что PSDK не поддерживает 32-ух битные ATL библиотеки. Только 64-ех битные. А что бы иметь доступ к первой надо перейти на полную платную версию Visual Studio... ну или просто закоментировать #pragma comment(lib, "atlthunk.lib") в файле atlbase.h. Я выбрал второй вариант.
Еще хотелось бы заметить, что WTL под vc8.0 не компилируется, из-за использывании не совместимых со стандартом С++ приемов. В файле atlwin.h на 1753-ей строчке используется не объявленная переменная в качестве счетчика цикла. Всё же VC6.0 очень развращает людей.

С++ жив!

2006-04-12T15:35:00.000-07:00

Наконец-то руки дошли до boost::multi_index. Очень красивая концепция и замечательная реализация. Одна из самых красивых вещей в бусте. А почему? Да потому что стиль программирования контейнеров объектов, с различными отношениями порядка, похож на стиль программирования динамических систем в моей DSP библиотечке :) Даже идею с метками использовали.
Вообще не перестаю удивляться мощности языка С++, а в особенности, его возможностей в области метапрограммирования.

На форуме программистов на КРИ звучали мнения о том что С++ язык неудобный, сложный и неповоротливый, что лучше переходить на С#, Java, Дельфи и прочие гадости. В тоже время те самые люди плевались в сторону буста, шаблонов и вообще modern C++ programming. Странные какие. Конечно, если не использовать одну из самых сильных сторон языка, он не будет очень удобен.

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

Будни разработчика

2006-02-14T16:05:00.000-08:00

Будни разработчика