If a C programmer asks "do you want to see something cool?", run away.
--John Van Enk

Tuesday, July 31, 2007

Процесс разработки как он есть

Нашел картинку, которую когда то давным -давно встретил в одной из книг. Все это конечно весело если бы не было так жизненно ;-).

Живность в коде. Часть 1. Генетические алгоритмы

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

Задача кодируется таким образом, чтобы ее решение могло быть представлено в виде вектора - хромосомы. Хромосома зачастую называется особью. Ее приспособленность (верность решения задачи закодированного в особи) оценивается при помощи целевой функции. Затем случайным образом создается начальная популяция - набор таких хромосом. Работа генетического алгоритма состоит в следующем:
  1. Селекция - выбираются особи для "производства потомства" (выборка может осуществляться различными способами, например случайным или выборка особей с приспособленностью не ниже заданной) - обычно две особи (хромосомы) но может быть и больше
  2. Между особями производится "скрещивание" - генетический оператор кроссовера, который состоит в следующем - вектора "разрезаются" а затем их части меняются местами. К стати сказать, это простейший вид оператора кроссовера - есть еще двухточечный кроссовер - когда "рассечение" особей происходит двумя сечениями, и другие
  3. Затем производится с определенной вероятностью мутация получившихся особей - в простейшем случае - инверсия случайного бита (гена) в хромосоме
  4. Также может применяться генетический оператор (опять таки с определенной вероятностью) "инверсия" - это когда хромосома рассекается и начальная часть с конечной меняются местами (есть и более сложные варианты) - хотя в принципе этот оператор можно считать разновидностью мутации
  5. Также можно вводить свои какие-либо генетические операторы, если оптимизируемая функция слишком сложна, но это больше поле для экспериментов
  6. Далее вычисляется приспособленность получившихся особей/особи - и если она выше наименее приспособленной особи в популяции то последняя заменяется на получившуюся (опять таки это всего лишь один из вариантов)
  7. Таким образом моделируется эволюционный процесс, который продолжается до тех пор, пока не будет найден глобальное, либо субоптимальное решение, либо пока не сменится несколько поколений (смена одного поколения - некий процент новых особей заменил старых особей), либо пока не будет выполнено определенное количество итераций алгоритма
Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. И, надо признаться, с этой задачей они довольно хорошо справляются.
В заключение хочу привести ссылку на библиотеку - реализацию генетических алгоритмов на С++, которой я пользовался и которая, на мой взгляд, довольно удачно и грамотно спроектирована. Это библиотека GAlib, изначально написанная Matthew Wall при финансировании MIT, сейчас распространяется под BSD like лицензией и поддерживается автором. Недавно к стати вышел очередной релиз.

IT Doesn't Matter

Статья Николаса Дж. Карра "IT Doesn't Matter", опубликованная в майском выпуске Harvard Business Review 2003 года вызвала бурную волну откликов и обсуждений (некоторые можно почитать на сайте автора, еще есть реакция Steve Ballmer и Carly Fiorina - HP CEO), что сподвигло его на написание книги "Does IT Matter? Information Tehnology and the Corrosion of Competitive Advantage" (в русском переводе Николас Дж. Карр "Блеск и нищета информационных технологий").

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

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

Там еще много каких мыслей умных и интересных - почитать определенно стоит, особенно менеджерам.

Monday, July 30, 2007

Books on Algorithms

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

Jorg Arndt "Algorithms for Programmers. Ideas and source code" - еще не вышедшая книга на английском, выход запланирован на 2008 год, драфт пока что есть в свободном доступе



Однако надо признаться, что ни одну из этих книг я не прочел, а пользовался ими как справочниками, когда возникала такая необходимость ;-)

Манифест Хакера

Оригинальный текст был опубликован в 7-ом номере электронного журнала Phrack. Перевод на русский можно почитать здесь. Да. к чему это я все? Свобода информации, как говорится.
Upd: Манифест Хакера в формате mp3 можно скачать здесь.

Алгоритм управления памятью TLSF

Опубликован перевод описания алгоритма управления памятью TLSF с эффективностью O(1). Кроме того, существует сайт, посвященный explicit dynamic storage allocation, на котором помимо TLSF представлен еще ряд аллокаторов для real-time систем. Надо будет предложить попробовать различные аллокаторы, указанные на этом сайте, в следующем проекте, а заодно можно будет и оценить их эффективность на реальном железе. Если дело выгорит, то с меня отчет ;-)

Friday, July 27, 2007

The Battle with RegExpr

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

