the written word remains

...these guys!!! Tough play, steel nerves and luck - they demonstrated everything today :) I'm proud!

By the way, this is IIRC the best result ex-USSR football team ever showed since 1970 when USSR entered the quarterfinals. Hurray to our team!!!

Today Ukrainian football team finally fulfilled my expectations! They will be playing in 1/8 final! They did it not without trouble especially thanks to Trabelsi from Tunisia's team. Even his name reminds of troubles ;) He was the best player today probably.

Now that was the real football game. 4:0 is what I wanted to see from Ukrainians today and they did it :) Keep going! Let us enjoy our first world championship!

It does look like I've finally reached the state where my job became my passion. You doubt it's possible? I have a counter-evidence :)

From this very moment Pluron company is starting sponsoring me to work on KDevelop. I'm allowed now to spend part of my work time on KDevelop! That's so increadibly cool! We'll make the announcement soon, but I can't wait to tell about that ;)

In Pluron we develop Ruby/Rails project and of course use KDevelop as our IDE, so my primary target would probably be to make KDevelop4 shine as a Ruby IDE but of course I'll continue my work on UI and other things. This is a good chance to make all the difference ;)

Thanks to Pluron and special thanks to Gleb Arshinov, company founder and great open source supporter who made this possible!

PS: this is a shameless plug, but if you live in Ukraine, passionate about open source, ruby and/or ruby on rails or just look for a cool place to work, consider joining us ;)

Today promised to be a good day but to my surprise it was not. Oh! Ukrainian football team did not make this day any better too. Catastrophic gameplay plus one unfair penalty made them lose with an awful score! Ok, they will have at least two another opportunities to win ;)

I hope people are not yet bored with my Ruby blog posts ;) It's just so cool to get into the new environment that makes you care about things you've never cared before. Ruby was definitely something I knew about but never enjoyed as much as I do now. Same applies to my new Ruby/Rails job. I don't think I would read a vendor branches chapter from the svn book without it :) Of course, the chapter is only the example, there were (and are) more interesting things ;)

I started to write long posts not so long time ago, so let me keep this tradition and mention my search for elegant LALR grammar for lists of nested lists.

Let's say we need to parse token stream:

BBABBBABB

as the list of two items with one nested list inside. The ideal result would look like

(B (BAB) B) (B (BAB) B).

The grammar that comes to mind is:

list: item
    | item list
    ;

item: B list B
    | A
    ;

This grammar is ambiguous and has one shift-reduce conflict (it's not clear whether we shall reduce finishing the list or shift starting it). All LALR parser generators would resolve the conflict to shift over reduce and would in fact make our parser fail. So we need to say "prefer reduce". I have several solutions but the cleanest (from the parser's viewpoint) is to add an artificial terminal, say X, denoting the beginning of the list. The grammar

list: item
    | item list
    ;

item: X B list B
    | A
    ;

has no conflicts at all. This solution is good for parser but hacky for lexer which has to supply this fake terminal;) Well, I'm sure there are better solutions but I'm completely missing them today.

Addon: of course, if we allow to modify the lexer, something like

list: item
    | item list
    ;

item: B_START list B_END
    | A
    ;

would be even better.

As work on my ruby-based wiki parser continues, I started to have more and more fun with it. Today I travailed, trying to get RACC to fit my needs and discovered lots of interesting things about it. If you don't know the RACC - this is YACC for ruby (but without Lex/Flex companion ;) to make you get more fun while you write hand-made lexer).

Some time ago I discovered that RACC has one trouble. When a rule has a code block executed before entering the rule, usual numbering for ''val'' array becomes broken.

For example, if we have a rule:

foo: moo boo
     { result = val[0] + val[1] }
     ;

The result of the rule is computed by calculation of a sum of right part nonterminal's return values.

But if we use the rule like this:

foo:
     { result = "I break " }
     moo boo
     { result = val[1] + val[2] }
     ;

