BaSzErr - blog:2010

2010.01.03

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:01 +0000

2010.01.03 - open source and licensing

i had some problems with GPL and LGPL licenses in the past and recently it bounced back to be. this is why i decided to share with you my opinion on in an short article open source and licensing. if you plan to release some code/project open source, read it first and think twice if this is what you really want to do. (L)GPL is not that “free” as you might think…

2010.01.05

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:58 +0000

2010.01.05 - fly?

“If God had really intended men to fly, he'd make it easier to get to the airport.” – George Winters

2010.01.06

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:02 +0000

2010.01.06 - own company in Rwanda

i just got message from a friend to read an interesting article. it is written by a guy who traveled to Rwanda and noticed interesting differences between that place and Poland. in fact – Poland is the one that looks like 3rd-world country, when you want to open your company. since this is problem i'm familiar with for some time now i found this text very touching – how easy an simple it might be, when there is no shitty laws all around you…

i strongly advise you to read this text yourself. or, if you plan to open your business in 3rd-world country, like Poland – better don't…

2010.01.08

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:01 +0000

2010.01.08 - genetic algorithms resurrected

during my M.Sc. studies i had a lot of courses in artificial intelligence, along which there was one semester of genetic algorithms (aka: GA). yesterday, when i was at my friend's place he asked me to search for some materials we were presenting during that course, since he was asked to prepare a GA overview seminar.

after doing some digging on the hard drive i've found lectures, seminars we were presenting and project that we implemented. the application was called 'sciezka' (ang. 'path') and it used GA to find 'cheap' (in terms of length and up/down complexity) path from one point to another, on a given map. maps were gray-scaled, where black was the lowest height, while white was the highest part – it gave us 256 levels. crossing level up/down (going up/down the hill) was more 'expensive' than walking on the same height all the time, so the best path should be as short as possible, but also should not go up/down a lot.

example path found by our algorithm on 'the warehouse' map means staying on the ground and not climbing to the top of the package. just to go straight ahead to the destination.

another examples are quite obvious – paths find by GA are easy to spot straight ahead.

there were though some of them, that were not exactly “the expected results”. paths were fine, but the trick was, that when map has been created we were thinking about other solution, that would go through as little lines as possible. in few cases we haven't spotted the most obvious solution…

when following map has been prepared we though about path similar to one of the previous – we though GA will go ahead, but it will stay on the top of the map for the whole trip and then go down to the destination. it appeared though that going through such a high hill is very expensive and GA decided… to walk it around! would you cross 10[m] high wall? GA either. :)

the last, but not least, was 'entering the castle' map. there were 2 walls around destination point and to make things a bit more difficult of GA, we painted few more lines, that would make simple “go ahead” tactic sub-optimal (it would require crossing extra lines). again it appeared that map had a little trick – while painting these lines we were already focused on the solution of crossing two walls we haven't spotted that some of the newly added lines make our original solution outdated. see for your selves.

i must say it is a very pleasant moment in life when your program exceeds your initial expectations… :)

2010.01.09

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:59 +0000

2010.01.09 - C++ and 'final' virtual methods

as we all know there is no 'final' key word in C++, as is in for example Java or similar 'sealed' keyword in C#. it is also not planned to be introduced in C++0x. until just a few days ago i didn't find it an interesting topic myself… until i came across such a need.

situation

what i had were 2 set of classes: BaseA (with pure-virtual methods), BaseB (also with pure-virtuals) and many classes derived from one of these two. in fact, there were 2 disjoint class hierarchies, except for one thing – both BaseA and BaseB had identical public interface, though private, pure-virtual methods differed. the simplified version could look like this:

class BaseA
{
public:
  void process(Sth o)
  {
    // [some other code here]
    findQuestion(o, 42);
    // [some other code here]
  }
 
private:
  virtual void findQuestion(Sth o, int answer) = 0;
};

class BaseB
{
public:
  void process(Sth o)
  {
    if( check(o) )
      doIt(o);
    // [some other code here]
  }
 
private:
  virtual bool check(Sth o) = 0;
  virtual void doIt(Sth o) = 0;
};

what happens in process() in both classes is typical template method pattern. since public APIs are identical, why not make it common? these classes were to be used together either way! so what do we do? we add base class to these two – let us call it CommonBase.

class CommonBase
{
public:
  virtual ~CommonBase(void) { }
  virtual void process(Sth o) = 0;
};

now let us derive BaseA and BaseB from our new class!

class BaseA: public CommonBase
{
public:
  virtual void process(Sth o) // final
  {
    // [some other code here]
    findQuestion(o, 42);
    // [some other code here]
  }
 
private:
  virtual void findQuestion(Sth o, int answer) = 0;
};

