Having read a recent version of C++ ABI standard, I noticed that certain bits of it were revised (the version of the standard hasn't nevertheless been changed). Particularly, a vtable entry of a mysterious "deleted virtual function" was documented. I thought that it could influence binary compatibility, and here's what I found out.

What deleted functions are for?

C++0x introduces another form of a function definition -- deleted function:

When a function is deleted, it means that calling it is prohibited, but substitution of it is not a failure. This is mainly to be used instead of making constructors private and providing abort()ing definitions to them (to explicitly prohibit copying objects, as in example above):

Another use-case is to prohibit certain type conversions. The use cases are well described at the relevant wikipedia entry.

In other words deleted function means "the function is declared but it actually doesn't exist."

That's all it could be used for. It can't benefit SFINAE, since deleted functions do not influence lookup rules, so a deleted function should be considered a proper substitution; this, in turn, leads to compile error because deleted functions can't be used in any way, even if they're not called. However, this sometimes is of benefit, since we may want certain lookups to fail, instead of silently picking a badly-working substitution.

So the main purpose of deleted functions is additional compile-time checks. Not even altering the way a code that uses certain functions and classes works, but mere checking. However, hiding constructors arises issues that concern binary compatibility. Let's check if there's anything interesting.

Binary compatibility issues

In the problem of binary compatibility we consider two versions of a C++ library: A and B. We try to write B in such a way that any program built against A lib keeps functioning if there's just a B library in the system. I usually restrict it to GCC compiler, because I don't know much about the other ones :-) (and because of the means described in the other blog post about C++).

If a function is declared deleted, then a) it's considered inline, and b) it can't be called by a complying program.

The property b) is interesting since it influences source-code compatibility. In my research I assumed that binary compatibility of libraries should only be retained for source compatible programs, i.e. for those which compile unmodified with both versions of a library.

This means that if from a deleted function in library A the delete specifier was removed in library B, then it can't influence anything, because that function wasn't referred to in any program built against A library. Moreover, if it's the case of a virtual function, the claim cited above of ABI standard makes virtual table not change in size.

This also means that if a function gains delete specifier in B library, the source compatibility requires all programs that are built against A library... just not use that function. This means that anything can happen on binary level (note again that a slot in vtable is kept) with this function, and it won't influence any of older programs.

API modifications: would delete help?

So for source-compatible programs deleted functions introduce absolutely no problems. I'd like to refrain from analyzing source incompatible programs, because, strictly speaking, we could then dive into unfruitful analysis of compatibility of sound library and instant-messaging libs.

