the written word remains

I've too tired today to hack and therefore decided to blog a bit. I'm sitting at the Budapest airport waiting for my flight to Dublin which should be my last flight for the next week. And that week I hope to spend in Dublin without any traveling.

Ok, ok. I do like traveling, I like flying but after going from Mykolayiv to Kyiv (500km) to apply to Irish visa, going back home, going to Kyiv again to catch the flight to London, going back from London to Kyiv, then traveling Ukraine with the usual "give me my visa" route again (Kyiv-Mykolayiv-Kyiv-Mykolayiv) I feel like a bit tired ;) I've already covered 6x500=3000 km of Ukrainian territory and I observed each kilometer from the window in the bus! Yeah, yeah, you don't travel Ukraine by plane - it's extremely expensive.

But all that had positive result - I have my visa and I'm already heading Dublin for aKademy! By the way I also visited the RailsConf Europe in London which should really be the topic of my next blog.

In Qt 4.2 trolls did amazing job at improving dockwidgets. They even added the tabbing feature so that you can group docks into the one tabwidget by just dragging one on top of another.

A couple of months ago I thought that would replace "Ideal buttonbars" - those groups of buttons you can see in KDevelop and Quanta in Ideal UI mode at the window borders. But today I think that buttons should still stay if we want the Ideal mode like we had before. We just don't have enough control of those new tabs and can't make them do what we want (i.e. hide toolviews). Also they seem to be always horizontal which is a pity because we got used to vertical rows of buttons.

So, this and this is how KDevelop4 with toolviews looks now. Notice that KDevelop4 looks exactly like Qt Designer - all toolviews are just plain dock widgets. And this is how Ideal mode looked before. Notice the "button bars" at the bottom, left and right window sides.

The question now is Qt Designer-like interface good enough or is it better to back to good old Ideal UI with buttonbars? I don't have the good answer, please share your opinion with us at kdevelop-devel@kdevelop.org or just leave a comment here.

For now I'll continue working on new Ideal library. I miss Ideal too much ;)

Yes, I'm back after not committing for a month and I'm back with the new ruby parser for KDevelop. The parser is of course not finished and it barely parses simple ruby code but it is there. I'm looking forward to implementing some real ruby language support features. First will most likely be a code model (which will automatically give nice code view with classes, methods, etc.). As it turned out our kdevelop-pg parser generator framework makes it dead easy to do that. And its not only the kdevelop-pg that helps, the whole KDevelop4 architecture makes the process a lot faster.

Previously when you wanted to implement the language support in KDevelop, you should have done:

1. lexer to tokenize the source


2. parser to transform the token stream into the AST


3. AST walker to make it possible to do something with it


4. AST parser to create the abstract code representation - the code model


5. "background parser" to execute the parser as a background job and fill the code model


6. language support part to run the background parser

Today you still have to write the lexer and the parser, but you no longer have to care much about the AST and AST walkers(visitors) because they are generated for you. And once the code model definition file is written, the entire code model will be generated too. kdevelop-pg does all those things.

From the other side, KDevelop4 has more generic language support and abstracted background parser so you can just tell the language support in several lines of code to use your parser. There's no need for language support code duplication which was so common in KDevelop3.

Simply put, points #3 and #5 are automatic now, #2, #4 and #6 were made easier. At this point I'm wondering if it is feasible to eliminate the #4 completely, i.e. implement automatic generation of code model binder which traverses the AST and fills the codemodel with items.

From what I can see KDevelop4 will really shine in the area of language supports. blackarrow is doing wonders with C++. jpetso completed his summer-of-code csharp project and the excellent csharp support is already in SVN. manyoso added java support that uses the complete java parser jpetso created last year. And if we add up language-neutral refactoring (which was another SOC project) to the stack, we would get the idea of how cool KDevelop4 is going to be!

It doesn't look like I'm short of cool material for my aKademy presentation :) Rock on, KDevelop!

That's what I heard from manyoso lately and he was damn right. This indeed happens and I see I'm not the one. Well, my day this week consisted of 16 hours and if I substract two hours I spend to have some food and read my mail I'll get same 14 working hours as geiseri had.