Thursday, July 26, 2007

Анатомия ядра Linux

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

Wednesday, July 25, 2007

Flex & Bison C++ Interoperability Continued

Итак, возвращаясь к когда-то написанному мной введению об interoperability лексических анализаторов на С++, сгенерированных при помощи Flex, и синтаксических анализаторов, сгенерированных при помощи Bison, в этой статье хочу разобрать простенький примерчик в котором лексический анализатор (далее лексер) распознает строки комментариев командного интерпретатора bash и пустые строки и пропускает их, а все остальные возвращает синтаксическому анализатору (далее парсеру) для последующего вывода в командную строку. Сначала я приведу код, а затем уж постараюсь объяснить по возможности что какая строчка значит, ну и соответственно команды которые необходимы чтобы это все собрать в кучу.

Файл intertest.cpp

#include <fstream>
#include "lexer.h"
#include "parser.h"
using namespace std;
using namespace test;
int main(int argc, char *argv[])
{
    ifstream infile(argv[1]);
    Lexer lexer(&infile);
    Parser parser(lexer);
    return parser.parse();
}

Тут я думаю обьяснения излишни ;-)

Файл lexer.h

#ifndef _LEXER_H
#define _LEXER_H

#ifndef __FLEX_LEXER_H
#undef yyFlexLexer
#include <FlexLexer.h>
#endif
#include <stdexcept>
#include "parser.h"
namespace test{
class Lexer: public yyFlexLexer {
    //tokenizer
    int yylex();
public:

    //ctor
    Lexer( std::istream* src = 0 );

    //dtor
    virtual ~Lexer();

    //functor
    Parser::token_type operator() ( Parser::semantic_type* lval, Parser::location_type* lloc = 0 );

    //error report routine
    virtual void LexerError( const char* msg );

private:

    Parser::semantic_type* yylval;
};
}
#endif

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

#ifndef __FLEX_LEXER_H
#undef yyFlexLexer
#include <FlexLexer.h>
#endif

По поводу перегрузки operator() подробно также можно почитать там же.

Файл lexer.lpp

