What goes on in Andy's head - warning, extreme geekiness.

[andrewducker]

A few days ago I was waiting for something or other to get sorted before I could proceed with the current round of bugfixing (the latest project is very nearly done) when I got into a discussion with channelpenguin about the syntax of the for statement in C#. She was complaining that it felt wrong - it didn't really fit with any other statement in C#, what with having semicolons inside brackets. In fact, the for statement was the one I kept having to check the syntax of when I first started using C#, so I could sympathise with her.

The syntax is:

for (initialisers; expression;iterators)
{
    Stuff();
}

for instance:

for(int myInt = 0;myInt < 5;myInt++)
{
	Console.WriteLine(myInt);
}

meaning "Create an integer. Set it to zero. While said integer is less than 5, output it to the console and then increment it by one."

Now, I thought about how you could write the for statement differently, and I couldn't think of one that was any clearer without expanding it out entirely into its equivalent while statement. Which looks like this:

int myInt = 0;
while (myInt < 5)
{
	Console.WriteLine(myInt);
	myInt++;
}

In fact, the more I thought about it, the more it seemed likely that the for statement was just a macro - and at compile time the for statement was translated into the equivalent while statement, and _that_ was compiled - so that the original syntax statement above would become:

{	
	initialisers;
	While (expression)
	{
		Stuff();	
		iterators;
	}
}

(the braces around the entire of the expanded statement are to make sure that any variables created in the initialisers are local to that code segment)

Fortunately, Visual Studio comes with a neat little disassembler (ILDASM), so I compiled the two above bits of code and they both came out exactly the same, as:

 .locals init ([0] int32 myInt)
  IL_0000:  ldc.i4.0
  IL_0001:  stloc.0
  IL_0002:  br.s       IL_000e
  IL_0004:  ldloc.0
  IL_0005:  call       void [mscorlib]System.Console::WriteLine(int32)
  IL_000a:  ldloc.0
  IL_000b:  ldc.i4.1
  IL_000c:  add
  IL_000d:  stloc.0
  IL_000e:  ldloc.0
  IL_000f:  ldc.i4.5
  IL_0010:  blt.s      IL_0004
  IL_0012:  ret

which gave me a warm glow inside. It's nice to be right about something, especially when you're just stabbing in the dark.

Of course, I'm now curious about .NET's Intermediate Language (which is what that stuff at the end is). So possibly a look into _that_ is in order next.

[Poll #705445]

Comments

[wychwood]

...for given values of "understood", at least :)

[andrewducker]

I enjoy reading all sorts of stuff that I only partially 'get', because it reminds me that I don't actually know that much in vast areas of knowledge.

[jccw.livejournal.com]

Yes, C style for loops are counterintuitive... better than "goto", but not much.

Does C# have C-style break and continue? If so, I think the translation no longer works since "continue" in a for loop runs the iterators again but in a while loop they will be skipped. (The fix is to translate "continue;" to "{iterators;continue;}"

[andrewducker]

Yup, it does both break and continue. I had to check whether it did continue, as I've never had to use it.

I have to admit that the majority of the time I have foreach rather than for, which is much more intuitive to use. But sometimes for is necessary.

[figg.livejournal.com]

In dylan for instance, for is implemented as a macro, but you coudn't implement this as a macro in C due to the preprocessor being crap.

Also, the reverse translator for the Psion 3a (REVTRAN) had an option to turn p-code back into while loops or for loops.

[figg.livejournal.com]

