C++ evaluation order gotcha

My girlfriend was looking through an introductory C++ programming book the other day, but while she was comparing actual results with expected results, she saw a discrepancy and I was called in to figure out what was going on.

The program is pretty simple:

#include <iostream>

int f(int x, int y)
{
    std::cout << "f()\n";
    return x + y;
}

int main()
{
    std::cout << "Calling f()\n";
    std::cout << "Result is: " << f(3, 4);
    std::cout << "\n";
    return 0;
}

The book indicated that it should print out the following, which indeed it does (using bcc32 6.10, g++ 3.4.4 and cl 9):

Calling f()
f()
Result is: 7

The question my astute girlfriend has is: why is 'f()' printed out before 'Result is: ', when 'Result is: ' appears earlier in the expression? In other words, why doesn't it print out:

Calling f()
Result is: f()
7

... as you might expect, following the logic from top to bottom and left to right?

The answer comes down to how C++'s designers have, in their infinite wisdom, decided to implement I/O. The left shift operator, '<<', is overloaded and so the critical expression gets parsed as a set of function calls, roughly like this:

operator<<(operator<<(std::cout, "Result is :"), f(3, 4));

This is somewhat explained on the MSDN page allegedly describing Order of Evaluation (C++).

So, the most nested things need to get evaluated first, that's pretty unavoidable. Because of the associativity of the '<<' operator, things on the left end of the line get printed first, followed by each successive item.

Here's where the subtlety is, though: that most noble order, C++ definers, have decreed that the order of evaluation of arguments is beneath their dignity; that is to say, order of argument evaluation is undefined.

However, there are some general things we can say about C++ as implemented on x86. It usually defaults to the C calling convention, which pushes arguments on the stack from right to left, in order to support varargs. Since the arguments need to be pushed from right to left, the compiler will generally take a hint and evaluate them from right to left too. That's where our strange out of order result comes from.

Delphi isn't much less guilty on this specific front, however: it doesn't have a standard in the first place, and it also generally evaluates arguments from right to left. That's often more efficient when starved for registers: usually one will want to use EAX, EDX and ECX - the registers available for Delphi in the default calling convention - for purposes of evaluating the excess arguments (if more than three), which will end up pushed on the stack. If the first argument, which will ultimately end up in EAX, got evaluated first, and so on, many valuable registers would be tied up only to calculate values that end up pushed on the stack, no longer needing a register. The alternatives, spilling to the stack or evaluating to a temporary, are wasteful.

However, for the specific instance of I/O - Writeln - Delphi breaks up multiple outputs into separate calls. So, our code, in Delphi:

 Writeln('Result is: ', f(3, 4));

get translated, behind the scenes, into something vaguely like:

Write0LString(Output, 'Result is: ');
WriteLong(Output, f(3, 4));
WriteLn(Output);

... with much less confusion for the beginner.

Procedurally-typed expressions redux

A few days ago I blogged about some issues that the Delphi parser has with certain constructs. A little discussion ensued in the comments, so I think I want to clarify what I meant a little.

Specifically, there were two problems I pointed out:

1. Calling procedurally-typed values in non-trivial expressions
2. Creating procedurally-typed values from no-arg procedures (and functions and methods etc.) that appear in slightly non-trivial expressions.

The first problem can be solved by interpreting the appearance of an argument list (introduced by '(') in an expression as an attempt to call what is effectively the left hand side of the '(' operator. The second problem can be solved by more deeply analysing the expression tree during argument processing so that it isn't confused by something as simple as an extra set of parentheses. The first problem is more pressing as it's affecting certain features I'm trying to get into the product.

Nothing will be imposed. There will be no breaking changes in syntax or semantics, if it can possibly be helped. All that should change is that previously invalid code becomes valid.

While there is an ambiguity when looking at some hypothetical function to a function to a function, where, when calling f()(), it might appear unclear from the rules which function is being called, this syntax is currently not valid at all. Currently, the first set of parentheses is parsed as part of the first call to f, but the attempt to call the return value (of type function to a function) will fail. Extending this so that the second call succeeds shouldn't be problematic, because there's a simple rule: the '()' on a no-arg function is optional, but it will be parsed if it's found. It can't be "delayed", such that the raw 'f' is interpreted as a function call and then the '()' applied to the return value. The parser eats the tokens when it sees them and it has a rule for matching them.

The further testing I did for this post exposed another problem, potentially more severe than the others - it's a type hole:

{$apptype console}
{$T+} // you'd like typed-@ to help you here, but it doesn't...

type
 TF = function: Integer;
 PF = ^TF;

function MyF: Integer;
begin
 Result := 42;
end;