then we suddenly break ''val'' numbering scheme. Instead of ''val[0]'' and ''val[1]'' we should reference nonterminal's return values using ''val[1]'' and ''val[2]''. Apparently the code block before nonterminals breaks. Not a grave bug... but costed me several minutes to get an idea of what is happening.

But today I glanced over racc output file and was stunned! RACC effectively considers:

 foo: {} moo boo ;

as

foo: _nonterminal_ moo boo;

and adds extra rule that breaks not only val[] numbering ;)

Example 1:
 a: {} a B
     | A
     |
     ;
Example 2:
 a: a B
     | A
     |
     ;

I implemented two examples (first is broken and second is ok) and studied them. I found that the source of the problem was that for {} a special nonterminal @1 will be created and artificial rule like

@1 -> ε

will be added. But given input token A the parser allows both reducing the rule above and shifting A. Thus we have shift/reduce conflict that RACC hapily reports.

Another issue is endless loop: if the input is B then the parser reduces using the artificial rule and keeps reducing it forever. That happens because it always observes the empty symbol(together with B) and has the rule to reduce it. Ironically, another competing rule to reduce (say hello to reduce/reduce conflict!!!)

a -> ε

stays after the first one and is not selected for reduce.

To summarize, we have two shift/reduce conflicts and one reduce/reduce conflicts just because of the block. RACC is either was not designed to have before-rule blocks or the developers had something else in their mind. Alas, I haven't found any references to this issue yet.

Yesterday night was one of those rare productive KDevelop hacking nights. Last time I had it several month ago. Looks like I'm getting older ;)

Anyway, I managed to finally introduce "good-enough" keyboard navigation for KDevelop UI. Changes went to the Simple Ideal UI mode (which is now default in KDevelop 3.4).

Of course, you have Ctrl+Alt+Shift+(B|R|L) keys to activate toolviews at the bottom, right and left. But contrary to KMDI, if the toolview is already active and not focused, it will just get the focus, and not close. Also Alt+(Left|Right) is used for both toolview and editor switching depending on which of those have focus.

That's not everything, of course. You can right-click at the toolview button and assign an accelerator number to it and switch to and from the view using Alt+<Number> shortcut (like in IntelliJ IDEA).

I'm not sure those changes solve all keyboard navigation problems we have, but at least 3.4 is going to be an improvement in this area. Expect better UI navigation model from me only for KDevelop 4 ;)

PS: did I say that Simple Ideal will store the toolview layout (opened/closed state, sizes) ;) ?

Looks like this time we did it right! KDevelop will have 3 summer of code projects contrary to only 1 last year :) This is awesome!

The overall number of KDevelop applications was 15 and 5 of them were inside the first 50. The interesting thing is that 6 proposals were aimed for "C# parser/integration". Ok, people, we finally began to understand. You need C# support in KDevelop, the thing we (KDevelop devels) has not been paying attention to for several years ;)

I wish we had higher limit for KDE projects, but in any case it's great to see 24 nice applications approved! Thanks to Google again!

Ok, now back to work. It's going to be a "hot" summer for me cause I'm mentoring two of our three students. Another one goes to our 4.x series maintainer Matt Rogers. Carsten Pfeiffer, Vladimir Prus and Andras Mantia kindly agreed to help us as co-mentors. Thanks :)

Today I joined the SuSE 10.1 users community. I've installed it on my laptop replacing 9.3. Everything went fine and pretty fast (yes, I've turned beagle off at installation :) ). Problems came thereafter. Networkmanager + konqueror combination became to annoy me though. When networkmanager thinks it's disconnected from my local home network, konqueror disagrees to go to any url, even local. For example, it does not connect to localhost:3000 where my rails app lives. Firefox does not care about networkmanager apparently and works fine. Otherwise, the system looks and works ok so far. I do appreciate working suspend-to-disk and ultra-fast KDE startup!

As probably some of you already know, I've got a new cool job recently (no, the university is still my employer, that's the job I do after the Uni). My new duties are Ruby and Rails application development :) Some things I do now are free software, some not. One of the free software things is MediaCloth - MediaWiki syntax parser and HTML generator which I started to implement last week.

