Reflection in C++?

January 12, 2012

I always thought that there is no reflection in C++ because the latter is totally native. But come to think of it, C++ already has RTTI, so why not add member pointers together with names and metadata to type_info?

Come and join!

July 22, 2011

History Q&A site
This History Q&A site will open when 87 more people to promise to participate.

Who wrote what in a Wikipedia article?

July 2, 2011

Wikipedia is a great knowledge base, but sometimes you want to check the truthfulness of what you read. One way is to find out who wrote a particular word or phrase.

Programmers already have tools that annotate code and show who wrote or last changed a specific line. They are called “Blame” or “Praise”. So why is there no such tool for the Wikipedia? One reason is that retrieving all versions of a particular page can be a very long process, e.g., the article “United States” is 700 KB large and has tens of thousands of versions!

Nevertheless, I’m making such a tool. It will be a Web site. I expect to launch an alpha soon.

Suggestions for a name are welcome.

Grassroots traffic laws

November 6, 2010

There are several ideas I want to blog about. One I heard recently at lunch:

Traffic is governed to a large extent by norms rather than laws.  Then why not let the public that creates those norms also enforce them?

He didn’t know how to do this, so I suggested creating a communication system between cars, where a driver can send signals to another driver. (The current communication system, honking, is very primitive, since there is only one signal, and it’s not explicitly addressed to a certain car.) The signals should go through a centralized system, and it should register a certain kind of signal (let’s call it “F you”). A driver that gets above, say, 10 Fs a month gets fined. If he gets very many Fs in a month, his license is invalidated.

What do you think?

Hamiltonian Handicap

July 27, 2010

Today I present the simulation “HamiltonianHandicap” (download), a case of the Handicap Principle. HamiltonianHandicap is one of the more intuitive cases of HP, based on the work of William Hamilton: The advertisement (handicap) costs almost nothing to a healthy male, but is very costly to an ill male. Here is an example given by Richard Dawkins:

[…] think of the spectacularly long tail of a male bird of paradise. […] A common symptom of disease in a bird is diarrhoea. If you have a long tail, diarrhoea is likely to mess it up. If you want to conceal the fact that you are suffering from diarrhoea, the best way to do it would be to avoid having a long tail. By the same token, if you want to advertise the fact that you are not suffering from diarrhoea, the best way to do so would be to have a very long tail.1

The Handicap Principle, when applied to choosing a partner, is similar to Sexual Selection in that both are self-sustaining. The difference lies in the way the self-sustaining loop emerges. In ordinary sexual selection, females first start favoring males with a trait because that trait is advantageous in and of itself, but can keep doing so even when the trait becomes disadvantageous. With the Handicap Principle, females start favoring males with a trait because it communicates their quality (not because it’s disadvantageous — that’s a misunderstanding). Therefore, it is interesting to start with only a small percentage of advertising males and selective females.

In this sim, each animal has the following genes:

  • sex
  • health (true = healthy, false = sick)
  • advertise (true or false)
  • partner selection strategy

Health and advertisement are only expressed in males, selection strategy only in females. A female sees whether a male advertises, and if yes, whether he is healthy or (genetically) ill. That is, she sees one of three possibilities. The selection strategy is represented by a vector of length 3, giving a rating to each of those possibilities. When a female selects among several males, she first selects those males to whom she gives the maximum rating, then among those, one at random. Initially, most females have a neutral selection strategy (all males have the same rating), and a small part have random strategies, that is, they can prefer any of the three visible possibilities, or even more than one — some ratings may be equal.

The survival score a male receives depends on both health and advertisement, and all four combinations receive different scores. The highest is for a healthy non-advertising male. A healthy advertising male receives a very slightly lower score — if his score is much lower, he will prefer not to advertise. The reason I didn’t just give him the same score as to a healthy non-advertising male is that in real life, nothing is free. An ill male, of course, has a lower score, and if he advertises, even lower (otherwise that wouldn’t be a handicap).

The survival of females doesn’t depend on health or advertisement — each female receives the survival score of the average male, so that about half the population are females, and all females have equal survival chances.

Instead of Mendelian genetics, here each animal has only one version of each gene, and each child inherits the gene from one of its parents at random. This avoids the asymmetry between the dominant and recessive genes. There is also a small probability of mutation from healthy to ill, intended to keep the advertisement relevant.