But I'm having that since February and I can't see the way to avoid this in the next 6 months too so I should live with that. But there's one Cicero's statement that consoles myself. He said once that if we avoid the weight of cares then we miss the prowess. And indeed what would I have done and what kind of man would I be without my cares ;)

Speaking about cares, I had plenty of them recently. Just to mention the first Ruby/Rails meetup I and my fellow Anton organized here in Mykolayiv. The cool thing is that event was financed by the company I work for now and we managed to rent the good conference hall and gather the most interesting people there (we have the meetup site in russian and some pictures).

Anton did extremely well at organizing so my job was only to enjoy and educate people who came to this event. Hopefuly I did it not so bad ;). I was speaking on Ruby and Rails, showed live demos writing some real Ruby and Rails code and I was overwhelmed with questions during the whole event. I thought 3 hours would be enough and I was surprised to be proven wrong :) Four hours the people tortured me asking more and more (especially about Ruby language itself) and then after the event was finished they were continuing torturing me in the bar nearby till late evening :)

As far as I can see, people who work in software development industry in my town are really interested in something new and innovative. This is nothing surprising.

What's more surprising that engineers who worked in the industry at least for two years are more interested in technologies than students in my university. I've been working at the university for four years and I can see this tendency growing in last two years. Most CS students pick one thing they think will bring them money and get stuck (no it's not Java, here in Ukraine we all like Delphi ;)). On their second year they already know (or think they already know) how to program in Delphi/ObjectPascal/whatever and stop listening to their teachers. Of course they miss algorithms, parsing theory, OO programming modelling and lots, lots of really necessary things including two Unix courses we have in our university. Of course they don't hear me telling them about the beauty of Unix, Ruby, whatever else.

And I now kinda enjoy when I see same people to have interest in all those things they missed at the university after spending a couple of years doing real life work. Why does that happen? Only recently I found out an answer. The very simple answer. Money is the answer.

Typical ukrainian student grows in the environment where he constantly lacks money. And after they are able to develop another cool accounting application in Delphi they find out they already can earn quite a lot of money. In fact, that amount can be already bigger their teachers get from the university. This convinces them the university teachers are worthless and they don't believe in their authority anymore. Heh.

Of course thereafter they grow, they start think more about their profession, maybe read blogs like this one (I was shown this several days ago). And their interest level actually starts growing and they start growing themselves at the same time. I wish our students looked one step further or just believed their teachers.

Hmm, why am I writing all that? Maybe I'm just ranting. But maybe that's just my own discourse on duties. Do not neglect your duties, even if they sound wrong if you're student and think the world domination is one step ahead. Just believe me, the real life happens and you will not have enough time to educate yourself after the university. I know it. Don't repeat my mistakes. I know how hard is now to extract just two hours from your daily schedule to learn new language or to read new book.

I've recently moved into the new appartment. The move itself was wery taxing and took more than a week (mostly because all my family including grandparents and parents was moving). But we finally made it and now I enjoy my new room. Today I've taken some pictures of alpha version of the room. Some furniture is not yet there and ADSL connection is still missing but we're in progress ;) At least this "alpha" version is already capable of containing all my library. In my old appartment those books were laying here and there without any chance of finding the book, now things are a lot better!

Now that I'm getting back to the life again I'll start working on KDevelop again. Last week I didn't commit at all and that doesn't make me feel good. I'm going to restore the good old habbit of committing stuff every day again ;)

Today I finally finished listening to the Wagner's "Der Ring des Nibelungen" opera (CD recording only alas). The complete Ring Cycle took me exactly four days to finish listening but I don't regret of any single hour spent! Only now I think I can understand Nietzsche's "The Birth of Tragedy out of the Spirit of Music" better. Indeed when Dionysian and Apollonian origins join they form something that is equally solemn (the music) and tragical (the epic) but leaves you anyway exhilarated.

I'm still sitting here, humming Hojotoho! ;) and reading more about Nibelung. Honestly, these days I discovered a previously unknown to me Norse mythology and epic. I didn't think of such rich mythical worlds existed outside the Greece. Obviously, I need to learn more (just ordered a book with West European epics collection, it will be a nice addon to my collection of Greek, Roman and Slavonic mythology).

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