// P is separate procedure so 'f' stands out as a stack variable
procedure P;
var
 f: TF;
 x: PF;
 // use absolute to get around oddities of procedural types
 f1: Integer absolute f;
 x1: Integer absolute x;
begin
 Writeln('MyF is at ', Integer(@MyF));
 Writeln('f is at ', Integer(@@f));
 f := MyF;
 Writeln('f is pointing to ', f1);
 x := @f;
 Writeln('x should be pointing to f, but is pointing to ', x1);
 // The following line doesn't do what you'd expect: it crashes.
 // Writeln(x^);
end;

begin
 P;
end.

Unhappily enough, this prints out the following on my machine, with no warnings or errors during compilation:

MyF is at 4211536
f is at 1245092
f is pointing to 4211536
x should be pointing to f, but is pointing to 4211536

The line commented out does in fact crash.

Update: Craig in the comments asks why it's wrong. There are at least two things that could be wrong, and one of the unfortunate problems here is that there's no standard for Delphi beyond what the compiler currently does, so we can't say for sure. Either the '@f' when assigned to x should take the address of f rather than just inhibit calling the function pointer, or it should result in a compiler error - particularly as typed-@ operators are turned on here. The commented out line, x^, ought to call the function pointer being pointed to by x, but it doesn't, since it's simply pointing to the function 'MyF', rather than the function pointer 'f'.

Not a Delphi post: PC Games

A couple of things I saw yesterday got me thinking about games, something I've been meaning to write down my thoughts about for some time. From long-time experience, I've gathered that my tastes in games are somewhat (but only somewhat) off the beaten track, if only because of the lack of market supply for what I like to play.

