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

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

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

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

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

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

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

Тема конечно не новая, но просто стало интересно. Ввёл вот эту комманду в директории с исходниками линукса
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

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

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

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

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 работы с системой очень удобен и комфортен, особенно для программиста. Вместо того, что бы тыкать мышкой в ограниченное по функциональности гуи, я просто пишу то, что мне надо сделать и система это делает.

Шрифты

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

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

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

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

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

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

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

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

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

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

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

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

Продолжаю делать мощный рефакторинг в библиотеке 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 - количество кадров. Учитывая то, что анимации могут занимать весьма ощутимое количество памяти, это неплохой выигрышь. Причём тут куда важнее не скорость загрузки, хотя и она сильно возрасла, а то, что память меньше фрагментируется таким образом.

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

Недавно передо мной встала интересная алгоритмическая проблема.
Как я уже говорил, движок 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

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

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

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

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

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

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

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

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

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

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

Допустим вам пришло сообщение "äîïóñòèì âàì ïğèøëî ñîîáùåíèå". И ваш зоркий глаз в нём сразу же увидел кодировку 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

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

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

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

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

vim

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

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

Деликатес

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

О кошерном

* 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.

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

былое

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

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

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

Реализация

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

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

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

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

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

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

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

Пусть есть некоторая бинарная операция @
Значит некоторой сущности 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)

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

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

Решил в рамках укрепления навыков работы с Хаскеллем написать простенький калькулятор.
При этом без предаврительного лексического разбора и перевода в обратную польскую нотацию. Задача получилось интересной.
Но так я до конца её не решил, так как при таком подходе не получается сделать функции сложения и вычитания левоассоциативными. То есть выражение 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

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

Intel® C++ STM Compiler, Prototype Edition