%option 8bit
%option noyywrap
%option c++
%option yyclass="test::Lexer"
%option pointer
%option nodefault
string [^#\n]+\n
garbage .*\n
%{
#include "lexer.h"
#include "parser.h"
%}
%%
{string} {
      yylval->str=yytext;
      return Parser::token::STRING;
}
{garbage} //skip all other
%%
namespace test{

//ctor
Lexer::Lexer( std::istream* src ): yyFlexLexer( src, 0 ){}

//dtor
Lexer::~Lexer( ){};

//error report routine

void Lexer::LexerError( const char* msg ) {
    throw std::runtime_error( msg );
}

//function call operator overloading 
Parser::token_type Lexer::operator() ( Parser::semantic_type* lval, Parser::location_type* lloc ) {
    yylval = lval;
    return Parser::token_type( yylex() );
}
}

%option 8bit - использовать 8 битную кодировку символов

%option noyywrap - yywrap() - функция которая вызывается по достижению конца файла, ее можно использовать для того чтобы открыть новый файл и продолжить сканировать его (в этом случае функция возвращает 0). Поскольку нам это не нужно, то используя эту опцию указываем что yywrap всегда возвращает 1 - сканирование завершено

%option c++ - генерировать код на С++

%option yyclass="test::Lexer" - сгенерировать реалзацию функции yylex(), осуществляющей сканирование для класса Lexer, унаследованного от yyFlexLexer и находящегося в пространстве имен test, это необходимо для того, чтобы в теле правил flex файла были доступны указатели на переменные, передаваемые парсером в лексер при вызове последнего для получения следующего токена

%option pointer - опция, контролирующая каким образом определен yytext, - как указатель на распознанную строку или как статический буфер, содержащий ее копию. Нам нужен указатель, потому на всякий случай указываем ее.

%option nodefault - по умолчанию весь ввод который не может быть распознан лексером вываливается в консоль, нам этого behaviour не нужно, говорим об этом flex'у

string [^#\n]+\n - регулярное выражение для строки - строка это все что угодно кроме символов '#' и '\n' встречающееся в тексте более одного раза и заканчивающееся символом '\n'

garbage .*\n - выражение для "мусора" - т.е. всего что не подходит под определение строки

Далее включаем заголовочные файлы лексера и парсера. Файл парсера нужен для констант токенов, которые в нем определены.
%{
#include "lexer.h"
#include "parser.h"
%}

Далее начинается секция правил flex'а
%%

Следующее правило служит для распознавания строки. Поскольку оба правила могут распознать одну и ту же строку, то указываем именно правило для string первым поскольку при разрешении таких неоднозначностей flex использует первое в списке правил для обработки ввода (first rule match).
{string} {
    yylval->str=yytext; //копируем
    return Parser::token::STRING;
}

{garbage} //все что не нужно пропускаем 
//(т.е. не делаем return)


Далее идет секция кода
%%
В ней размещаем реализацию методов класса Lexer.

Файл parser.ypp

%skeleton "lalr1.cc"
%parse-param {test::Lexer& yylex}
%define "parser_class_name" "Parser"
%name-prefix="test"
/*
 *   Секция кода
 */
%{
/*
 *   Этот код (находящийся перед директивой %union)
 *   будет включен в сгенерированный bison'ом 
 *   заголовочный файл ДО ОПРЕДЕЛЕНИЯ КЛАССА 
 *   СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА Parser
 */
namespace test{
class Lexer;
}
%}
%union {
      char* str;
}
%{
/*
 *   Этот код (находящийся после директивы %union)
 *   будет включен в сгенерированный файл парсера 
 *   (синтаксического анализатора)
 *   (parser.cс например)
 */
#include "lexer.h"
#include <cstdio>
#include <stdexcept>
%}
%token <str> STRING
%start file
%%
/*
 *  Grammar rules follow
 */
file    :
      | file STRING   { printf("%s",$2);}
      ;
%%
void test::Parser::error (const location_type& loc, const std::string& msg){
    throw std::runtime_error(msg);
};

%skeleton "lalr1.cc" - используем шаблон для генерации кода парсера на С++

%parse-param {test::Lexer& yylex} - указываем что конструктор сгенерированного парсера должен принимать аргумент - ссылку на лексер

%define "parser_class_name" "Parser" - указываем что сгенерированный bison'ом класс парсера должен называться Parser

%name-prefix="test" - указываем что пространство имен в котором находится сгенерированный bison'ом класс будет называться test

namespace test{
class Lexer;
}
- объявляем класс Lexer, потому как оба класса (Lexer и Parser) зависят друг от друга - Lexer использует типы определенные в Parser а конструктор Parser принимает ссылку на Lexer в качестве аргумента.

%union {
char* str;
}
Директива %union используется для следующей цели:
иногда бывает необходимо возвратить из лексического анализатора в синтаксический кроме константы, определяющей токен (лексическую единицу) еще и значение связанное с этим токеном (например если в тексте встретилось 8536 то лексический анализатор возвращает токен INTEGER (целочисленная константа) а само значение присваивается переменной, имеющей тип Parser::semantic_type* var , следующим образом:
var->integer=atoi(yytext));

При этом в файле Bison директива %union выглядит следующим образом

%union{
int integer;
}


Указатель на переменную типа Parser::semantic_type передается парсером лексеру при вызове последнего для получения следующего токена затем в теле правила это значение может быть получено путем использования следующей конструкции: $номер_элемента_правила

%{
/*
*   Этот код (находящийся после директивы %union)
*   будет включен в сгенерированный файл парсера 
*   (синтаксического анализатора)
*   (parser.cс например)
*/
#include "lexer.h"
#include <cstdio>
#include <stdexcept>
%}
- в сгенерированном файле реализации парсера (например parser.cc) интерфейс класса Lexer уже должен быть известен, поэтому включаем его заголовочник.

%token <str> STRING - объявление токена конструкция в угловых скобках указывает на то, что с этим токеном связано значение и что оно хранится в поле str union'a

%start file - объявляем стартовое правило

file    :
      | file STRING   { printf("%s",$2);}
      ;

правило определяющее что из себя представляет файл - это набор из 0 или более токенов STRING. Правила записываются в расширенной форме нотации Бэкуса - Наура (Enhanced Backus Naur Form - EBNF).
Конструкция в теле правила $2 - это обращение к значению токена STRING (тому самому которое хранится внутри union)

Далее следует секция кода, в которую можно поместить различные функции - я разместил в ней реализацию метода error класса Parser, которую и так надо писать самому.

Теперь собираем все в кучу:

$flex -olexer.cpp lexer.lpp
$bison --defines=parser.h -oparser.cpp parser.ypp
$g++ intertest.cpp parser.cpp lexer.cpp -o test

Проверим на следующем файле

#!/bin/bash
#comment

ls -l

#another comment

ps


Результат работы программы

commander@a64:~/work/src/test$ ./test test.bash
ls -l
ps


Фуф! Вот кажись и все ;-). Have fun!

Tuesday, July 24, 2007

Linux Kernel Vitualization

Грядущий релиз ядра Linux 2.6.23 готовит новые вкусности - согласно KernelTrap, средства виртуализации Xen и lguest включены в основное ядро. Перед этим та же участь постигла KVM, предоставляющий возможность запускать несколько виртуальных машин, каждая со своей ОС

Wednesday, July 18, 2007

Moblin

Сотрудничество Intel с Canonical Ltd и Red Flag Linux вылилось в проект Mobile & Internet Linux Project, являющийся проектом по созданию программной начинки с открытым исходным кодом для Intel Mobile Internet Devices на базе Linux. На страничке проектов уже представлен предварительный ряд решений. Что же, позиции Linux в качестве mobile & embeded platform все упрочняются по мере adoption by leading manufacurers.

Инициализация структур

В стандарте С99 (6.7.8) есть интересная вещь - так называемые designators (обозначения?). Их использование позволяет инициализировать элементы структур при помощи списка инициализации не обращая внимания на порядок следования элементов. Например

struct StTest {
int i;
char c;
double d;
};

int main(int argc, char *argv[])
{
struct StTest st1={.d=0.1, .i=1, .c='a'},
st2={.c='b',.d=0.2,.i=2};
printf("st1.i= %d st1.c= %c st1.d= %f\n",st1.i,st1.c,st1.d);
printf("st2.i= %d st2.c= %c st2.d= %f\n",st2.i,st2.c,st2.d);
return EXIT_SUCCESS;
}

А вот собственно и результат работы такой програмки

commander@a64:$ ./teststructinit
st1.i= 1 st1.c= a st1.d= 0.100000
st2.i= 2 st2.c= b st2.d= 0.200000

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

Tuesday, July 17, 2007

C vs. C++

На днях задался философским вопросом: если С++ лучше С, то почему ядра многих операционных систем (BSD, Linux, Windows?) написаны на С? На мой взгляд С++ довольно сложный и многообразный язык, и богатство его возможностей в данном случае только мешает, а не помогает, поскольку перед разработчиком встает проблема выбора. В то же время, чтобы выучить С достаточно книги Кернигана и Ричи, простой, лаконичный, и разработчик вместо того чтобы решать проблему выбора, занимается решением поставленной задачи. С позволяет сконцентрироваться на решении прикладной задачи, а не углубляться в архитектуру. Это все конечно же ИМХО и на истину в конечной инстанции не претендую, вполне возможно что ядра пишут на С по историческим причинам, и чтоб не сломать уже созданную кодовую базу.

Monday, July 16, 2007

Amaya - web browser from W3C

W3C видимо надоело бороться с наличием множества глюков в различных веб браузерах, посему было создано чудо, и имя ему нарекли Amaya. Что характерно - acid2 test он валит. Версия 9.55 от 10 июля 2007 года. Впечатления, мягко скажем, отрицательные. При этом натравив W3C QA Markup Validation Service на страницу acid 2 test можно убедится что код валидный. Посему возникает вопрос - зачем?

Friday, July 13, 2007

Ride The Tide

На мой взгляд сейчас в созревшем состоянии находят два очередных бума в сфере IT - это web services и mobile devices (в широком понимании этого слова). Скорее всего два этих явления будут дополнять друг друга. Самое время задаться вопросом "What to do to Ride the Tide?", как это в свое время сделали в SUN, когда решили что нужно что-то делать и сделали Java. И в заключение несколько ссылок:
Silicon Valley's next boom
ID theft: The next IT industry boom?
2001: A Perfect Time To Learn New Technology And Catch The Next Boom

Thursday, July 12, 2007

Linux Mobile

Речь опять пойдет про ubiquitous computing. Linux все более активно позиционируется как платформа для мобильных устройств. Вот, например, какой девайс соорудили в рамках проекта OpenMoko:

neo1973neo1973 board

Довольно подробный обзор можно почитать на LinuxDevices.com. Кроме того данное событие довольно активно освещается различными ресурсами, ссылки на которые можно найти на сайте OpenMoko. Ну скажите, чем это не альтернатива Apple iPhone? Девайс можно купить онлайн. Существует он в двух редакциях Neo Base и Neo Advanced. Advanced от Base отличается наличием дополнительных аксессуаров for mobile device hacker.

Tuesday, July 10, 2007

Google Translate

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