Since selection strategies don’t mutate, it’s important to have a large enough number of selective females initially in order to ensure diversity and to be able to watch the different strategies compete. Therefore, either the population or the initial selectors percentage has to be big. I prefer the former: as I said, I’m interested in emergence.

Graphs: health + advertisement selectors are those females that rate healthy advertising males higher or equally to the other two groups. strict h+a selectors are those that give healthy advertising males the strictly highest ratings. In both cases the ratios are among all selective females. As an extra output after the simulation stops, the variable selection contains the strategies of all selective females, and its statistics are printed.

Technical: This time, the code is not Matlab-compatible, so it will only run on Octave with the “gnuplot” toolbox installed. To stop the simulation, press “Enter” in the command window.

Enjoy. If you have any feedback, I’ll be glad to hear it.

1 Richard Dawkins: The Selfish Gene, 30th anniversary edition, page 306, Oxford University Press, 2006.

Evolutionary models

July 22, 2010

I have found a new hobby: simulating evolutionary models. Mostly I do it in the train on my way to and from work. Yes, you can do a lot in 1 hour a day! And it’s quite captivating.

When I tell people about this, they ask me how I make simulations. Here’s how.

Yes, I program them myself. I use Octave, a free and open-source environment similar to Matlab. Octave supports a large part of the Matlab syntax and library. It also has its own extensions, such as C-like operators. I like to use ++ and +=, but today’s example will be Matlab-compatible.

The example simulates the survival of the fittest, and is only 40-odd lines long.

Here we go:

worldCapacity = 100;
survivalScores = [1 1.2]; % of the 2 types
initNum = worldCapacity;
init2Ratio = 0.1; % The ratio of 2's initially
meanNumChildren = 1;
maxNumChildren = 3;

Our world has a limited capacity — more about that later. There will be two kinds of cells, type 1 and type 2. As you see, type 2 is slightly better at survival.

First, we create our population:

% init
population = [];
for i = 1 : initNum
  population(i) = (rand() < init2Ratio) + 1;

rand() returns a random number between 0 and 1. rand() < p is true with probability p. rand(i, j) returns an i x j matrix.

As you see, initially, only 10% of the cells are type 2.

generation = 0;

ratios = [];
while 1
  generation = generation + 1;

  % show
  ratios(generation) = length(find(population == 2)) / length(population);
  plot(1 : generation, ratios);

  if kbhit(1)

I use kbhit() because Octave doesn’t always handle Ctrl-C well.

  children = [];
  for cell = population
    for i = 1 : maxNumChildren
      if rand() < meanNumChildren / maxNumChildren
        children(end + 1) = cell;
  population = [population, children];

As you see, reproduction is asexual. With maxNumChildren large enough, the distribution becomes close to Gaussian, but that’s not today’s point.

  scores = survivalScores(population);
  prob = scores * (worldCapacity / length(population));
  survive = rand(1, length(population)) < prob;
  population = population(survive);

Our world has limited resources and can host only about worldCapacity cells.  So they have to compete for survival. There is no absolute survival in this model, i.e., if a cell is in the world alone, it won’t die. The reason a cell can die is that someone else is better at getting resources from the environment.

Most of the time I don’t use absolute survival at all. The reason to use competitive survival rather than (only) absolute survival is that with absolute survival, unless you calibrate the probabilities very well, you population will either die out or explode, making your simulation slow and eating up too much memory. The other reason of course is that in the real world, resources are indeed limited.

Competitive survival works like this: Each organism gets a survival score. They are then all multiplied by the same multiplier, such that their sum becomes worldCapacity. The products are survival probabilities. Of course, if a “probability” is greater than 1, the organism surely survives. This may be a little unnaturalistic and also gives the population a bias towards an underpopulated world.

What next? The next step is to download the whole program and run the simulation!

Launching the webcomic

April 20, 2010

The third time I scream / is a charm. Since I’ve drawn the third comic, it’s time to officially declare it a webcomic with a separate feed.

I hereby present Ad absurdum, the webcomic.

The Golden Rule

April 11, 2010

Prisoner of Conscience

April 3, 2010

VETO: A riddle

March 13, 2010

For the last several days, trains in Israel have been showing gibberish instead of station names:

(That’s YWLEO and :PINIPD)

So what station names are encoded here, and how does the encoding work in general? Hints: the encoded words are in Hebrew. There is a slight irregularity in the code.