First off, "PC game" or "video game" etc. is too broad a category to talk about meaningfully, so it needs to be broken up. However, I'm not so happy with the usual division of games into genres like real-time strategy (RTS), turn-based strategy (I'll call this TBS), first-person shooter (FPS), third-person shooter (I'll call this TPS), etc., though sometimes those divisions accidentally coincide with the divisions I have in mind.

I look at games using several axes: the kind of skills being exercised, the depth of immersion and storytelling, and the nature of the in-game stress / release cycle and pacing.

By the kinds of skills, I mean things like strategic thinking (e.g. Civilization - non-repeatable long-term plans to achieve goals), tactical thinking (e.g. most FPSes - repeatable short-term templates of action that solve categories of problems), mastery (e.g. simulation games), hand-eye coordination (twitch games like almost every arcade game, and also including many FPSes, RTSes and TPSes)

By the depth of storytelling, I'm talking about how essential the story is to one's experience of playing the game. Is the story just an add-on to rationalize the gameplay? Is it just very effective atmosphere, made effective by how the level design directly reflects the story? Or is the story essential to successfully playing the game, or perhaps even ultimately user-written, as they make choices in the world? And by immersion, how easily can I forget than I'm at a computer, and instead think of myself as being a character in the game?

When I talk about an in-game stress / release cycle, I'm thinking in particular of how stress builds up in the player, to what degree it builds up, how it is built up, what options the player has to reduce this stress, and the pacing refers to how long the stressful periods are versus the (relatively) relaxed periods. For example, many FPSes have "action bubbles", where lots of bad guys surround some kind of goal than the player usually has to physically get to. If the FPS is heavily corridor-oriented (e.g. pretty much all the Doom games), where there's really only one way to go, then the player will probably have to kill almost every bad guy met, and can only stop for a breather if any pursuing bad guys have been killed off. On the other hand, there may be relatively quiet corridors linking areas that trigger action after a certain point is reached, something done very well by Half-Life (the original).

My favourite games have been Thief series, Far Cry, Deus Ex, Outcast and Civilization 2, roughly in that order. I've enjoyed playing games like Doom, Half-Life, Crysis, Bioshock, Oblivion, System Shock 2, but none of them had the long-lasting appeal to me that my favourites have. I tried to replay Half-Life several years ago, but it didn't take long in-game before I discovered I'd lost my love for it. On the other hand, I've replayed Thief 2 (in particular) pretty much at least once a year since it came out - an older game (older technology-wise as it uses the same engine as Thief 1, which was weak compared to the upgraded Quake engine behind Half-Life, both being 1998 vintage), but one with far more potency for me.

So, coming back to those axes, what do I like in a game? Story and immersion is very, very important, probably the most important thing. Almost all the games above are FPSes, because that's the format which lends itself best to immersion. Civilization is so sparse on the story side - the only real identity you have is as a nation of peoples, rather than a character - that one's imagination fills in the gap. This usually leads to even more identification with the game than a heavy-handed plot, because it's entirely user-driven. Far Cry has the weakest story of the lot, but its immersion is extremely effective - you really do feel like you're on a tropical island, sneaking through the bushes. Far Cry also makes up for the weak story on the other axes. The other games, in particular the Thief series, are strongly story-driven, but they don't lack in the other axes. Deus Ex has a degree of user participation in the story creation, as certain choices you make affect the plot fairly substantially - for example, you can choose to save your brother or leave him to die (which he urges you to do). The music in Outcast is amazing and highly atmospheric. The feeling of being in an Arabic-style souk is pretty strong in the city of Okriana in Talanzaar, and I have visited e.g. the souks of Marrakesh, with that atmosphere coming back to me.

I like to use strategic skills over tactical or twitch skills in games. So, even though Doom can be fun for a 30-minute blast (on a Windows 3D port, with jump and mouse-look in the Y dimension enabled), it's not what gets me hooked. The Thief series' player character, Garrett, is sneaky enough to be able to assess the ground and the disposition of enemies without being seen. The player's job is then to plan and navigate a path through the ground without being seen or heard, within the resource constraints of the gadgets available. A good friend of mine, far and away my better in twitch games like Quake multiplayer, found progressing in e.g. Thief 2's Bank level very difficult - he got stuck and ultimately bored in many situations that simply increased my appetite for the problems. Civilization is all about strategy - there isn't even a constraint on turn time. Far Cry, Outcast and Deus Ex have sufficient freedom of movement that you can usually plan your encounters from afar and engage on your own terms. All things considered, I prefer engaging from a position of strength (usually means being higher up) and unseen where possible. Up-close and twitchy is too risky: I don't like dying in a game, because that breaks my immersion. In real life, there's no way back from death: why should I play my games like it was any different? Evaluating the enemy, navigating unseen to that position of strength and planning the encounter is usually more fun for me than the encounter itself; however, there is the gratification of a plan well executed and performing as anticipated, something very akin to the pleasure of programming. It also turns out that freedom of movement is very important to permitting a strategic approach to the game: strictly linear games like Half-Life 2 almost actively prohibit strategic thinking.

About the stress & release cycle: one is usually stressed in a game because one is threatened with in-game death. There are different graphs one could draw of the typical stress patterns of different games and gaming styles. A game like Doom 3 or Half-Life 2 often rely on "surprises" - quiet areas / dark alcoves which are obvious traps, and the only "surprise" is the exact trigger location or time. This is probably a feature I hate most about some games: knowing that something bad is going to happen, but not being able to control it. Half-Life wasn't too bad, because one had tactical weapons like grenades and strategic weapons like trip-mines wherein action bubbles could be analysed and solved pre-trap-triggering, but Half-Life 2 (and especially Doom 3) used such cheap tension tactics that I stopped playing the games in disgust. These games often have a ::^^::^^::^^:: kind of tension graph: medium tension interspersed with high tension. On the other hand, a game like Thief 2 looks more like ..:..:..:^^.^^.^^:...: lots of low-tension observation, occasional medium-tension moments when encountering danger areas while scouting, followed by a long stretch of alternating high-stress navigation and resting safely in shadows. The key is that the player has control over the resting and the initiation of the next high-stress section. I far prefer games where I have control over the stress level pacing and have time to consider my options before proceeding.

If you've read this far, well done for putting up with me! I just wanted to get those thoughts out of my head, but if it's been interesting to someone else, then that's gravy.

Odd corner of Delphi: procedural expressions are not expressions

Here's an odd corner of Delphi: expressions of a callable type (e.g. a function pointer or method pointer) are not fully-fledged expressions; or rather, the expression grammar for function application doesn't acknowledge function pointer types as proper first-class parts of the type system. For example:

type
  TFoo = procedure(x: Integer);
  TBar = function: TFoo;

var
  bar: TBar;
begin
  bar(42); // doesn't compile; too many args for TBar
  (bar)(42); // doesn't compile; bar's value doesn't flow through
  bar()(42); // still no good; bar()'s value doesn't flow through
  (bar())(42); // again, no good, for same reasons as previous two
end.

The reasons are probably directly related to two things: the historical lack of general function pointers in Pascal and the rule that no-argument procedures can omit the parentheses.

The following are valid expressions that call the function pointer, but the resulting value can't be invoked in turn:

  bar; // ok: return value dropped
  bar(); // ok: return value dropped

The above results in some serious drawbacks if one wants to program Delphi in a functional style. Currying can't work, for example: there's no way you could turn foo(1, 2, 3) into foo(1)(2)(3), since the latter syntax isn't valid.

I personally consider it a bug, but this behaviour, at the heart of expression parsing, is tricky to fix while guaranteeing not to break anything that already works. For example, there are other odd semantics around these Delphi function pointers:

type
  TFrob = function: Integer;

function MyFrob: Integer; begin Result := 42; end;

procedure Baz1(x: TFrob); begin end;
procedure Baz2(x: Integer); begin end;

procedure BazO(x: TFrob); overload; begin end;
procedure BazO(x: Integer); overload; begin end;

begin
  Baz1(MyFrob); // passing MyFrob
  Baz2(MyFrob); // calling MyFrob and passing result
  BazO(MyFrob); // guess which?
end.

The above call to Baz1 is currently handled, believe it or not, by parsing as a function call and then later, in the middle of function application, throwing away the call bit and turning it back into taking the address of the function. You can see this by hiding the function call just a tiny bit, so the function application logic can't see it so easily:

  Baz1((MyFrob)); // no longer passing MyFrob

The lesson to me in the above case is pretty clear. If you want to have function pointers in your language, you shouldn't make function application look like a function value - that way madness lies. This is why the '@' operator was invented:

  Baz1((@MyFrob)); // works again; passing MyFrob

Unfortunately, its use in Delphi for these cases is optional.

The two issues discussed in the above post are distinct. However, I may need to fix the first one in order to get certain features into the product...

Lang.NET Symposium videos are up - in WMV

The Lang.NET symposium videos are up, but the user interface over there is pushing Silverlight. The videos are actually in WMV format. The URLs are hidden in StartPlayer.js. If you want to avoid having to install Silverlight, these urls should do (mind the spaces):

http://langnetsymposium.com/talks/Videos/1-00 - Keynote - Jason Zander.wmv
http://langnetsymposium.com/talks/Videos/1-01 - CSharp3 - Anders Hejlsberg.wmv
http://langnetsymposium.com/talks/Videos/1-05 - Lively Kernel - Dan Ingalls - Sun.wmv
http://langnetsymposium.com/talks/Videos/1-06 - JScript - Pratap Lakshman.wmv
http://langnetsymposium.com/talks/Videos/1-07 - Irony and ERP Language Challenges - Roman Ivantsov.wmv
http://langnetsymposium.com/talks/Videos/2-00 - Democratizing the Cloud with Volta - Erik Meijer.wmv
http://langnetsymposium.com/talks/Videos/2-01 - Newspeak - Gilad Braha - Cadence.wmv
http://langnetsymposium.com/talks/Videos/2-02 - Resolver One - Giles Thomas - Resolver.wmv
http://langnetsymposium.com/talks/Videos/2-03 - Retargeting DLR - Seo Sanghyeon.wmv
http://langnetsymposium.com/talks/Videos/2-04 - Visual Basic - Paul Vick.wmv
http://langnetsymposium.com/talks/Videos/2-06 - PHP - Wez Furlong.wmv
http://langnetsymposium.com/talks/Videos/2-07 - Phalanger - Tomas Petricek.wmv
http://langnetsymposium.com/talks/Videos/2-08 - Pex - Peli de Halleux.wmv
http://langnetsymposium.com/talks/Videos/2-09 - Numerical Computing with the CLR - Jeffrey Sax - Extreme Optimization.wmv
http://langnetsymposium.com/talks/Videos/2-10 - remotion Mixins - Stefan Wenig and Fabian Schmied - rubicon.wmv
http://langnetsymposium.com/talks/Videos/2-11 - CodeIt - Serge Baranovsky - submain.wmv
http://langnetsymposium.com/talks/Videos/3-00 - IronRuby - John Lam.wmv
http://langnetsymposium.com/talks/Videos/3-01 - Ruby.NET - Wayne Kelly.wmv
http://langnetsymposium.com/talks/Videos/3-02 - FSharp - Luke Hoban.wmv
http://langnetsymposium.com/talks/Videos/3-03 - Parsing Expression Grammars in FSharp - Harry Pierson.wmv
http://langnetsymposium.com/talks/Videos/3-04 - NStatic - Wesner Moise - SoftPerson.wmv
http://langnetsymposium.com/talks/Videos/3-05 - Moonlight and Mono - Miguel de Icaza.wmv
http://langnetsymposium.com/talks/Videos/3-06 - Visual Studio Shell - Aaron Marten.wmv
http://langnetsymposium.com/talks/Videos/3-07 - Modeling and Languages - Don Box.wmv
http://langnetsymposium.com/talks/Videos/3-07 - Modeling and Languages - Don Box_1.wmv
http://langnetsymposium.com/talks/Videos/3-08 - Cobra - Chuck Esterbrook.wmv
http://langnetsymposium.com/talks/Videos/3-09 - Intentional - Magnus Christerson.wmv

You didn't read it here :)

Edit: As nbrooks commented, you'll need to install the WVC1 codec to view the videos (if you haven't actually installed Silverlight). You can get it here: http://support.microsoft.com/kb/942423