I don't know if there are true mediawiki parsers out there, but this one is "true". It has handwritten lexer, LALR Yacc-generated parser, AST and HTML generator (which is just another AST walker). AFAIK the "official" parser is regexp-based.

Development of the parser was much fun for me and made me think about some apparently simple things that suddenly became more and more complex. The one of such things was the discovery that MediaWiki syntax is actually context-sensitive. Heh, that's why people like it! We people hate html and xml in general. It's complex for us but simple for our computers because it's context-free. But we do like context-sensitive languages, we apparently have good parsing mechanisms for them.

Let's look at simple list written in wikimedia syntax:

 * a
 * b
 * c

This is normal flat bullet list and its parsing does not imposes any difficulty. The context-insensitive grammar below will parse the list:

List -> Item List
    | ε

Item -> * ID

Here ID is any terminal symbol like ''a'', ''b'' or ''c'' above.

The left derivation of the list from the root nonterminal will look like:

List => Item List => *a List => *a Item List =>
=> *a *b List => *a *b *c List => *a *b *c

The example above would have persuaded you that wiki language is context-insensitive and thus simple (at least in computer's sense of simple). But we all know lists can be nested like this:

 * a
 ** 1
 ** 2
 * b

Ok. Now we have a parsing problem. The grammars that come to mind are not context-insensitive anymore. One of such possible grammars is shown below:

List -> Item List 
    | Sublist List
    | ε

Item -> * ID Level1
Level1 Sublist -> ** ID Level1
Level1 Item -> Item
Level1 List -> ε

With this grammar we can derive our list from the root nonterminal with left derivation like this one:

List => Item List => * a Level1 List => * a Level1 Sublist List =>
=> * a ** 1 Level1 List => * a ** 1 Level1 Sublist List =>
=> * a ** 1 ** 2 Level1 List => * a ** 1 ** 2 Item List =>
=> * a ** 1 ** 2 * b List => * a ** 1 ** 2 * b

If we look at the grammar closely, we would notice it's actually context sensitive. Even more closer look would reveal that the grammar is recursively enumerable because the right part of production

 Level1 Sublist -> ** ID Level1

is longer than its left part.

From the all discussion above it turns out that the mediawiki language is not only context-sensitive, but recursively enumerable. In computer world such languages are usually considered ''hard'' and ''complex''. The interesting thing is that people obviously disagree with such definition for complexity. A person does have an effective mechanism to parse context-sensitive languages and therefore loves wiki formatting!

Heh, probably for the time we use Turing machines our computers will still fail at those apparently simple tasks like language parsing. You can believe in Gödel's hypothesis or not, but people still have more computation power than their computers ;)

The deadline for Google SOC applications is really soon (TM) so I'm here to invite you to join KDevelop team this summer and have a lot of fun!

We have a lot of interesting proposals in our website for you and apart from C# support they are all still free.

If you are student, KDevelop user and know programming - join! Don't worry about KDevelop codebase being large. It's modular and we will give as much help as we can.

The greatest project proposals are "Unified code/header editing" and "Next-gen version control" but you're free to make your own. Everything that is about programming language parsing, code completion and refactoring is always welcome! Support for a build system of your choice also looks like a good project to hack on.

Oh, Ruby has become a hot topic on KDE blogs again :) Let me also join with my 2 kopiykas.

My taste of programming languages tells me Python is not good for me. I don't want to claim here Python is bad, it's just not the language of my choice.

There are two good things about Ruby. First - when I've started learning both Python and Ruby year ago Ruby was perceived "cool". Today I work on Ruby (and Rails) projects half-time and the language is still "cool". There's nothing like this feeling to be commited to something cool :) Good advertising you say. Yep, pretty good but there's also something inside me telling Ruby is cool ;) Cornelius described that feeling in a more precise way.