Here is the annotated dissasembly of the .net program. (I was curious about what the instructions were, and so looked them up, and I thought i'd share the below)

To cut down on words: #0,#1,... refer to the local variables 0,1,...
                      $0,$1,... refer to the first,second,third items
                      in the stack

.locals init ([0] int32 myInt)

# initialisation, set up counter in #0 at 0.
        IL_0000:  ldc.i4.0              # Push 0 (int32) onto the stack
        IL_0001:  stloc.0               # Pop $0 off stack (0) and store in #0
        IL_0002:  br.s       IL_000e    # Jump to TEST

# loop body. Increment #0 by 1, and call WriteLine.
LOOP:   IL_0004:  ldloc.0               # 
        IL_0005:  call       void [mscorlib]System.Console::WriteLine(int32)
                                        # Write stuff!
        IL_000a:  ldloc.0               # Push #0 onto the stack
        IL_000b:  ldc.i4.1              # Push 1 (int32) onto the stack
        IL_000c:  add                   # Pop two numbers, add, push result
        IL_000d:  stloc.0               # Store result (top of stack) in #0

# Test for exit condition.
TEST:   IL_000e:  ldloc.0               # Push #0 (counter) onto stack
        IL_000f:  ldc.i4.5              # Push 5 (int32) onto stack
        IL_0010:  blt.s      IL_0004    # If counter ($1) < 5 ($0) 
                                        # jump to LOOP:
                                        
        IL_0012:  ret                   # return to caller

[call-waiting.livejournal.com]

If the compiler is anything like halfway decent, so long as your programs have the same semantics, it should produce the same object code. Which I guess is to say that the object code is a result of the semantics of the code rather than the syntax, so you can't necessarily infer anything about the syntax (or meta-syntax, in the case of 'X is a macro of Y') of the language from the object code.

In this case it's not quite a macro, for reasons pointed out elsewhere. Unless C# happens to have python-style 'continue' blocks, in which case it'd map to a macro that spans the entire for loop and places a 'continue' block at the end.

The reality of the situation is more likely to be that the compiler recognises the syntax of the for (;;) loop independently of the syntax of the while() loop and translates them both to equivalent structures in the compiler's intermediate representation.

The real thing that's abhorrent about the C 'for' construct, from my point of view, is that (syntactically) there are three statements, with entirely different usage semantics, but visually entirely undistinguished from each other except by position. You can remove the code inside the '()' and drop it elsewhere in a program and it'll be a syntactically valid sequence of statements. Same code, entirely different semantics. A sensible syntax would identify them independently in some way.

The only thing that 'for(;;)' has going for it over a plain and simple 'while ()' is that it lets you put that S3 up at the top of the loop body rather than at the end. If it wasn't for that... its days would be numbered.

[0olong.livejournal.com]

"S3"?

[figg.livejournal.com]

for (S1;S2;S3) { }
in a while, you have to put S3 (the increment.) at the end.

[call-waiting.livejournal.com]

Bingo. I could have sworn I typed 'for (S1; S2; S3)' somewhere in that comment...

[moniqueleigh]

For vague values of "read"... OK, actually, I realized it was C# (which I've never bothered to learn), realized it was a bit of code that looks suspiciously like most of the other languages I have bothered to learn, and then read the rest of the post. And realized that it still made sense in the translation. Yes, yes, I am a geek. *nods*

[0olong.livejournal.com]

For years, I never ever used for in C or Java for more-or-less the reasons you talked about. The whole syntax just seems out of place, it's very odd. I still use while statements almost every time.

[drdoug.livejournal.com]

This is directly inherited behaviour from the granddaddy language C (which happens to be my first language). I'm pretty sure that K & R* says that for and while loops are entirely equivalent in just the manner you describe, with the exception of the behaviour of continue.

(IIRC, continue in a for loop means 'skip to the iterator part' but in a while loop it means 'skip to the test-expression part' - I imagine it compiles to the equivalent of 'goto the closing curly bracket of the loop'... but I hardly ever use continue anyway.)

Interesting to see that for and while loops compile exactly the same in C#, as they should. Fancy a quick test of continue too to see if I'm right?

* Kernighan & Ritchie, "The C Programming Language", the definitive tome on C. Although it is a mere pamphlet by comparison with definitive tomes for other languages.

[andrewducker]

Yup - with "for" continue jumps to the iterator section, whereas with "while" it jumps straight back to the start of the loop. Very different behaviour.

I can, however, make them behave exactly the same by wrapping the iterator in the "while" in a finally block, like so:

int counter = 0;
while (counter < 5)
{
	try
	{
		if (counter ==3)
			continue;
		Console.WriteLine(counter);
	}
	finally
	{
		counter++;
	}
}

which doesn't compile to the same code as the equivalen "for" but seems to have the same effect.

[drdoug.livejournal.com]

Cool - thanks for that, interesting to know. I still don't like continue much, though.

[andrewducker]

Feels too much like "goto"?

[drdoug.livejournal.com]

Partly - but more a vicious circle of unfamiliarity. I don't know it well enough to be totally certain of how it works without double-checking, so I tend not to use it, so I don't get to know it well.

I'm not entirely averse to goto. I've seen some hairy deeply-nested loops where a judicious goto to just get the hell out of there would not be as bad as the morass of continues, breaks and flag variables you need to get round it. Mind you, probably better to turn that section in to a function and just 'return' from the depths, which would transform a mess in to what's widely accepted as perfectly good style - which I think it what I'd tend to do when others might use continue.

[andrewducker]

I've used Exceptions in a similar way - I have this at the top level:

bool passedValidation = true;
try
{
DoSomeValidation();
}
Catch (ValidationException ex)
{
MessageBox.Show(ex.Message);
passedValidation = false;
}

and then I can have twisty-turny mazes of validation nested as deep as I like, and jump back to this level instantly (well, with a 0.1 second lag for exception throwing) as soon as I hit something that's invalid.

[drdoug.livejournal.com]

I'm sure that's the Right Answer these days. I had a slight nervousness at the performance overhead of a function call - which is so last century.

[andrewducker]

It certainly is. I just knocked together a quick test application. For 1,000,000 iterations a simple bit of code took 0.002 seconds without a function call and 0.021 seconds with it. Which means that the difference is 0.019 seconds per million function calls.

Should you be worried about that kind of performance loss then you will want to optimise for it. Personally, I'm not running that kind of app - I suspect I've spent more time typing this reply than I'll ever save in my life through optimising away function calls.

[drdoug.livejournal.com]

TBH I'm surprised the difference is that large. And as you say, for most applications that's so trivial to be not worth bothering about, but if you are worried about it you should optimise for it.

So if, say, that code was in the main loop of your Shiny New Brute-Force Sudoku Solver, an order of magnitude improvement would be well worth having. (Although you still have another half-dozen or so orders of magnitude to somehow knock off the computation time to get it complete before you die. Ah well.)

The key, as ever, is recognising the one situation from t'other.

The right sort of optimisation can be an astonishing thing to behold, particularly when the function call you're optimising away is to an API. I once wrote some code to display large 2D datasets on screen. My initial attempt simply handed each data point (suitably scaled) to the drawing API in turn and told it to draw a line to there from the previous point. It took more than 10 minutes to refresh the screen on a smallish test dataset - not good when a key point of the app was to be able to fly around in the data. So I optimised by tracking the highest and lowest point for each horizontal pixel before handing it to the API, and bingo - pretty much instant, even for the larger datasets I was using.

[andrewducker]

I suspect modern graphics cards would giggle at your datasets and do them with ease.

But that was then, etc.

I know what you mean though, optimising the right things in the right way can dramatically speed things up. I sped up some code a while back by two orders of magnitude by storing trimmed values for text rather than trimming it when it was being compared. Who knew that trimming text took so long?

[azalemeth.livejournal.com]

Ever heard of the GCC funroll-loops optimiser? (i.e. gcc --funroll-loops -M2 -[required other options] foo.cpp)

If you compile a for loop "as is", you have to have (and this is in english I'm afraid, as my x86 assembler consists of 'NULL'...) basically [initialisers] [check] [do something] [check condition] [increment] [do something] [check condition] [increment] ... [check condition] [end instruction block], which is functionally the same as what you've just discovered :). The --funroll-loops option "funrolls" the loops, so you get [initialisers] [do] [advance] [do] [advance]....[end], which is a lot faster. Or something like that.

At any rate, for, and while are just GOTO in disguise :).

[andrewducker]

for, and while are just GOTO in disguise :).

To be precise, they're IF and GOTO in disguise.

But then pretty much all programs break down mostly into MOVE, BRANCH and COMPARE commands.

Oh, and how does funroll-loops work with loops that can work different numbers of times?

[azalemeth.livejournal.com]

Badly.

Hence, http://www.funroll-loops.org. It has a nasty tendency to break lots of stuff. Me, I stick to -O2 (second level of optimisations) in 'home' code, and -O1 for important stuff. It's fast enough that you notice the difference, and yet not so insanely optimised that you notice the need to punch in assembler from the front panel.....