class BaseB: public CommonBase
{
public:
  virtual void process(Sth o) // final
  {
    if( check(o) )
      doIt(o);
    // [some other code here]
  }
 
private:
  virtual bool check(Sth o) = 0;
  virtual void doIt(Sth o) = 0;
};

the problem

and here the problem arises – what if user accidentally overwrites process() call? she can do this, since its virtual call now. if i'd happen, compiler would not warn her, and application would be damaged, since code would not behave as expected in such derived classes – problems would not be so obvious in bigger application, where side effects of code in process() were minimal…

what i wanted to do was use 'final'-like mechanism, which C++ does not provide and will not provide in reasonable future. and so i start digging… i came across number of forums (ex.: _1_ _2_ _3_ and so on…) sometimes find comments like “just insert the comment this method cannot be inherited from and it will be just fine 90% of the cases”_4_. my answer is: NO – it won't be fine, since if there is a simple way to make a mistake, it will be made – it's just a matter of time…

the solution

after a while i came to a conclusion – it can be made, though it requires some extra effort. my idea is to use static polymorphism to achieve this. trick is to break inheritance where process() is implemented. and so we make template-based derived class of CommonBase that takes strategy class as a parameter. this strategy implements process() as a non-virtual call, with proper call order and other stuff we need and defines pure-virtual methods – all as in original code. and so we have something like this:

class CommonBase
{
public:
  virtual ~CommonBase(void) { }
  virtual void process(Sth o) = 0;
};

template<typename TImpl>
class CommonBaseImpl: public CommonBase
{
public:
  virtual void process(Sth o)
  {
    impl_.process(o);
  }
 
private:
  TImpl impl_;
};

class StrategyA
{
public:
  void process(Sth o)  // notice - not a virtual call!
  {
    // [some other code here]
    findQuestion(o, 42);
    // [some other code here]
  }
 
private:
  virtual void findQuestion(Sth o, int answer) = 0;
};

class StrategyB
{
public:
  void process(Sth o)   // notice - not a virtual call!
  {
    if( check(o) )
      doIt(o);
    // [some other code here]
  }
 
private:
  virtual bool check(Sth o) = 0;
  virtual void doIt(Sth o) = 0;
};

now we're almost done. all we need to do is to implement our strategies the way we want and create instances. so it's go!

class StrategyA_1: public StrategyA
{
private:
  virtual void findQuestion(Sth o, int answer)
  {
    // ...
  }
};

class StrategyB_1: public StrategyB
{
private:
  virtual bool check(Sth o)
  {
    // ...
  }
  virtual void doIt(Sth o)
  {
  }
};

now we can create an instance and run it:

  std::auto_ptr<CommonBase> base( new CommonBaseImpl<StrategyA_1> );
  base->process();

and that's all - we have running code, where it is not possible for user to accidentally overwrite relevant code, she should not be possible to.

download

to see how this works in real-life you can download 'final-like' example code and run it yourself. package contains 4 different implementations of 2 different strategies, so you're free to do experiments or used it as you want.

example is licensed as beerware, if you plan to used it for more than just exercises. ;)

c-tor parameter(s)

there are few things that can be improved in above example. first of all is constructor – in most real-life cases c-tors do take parameter(s), so default c-tor is not enough. i skipped this step in above example just to stick to the point and not add additional noise to the basic idea. when you want to be able to pass any parameter(s) in generic way you should modify CommonBaseImpl like this:

template<typename TImpl, typename TParam=int>
class CommonBaseImpl: public CommonBase
{
public:
  CommonBaseImpl(const TParam &p):
    impl_(p)
  {
  }
  CommonBaseImpl(void)
  {
  }
 
  virtual void process(Sth o)
  {
    impl_.process(o);
  }
 
private:
  TImpl impl_;
};

in case you need more paramters, make TParam ba a std::pair<>, boost::tuple<>, or just a dedicated structure that holds all of your parameters and so you can passes anything you want to any possible implementation you want.

minimizing virtual calls

if you've read this carefully you probably noticed that there is no real need for using virtual calls when writing StrategyX and its derived classes. you can do the same trick as with CommonBase – just make StrategyX_Y (implementation) a template parameter to StrategyX using CRTP.

i've skipped this point again for sake of clarity. adding more templates (1 – if you stick just to CRTPl; 2 – if you need c-tor parameters to be passed (see example before)). this step does complicate code even more, and efficiency difference is minimal, since virtual calls does not cost much¹⁾ – if this is not very time-critical code part, you can just stick to the virtuals – remeber: architecture and readability first, then optimizations²⁾!