The second good thing I found about Ruby is syntax. Surprise! Looking at the blogs and comments most people complain about perlish syntax. It's probably possible to write perlish code in Ruby but I barely see anyone does it. For example, what's wrong with Richard Dale's code?

Honestly, syntax matters were the first to take my attention away from Python. I like def initialize more than def __init__(self):. I also like code blocks ending with end and not just backward indentation. Writing self.foo disturbs me more than @foo. My list of preferences is long :)

Ok, I'm sure Python is a great language but I like Ruby more!

Ok, thanks to all Gods people ever beleived in! Ukraine is going to have parliament elections tomorrow. For the fourth time for the last 14 months we are going to elect somebody to govern us. I really hope that will put an end to this endless flow of political advertisement, speeches and other craziness.

Too many politics, too many politicians for poor Ukraine! Ok, we have the fourth elections tomorrow, and I'll vote for nobody the fourth time - just to send my message to those politicians (both from "orange revolution" and "opposition" camps) - you are not good to become presidents, deputies, majors, etc.

Gee, at last I got a permanent internet connection. Looks like the progress has finally made its way to my home :) It's an <2Mbit ADSL connection with 1.5Gb of prepaid traffic for 183 UAH (~30 euro) per month. Quite expensive but at least I won't be counting minutes of damn slow dialup ;)

What's more interesting, is that a device which I am connected through is a DLink 500T ADSL router with MontaVista Linux operating system inside. It's just amazing how can a full-blown Linux system with apache, firewall, etc. live and work fast on a small flash drive :)

Oh, this competition project turned out to be very fruitful! I wish we could do that kind of UI design competition for KDevelop. For now we don't have $1000 but I do appreciate everybody sending me their ideas of IDE design and workflow ;)

Yep, New Year has come to Ukraine for the second time! It was 1918 when Soviet Russia adopted Gregorian calendar. And the difference between Julian and Gregorian calendar was -13 days then. I don't know how that happened but people in ex-Russian Empire, ex-USSR countries still unofficially celebrate the New Year by Julian style calling January 14 the "Old New Year". So, happy "Old" New Year! :)

Yes, one of those rare quizs that worked for me :)

You scored as Mathematics. You should be a Math major! Like Pythagoras, you are analytical, rational, and when are always ready to tackle the problem head-on! Engineering 100% Mathematics 100% Philosophy 92% Linguistics 83% Theater 67% Biology 67% Chemistry 67% English 67% Journalism 58% Sociology 58% Psychology 50% Art 42% Anthropology 33% Dance 17% What is your Perfect Major? (PLEASE RATE ME!!<3) created with QuizFarm.com

OMG, today I received payment for my Google SOC project. Gee, I've never got that much money for a software project! My thanks to Google and my mentors Carsten, Harald, Roberto. Thanks also to Zack for pointing me to this program. Special thanks to Roberto for being so enthusiastic about Eclipse. I'd never touched that piece of code without you ;) Great :)

Yesterday I attended annual OSDN.UA conference in Kiev, Ukraine. I was talking about KDE4 technology and plans.

I couldn't resist speaking about KDevelop a bit so I revealed some KDevelop4 information ;) Most common questions were "why are you replacing of autotools?" and "what will happen with multimedia?".

After the talk I was communicating with the people and here I'd like to present a short summary.
First, KDE users asked for a simple way for them to participate in writing documentation. What they did ask IMHO was like offline wiki engine for KHelpCenter. They'd like to be able to put some notes and text into the offline documentation. For example, KDevelop/Automake documentation section is unfinished. Users say they could have finished it (or at least write several centences just to share their experience). But currently they'd need to either modify docbook sources or figure out a documentation maintainer and send him an email with a text. What would users love is a way to put some text/comments into the documentation and then click one button and send a patch with their changes to the documentation maintainer automatically.

Also I talked to ReactOS developer. He said they'd like to have Qt/KDE compiled and used as a default desktop on their operating system. They're compiling the system with MinGW32 compiler so I think Qt4 should work and KDE4 should work as well (when ported to win32).