However, there are practical patterns of API changes that break source compatibility but still make sense. For example, we want to deprecate a function, so that newly linked programs (against B library) will use a safer equivalent, while those linked against A will keep working. Would delete be of help here? (That's actually the first thing I thought about when I saw delete modifier).

Unfortunately, it wouldn't. Deleted function don't have a body; it's just not emitted, because they're inline and... erm, inapplicable to calls, by definition. Moreover, providing a body for a function previously declared "deleted" is a violation of one-definition rule. So, unless you're doing dirty hacks, when the header you compile library with and the header you expose to user are different, you're out of luck here.

What would help is making functions private. If you want to safely "delete" your virtual function, you should just make it private (and ditch all references to it from your internals, of course). The virtual tables won't change in any way. For non-members, where "private" is not available, the best you could is putting a line in your documentation "DON'T CALL THIS!"

Of course, after some time you may declare your function deleted thus making all programs that still use it incapable to start (dynamic linker will signal unmet dependency). If the function was virtual, no problems with virtual tables will arise as well. That seems like a sane and safe deprecation method (normal-private-deleted).

No problems may arise if a private abort()ing function was declared deleted in the new library version. Such function couldn't be referenced from the complying programs (unless you for an insane reason did this in your public inline member functions). So no dependency on their symbols would be introduced.

Conclusion

The first thing I thought when I saw a delete specifier was, "Wow, that is probably cool stuff for binary compatibility!" Indeed, it helps to remove obsolete functions (and break compatibility if it's intentional), but in most cases (when it's non-virtual) it's no different from just removing this function. So deleted functions don't bring any new concepts to binary compatibility. Nevertheless, to be fair, they don't bring in anything harmful as well.

The idea behind this blog post has always been to make peace between two things. One of these is my honest belief that sexism is unwise and disgusting, and all human beings are equally smart regardless of their gender. The other thing is dismal amount of women in programming profession I observed at that time and place. In 2010, some discussion on the web finally gave me the idea that an easy mathematical construct can demonstrate how these two things can be true at the same time, so I wrote a provocative and--as one of the commenters puts it--"needlessly argumentative" post about it. Here it is, slightly, rewritten.

Are women worse developers than men?

There are slightly more women than men among humans. However, there's just a small amount of women in software development, as observed and acknowledged by us daily. I observe this in the place I work, and I hear a lot from others that they observe the same at their workplaces. If you're a software developer, take a look who surrounds you: how much of them are women? Not much I guess, much less than 50%.

So does this mean that women are somehow inherently worse in programming? No.

A survey of participation of women in computing over the world demonstrates that it varies dramatically from country to country: from 6% in Denmark to 55% in Thailand (anecdotal evidence reports 60%+ participation in Qatar). If somehow women were worse at this, these rates would have much more similarity. This seems to somehow depend on the culture.

The thing, however, is that whether women are worse or better at it is completely irrelevant for most situations that occur in practice. That's right: even if you are somehow sure that women are inherently worse at programming, this does not warrant any kind of different attitude towards them in the workplace, and here's why.

Why shouldn't one just fire all women if one thinks they are inherently worse at programming?

Short answer: because conditional probability. Longer answer follows.

Assume you are doing an interview, and assume also that you are sure that women are worse programmers than men. Does that mean that the probability that a woman who comes to your interview is a good programmer is lower than the probability that a man in similar position is a good programmer? No, and the reason is that the group your interview candidates come from is no longer "all women" or "all men." Instead, these are "all women who chose their careers in computing" and "men who chose computing".

The probability that "a woman is a good programmer" (A) given that "a woman chose programming as her career" (B) is not equal to the probability that "a woman is a good programmer" (A). This probability can be both greater or less than this, according to conditional probability definition (see illustrations):

P(A given B) = P(A and B) / P(B)

And something tells me, that this very particular group "women self-selected as professional programmers" will have more good programmers than general population. In any case, no matter how small the ratio of good programmers among all women you believe is, it tells you nothing about women in the profession. Any kind of unfair treatment of female peers can't be justified by reasoning about general population, and understanding of conditional probability gives us a mathematically solid proof why.

Why is there a debate about whether women are good at programming in the first place?

Because many people believe that participation of women in software engineering and the skills of women in general are correlated, while in reality these numbers have absolutely nothing to do with each other. Yes, lack of participation is still a problem, that is worth addressing, but the innate skill levels is not factual. The correct application of basic probability theory should settle this for anyone who has doubts.

Some see low participation of women in engineering as a sign of their inferior skill, and therefore reason that women should not be hired, or should be not taken seriously. This line of reasoning is mathematically wrong, as shown in the previous section, even if it somehow turns out that women are indeed worse programmers, which I do not believe is true.

Others believe that women and men have equal programming abilities (which is a completely justified belief), and make a conclusion that they must be equally represented in the workplace regardless of other factors, thus interpreting the disparity we observe as deliberate diminishing of women's programming skills. This line of reasoning is as unjustified as the previous example because, again and again, skill and participation may have nothing to do with each other. It's still a problem that needs to be addressed, but the issue is not the lack of innate ability.

Instead of trying to eliminate bias in prior perceptions, I offer to focus on fixing what is easier to fix. Math has a certain appeal that other ways of persuasion don't have.

There still exists this vicious cycle when female programmers are considered uncommon, and this wards off women by itself, making them uncommon, again. People stop caring about women because there are none on their team, and there's simply nobody to care about; they forget--or even never learn!--that programming is something people of all gender can do. Feminist websites like this have a lot of advice to offer to mitigate this.

Comments imported from the old website

As everyone knows, StackOverflow founders, Joel and Jeff have recently received mysterious VC funding that should help to support StackExchange platform and the Trilogy sites.

Meta had a number of threads where people tried to guess, jokingly and seriously, what kind of dirty trick the Trilogy crowd will encounter. As far as I remember, none of the guesses were unobvious. But the dirt wasn't novel either.

Defense of the Ancients and the "Clan DCE" affair

When I was at my first year in the university (that was five years ago), and didn't have enough time and money to have a good entertainment, I played online computer games. One of them, which I sometimes play even now, was Defense of the Ancients (DotA), a Warcraft III modification (but virtually it was a separate game implemented as just a map for Warcraft). Five players on each side, two-hour battle and a lot of fun and adrenaline.

This game has one peculiarity. It requires ten people to pay continuous attention to the game that lasts two hours. This means that if a player leaves the game, it is virtually ruined. However, it doesn't affect the status of that player in any way, so he could join another game and keep ruining them, destroying all the fun.

No wonder that the most crucial long-term goal was to find or create a good community, where each member respects others and doesn't spoil anything. That was achieved by rating systems, such as "Dota-league", and private channels (such as "Clan DCE", which gathered around a professional dota clan).

I participated in "Clan DCE", was a player of moderate skills, but I never ruined games by leaving. In fact, I even sometimes was late for university studies because I had to keep playing. But as that community grew, it became full of incompetent leavers, and the clan heads made a decision.

The decision was, exile everyone except the players "with invites" (which was effectively a randomly selected 20% of the community) and don't allow anyone in without two vouches from insiders. So most of the people who invested their time into building the community were exiled and didn't have a chance to return. That was a tough lesson of my Internet life, and now I pick communities to join way more carefully. The lesson was that those who own the platform own the community. Literally own. And can do everything they wish, regardless of what other think, and people have little to do with it.

StackExchange 1.0

StackOverflow, as any kind of such a site, is only successful if it has a strong community. When I was joining StackOverflow, I paid special attention to how the community is formed. It became apparent that community leaders and platform owners are separate people (due to what I saw on meta). Later I realized that SO is a jewel in Jeff's crown, and it won't do any harm to it ever. So I relaxed and didn't think much about it.

StackExchange is a Software-as-a-Service (SaaS) "make-stackoverflow-like-site" platform. It was bought by about 200 people, and even if they fell suspicious about buying a SaaS, Jeff's and Joel's reputation, I suppose, made them not bother about it. These guys built the communities, published their own ads... and some succeeded! But then VC funding came into play.

StackExchange 2.0

StackExchange 2.0 has a very hypocritical introduction blog post. I'll summarize it briefly:

1. StackExchange will not require any monthly payments!!!!1 LOVE US, GUYS! (and we hope you won't read the rest of blog post)
2. Opening a StackExchange site will be more like a game, not just a pay-to-get process. LOVE US EVEN MORE! (we know you like games)
3. All unsuccessful StackExchange sites will be purged.
4. All your bases successful StackExchange sites are belong to us. We will now get revenue from the ads. No matter that this revenue only exist because the current owners created and parented the community -- it's all ours now.

And if the community owners will try to move to another website (and some alternative stackexchange clones have already announced migration services), not many people will follow them, I suppose. Because why bother?. A current site is stil running, and is still free, so why bother moving anywhere?

The "stolen sites are still free" is Robin Hood-ish of sorts. For me it's plain simple: if it's a Robin Hood stealing, it's still a theft. But many people don't think that way, and they have other values. So, competing with a free site with full-blown support by platform owners will be incomprehensibly hard for those who really were the creators of the communities.

I bet just a few sites will even try to migrate, and the communities, torn apart, will survive in those parts that didn't move anywhere. Though, only time will tell.

Conclusion

Perhaps, it's not that bad. A quick whois querying shows that domain names seem to belong to the real owners of the sites, so if they just migrate to open source platform, they'll still have everything. Bu that domain name stuff is really out of my competence.

But anyway, I think that VC funding won. They developed a neat model to steal stuff from the people who created it, and they seem to gain support for a scenario "we will steal best of you, and destroy others". In Real Life that's generally called "marauding". And Internet Life teaches the same lesson again. Those who own the platform own the community.

And another lesson: Software-as-a-Service model, even before it became popular, already shows its evil grin: it's not you who own the software and tell it what to do, it's software owners who tell you what to do. Sad that it happened with the most open community I ever encountered.

I'm not a muscleman. In fact, I'm kind of a wimp. But given all this, my weight is 15 kilograms greater than I should have with my height. Time to lose some.

I've been logging my weight for quite a time, but I realized that logging alone doesn't help. I need other people to nudge me, so I would be more ashamed of my condition. To achieve this aim, starting today, I will publish a graph of my weight. It is rendered by gnuplot, and that page contains the script that renders it.

And, of course, since I'm a geek, the process of displaying the graph should be made as automated as possible.

Nearly every morning I weigh and log the result in the text file. My aim is to automatically upload it to the server right after I edit it; of course, manual uploading is out of the question. The update happens at different times, and I don't want to poll the file every hour, since it is just inefficient, and induces an unnecessary latency. And here's the neat solution.

Tracking filesystem events with inotify-tools

Starting from 2.6.13, Linux kernel has an interface that watches for filesystem events without need to wake up on timer to check them. This subsystem is referred to as "inotify". We can utilize it for our aims.

The generic idea is to run daemon that waits for the weight log file to be changed. After I click "Save" in the text editor, the daemon notices it and sends file to server via scp (copy over ssh). On the web server another notification daemon watches for changes in the destination file, it renders an image with a plot and copies it into the webserver place.

Of course, nowadays one doesn't need to write C programs to access inotify directly via syscalls. Instead, I installed inotify-tools package (sources), which allows to use inotify from shell; a command we will use is inotifywait.

Inotify, as noted in Kernel docs, is interfaces via establishing watches that write information about the events via file descriptors. Waiting for a filesystem event is a mere blocking read from a file descriptor, the intrinsics being handled by the Kernel. The inotifywait command just wraps this in a convenient way.

One of the ways inotifywait can be used is to "monitor" events: the inotifywait process just prints a line to STDOUT when an event we watch for occurs. So we can just pipe the output of inotifywait invocation to a simple shell script that reads the lines and does work on each read. Here's how the daemons look like:

Local PC:

Remote server:

These daemons are currently deployed on my local machine and on server.

Version without monitoring

Due to misunderstanding of how stuff works, I encountered strange denials when I used the -m option to inotifywait. That's why previously I used the following daemons:

Local PC:

Remote server:

The calls to inotifywait here contain no -m option, which means that they exit after the event watched for occurs.

There are several wait operators and subshell spawns that may seem excessive at the first glance. However, they're there to avoid losing data during the race condition.

Assume there's no waits and no subshells, just inotifywait and copy/plotting commands. Then the following scenario is possible:

1. I enter new value and save file
2. The file is copied to remote server
3. Remote server notices that file's changed and starts plotting it
4. I notice a mistake I made in data, fix it and save the log again
5. The file is copied to remote server
6. Remote server finished plotting previous log with mistake
7. Remote server starts waiting for file modification
8. Changes made in p.4 are ignored!

If the file is copied to remote server while it was plotting it (and plotting/converting takes noticeable time), the subsequent inotifywait call won't notice any changes. Because when the file was modified, inotifywait was not running!

We solve it by doing conversion work asynchronously. Then, step 7 doesn't necessarily follow step 6. Instead, it's executed (hopefully) right after step 3.

If we spawn subprocesses instead of running the whole conversion, the time when we miss modification events is dramatically decreased, and doesn't depend of length of processing.

On the other hand, we can miss modifications when we're waiting for child processes to terminate. But even if we miss modification events, when we finish waiting, we will handle the modified file anyway. So that's acceptable. In general, it's also of no harm to do a, say, sleep 10 after inotifywait: another data save is likely to happen after the first one.

Conclusion

Finally, we've created a synchronized system of two daemons for the local and remote machines, based on inotifywait program of "inotify-tools" package. And now I have a public tracker of my own weight deployed within an hour, but I still wonder, wouldn't it be better if spent this time jogging?..

I realized why I was so aggressive in attempts to guide one of the latest StackOverflow questions so it would gain useful answers and wouldn't be closed as subjective. The question title is "Why are most really fast servers written in C instead of C++", and I really wondered why they are. Because that's... a bit personal to me. So, let me tell you this story.

Some time ago, after I suffered a fiasco to get a job in the USA, I thought it was a good idea to change my career to a less ivory-tower-ish. I thought about what was going on in the industry, and decided that since everything was moving to web, it would be a fruitful choice to become a web server developer. So I sent my resume to three companies that were hiring a newbie Linux C++ web server developer. Being under impression of "Smart and Gets things done" stuff, I wrote a resume that way and explicitly stated that I don't know anything about web serving.

First

One company, which is the top Russian search engine, declined me with a note "Your skills are valuable, but we can't offer you a job now" (bold is mine). I still wonder what that means: am I good or bad? Should I get more experience and try again or that's just a polite rejection? But well, alright, that's the number-one company, so I didn't frown upon that.

Second

The other company was an emerging startup. They had a shiny big office with free coffee, and a large restroom (at least that's what they said). A sign of warning was that the team failed its previous startup, but hell, why not give it a try? I was contacted by the CEO (it's a small startup, isn't it? Anyway in one Silicon Valley startup I was also interviewed by a CEO, so that didn't bother me) and was sent a sample task.

The task was to develop a C++ anti-DDOS module that drops any IP that exceeds a connection limit per a prespecified time. The task had been sent without any prior notice, and had a week-long time limit (who cares that I have plans for the week?). Period.

Well, alright. I didn't have any experience with Apache and web serving at all, so I started googling like crazy. After five hours of googling, I learned how to create apache2 modules, I devised a way to create a C++, not a C, module and I wrote a module that worked but was thread-local (apache starts a lot of threads). Essentially it was useless, but, well, spending more than 5 hours for a job application is a commonly acknowledged overkill!

I thought it did prove that I was a fast learner and a capable programmer. I sent that solution with notes how it should be improved to make up a complete module. However, "the architect was not satisfied with my code," and I was asked to finish what I had been assigned to. A note that I already had invested enough time for them to see if I was capable good enough to do the job was replied with a hilarious letter. It happens that I don't profess the company's philosophy that values result rather than capability! And unless I finish the code I'm not accepted.

Well, if the company values working for it for free, then it indeed is of a different philosophy than me. Good luck to these guys, I hope they won't fail many startups until they learn something.

Third

The third was another top Russian Internet company. They assigned an interview in their shiny big office with free a pong table, PS3 avaliable, as well as the usual free coffee and a large restroom! The interview started with a question "Why didn't you apply to Google?" -- apparently because of my Summer of Code participation (or because I was a candidate to replace a guy who transferred to Google from there).

The interview went smoothly, even considering that I didn't know anything about how HTTP or web servers work. After more usual questions, I was given a coding assignment. The clouds started gathering: they asked to write a C program to parse apache log and detect how many different IP addresses were in it. "Why not C++?" I asked, "it's easy and fast in C++!" The reply was that they wanted to judge my algorithm skills, not the knowledge of standard libraries. Well, OK, that seemed fair.. So, let's reckon how I did it in programming contests... *rubbing hands*

In 20 minutes the program was ready, but the remote server I was ssh-ed to suddenly went out of space, and the source somehow managed to get erased after a failed attempt to save it (Vim let me down this time). I spent another 20 minutes to code it again; it was all OK, and the interviewer even didn't see anything to criticize my code about.

The interview seemed to have gone great. The architect that interviewed me happened to come from the same university as me, was a fan of Vim as well, and sounded pleasant. We proceeded to discussing my salary, I made an offer, and there it happened.

"Okay, now I must confess," the architect started, "We lied to you a bit. All our software is actually written in C. Although we were looking for a C++ developer, you'll have to do C programming mostly."

O_O

The thing, yet unknown to the interviewer, is that I hate C; I hate it as much as I love C++. Feeling so deceived, I burst into explaining that writing in C is disgusting, since C is the new assembler, regardless of that I can do it quite well... No wonder I didn't get this job either.

Of course, I asked why they did development in C. And the answer was, "well, we sometimes feel urges to start rewriting it all in C++, module by module. But then we question ourselves—"but why?", and leave things as they are".

***

And now I also question myself—"why?" The fact that servers are mostly developed in C, I think, was crucial for my life. Perhaps, if it weren't the case, I would already have said goodbye to science and my masters studies, and would become a full-time corporate server developer. But sometimes at nights I still wonder why... why didn't they rewrite it in C++? And that's why I wanted that SO question answered.

Recently I tried to add a feature to this site. The feature is to display a Russian flag near links that point to web-sites, language of which is Russian. Of course, I wanted its height to be equal to that of a letter.

So, basically, I want my image to scale up to the size of a letter by user's browser capabilities. "What format does that mean?" I thought. Of course Scalable vector graphics (wiki)! Then this stuff would be scaled with a simple style

But it doesn't work. I tried googling, and it seems that there's no way to make it work. The conclusion is that a Scalable Vector Graphics image just doesn't scale!

Vector graphics surely can scale, and what "scalable" should mean is that the format is designed in such a way, that image is easy to scale in size. Perhaps, format allows it, but the way it is integrated in HTML code doesn't allow it.

It was a great surprise to me: I misunderstood the word "scalable" within the definition of SVG. The ability to grow/shrink in size is not appealing enough for standard developers that live in their ivory tower (SVG has been arount for 10 years, and is still not fully supported anywhere). Here's what "scalable" really means:

To be scalable means to increase or decrease uniformly. In terms of graphics, scalable means not being limited to a single, fixed, pixel size. On the Web, scalable means that a particular technology can grow to a large number of files, a large number of users, a wide variety of applications. SVG, being a graphics technology for the Web, is scalable in both senses of the word.

SVG graphics are scalable to different display resolutions, so that for example printed output uses the full resolution of the printer and can be displayed at the same size on screens of different resolutions. The same SVG graphic can be placed at different sizes on the same Web page, and re-used at different sizes on different pages. SVG graphics can be magnified to see fine detail, or to aid those with low vision.

SVG graphics are scalable because the same SVG content can be a stand-alone graphic or can be referenced or included inside other SVG graphics, thereby allowing a complex illustration to be built up in parts, perhaps by several people. The symbol, marker and font capabilities promote re-use of graphical components, maximize the advantages of HTTP caching and avoid the need for a centralized registry of approved symbols.

Scalability happens to mean something more cool than just resizing, wow! The ability to be re-sized was lost in the row of cool practices SVG allows. But still, while the standard says about different sizes that "it can", in realty it can't. Totally useless.

Comments imported from the old website

This article was planned before the creation of this blog. I tried to understand what programming is as an approach to problem-solving, rather than just as a tool. And I found out that the approach of programming reminds what happens when you mine gold (but the analogy is not the most obvious one you probably thought about). The article describes the gist of this point of view to programming and depicts the connection to mining.

The difference between programmers and common herd

Unlike the IT guys, like me and you, people aren't that excited with programming. Connecting and arranging components of an upcoming system on a blackboard is not an inspiring activity for them. They don't cheer when they manage to write a function in a curiously small number of lines. They have no possibility to settle back, satisfied, and smile, when the program works outright after the first compilation without need to debug it.

But the world is somehow arranged in such a way that these insensitive people nevertheless are those who pays us money! What programming is valued for by them is that it's a good way to solve problems. These problems are usually beyond those a human can handle, and you usually need a horde of zombies to tackle them.

However, problem solving is approached differently by those who can code and those who can't. The management of a non-software company usually needs to do something concrete, like being able to fill forms M-186 and P-337b through the web browser. After they find out that such an automated system would help to run the business, they assign their IT guys to the task. They actually don't care how beautiful the code will be, how much satisfaction will the IT crowd have. They have a problem, and they need a solution.

Sorting ten cards

Assume you are given the task to sort 10 cards... You could write code like this...

But I am sure that there's no one who calls himself a programmer and does it this way. The code's too inefficient, impossible to maintain and can't be written without help of an external program.

So you end up writing something like this (that's a Bubble sort):

But let's reckon the original task. It was, let me remind, to sort ten cards. But it happens, that to sort ten cards you literally have to write a somewhat complex program, which sorts any number of cards. You can't write 10-element sorting without writing any-number-of-element sorting!

In fact, the fact stated in previous paragraph explains the crucial difference that prevents others from understanding that programming is hard. They think like "what is so difficult in sorting ten cards?" "You could just ... what's the word?.. Um, ah! Hardcode the form M-186 onto the webpage and collect results into a database!" They can't understand that you need to create a program, which is close to processing any form, in order to do it only for two forms.

This is the evidence of the idea that programming a solution to a particular problem is always nearly as hard as programming the solution for a general one.

Boon or bane?

The downside of a tendency of "programming" to solve problems more general is that people don't understand how sorting ten items may be so hard. Books are written about it (reckon Don Knuth's "Sorting and Searching" TAoCP book?). Research is held about it (new sorting methods are still developed to solve ever increasing number of edge cases and to handle specifically ordered arrays effectively). But, hell, any kid can arrange ten cards in the order of increasing value! He can't devise an algorithm of doing it for N cards, but we didn't ask for N, did we? Thinking like this, most people just can't understand what's so hard, and seem to value the art of sorting less than it really deserves. Let alone the other crafts of programming.

On the bright side is the possibility to recycle the waste of programming. Once you've written a sorting function for array of 10 cards, it takes you just to increase the array size to make your program sort a lot of cards. Of course, if you wrote an Ω(n²) sort, like I did in the example above, it won't scale that well, but we assume you picked a better solution to the initial problem. So now you have a program that can sort any array.

Creating such residue is inevitable. We have a good analogy in the other fields: the one who extracts oil should also extract the accompanying gas, build facilities to handle it and make the site protected from accidents that involve gas. In the very same way, a programmer is doomed to produce programs that are more general, and he should be aware that it's just more hard.

This property has even been a source of jokes. Alex Exler in his "Notes of a programmer's bride" (oh, I re-read that and fixed the description that follows) describes a situation that a programmer spent a day to write a program that prints invitations to his wedding. The bride bragged that her husband has such a good and a very useful profession. The man she bragged to questioned if it was easier to just fill them manually in a text editor, and after bride's reply about "generalization", he astonished her with, "Yeah? So how many times are you going to get married?"

Conclusion

Back to a programmer's residue. Brooks in his famous "Mythical man-month" claims, however, that producing a reusable component takes three times greater effort than producing the non-reusable one tied to a specific task. Most programs that don't have such a clear abstraction as array sorting, are far more tricky to be scaled to greater inputs without effort.

But that does not contradict the main idea that you can't evade producing residue. The raw "general" residue programming leaves after solving a particular problem is useless, just like in gold mining. To concentrate the ore, you must put effort into doing it, and to get some product from the residue, you should work more. And that's what happens when we write programs. So, isn't programming a gold mining of sorts?

I was trying to invent the way for GNU Make to depend on contents of files, rather than on timestamps.

If what was implied is the content change between consequent make invocations (i.e. target should not be remade, if timestamp has changed, but the content did not), it's easy. Prototyped in my own Stackoverflow answer, the solution was simple:

content=.md5-$1-$(shell md5sum <$1 | sed 's/[[:space:]].*//')
define track
$(call content,$1):
        rm .md5-$1-*
        touch $$@
endef

$(eval $(call track,foo))
$(eval $(call track,bar))

all: $(call content,foo) $(call content,bar)
        ...

However, then I tried to solve more common use-case. The file gets updated, but if after update its content didn't change, then treat it as if it wasn't updated. I think it's impossible.

An only way to achieve it is to make makefile rebuild itself after such update. But it means that makefile should depend on this file, and this way the file will be rebuilt at each make invocation, regardless if it's really needed in this particular case.

In other words, once make established its plan of action, chose what targets will be rebuilt, nothing can change this plan. The targets will be executed in an order picked, and nothing that happens during the run will make the order or the set of them change.

And that's virtually the most important and the most restrictive make limitation. When I write my own build system, I'll make it powerful enough to solve this.

And for now, let's keep tracking timestamps, or search for better tools.

A year ago I've completed my first "scientific" paper. I presented it in a local conference for junior researches. It actually didn't have much effect: as far as I understood no one at the conference was into the subject (ah, no, I'm wrong, there was one guy who developed boost::build). I wanted to fix it (since it contained minor bugs) for a very long time. But since I haven't done it, then, I suppose, I will never manage to fix it.

So here it is. A pdf text is available online freely, and there's even a ppt presentation.

Small abstract: it aims to describe why C++ libraries may lose binary compatibility. It also analyzes if certain compatibility restrictions may be relinquished if the user of the library is only allowed to use a subset of C++ by library's specifications. No one did such analysis before.

The paper is also a somewhat successful attempt to analyze C++ with scientific method. It appeared that this language is not eligible for such analysis, since it's just too huge. But anyway this is the most complete--and thus the most useless--compatibility guide. It was quoted by GCC folks in their manual, but that's an only known reference; and I have no idea how they found my article.

The developer of ABI Compliance Checker used the knowledge gained during this study, and this checker happens to be a working tool. This proves that my studies haven't been useless or erroneous.

Well, on this weekend I'm committing another article to a conference; and I hope it will be less useless to the world. Wish me luck.

Imagine that you have a project of a medium size, and you need to add a couple of functions to it. The whole system is a complex program, and is debugged by printing traces to a log file. So you've implemented a half of the new functionality, and you'd like to check if that half works more or less correct. Of course, you have a couple of your personal test cases and know how should the resultant execution trace look like. But the problem is that part of your system is a stub, and you can't get the desired trace, when an important part of system is not actually doing anything.

Another case: you have a program that runs in a complex environment, and you want to check how program operates when a series of similar queries to this environment yield specific output. You can, of course, implement a proxy that mimics the desired behavior, but you're lazy, and want to do it faster.

In other words, your program queries the environment or the unimplemented module (we'll treat them equally from now on), and you want--for debugging purposes--to make these queries return specific values without spending too much time for implementing a stub for a query handler. This can be achieved with what I call randomized debugging.

Two kinds of modules

There are basically two kinds of modules.

A module of the first kind yields as its output a "tricky" data structure that has complex constitution. If it is such function that is unimplemented in its stub the structures should should be restored keeping all their complexity and consistency. In this case, you really don't have a choice and consider creating a full-blown proxy to mimic its behavior.

In the other case, it's different. A module of a second kind is complementary to the one described above. As its input it gets a complex structure that contains a lot of data. And it behaves as oracle: its result is of a type with a small value range; say, a boolean. The modules of two kinds can behave in a nice pair, as shown on the sidenote picture.

No wonder that such a boolean, provided it is not to flag an "exception" of sorts, branches the program execution dramatically. And it is a specific series of values of these booleans returned which we want the stub to yield, as said in the introduction.

However, since the algorithm is not very simple, and a lot of different factors influence the output (remember, input data are complex!), it would take too much time to implement a stub precise enough. First, we should parse the input correctly. Then, we need to implement a state-machine that remembers what had been queried before and picks up the next result. That's too complex, while we need a fast solution.

The solution proposed is simple. Just replace the unimplemented function with a random number generator. Then run the test several times until the execution trace fits the desired behavior.

"Fuzz testing"? No.

Note, that this is not for testing. This is for debugging; the system is still in not a good shape to test it. Unlike the similar "Fuzz testing" technique linked to by silky in comments (it is to use [semi-]randomly generated data as test input) the randomized debugging achieves different aims. While the former aims catching the untrodden execution paths, the purpose of the latter is to make an unimplemented module to process the given tests correctly in one out of several runs.

The other, "unlucky" runs, when the random generator didn't hit the desired result, might be of some value to the developer, but that's not the aim of the whole thing. For "Fuzz testing" such tests are of primary value, as its aim is to make the program trigger extreme cases. The aim of randomized debugging is to make a system without parts execute as desired with little effort, at least, sometimes.

Where randomized debugging works best

Of course, it's not that good if the function is called several times, and thus you may spent quite a time running the test until it goes well. However, certain programs fit the idea of randomized debugging well. These are the systems that run in a loop, which is terminated when an unimplemented module returns a correct result, the wrong result doing no harm to the processes you want to check.

And of course, the less times the unimplemented subroutine is called, the more effective randomized debugging is. If you call it only twice, and it returns boolean, you'll get the correct execution path in 1/4 cases, no matter if your program is organized in the specific way described above.

Conclusion

Certainly I'm not the only one who noted such a simple way of debugging programs. I'd be glad if you provide links to the similar stuff. But whatever, it's simple and uncommon approach to rough debugging, so it's worth being a blog post. Let alone that at work I successfully used it a couple of times.

Comments imported from the old website