final remarks

as you can see, one can live without 'final' keyword but it's not straight-forward nor does explicitly express programmer's intentions. why there is no such keyword in C++, i do not know. it would be helpful if there were – in a way it is in C++ spirit, since it does not introduce any overhead (this is just a compile-time check, and since compiler have to know full class declaration when deriving, it could be always checked) but does simplify life.

¹⁾

i've measured it on my old Pentium IV to be ~2-3% during millions of executions of simple (but not inlined!) method

²⁾

off course time-critical parts are exception here, but these are typically estimated as ~2% of all code.

2010.01.10

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:58 +0000

2010.01.10 - carpe diem

Twenty years from now you will be more disappointed by the things you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. – Mark Twain

2010.01.14

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:58 +0000

2010.01.14 - Liskov vs. 'final'

few days ago i wrote about workaround for lack of 'final' keyword for methods in C++. Michał Rzechonek pointer out thing i haven't spotted – there is an issue with Liskov substitution principle. though it may not be crucial here, but it gives some light on why 'final' is not present in C++, nor is planned to be in C++0x.

2010.01.16

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:58 +0000

2010.01.16 - sledge's done

yesterday i've finished developing and field/testing sledge project, started last year. it is really a great fun. as for me snow could be here for another year all the time! :)

2010.01.21

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:59 +0000

2010.01.21 - it's not polite to say to a thread 'fork you!'

recently, while working new ACARM version (aka ACARM-ng³⁾) i was investigating threads and how do they behave when fork() is called. i found a set of articles you might be interested in.

if you want to keep it short, the general idea is – don't mix them (see: quotation in the title of this article)! the only exception is when calling fork() from within multi-threaded application just to call exec() in the forked process (ex. just like system() call does). there is a pitfall however, one must be aware of. when forking and spawning new process one must remember about secure file descriptor handling. in short, when calling exec() open descriptors are moved to exec'ed application.

when talking about threads there is also interesting topic on how to handle signals in threads. article thread-specific data and signal handling in multi-threaded applications covers this, though its VERY old and many things are outdated right now. the idea is to run dedicated thread just to handle incoming signals (i.e. idle 99.9999% of the time). this has another advantage – it allows to use mutexes and other synchronization mechanisms, since you know that signal will be handled in a separate thread, that will not wait forever for mutex to release.

³⁾

no home page yet

2010.01.22

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:01 +0000

2010.01.22 - scripts in GUI

there was once a talk on one of the forums – text console vs. GUI. the final post was from one of the console guys was: “ok - so how do you make for f in *.tar.bz2 ; do tar xjvf “$f” ; done in GUI?”. it quite end up the discussion. recently the sikuli script has been developed to handle GUIs from a scripts. nice idea, but as you can see on the demo - a lot needs to be improved. performance is a tragic – but if you run python on the java vm, and all this to process images – it's not a surprise i guess… ;)

2010.01.30

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:08:59 +0000

2010.01.30 - white mountains

the winter has come this year the big way. i always loved winter, snow and all the corresponding views associated with it. since few years i complained about lack of snow, lack of cold, etc… this year i must say i feel satisfied – it is snowing since few weeks, temperature is (way!) below freezing point and so it is nice outside, it is white everywhere… it is just beautiful! just the way it should be every winter! :)

i've already done some sledging. to enjoy “the white time” even more i've decided to do a little mountain traveling. the view was truly delightful! if you do have some time just see the mountains covered in snow every way you look! :) see some pictures yourself (clink on the image to enlarge it).

2010.01.31

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:01 +0000

2010.01.31 - WarHammer and the battle of Wizna

yesterday evening i reminded myself incredible intro to Warhammer 40,000: Dawn of War. i started to look for other intros that were present in other Warhammer games. a collection i recommend to see goes here:

looking for more i've came across Swedish band called Sabaton. they play power metal and do it very well. i got interested a little more and found out that they have written a song about Polish soldiers fighting in the battle of Wizna, during world war II, who stand in power of 720 man and few bunkers against 42000 (yes - 42 thousands!) Nazi army, armed with over 600 tanks, air support, lightly armored vehicles and artillery for 3 days, giving time for Warsaw to organize the defense. nearly everyone of them died, standing the ground until the end. for this, the battle of Wizna is often referred to as “Polish Thermopylae”. i strongly advise you to read more about this battle and listen to Sabaton's 40-1 song (see also: official '40-1' video).

2010

anonymous@undisclosed.example.com (Anonymous) — Tue, 15 Jun 2021 20:09:02 +0000