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

linux shed

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

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

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

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

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

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

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

haskell monads

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

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

gcc defines

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

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

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

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

memory

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

ANSI C

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

dsound note

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

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

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

functional style

Люблю функциональный стиль кода и рекурсию. Надоели мне 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

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

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

floating point

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

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

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

---

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

What Every Computer Scientist Should Know About Floating-Point Arithmetic

gDEBugger

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