tag:blogger.com,1999:blog-182414822024-03-06T22:21:33.033-08:00Programming and Debugging (in my Underhøøsen)Mostly C++ and D stuff... from the maker of <a href="http://zerobugs.codeplex.com/">ZeroBUGS</a>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.comBlogger120125tag:blogger.com,1999:blog-18241482.post-52453532581263905302013-01-13T21:12:00.000-08:002013-01-14T16:49:42.900-08:00I'm Coming in With the FlagI got so excited about my success with <a href="http://the-free-meme.blogspot.com/2012/10/hackenbraten-native-xinput-support-for.html">modding Sauerbraten and adding XInput support</a> that I decided to add the gamepad code to AssaultCube as well. Because Cube1 and Cube2 engines are similar in many ways, doing so was a breeze (took me a bit to figure that the Y axis is reversed in AssaultCube but other than that it worked great). Since my last post I also made some enhancements to the controller code, such as the ability to bind buttons and triggers to arbitrary script code. Actions can now be bound to the analog trigger half-presses which is extremely useful for engaging the aim-assist code. Yeah, I wrote my own aim-assist to compensate for the game controller's lack of precision and maybe it is best I do not elaborate any further on that, the fine line between aim assist and aim bots being a controversial one.<br />
<br />
Controller in hand and cold beer in reach, I sat down for a single-player session of AC only to realize that the AI is not as capable as Sauerbraten's and the bots have many limitations. For example they cannot play Capture the Flag (CTF) and cannot navigate the underground sewage system in the <i>ac_aqueous</i> map. It also seemed a little strange that the AC bots use a configuration file with a syntax of its own instead of using the powerful Cubescript language.<br />
<br />
I could not pass the challenge and decided to look into writing my own AI code. I have never tackled this kind of stuff before. As a professional programmer I worked with compilers, debuggers and touched databases; I worked for Amazon.com and for Microsoft (yeah, I did write a few thousand lines for Windows 8, guilty as charged). But I have no game development experience, aside of a lame <a href="https://skydrive.live.com/redir?resid=497FC64FB6C9AE55!154&authkey=!APG-AluG9Rr03mc" rel="nofollow">Python implementation of Reversi</a> I wrote a few years back.<br />
<br />
Naturally I got very excited about experimenting with an AI system. My goal was to come up with playable, good-enough code that could coexist with the current AI. I did not want to overhaul the entire bot code and disturb other parts of the game that depend on it. I just wanted to add a side-by-side AI, and I must admit the thought of having the two AIs fight each-other while I spectate crossed my evil mind. I aimed for keeping the code small and compact, in the minimalist tradition of the Cube engines.<br />
<br />
I decided to use a waypoint system for navigating the maps, similar to what the existing bots use. I am aware that better systems can be devised (<a href="http://www.ai-blog.net/archives/000152.html">http://www.ai-blog.net/archives/000152.html</a>) but I wanted to keep the code very simple. The waypoints are created by a greedy algorithm that tries to span trees to cover the entire map using a collision detection scheme. A second pass ads a few more edges and attempts to connect together unconnected sub-graphs. This work is not spread across several frames so depending on how fast (or slow) the computer is the game may seem to "freeze" for a short moment when it loads the map. I added a variable named <i>wpxautosave </i>which when set causes the waypoints to be written to a file named the same as the map (plus the .wpx extension). This file is automatically loaded if present, so the short "freeze" inconvenience can be alleviated this way. I preferred this over a more complicated code that spreads the work over several frames.<br />
<br />
The problem I grappled with for many weekends is that using the game physics for collision detection is not a precise business. Trying to move the player's character on all possible edges in order to validate them is expensive. Cutting some corners (pun well intended) may yield graphs that are incorrect and cause the AI to bump into walls. On the other hand, being too conservative may end up in disconnected graphs. I decided to go with a hybrid approach were waypoints can be generated automatically (with a somewhat conservative take on collisions) but also manually, by running over the map and dropping waypoints in Sauerbraten's style. This way, if I have time to kill I can make my own waypoints (manually and accurately) for a given map, or if I just want instant gratification I let the machine generate them, and more are added as I play. The latter approach has an interesting side-effect. As new waypoints are added, the bots appear as they "learn" new ways around the map. I added a variable (exposed to the user via Cubescript) to limit the growth of the graph, and thus the computational effort required for path finding during game play.<br />
<br />
The bots use the Dijkstra algorithm for their path finding instead of A*. I thought this was more convenient in situations where they are not interested in finding their way from point A to a specific point B, but rather to the nearest of any points that satisfy certain criteria (any health pickup, or any Kevlar or helmet, or any ammo pickup, for example).<br />
<br />
I wrote the code using Visual Studio 2010 to take advantage of the <a href="http://en.wikipedia.org/wiki/C%2B%2B11#Lambda_functions_and_expressions" rel="nofollow">C++11 features that it supports, such as lambda functions</a>. I guess GCC would've worked just fine but these days I have no compelling reason to boot up Ubuntu, thanks to how badly Gnome 3 managed to disgust me; but that's a story for another day.<br />
<br />
Each bot implements a simple state machine in the form of a stack of <i>std::function<void()></i>. The function at the top of the stack represents the current state; when it is popped off the stack the bot returns to executing its previous state. If the stack is empty, it executes an <i>idle()</i> routine. The stack is populated by the <i>think()</i> routine, which sets a long term goal and optionally some short-term goals, following the wisdom of the <a href="http://dev.johnstevenson.co.uk/bots/20585341-The-Quake-III-Arena-Bot.pdf" rel="nofollow">Quake Arena AI</a> design. In a Team Death Match game, the long term goal is to seek and engage enemy units. In a CTF game the goal is to locate and retrieve a flag.<br />
<br />
Because the collision detection is not perfect and because of using a waypoint system for navigation, the bots may get stuck every once in a while. I added some heuristics to resolve the collisions by jumping, crouching, or rotating around the obstacle which so far seems to work well with solid obstacles but requires more future tweaking for things such as link fences or light posts; overall I am pretty pleased with the result and last night I was able to play CTF on <i>ac_aqueous</i> with the bots chasing me through water underground.<br />
<br />
And I could not resist wiring in some sound bytes since they are already present in the game. Your bot team mates will complain when shot at accidentally, or may brag about their kills.<br />
<br />
For the curious and courageous that want to play with the code: first, get the latest AssaultCube 1.2 source from <a href="http://sourceforge.net/projects/actiongame/">http://sourceforge.net/projects/actiongame/</a>. Then get my hacks from my SkyDrive:<br />
<a href="http://sdrv.ms/Rvozms">http://sdrv.ms/VEU0f0</a> and <a href="http://sdrv.ms/VFH0C8">http://sdrv.ms/VEU12G</a> and follow the instructions in the comments at the top of the <i>ai.cpp</i> file. Adapting the code so that it builds under Linux is possible but I have not tried it, VisualStudio 2010 is the only environment under which I built the code. You can also grab the Windows binary file from <a href="http://sdrv.ms/VEUkug" rel="nofollow">here </a>and overwrite your AssaultCube 1.2 (make sure you get the latest bits from sourceforge, the mod may not work with older versions).<br />
<br />
Currently there is not a lot of magic in the bots decision making process. It is by and large driven by their health, armor, ammunition, who they may cross paths with, and plain randomness. I plan to experiment with genetic algorithms once I get a good feel for the quality of the existing code (got a couple of bugs to address before I move on).<br />
<br />
There are other interesting features in the relatively small code (around 2600 lines of C++), such as team collaboration. The bots ask for help when attacked or when going for the enemy team's flag. I could go on and on about how much fun I had with this experiment. But I've a game to play!<br />
<br />
<br />Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-35331939216385437602012-10-17T23:39:00.000-07:002012-10-20T16:51:06.369-07:00Hackenbraten: Native XInput Support for SauerbratenAlthough I've been programming professionally for eighteen years I've very little to no experience with video game development and I always wanted to get my hands dirty messing with a FPS engine. An open source game is a great place to start so I checked out Sauerbraten from <a href="http://sauerbraten.sourceforge.net/" rel="nofollow">http://sauerbraten.sourceforge.net/</a>.<br />
<br />
The rain was back in Seattle this past weekend. An excellent excuse to cozy up indoors and hack <a href="http://sauerbraten.org/" rel="nofollow">Sauerbraten</a>.<br />
<br />
I must say that I am quite impressed with the no-fuss, minimalistic coding style of the authors and by how well the code reads. I was able to find my way around it fairly quickly. As a professional developer I have seen way too many over-complicated code bases, polluted with "clever" design patterns and unnecessary C++ - isms that nobody under an IQ of 300 understands. Heck, I wrote my own fair share of inscrutable C++ templates. Saurebraten's style is all about self-explanatory short functions that focus on the algorithms. The scripting engine is very efficient and elegant.<br />
<br />
Because I type all day for a living when I play videogames I prefer giving the keyboard a rest and use a controller.<br />
<br />
Although Sauerbraten has no native support for gamepads it can be played with controllers that know how to emulate keyboard and mouse events (such as the <a href="http://www.amazon.com/Logitech-940-000106-Rumble-Gamepad-F510/dp/B003VAM392/ref=sr_1_2?ie=UTF8&qid=1350327094&sr=8-2&keywords=logitech+gamepad">Logitech F510</a>, which comes with software for customizing it). This is okay, albeit not the best experience you can get.<br />
<br />
In particular you miss on the rumble / vibration feedback, and shooting things is all that Sauer is all about. There are other potentially cool things such as analog triggers with configurable threshold. And how about some finesse and control the speed of your movement with the thumbstick (move faster when it is pushed farther out)?<br />
<br />
I was curious if I could improve my gaming experience (and maybe learn a thing or two about the Sauerbraten engine in the process). Since I was doing this on Windows 7 and the game engine works on Linux and Mac as well one goal was to make a minimal impact on the overall portability.<br />
<br />
I ended up with a "hybrid" implementation, in the sense that for some gamepad actions I directly interact with the engine (for moving the player I mess with the move, strafe, and velocity data) and for others (such as mouse motion) I just push SDL_Events into the event queue.<br />
<br />
Overall I am pretty pleased with the result. At the high level, the "mod" I came up with consists of:<br />
<ul>
<li>a change to weapons.cpp so that custom actions can be performed upon firing a gun;</li>
<li>one C++ file for the gamepad module proper;</li>
<li>two function declarations (the "entry points" into the module), one for polling the controller state and the other for writing back the bindings to the config file when the game exits, and</li>
<li>changes to main.cpp and console.cpp to call the functions above.</li>
</ul>
The first item on the list is orthogonal to the rest of the gamepad code and it could be useful in its own right for example to play the sound of an empty cartridge hitting the floor.<br />
<br />
The gamepad can be turned on or off with the <i>gamepadon</i> variable, and <i>gamepadbind</i> allows for extra tweaking. One kludge that I am not particularly proud of is that gamepad buttons cannot be bound directly to cubescript, instead they have to be bound to a key, like in this example:<br />
<br />
<code></code>
<br />
<pre><code>sound_drop = ( registersound "cristiv/dropcartridge" )
bind F8 [ sound $sound_drop ]
gamepadbind right_trigger_release F8
</code></pre>
<br />
it would be nicer to simply say:<br />
<pre><code>gamepadbind right_trigger_release [ sound $sound_drop ]
</code></pre>
<br />
But this is an exercise for another rainy day. By the way, it is so cool being able to map separate actions to analog trigger presses and releases. For example, in my implementation the default mapping of the left trigger is to zoom in when pressed, and zoom out when released. One idea I'd like to try out some day is to make my player character start jumping when the left trigger is pressed, and stop when it is released.<br />
<br />
I am right handed. My default bindings are to control movement with the left thumbstick or D-pad, look around with the right stick, and shoot with the right analog and digital triggers. This scheme can be easily reversed by using the <i>gamepadbind</i> command to remap the triggers and thumbsticks.<br />
<br />
One thing I did before proceeding with implementing the gamepad input code, was to add some triggers for the guns, so that I can call custom cubescript when the weapons are fired. In weapons.cpp I added this block (right before the <i>shoteffects</i> function):<br />
<pre><code>
VAR(gun_trigger_debug, 0, 0, 1);
static void doguntrigger(const fpsent* d, int gun)
{
defformatstring(aliasname)("gun_fired_%d", gun);
if(gun_trigger_debug) conoutf(CON_DEBUG, "%s:%s", name, aliasname);
if(identexists(aliasname)) execute(aliasname);
}
</code></pre>
<pre><code>
</code></pre>
And then I added a line at the end of the <i>shoteffects</i> function:
<br />
<pre><code>
if (d==player1) doguntrigger(d, gun);
</code></pre>
<br />
The gamepad code exposes a function called <i>vibrate</i> to cubescript which takes three parameters: the speed for left vibrate motor, speed for right motor, and the duration in milliseconds. The above plumbing allows for it to be called from my configuration script:<br />
<code></code><br />
<pre><code>// guns feedback
gun_fired_0 = [ vibrate 20000 20000 500 ]
gun_fired_1 = [ vibrate 5000 35000 200 ]
gun_fired_2 = [ vibrate 10000 25000 300 ]
gun_fired_3 = [ vibrate 32000 64000 360 ]
gun_fired_4 = [ vibrate 0 30000 200 ]
gun_fired_5 = [ vibrate 0 25000 200 ]
gun_fired_6 = [ vibrate 0 25000 200 ]
gun_fired_7 = [ vibrate 2000 10000 200 ]
</code></pre>
<br />
The next thing to do was to add two function declarations to <i>engine.h</i> (towards the end of the file, right before the closing #endif):
<br />
<code></code><br />
<pre><code>namespace gamepad
{
#if _WIN32
extern void checkinput(dynent*);
extern void writebinds(stream*);
#else
inline void checkinput(dynent*) {}
inline void writebinds(stream*) {}
#endif
}
</code></pre>
<br />
These two entry points are called right at the beginning of <i>checkinputs</i> (in main.cpp), and at the end of <i>writebinds</i> (in console.cpp), respectively:
<br />
<pre><code>
void checkinput()
{
gamepad::checkinput(player);
SDL_Event event;
int lasttype = 0, lastbut = 0;
// etc...
</code></pre>
<br />
<pre><code>
void writebinds(stream *f)
{
// ...snip...
gamepad::writebinds(f);
}
</code></pre>
<br />
Finally, I "just" added a file to the Visual Studio project (the most recent development version of Sauerbraten comes with a solution file in src/vcpp which plays nice with Vistual Studio 2010) called <i>xinputpad.cpp</i>, and then edited its properties so that it uses the engine.h / engine.pch files for precompiled headers (rather than cube.h / cube.pch).<br />
<br />
I think this approach is minimally invasive as the code sits nicely in its own file, and the changes to <i>engine.h</i>, <i>main.cpp</i> and <i>console.cpp</i> are tiny. I also tried imitating the terse coding style of Sauerbraten rather than using my own (C++ politically correct and at times bombastic) pen.<br />
<br />
I am having a blast (rumble rumble) with this game. Boy I love that rocket launcher!<br />
<br />
<br />
<i>This is the full xinputpad.cpp code. Be careful when copying and pasting, some characters that are "unsafe" for HTML might have been encoded.</i><br />
<br />
<pre><code>// Experimental support for Microsoft XInput-compatible gamepads in Sauerbraten.
// Zlib license. Copyright (c) 2012 cristi.vlasceanu@gmail.com
#include "engine.h"
#include <XInput.h>
#if defined(_MSC_VER)
#pragma comment(lib, "XInput.lib")
#endif
#ifndef _countof
#define _countof(a) sizeof(a)/sizeof(a[0])
#endif
#define DECLARE_XINPUTS \
XINPUT(none, action_none), \
XINPUT(left_stick, action_move), \
XINPUT(right_stick, action_mouse), \
XINPUT(left_trigger, action_key, "z"), \
XINPUT(right_trigger, action_key, "MOUSE1"), \
XINPUT(left_trigger_release, action_key, "z"), \
XINPUT(right_trigger_release, action_none ), \
XINPUT(dpad_up, action_key, "w"), \
XINPUT(dpad_down, action_key, "s"), \
XINPUT(dpad_left, action_key, "a"), \
XINPUT(dpad_right, action_key, "d"), \
XINPUT(start, action_none), \
XINPUT(back, action_none), \
XINPUT(left_thumb, action_none), \
XINPUT(right_thumb, action_none), \
XINPUT(left_shoulder, action_key, "c"),\
XINPUT(right_shoulder, action_key, "MOUSE1"), \
XINPUT(button_a, action_key, "0"),\
XINPUT(button_b, action_key, "F10"), \
XINPUT(button_x, action_key, "F9"), \
XINPUT(button_y, action_key, "SPACE")
#define XINPUT(i,...) x_##i
enum { DECLARE_XINPUTS };
#undef XINPUT
#define STRINGIZE(i) #i
#define XINPUT(i,...) STRINGIZE(i)
static const char* inputs[] = { DECLARE_XINPUTS };
// bind to keyboard, mouse motion or player movement
enum actiontype
{
action_none,
action_mouse,
action_move,
action_key,
};
static const char* actions[] = { "none", "mouse", "move" };
struct keym; // defined in console.cpp
extern keym* findbind(char* key);
extern void execbind(keym &k, bool isdown);
#undef XINPUT
#define XINPUT(i,...) { __VA_ARGS__ }
static struct action
{
actiontype type;
const char* def;
keym* km;
Uint8 prevstate;
string name;
}
const defaultbinds [] = { DECLARE_XINPUTS };
static void bindaction(action& a, actiontype type, const char* key)
{
a.type = type;
a.def = NULL;
a.km = NULL;
a.prevstate = 0;
if (type==action_key && key)
{
copystring(a.name, key);
a.km = findbind(const_cast<char*>(key));
if(!a.km) conoutf(CON_ERROR, "unknown key \"%s\"", key);
}
}
// used when synthesizing mouse events, affects how fast the player turns
VARP(gamepadspeed, 0, 32, 512);
// invert y axis when emulating mouse motion events
VARP(gamepadinverty, 0, 0, 1);
VARP(triggerthreshold, 0, XINPUT_GAMEPAD_TRIGGER_THRESHOLD, 255);
struct controller
{
enum thumb { left, right };
int id, vibratemillis;
bool bounded;
action binds[_countof(defaultbinds)];
static int count;
controller() : id(count++), vibratemillis(0), bounded(false) { }
~controller() { XINPUT_STATE state; if (getstate(state)) vibrate(0, 0); }
void resetbinds()
{
loopi(_countof(binds))
bindaction(binds[i], defaultbinds[i].type, defaultbinds[i].def);
bounded = true;
}
void vibrate(int left, int right, int duration = 0)
{
XINPUT_VIBRATION vibration = { min(left, 65535), min(right, 65535) };
XInputSetState(id, &vibration);
vibratemillis = duration + lastmillis;
}
bool getstate(XINPUT_STATE& state)
{
ZeroMemory(&state, sizeof state);
bool result = (XInputGetState(id, &state) == ERROR_SUCCESS);
if (lastmillis > vibratemillis) vibrate(0, 0);
return result;
}
void motionevent(int x, int y, int dx, int dy)
{
SDL_Event e = { };
e.type = SDL_MOUSEMOTION;
e.motion.x = x;
e.motion.y = y;
e.motion.xrel = dx;
e.motion.yrel = gamepadinverty ? dy : -dy;
SDL_PushEvent(&e);
}
int inline mousedelta(int x, int xmax, int speed)
{
if (x >= xmax) return speed;
if (x < -xmax) return -speed;
return 0;
}
// compute the delta that we're going to use in constructing a fake mouse motion event
int mousedelta(thumb t, int x)
{
static const int xmax = 32767;
const int speed = gamepadspeed;
int dx = mousedelta(x, xmax, speed);
for (int i = 2; i != 32; i *= 2)
if (dx == 0) dx = mousedelta(x, xmax / i, speed / i);
return dx;
}
void checkthumbstick(thumb t, int x, int y, dynent* player)
{
static const int deadzone[] = { XINPUT_GAMEPAD_LEFT_THUMB_DEADZONE, XINPUT_GAMEPAD_RIGHT_THUMB_DEADZONE };
int dx, dy;
switch (binds[t + x_left_stick].type)
{
case action_mouse:
dx = mousedelta(t, x);
dy = mousedelta(t, y);
if (dx || dy) motionevent(0, 0, dx, dy);
break;
case action_move:
if (player->k_up || player->k_down || player->k_left || player->k_right) break;
player->move = y > deadzone[t] ? 1 : (y < -deadzone[t] ? -1 : 0);
player->strafe = x > deadzone[t] ? -1 : (x < -deadzone[t] ? 1 : 0);
if (player->move || player->strafe) player->vel.mul(sqrtf(x*x + y*y) / 32767);
break;
}
}
void checkbindkey(action& a, Uint8 on)
{
if (a.type != action_key) return;
if (on != a.prevstate)
{
if (a.km) execbind(*a.km, on != 0);
a.prevstate = on;
}
}
void checktrigger(thumb t, BYTE level)
{
const bool pressed = level > triggerthreshold;
// check for trigger release
if (!pressed && binds[t + x_left_trigger].prevstate)
{
auto& release = binds[t + x_left_trigger + 2];
if (release.type==action_key && release.km) execbind(*release.km, true);
}
checkbindkey(binds[t + x_left_trigger], pressed);
}
void checkbuttons(WORD b)
{
checkbindkey(binds[x_dpad_up], (b & XINPUT_GAMEPAD_DPAD_UP) != 0);
checkbindkey(binds[x_dpad_down], (b & XINPUT_GAMEPAD_DPAD_DOWN) != 0);
checkbindkey(binds[x_dpad_left], (b & XINPUT_GAMEPAD_DPAD_LEFT) != 0);
checkbindkey(binds[x_dpad_right], (b & XINPUT_GAMEPAD_DPAD_RIGHT) != 0);
checkbindkey(binds[x_start], (b & XINPUT_GAMEPAD_START) != 0);
checkbindkey(binds[x_back], (b & XINPUT_GAMEPAD_BACK) != 0);
checkbindkey(binds[x_left_thumb], (b & XINPUT_GAMEPAD_LEFT_THUMB) != 0);
checkbindkey(binds[x_right_thumb], (b & XINPUT_GAMEPAD_RIGHT_THUMB) != 0);
// these are the digital triggers on some Logitech controllers
checkbindkey(binds[x_left_shoulder], (b & XINPUT_GAMEPAD_LEFT_SHOULDER) != 0);
checkbindkey(binds[x_right_shoulder], (b & XINPUT_GAMEPAD_RIGHT_SHOULDER) != 0);
checkbindkey(binds[x_button_a], (b & XINPUT_GAMEPAD_A) != 0);
checkbindkey(binds[x_button_b], (b & XINPUT_GAMEPAD_B) != 0);
checkbindkey(binds[x_button_x], (b & XINPUT_GAMEPAD_X) != 0);
checkbindkey(binds[x_button_y], (b & XINPUT_GAMEPAD_Y) != 0);
}
};
int controller::count = 0;
static controller c;
ICOMMAND(vibrate, "iii", (int* left, int* right, int* millisec), {
c.vibrate(*left, *right, *millisec);
});
void gamepadbind(const char* name, const char* act)
{
if (!c.bounded) c.resetbinds();
if (strcasecmp(name, "reset") == 0) { c.resetbinds(); return; }
int a = 0, n = 1;
for (; a != _countof(actions) && strcasecmp(actions[a], act); ++a);
for (; n != _countof(inputs) && strcasecmp(inputs[n], name); ++n);
if (a == _countof(actions)) a = action_key;
if (n == _countof(inputs)) conoutf(CON_ERROR, "gamepad input %s is not defined", name);
else if (a == action_key && (n == x_left_stick || n == x_right_stick))
conoutf(CON_ERROR, "Cannot bind thumbsticks to key presses");
else if ((a == action_move || a == action_mouse) && n != x_left_stick && n != x_right_stick)
conoutf(CON_ERROR, "Cannot bind mouse or movement to key presses");
else bindaction(c.binds[n], actiontype(a), act);
}
COMMAND(gamepadbind, "ss");
VARP(gamepadon, 0, 0, 1);
namespace gamepad
{
void checkinput(dynent* player)
{
if (!gamepadon) return;
if (!c.bounded) c.resetbinds();
XINPUT_STATE state;
if (!c.getstate(state)) return;
c.checkthumbstick(controller::left, state.Gamepad.sThumbLX, state.Gamepad.sThumbLY, player);
c.checkthumbstick(controller::right, state.Gamepad.sThumbRX, state.Gamepad.sThumbRY, player);
c.checktrigger(controller::left, state.Gamepad.bLeftTrigger);
c.checktrigger(controller::right, state.Gamepad.bRightTrigger);
c.checkbuttons(state.Gamepad.wButtons);
}
void writebinds(stream* f)
{
for (int i = 1; i != _countof(c.binds); ++i)
{
action& a = c.binds[i];
f->printf("gamepadbind %s %s\n", inputs[i], a.type==action_key ? a.name : actions[a.type]);
}
}
}
</code></pre>
Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com2tag:blogger.com,1999:blog-18241482.post-16758061761911900782011-07-17T16:45:00.002-07:002011-07-17T19:23:21.178-07:00ZeroBUGS Lambda Fun<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRWrw8R8PAhviyURYcIkaUoVHVPC3-yOpSGL-JiTnqHCAieGJEo4GKY6LqNvj0Axn9ZQRbYgwaDCi281LGYOt0O5iCL5quowUWTBQ8T-8rwrPl4UYipJufO8Uqhc9bOnFYFGZ44g/s1600/Screenshot-zero.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="cursor:pointer; cursor:hand;width: 400px; height: 308px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRWrw8R8PAhviyURYcIkaUoVHVPC3-yOpSGL-JiTnqHCAieGJEo4GKY6LqNvj0Axn9ZQRbYgwaDCi281LGYOt0O5iCL5quowUWTBQ8T-8rwrPl4UYipJufO8Uqhc9bOnFYFGZ44g/s400/Screenshot-zero.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5630471700026999986" /></a><br /><br />A friend of mine tried to compile the code from <a href="http://the-free-meme.blogspot.com/2011/07/template-template-method.html">my previous post</a> using GCC, only to get a bunch of error messages. As I suspected, the fix was to specify <i>-std=c++0x</i> on the command line. But before answering my friend's G+ message, I had to verify that the code worked with GCC. And one thing lead to another. After compiling, I was curious to see how my ZeroBUGS debugger copes with lambdas. What else to do on a rainy Sunday afternoon in Seattle, other than playing with some old C++ code while listening to Judas Priest?<br /><br /><blockquote>ZeroBUGS is a visual debugger for Linux, a project that ate up all of my spare time between 2004 and 2008. I kept making small changes to it since, but very limited in scope. For some reason, since the Big Recession I found myself having lesser and lesser time for on-the-side projects. I tried for a while making ZeroBUGS a commercial enterprise, hoping to leave my day time job(s) and become self employed. I learned the hard way that selling proprietary software to Linux geeks is not very lucrative. Or maybe I should have partnered with a savvy sales guy, the kind that can sell refrigerators to penguins.<br /><br />In late 09 I put ZeroBUGS on ice and went working on Microsoft Windows for a short bit (just long enough to write a few lines of code that will hopefully make it into the upcoming Windows 8.) </blockquote><blockquote>After leaving Microsoft and joining <a href="http://www.tableausoftware.com/">TableauSoftware</a>, I yanked the closed source product off my web site, and re-released <a href="http://zerobugs.codeplex.com/">ZeroBUGS as open source</a> (and free as in free beer under the Boost License.)</blockquote>I have not come upon major bugs in the debugger since a few years ago, when I discovered that the "step-over" functionality was broken for recursive functions.<div><br /></div><div>So I was pretty confident the debugger will handle the new C++0X just fine. Except it didn't! </div><div><br /></div><div>After some debugging, I traced the problem to the unnamed classes that the compiler generates to capture the surrounding variables. My debugger cashes data types by name for performance reasons. Unnamed classes normally occur in some scope, and thus there is no clash. Except that in the case of lambda functions, GCC generates unnamed classes at the outer most scope (i.e. the DWARF entries describing their type is at level 1, immediately nested in the compilation unit scope.) The data structures visualization was completely off, because the debugger used the wrong datatype (the first "unnamed" always won).</div><div><br /></div><div>A simple hack that appends the file index and the line number to the offending "unnamed" solves the problem for now, as the snapshot above can testify. </div><div><br /></div><div>While I think of a better solution this one will have to do. I am done with the computer for now, off to enjoy the weather and barbecue in the rain for the rest of the night!</div><div><br /></div><div><br /></div><div><br /></div>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-53031161807592835762011-07-16T11:00:00.000-07:002011-07-17T18:38:32.596-07:00Template Template MethodI recently had to write a bunch of C++ functions that shared a common pattern:<br /><br />1) acquire a resource lock<br />2) TRY<br />3) do some work<br />4) CATCH exceptions of interest, and log them<br />5) release resource lock<br /><br />I was eager to implement the "do some work" bits but did not want to bore myself silly by repeating the steps 1, 2, 4, 5 in each function (about thirty or so of them.) Now, you may recognize the problem, it is what the <a href="http://en.wikipedia.org/wiki/Template_method_pattern">Template Method Design Pattern</a> solves: "avoid duplication in the code: the general workflow structure is implemented once in the abstract class's algorithm, and necessary variations are implemented in each of the subclasses."<br /><br />I could not however apply the Template Method pattern "as is" because my functions did not share a common signature. So wrapping them with a non-virtual function and then implement the "do some work" as virtual methods would not work in my case.<br /><br />One alternative was to code steps 1 and 2 above as a BEGIN_CALL macro, wrap up steps 4 and 5 into a END_CALL and decorate each of my methods with these archaic C-isms. The approach would indeed work for C, but it is utterly indecorous in C++.<br /><br />The spirit of the Template Method pattern can be preserved very elegantly by making the template method a <span style="font-style:italic;">C++ template method</span>, and <b>wrap the variant "do some work" bits into a <span style="font-style:italic;">lambda block</span>.</b><br /><br />The code sample below illustrates the idea (I added some mock objects to give more context).<br /><br /><pre>#include <iostream><br />#include <sstream><br />#include <string><br /><br />using namespace std;<br /><br />// Mock a resource that needs exclusive locking<br />//<br />// -- think CComCriticalSection for example:<br />// <a href="http://msdn.microsoft.com/en-us/library/04tsf4b5(v=vs.80).aspx">http://msdn.microsoft.com/en-us/library/04tsf4b5(v=vs.80).aspx</a><br />class Resource<br />{<br />public:<br />void Lock() { cout << "Resource locked." << endl; }<br />void Unlock() { cout << "Resource unlocked." << endl; }<br />};<br /><br />// Generic stack-based lock. Works with any resource<br />// that implements Lock() and Unlock() methods.<br />// See:<br />// <a href="http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization">http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization</a><br />template<typename T><br />class Lock<br />{<br />Lock(const Lock&); // non-copyable<br />Lock& operator=(const Lock&); // non-assignable<br /><br />T& m_resource; // Lock MUST NOT outlive resource<br /><br />public:<br />explicit Lock( T& resource ) : m_resource( resource )<br />{<br /> m_resource.Lock( );<br />}<br /><br />~Lock( )<br />{<br /> m_resource.Unlock( );<br />}<br />};<br /><br />/////////////////////////////////////////////////////////////////////////////<br />// Template Method Wrapper for an arbitrary lambda block:<br />// 1) lock a resource<br />// 2) log exceptions<br />// This is a variant of the Template Method Design Pattern<br />// -- implemented as a C++ template method.<br />template<typename F><br />auto Execute(Resource& r, F f) -> decltype(f())<br />{<br />Lock<Resource> lock(r);<br />try<br />{<br /> return f();<br />}<br />catch (const exception& e)<br />{<br /> // log error<br /> clog << e.what() << endl;<br />}<br />typedef decltype(f()) result_type;<br />return result_type();<br />}<br />/////////////////////////////////////////////////////////////////////////////<br /><br />// Usage example:<br /><br />static Resource globalResource;<br /><br /><br />int f (int i)<br />{<br />return Execute(globalResource, [&]()->int<br />{<br /> return i + 1;<br />});<br />}<br /><br />string g (unsigned j)<br />{<br />return Execute(globalResource, [&]()->string<br />{<br /> ostringstream ss;<br /> ss << '[' << j << ']';<br /> return ss.str();<br />});<br />}<br /><br />int main()<br />{<br />cout << f(41) << endl;<br />cout << g(42) << endl;<br /><br />return 0;<br />}<br /></pre><br /><b>Update:</b> to compile the code above using GCC you may need to specify "-std=c++0x" on the command line.<div><br /></div><div>One thing that I grappled with for a bit was how to make the Execute template function figure out the return type of the wrapped lambda. After pinging Andrei Alexandrescu at Facebook (or is it "on Facebook"? No matter -- my English as a second language works either way, because Andrei does work for Facebook) and some googling around, I found the magic incantation: <i>decltype(f())</i>.</div><div><br /></div>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com1tag:blogger.com,1999:blog-18241482.post-32961520960020272682010-12-12T21:59:00.000-08:002010-12-12T22:01:41.187-08:00A Voyage to the Center of the Borg<meta equiv="content-type" content="text/html; charset=utf-8"><div>A great while has passed since my last blog post. To my defense: I had been very busy playing <a href="http://memory-alpha.org/wiki/Locutus_of_Borg">Locutus of Borg</a>. Microsoft <a href="http://money.cnn.com/2007/05/18/technology/microsoft_aquantive/">bought out my employer back in 2007</a>, and consequently I spent the past three years working in their Online Services Division, and Windows Server (yes, I did contribute a few lines of code to the upcoming version of Windows).
<br /></div><div>
<br /></div><div>For months, if not years of my being a Redmondite I envisioned how I was going to blog about the strange and at times surreal experience of working for Microsoft. After all, I am the kind of geek who did not use Windows on his home machines. I only installed it after the acquisition, so that I could work from home every once in a while. I had imagined how the day would look like, when free of the Borg, I was going to report on how life on the inside felt like. I yearned to write about Microsoft politics, coding style and culture, the famous never-ending meetings and (some really amazing) people that I met there. I thought that I should document how their caste system (oops, I mean, career path model) twists people.</div><div>
<br /></div><div>But now that I am on the outside, I cannot think of anything interesting to write about my days at Microsoft. Life goes on.</div><div>
<br /></div><div>I'd rather blog on what a great product <a href="http://www.tableausoftware.com/">Tableau Software</a> (my new employer) has. Or I could write about what an exciting weekend this one was, living on the web with my new Chrome OS laptop from Google (thanks again Sorin for the great surprise that got delivered Friday night!) Or I could write about enjoying the great read that the <a href="http://www.amazon.com/D-Programming-Language-Andrei-Alexandrescu/dp/0321635361">D Programming Language</a> is.</div><div>
<br /></div><div>Later.</div><div>
<br /></div>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-20923702216371773022009-06-23T01:06:00.000-07:002009-06-25T19:14:37.670-07:00The Power of ForeachIn D, arrays can be traversed using the foreach construct:<br /><pre><code><br />int [] a = [1, 5, 10, 42, 13];<br />foreach (i;a) {<br /> writefln(“%d”, i);<br />}<br /></code></pre><br />The array of integers in this example is traversed and each element printed, in the natural order in which elements appear in the sequence. To visit the elements in reverse order, simply replace <code>foreach</code> with <code>foreach_reverse</code>. It is as intuitive as it gets.<br /><br />Moreover, linear searches can be implemented with foreach: simply break out of the loop when the searched-for value is found:<br /><pre><code><br />foreach (i;a) {<br /> writefln(“%d”, i);<br /> if (i == 42) {<br /> break;<br /> }<br />}<br /></code></pre><br />Consider now a tree data structure where a tree node is defined as:<br /><pre><code><br />class TreeNode {<br /> TreeNode left;<br /> TreeNode right;<br /> int value;<br />}<br /></code></pre><br />What is the meaning of a statement such as <code>foreach (node; tree) { … }?</code> The simple answer is that with the above definition of TreeNode, the code does not compile.<br /><br />But if it were to compile, what should it do? Visit the nodes in order, or in a breadth-first fashion? No answer is the right one, unless we get to know more about the problem at hand. If we’re using a binary search tree to sort some data, then foreach would most likely visit the nodes in-order; if we’re evaluating a Polish-notation expression tree, we might want to consider post-order traversal.<br /><br /><br /><h2>Foreach Over Structs and Classes</h2><br /><br />Tree data structures and tree traversal occur often in computer science problems (and nauseatingly often in job interviews). Balanced binary trees are routinely used to implement associative containers, as C++ programmers are certainly familiar with the standard template collections set and map.<br /><br />One difference between sequence containers (such as lists, arrays, and queues) on one hand, and containers implemented with trees on the other, is that there are more ways to iterate over the elements of a tree than there are ways to enumerate the elements of a sequence. A list (for example) can be traversed from begin to end and, in the case of double-linked lists, in reverse, from the end to the beginning; that’s it. But a tree can be traversed in order, in pre-order, post-order, or breadth first.<br /><br />No built-in traversal algorithm will fit all possible application requirements. D’s approach is to provide the opApply operator as "standard plumbing" where users can plug their own algorithms for iterating over the elements of a class or struct. The operator is supposed to implement the iteration logic, and delegate the actual processing of the objects to a ... delegate:<br /><br /><pre><code><br />class TreeNode {<br />public:<br /> TreeNode left;<br /> TreeNode right;<br /> int value;<br /> int opApply(int delegate(ref TreeNode) processNode) {<br /> // ... tree traversal<br /> // ...<br /> return 0;<br /> }<br />}<br /></code></pre><br />When the programmer writes a foreach loop, the compiler syntesizes a delegate function from the body of the loop, and passes it to <code>opApply</code>. In this example, the body of the delegate will have exactly one line that contains the <code>writefln</code> statement:<br /><pre><code><br />TreeNode tree = constructTree();<br />foreach(node; tree) {<br /> writefln(“%d”, node.value);<br />}<br /></code></pre><br />For an in-order traversal, the implementation of opApply may look something like this:<br /><pre><code><br />int opApply(int delegate(ref TreeNode) processNode) {<br /> return (left && left.opApply(processNode)) <br /> || processNode(this)<br /> || (right && right.opApply(processNode));<br />}<br /></code></pre><br />The delegate that the compiler synthesizes out of the foreach body returns an integer (which is zero by default). A break statement in the foreach loop translates to the delegate function returning a non-zero value. As you can see in code above, a correct implementation of opApply should make sure that the iteration is "cancelled" when the delegate returns a non-zero value.<br /><br />The traversal function’s argument must match the delegate argument type in the signature of opApply. In the example above the processNode function could modify the tree node that is passed in. If the TreeNode class writer wanted to outlaw such use, the opApply operator should have been declared to take a delegate that takes a const TreeNode parameter:<br /><pre><code><br />class TreeNode {<br />// …<br /> int opApply(int delegate(ref const TreeNode) processNode) {<br /> return processNode(this); <br /> }<br />}<br /></code></pre><br />The new signature demands that the client code changes the parameter type from TreeNode to const TreeNode. Any attempt to modify the node object from within the user-supplied traversal function will fail to compile.<br /><br />Another possible design is to encode all traversal algorithms as TreeNode methods. The following shows an example for the in-order algorithm (other traversal algorithms are left as an exercise for the reader):<br /><pre><code><br />class TreeNode {<br />// …<br /> int traverseInOrder(int delegate(ref int) dg) {<br /> if (left) {<br /> int r = left.traverseInOrder(dg);<br /> if (r) {<br /> return r;<br /> }<br /> }<br /> int r = dg(value);<br /> if (r) {<br /> return r;<br /> }<br /> if (right) {<br /> r = right.traverseInOrder(dg);<br /> if (r) {<br /> return r;<br /> }<br /> }<br /> return 0;<br /> }<br />}<br /><br />foreach(val; &tree.traverseInOrder) {<br /> Console.WriteLine(val);<br />}<br /></code></pre><br /><br /><h2>D Generators</h2><br /><br />A generator is a function or functor that returns a sequence, but instead of building an array or vector containing all the values and returning them all at once, a generator yields the values one at a time. Languages such as C# and Python have a yield keyword for this purpose. In D a generator can be implemented with foreach and a custom opApply operator. Assume one wants to print the prime numbers up to N, like this:<br /><pre><code><br /> foreach (i; PrimeNumbers()) {<br /> if (i > N) {<br /> break;<br /> }<br /> writeln(i);<br /> }<br /></code></pre><br />To make this work, the PrimeNumbers struct could be implemented like this:<br /><pre><code><br />struct PrimeNumbers {<br /> int n = 1;<br /> int primes[];<br /><br /> int opApply(int delegate(ref int) dg) {<br />loop:<br /> while (true) {<br /> ++n;<br /> foreach (p; primes) {<br /> if (n % p == 0) {<br /> continue loop;<br /> }<br /> }<br /> primes ~= n;<br /> if (dg(n)) {<br /> break;<br /> }<br /> }<br /> return 1;<br /> }<br />}<br /></pre></code>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com3tag:blogger.com,1999:blog-18241482.post-82995925922453029642009-06-18T00:11:00.000-07:002009-06-22T16:03:51.520-07:00Pragma AssemblyPublishing the source code for D.NET on <a href="http://dnet.codeplex.com/">CodePlex</a> in its current (rough) form turned out to be a great idea, as I received very good feedback. Tim Matthews of New Zealand has submitted several bug reports and patches and convinced me to change my stance on the "assembly class hack".<br /><br />The hack was a very limited solution to the problem of qualifying imported declarations by the name of the assembly where they live. I described the problem and the attempt to hack around it at the end of a post <a href="http://the-free-meme.blogspot.com/2008/12/hello-net-d-here-calling.html">back in December</a>; a diligent reader commented that I should have used the <span style="font-style: italic;">pragma</span> mechanism instead. I resisted the suggestion at the time, mainly because I am trying to avoid changing the compiler front-end if I can help it. (Front-end changes have to ultimately be merged back into Walter' s source tree, and he is a very very busy guy.)<br /><br />A D implementation on .NET is not going to be of much use without the ability to generate code that imports and interfaces with existing assemblies. Guided by this idea, Tim Matthews did a lot of trail-blazing and prototyping and showed that because in .NET namespaces can span across assemblies, there has to be a way of specifying an arbitrary number of assemblies in one import file. My "assembly class" hack allowed for one and only one assembly name to be specified.<br /><br />So I had to byte the bullet and do the right thing: assembly names are now specified with a pragma, like this:<br /><pre><code><br />pragma (assembly, "mscorlib")<br />{<br />// imported declarations here...<br />}<br /><br /></code></pre>Any number of such blocks can appear within a D import file. And in the future, the code will be extended to allow a version and a public key to be specified after the assembly name.<br /><br />Another thing that has to be fixed is to make the compiler adhere to the convention of using a slash between enclosing classes and nested types, as described in Serge Lidin's <a href="http://www.amazon.com/gp/product/1590596463?ie=UTF8&tag=zerobugscom-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=1590596463">Expert .NET 2.0 IL Assembler</a>, CHAPTER 7 page 139:<br /><blockquote>Since the nested classes are identified by their full name and their encloser (which is in turn identified by its scope and full name), the nested classes are referenced in ILAsm as a concatenation of the encloser reference, nesting symbol / (forward slash), and full name of the nested class</blockquote><br /><br />Tim also submitted a front-end patch that allows directories and import files of the same name to coexist, so that the code below compiles without errors:<br /><pre><code><br />import System;<br />import System.Windows.Forms;<br /></code></pre><br /><br />An alternative solution that I proposed was to create import files named "this.d", so that the above would have read:<br /><pre><code><br />import System.this;<br />import System.Windows.Forms;<br /></code></pre><br /><br />After some consideration, I bought Tim's point that this is not what .NET programmers would expect, and went on to apply his patch.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-69057194813296114252009-05-10T00:17:00.000-07:002009-05-10T00:32:39.307-07:00D .NET on CodeplexI will be taking a few days off next week and I decided to upload the code for the D compiler <span style="font-weight:bold;">.net</span> back-end on Codeplex before I close shop. I hope that it will provide context for the last few months worth of blog posts.<br /><br />Most core language features are usable, but there's no Phobos port and if you need to import functionality from external DLLs, you'll have to hand-write some import files (following the model in <code>druntime/import/System.di</code>); I hope to get around to writing a tool that automates the process one of these days -- and it will most likely be in D.<br /><br />There is a Visual Studio 8 (works with Visual Studio 8 Express) solution file in the source tree, and there is also a Makefile for the adventurous. The project compiles on Linux but it does not work quite well with Mono -- I strongly suspect it is Mono's seg<span style="font-style:italic;">fault</span>.<br /><br />Check it out at <a href="http://dnet.codeplex.com/">http://dnet.codeplex.com/</a>!Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com2tag:blogger.com,1999:blog-18241482.post-33425485124817406972009-04-28T22:47:00.000-07:002009-04-30T18:15:08.328-07:00Argument against _argptrVariadic functions work slightly different in my D.NET implementation than under the native D compiler.<br /><br />For functions with variable numbers of arguments, the native compiler synthesizes two parameters: <i>_arguments</i> and <i>_argptr</i>; _arguments is an array of TypeInfo objects, and _argptr is a pointer to the beginning of the variable arguments on the stack. The user is supposed to query the type information in _arguments, and do the proper pointer arithmetic to navigate the arguments. You can see some examples at <a href="http://www.digitalmars.com/d/2.0/function.html">http://www.digitalmars.com/d/2.0/function.html</a>:<br /><blockquote><pre><code><br />void printargs(int x, ...)<br />{<br /> writefln("%d arguments", _arguments.length);<br /> for (int i = 0; i < _arguments.length; i++)<br /> { _arguments[i].print();<br /><br /> if (_arguments[i] == typeid(int))<br /> {<br /> int j = *cast(int *)_argptr;<br /> _argptr += int.sizeof;<br /> writefln("\t%d", j);<br /> }<br /> else if (_arguments[i] == typeid(long))<br /> {<br /> long j = *cast(long *)_argptr;<br /> _argptr += long.sizeof;<br /> writefln("\t%d", j);<br /> }<br /> // ...<br /></code></pre></blockquote><br /><br />The pointer arithmetic is not verifiable in managed code. A separate array of type descriptors is not necessary in .net, because the type meta-data can be passed in with the arguments. <br /><br />In D.NET, the variable arguments are passed as an array of objects. For example, for a D function with the prototype <pre><code>void fun(...)</code></pre> the compiler outputs:<br /><code><br />.method public void '_D23funFYv' (object[] _arguments)<br /></code><br />I handled variadic support slightly differently from the native compiler: I dropped _argptr and provided a new helper function, _argtype, that can be used as demonstrated in this example:<br /><pre><code><br />void fun(...)<br />{<br /> foreach(arg; _arguments)<br /> {<br /> if (_argtype(arg) == typeid(int))<br /> {<br /> int i = arg;<br /> Console.WriteLine("int={0}".sys, i);<br /> }<br /> else if (_argtype(arg) == typeid(string))<br /> {<br /> string s = arg;<br /> Console.WriteLine(s.sys);<br /> }<br /> }<br />}<br /></code></pre><br />If the type of the arguments is known, there is no need to check for the typeid:<br /><pre><code><br />void fun(...)<br />{<br /> foreach(arg; _arguments)<br /> {<br /> int i = arg;<br /> Console.WriteLine(i);<br /> }<br />}<br /></code></pre><br />If an incorrect type is passed in, it is still okay, because the error is detected at runtime.<br /><pre><code><br />fun("one", "two", "three"); // int i = arg will throw<br /></code></pre><br /><br />The downside of this approach is that it is not compatible with the native code. This does not affect template variadic functions, which should be perfectly portable.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-5617827062102583112009-04-28T12:12:00.000-07:002009-04-28T14:24:59.346-07:00Slice and D-iceIt is amazing how much insight one can get into a language by <i>simply</i> writing a compiler for it... Today I am going to spend half a lunch break copying and pasting into this post a stack of notes related to array slices (collected over the past few months of working on a .net back-end for the D compiler).<br /><br />D sports a data type called <span style="font-style: italic;">array slice</span> that is intended to boost the performance of array-intensive computations. A slice is a lightweight value type, conceptually equivalent to a range of array elements, or a "view" into an array. It can be thought of as consisting of a reference to an array, and a pair of begin-end indexes into the array:<br /><pre><code><br />struct (T) ArraySlice {<br /> T[] a; // reference to array<br /> int begin; // index where slice begins<br /> int end; // one past index where slice ends<br />}<br /></code></pre><br />The actual representation of a slice is currently internal to the compiler, and completely opaque to the programmer. The template struct above is not what the layout of a slice actually looks like, it is intended for illustrative purposes only.<br /><br />Consider this code:<br /><pre><code><br />int a[] = [1, 3, 5, 7, 9, 11, 13, 17];<br />int[] s = a[2..5];<br /></code></pre><br />The second declaration introduces "s" as a slice of array "a", starting at position two and ending at (but not including) the fifth element. Using the template pseudo-definition of ArraySlice, the code is conceptually equivalent to:<br /><pre><code><br />int a[] = [1, 3, 5, 7, 9, 11, 13, 17];<br />ArraySlice!(int) s = { a, 2, 5 };<br /></code></pre><br />To understand how array slices may help performance, consider an application that reads and parses XML files. The input can be loaded as an array of characters (a huge string). The application builds a DOM representation of the input, and each node in the DOM contains a token string. This approach is wasteful, because the token strings hold copies of character sequences that are already present in the input; copying tokens around has a linear complexity (it is directly proportional with the number of characters in the token) and the same is true for the spatial complexity (how much memory is being used). But XML tokens could be modeled as slices of character arrays ("views" into the original XML input string), and complexity in both time and space would drop down to a constant value.<br /><br />This design can be implemented in other languages than D, but memory management issues may add unnecessary complexity. In C++ for example we'll have to make sure that the life-time of the token slices does not exceed the scope of the original input string. D belongs to the family of garbage-collected languages; by default, objects are reference-counted, and holding a reference to an array slice indirectly keeps the original array "alive", because the slice contains a reference to it.<br /><br />Now that the design rationale behind array slices is understood, let's take another look at the syntax. You have probably noticed that in the statement:<br /><code>int[] s = a[2..5];</code><br /><br />The declaration part introduces "s" as an array of integers; it is not until you see the assignment that the lightweight, array slice, true nature of "s" is revealed.<br />D has no special syntax for disambiguating between "true" arrays and array slices in declarations; they can be used interchangeably. As a matter of fact, a function signature with array parameters will happily accept a slice as argument. In the following code, both "a" and "s" are legal arguments for the count function:<br /><pre><code><br />int count(int[] arr) {<br /> return arr.length; // return the number of elements in arr<br />}<br />writefln("%d", count(a)); // ok<br />writefln("%d", count(s)); // also ok<br /></code></pre><br /><br /><h3>Resizing Slices</h3><br />Both arrays and slices support the built-in length property. As you expect, an expression such as a.length tells you how many elements are present in the array; the property applies to array slices as well, and in that case it gives the number of elements within the slice range. For example, the output of the following code is "3":<br /><pre><code><br />int a[] = [1, 2, 3, 5, 7, 9, 11, 13, 17];<br />int[] s = a[2..5];<br />writefln("%d", s.length); // prints 3<br /></code></pre><br />So far so good, but I forgot to mention that the length property is read-write: not only can you query the size of an array, you can also change it, like this:<br /><code><br />a.length = 100; // extend the array to 100 elements<br /></code><br />Assignment to the length property resizes the array. This begs the question: what happens when an array slice is being resized? The answer of course is "it depends".<br />With "a" and "s" defined as above, let's say we resize the "s" slice from 3 elements to 7:<br /><code><br />s.length = 7;<br /></code><br />This extends the view of "s" into "a" up to the ninth element of "a" ("s" starts at 2). It is as we have said:<br /><code><br />s = a[2..9];<br /></code><br />The slice is still within the bounds of the "a" array. Resizing it is a constant-time operation that changes one field inside the internal representation of "s". If instead of the built-in slice we had used the template ArraySlice struct introduced above, resizing the slice would have amounted to:<br /><pre><code><br />int a[] = [1, 3, 5, 7, 9, 11, 13, 17];<br />ArraySlice!(int) s = { a, 2, 5 };<br />s.end = 9; // resize the slice<br /></code></pre><br />Because "s" is simply a "view" of the array, modifying an element in the array is immediately reflected into the slice, for example:<br /><pre><code><br />writefln("%d %d", a[2], s[0]); // prints "5 5"<br />a[2] = 23;<br />writefln("%d %d", a[2], s[0]); // prints "23 23"<br /></code></pre><br />What happens if we re-size "s" past the end of "a"?<br /><pre><code><br />s.length = 100; // what does this do?<br /></code></pre><br />The answer is that the behavior is up to the compiler. The current native compiler from Digital Mars changes the type of "s" from a lightweight view into an array to a full-fledged array, and re-sizes it to fit 100 elements.<br /><pre><code><br />int a[] = [1, 2, 3, 5, 7, 9, 11, 13, 17];<br />int[] s = a[2..5];<br />writefln("%d %d", a[2], s[0]); // prints "5 5"<br />s.length = 100;<br />a[2] = 23;<br />writefln("%d %d", a[2], s[0]); // prints "23 5"<br /></code></pre><br />In other words, resizing a slice past the end of the original array breaks up the relationship between the two, and from that point they go their separate merry ways.<br />This behavior also underlines the schizophrenic nature of array slices that are not full copies of arrays, unless they change their mind.<br /><br /><h3>Concatenating Slices</h3><br />We saw how array slices may be re-sized via the “length” property. Slices may be re-sized implicitly via concatenation, as in the following example:<br /><pre><code><br />int a[] = [1, 2, 3, 5, 7, 9, 11, 13, 17];<br />int s[] = a[0..5];<br />s ~= [23, 29];<br /></code></pre><br />The tilde is the concatenation operator for arrays, strings and slices. In this example, the slice is resized to accommodate the elements 23 and 29. Note that even that in this situation the resizing is different from had we written:<br /><code>s.length += 2;</code><br /><br />Extending the length by two elements simply bumps up the upper limit of the slice (because there is still room in the original array, "a"). As we saw in the previous section, if the new length exceeds the bounds of the original array, the slice will be "divorced" from the original array, and promoted from a light-weight view to a full, first-class array. If we just extend the length by two elements, the bounds of "a" are not exceeded.<br /><br />However, in the case of appending (as in s ~= [23, 29]) in addition to resizing we are also setting the values of two additional elements. The slice needs to be divorced from the array, so the a[5] and a[6] are not overwritten with the values 23 and 29. The compiler turns "s" into a full array of length + 2 == 7 elements, copies the elements of “a” from 0 to 5, then appends values 23 and 29.<br /><br />The problem, as with resizing past the bounds of the original array, is that after the array and the slice part their ways, it is no longer possible to modify value types in the original array via the slice (which has now been promoted to a standalone array). This is a run time behavior, hard to predict by statically analyzing (or visually inspecting) the code.<br /><br /><h3>Rolling Your Own Array Slices</h3><br /><br />It is impossible to determine statically whether a D function parameter is an array or a slice by examining the function's code alone. It is up to the function's caller to pass in an array or a slice.<br /><pre><code><br />void f (int[] a) {<br />// ...<br />}<br />int a[] = [1, 2, 3, 5, 7, 9, 11, 13, 17];<br />f(a); // call f with an array argument<br />f(a[2..5]); // call f with a slice argument;<br /></code></pre><br />In some cases you may want to better communicate that your function is intended to work with slices rather than arrays. You may also want to have better control over the slice's properties. Say for example you want to make sure that a slice is never re-sized.<br /><br />You can accomplish these things by rolling your own ArraySlice. The template struct that was introduced earlier is a good starting point. The signature of "f" can be changed to:<br /><pre><code><br />void f (ArraySlice!(int) a) { // ...<br /></code></pre><br />That's a good start, but the struct is not compatible with a built-in array slice. The following code does not compile:<br /><pre><code><br />struct (T) ArraySlice {<br /> T[] a; // reference to array<br /> int begin; // index where slice begins<br /> int end; // one past index where slice ends<br />}<br /><br />int a[] = [1, 2, 3, 5, 7, 9, 11, 13, 17];<br />ArraySlice!(int) s = { a, 2, 5 };<br />foreach(i; s) { // error, does not compile<br /> writefln("%d", i);<br />}<br /></code></pre><br />You could of course rewrite the foreach loop to use the begin..end range:<br /><pre><code><br />foreach(i; s.begin..s.end) {<br /> writefln("%d", s.a[i]);<br />}<br /></code></pre><br />In addition to being more verbose such code is not very well encapsulated, since it explicitly accesses the struct's public members. If we later decide to factor out ArraySlice into its own module, and make the “a”, “begin”, and “end” members private, the code above will not compile anymore.<br /><br />All that's preventing the compact version of the foreach loop from compiling is that the <span style="font-style: italic;">opApply</span> operator is missing. So let's add one:<br /><pre><code><br />struct (T) ArraySlice {<br /> // ...<br /> int opApply(int delegate(ref int) dg) {<br /> foreach (i;begin..end) {<br /> dg(a[i]);<br /> }<br /> return 0;<br /> }<br />}<br /></code></pre><br />Great! This gets us past the compilation error. The foreach loop now compiles and prints out all the elements in the slice. There is a small and subtle bug in this code though. Suppose that instead of printing all elements in the slice, you're doing a linear search, for example:<br /><pre><code><br />foreach(i; s) {<br /> if (i == 5) { // found it!<br /> break;<br /> }<br />}<br /></code></pre><br />Astonishingly enough, this code will not break out of the foreach loop, instead it will continue through all the elements in the slice.<br /><br />The <a href="http://www.digitalmars.com/d/2.0/statement.html">http://www.digitalmars.com/d/2.0/statement.html</a> website prescribes the behavior of the opApply operator:<br /><blockquote>"The body of the apply function iterates over the elements it aggregates, passing them each to the dg function. If the dg returns 0, then apply goes on to the next element. If the dg returns a nonzero value, apply must cease iterating and return that value".<br /></blockquote>The D compiler synthesizes the delegate function from the body of the foreach loop, and the code above is transformed internally to this equivalent form:<br /><pre><code><br />int dg(ref int i) {<br /> if (i == 5) {<br /> return 1;<br /> }<br /> return 0;<br />}<br />s.opApply(&dg);<br /></code></pre><br />The bug in the opApply operator is that the loop should be broken out of when dg returns non-zero:<br /><pre><code><br />int opApply(int delegate(ref int) dg) {<br /> foreach (i; begin..end) {<br /> if (dg(a[i])) break;<br /> }<br /> return 0;<br />}<br /></code></pre><br />Now foreach works correctly. To support foreach_reverse, just add a <span style="font-style: italic;">opApplyReverse</span> member function to the ArraySlice template struct:<br /><pre><code><br />int opApplyReverse(int delegate(ref int) dg) {<br /> foreach_reverse (i; begin..end) {<br /> if (dg(a[i])) break;<br /> }<br /> return 0;<br />}<br /></code></pre><br />What about manipulating the length of the slice? Neither of the lines below compiles:<br /><pre><code><br />writefln("%d", s.length);<br />s.length = 100;<br /></code></pre><br />To support the length property, we have to add these methods:<br /><pre><code><br />struct (T) ArraySlice {<br /> // ...<br /> // return the length of the slice<br /> int length() { return end - begin; }<br /><br /> // resize the slice, preventing it to grow past<br /> // the original array's length<br /> void length(int newLength) {<br /> end = begin + newlength;<br /> if (end > a.length) { end = a.length; }<br /> }<br />}<br /></code></pre><br />To prevent resizing the slice, all there is to do is to leave the second overload undefined, effectively turning length into a read-only property.<br /><br />Clients of the struct can still set its individual members to inconsistent values. To disallow incorrect usage, the "a", "begin", and "end" members can be made private (and the struct will have to move to its own module, because in D private access is not enforced if the class or struct lives in the same module as the client code).<br /><br />To make the ArraySlice struct even more source-compatible with built-in slices, you can give it an opIndex operator:<br /><pre><code><br />struct (T) ArraySlice {<br /> // ...<br /> T opIndex(size_t i) { return a[i]; }<br />}<br /></code></pre><br />The opIndex operator allows this to work:<br /><code>writefln("%d", s[3]);</code><br /><br />Assignment to array elements is not allowed:<br /><pre><code><br />s[3] = 42; // error, does not compile<br /></code></pre><br />If you want the array elements to be modified via the slice like that, just define<br />opIndexAssign:<br /><pre><code><br />struct (T) ArraySlice {<br /> // ...<br /> void opIndexAssign(size_t i, T val) { a[i] = val; }<br />}<br /></code></pre><br />When you put it all together, the ArraySlice struct will look something like this:<br /><pre><code><br />struct (T) ArraySlice {<br />private:<br /> T[] a; // reference to array<br /> int begin; // index where slice begins<br /> int end; // one past index where slice ends<br />public:<br /> T opIndex(size_t i) { return a[i]; }<br /> void opIndexAssign(size_t i, T val) { a[i] = val; }<br /> int length() { return end - begin; }<br /> // comment this function out to prevent resizing<br /> void length(int newLength) {<br /> end = begin + newlength;<br /> if (end > a.length) { end = a.length; }<br /> }<br /><br /> // support foreach<br /> int opApply(int delegate(ref int) dg) {<br /> foreach (i;begin..end) {<br /> if (dg(a[i])) break;<br /> }<br /> return 0;<br /> }<br />}<br /></code></pre><br />In conclusion, by rolling your own array slice implementation the intent of your code becomes clearer, your level of control over it increases, and you can still retain the brevity of the built-in slices.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com1tag:blogger.com,1999:blog-18241482.post-5549832188266008402009-04-24T00:03:00.000-07:002009-04-24T13:53:31.698-07:00Static ctors in D.NET (Part 2)D allows multiple static constructors per class (all sharing the same signature). For example, the following code is legal:<br /><pre><code><br />version(D_NET)<br />{<br /> import System;<br /> alias Console.WriteLine println;<br />}<br />else<br />{<br /> import std.stdio;<br /> alias writefln println;<br />}<br />class A<br />{<br /> static int i = 42;<br /> static this() <br /> {<br /> println("static A.this 1");<br /> }<br /> static this() <br /> {<br /> println("static A.this 2");<br /> }<br />}<br />void main()<br />{<br /> println(A.i);<br />}<br /></code></pre><br />The program prints:<br /><pre><br />static A.this 1<br />static A.this 2<br />42<br /></pre><br />Because IL does not allow duplicate methods with the same signature, instead of mapping static constructors directly to .cctor methods, my compiler generates one .cctor per class (where needed) that makes function calls to the <span style="font-style:italic;">static this()</span> constructors. The .cctor is not called if the class is never referenced -- this behavior is different from the native Digital Mars D compiler. If we comment out the one line in main, it will still print the constructor messages in native mode, but not under the .net compiler.<br /><br />D classes may also have one or more static destructors, as in this example:<br /><pre><code><br />class A<br />{<br /> static int i = 42;<br /> static this() <br /> {<br /> println("static A.this 1");<br /> }<br /> static this() <br /> {<br /> println("static A.this 2");<br /> }<br /> static ~this()<br /> {<br /> println("static A.~this 1");<br /> }<br /> static ~this()<br /> {<br /> println("static A.~this 2");<br /> }<br />}<br /></code></pre><br /><br />Unlike with the class constructors, there is no special IL method to map static destructors to. My compiler supports them with <a href="http://msdn.microsoft.com/en-us/library/system.appdomain.processexit.aspx">AppDomain.ProcessExit</a> event handlers, registered in reverse order of their lexical occurrences. IL allows non-member .cctor methods, and the compiler takes advantage of this feature to synthesize code that registers the static destructors as ProcessExit handlers.<br /><br />It is interesting to observe that the global .cctor <span style="font-weight:bold;">does reference the class</span> when it constructs the event handler delegates:<br /><pre><code><br />.method static private void .cctor()<br />{<br /> // register static dtor as ProcessExit event handler<br /> call class [mscorlib]System.AppDomain [mscorlib]System.AppDomain::get_CurrentDomain()<br /> ldnull<br /> ldftn void 'example.A'::'_staticDtor4'(object, class [mscorlib]System.EventArgs)<br /> newobj instance void [mscorlib]System.EventHandler::.ctor(object, native int)<br /> callvirt instance void [mscorlib]System.AppDomain::add_ProcessExit(class [mscorlib]System.EventHandler)<br /> // register static dtor as ProcessExit event handler<br /> call class [mscorlib]System.AppDomain [mscorlib]System.AppDomain::get_CurrentDomain()<br /> ldnull<br /> ldftn void 'example.A'::'_staticDtor3'(object, class [mscorlib]System.EventArgs)<br /> newobj instance void [mscorlib]System.EventHandler::.ctor(object, native int)<br /> callvirt instance void [mscorlib]System.AppDomain::add_ProcessExit(class [mscorlib]System.EventHandler)<br /> ret<br />}<br /></code></pre><br />This means that the .cctor of the class will be called, even if no user code ever references it.<br /><br />In addition to class static constructors and destructors, D also features <span style="font-weight:bold;">module static constructors and destructors</span>. These are expressed as non-member functions with the signature <span style="font-style:italic;">static this()</span> and <span style="font-style:italic;">static ~this()</span>, respectively.<br />For example:<br /><pre><code><br />//file b.d<br />import a;<br />version(D_NET)<br />{<br /> import System;<br /> alias Console.WriteLine println;<br />}<br />else<br />{<br /> import std.stdio;<br /> alias writefln println;<br />}<br /><br />static this()<br />{<br /> println("module B");<br /> map["foo"] = "bar";<br />}<br />static this()<br />{<br /> println("boo");<br />}<br />static ~this()<br />{<br /> println("~boo");<br />}<br /><br />//file a.d<br />version(D_NET)<br />{<br /> import System;<br /> alias Console.WriteLine println;<br />}<br />else<br />{<br /> import std.stdio;<br /> alias writefln println;<br />}<br /><br />string map[string];<br /><br />static this()<br />{<br /> println("module A");<br />}<br />static ~this()<br />{<br /> println("~module A");<br />}<br /><br />void main()<br />{<br /> foreach (k, v; map)<br /> {<br /> version(D_NET)<br /> {<br /> Console.WriteLine("{0} -> {1}".sys, k, v.sys);<br /> }<br /> else<br /> {<br /> writefln("%s -> %s", k, v);<br /> }<br /> }<br />}<br /></code></pre><br />It is noteworthy that regardless in which order the two files above are compiled the resulting program prints the same output:<br /><pre><br />module A<br />module B<br />boo<br />foo -> bar<br />~boo<br />~module A<br /></pre><br />The explanation lay in the D language rules: if a module B imports a module A, the imported module (A) must be statically initialized first (before B).<br /><br />As in the case of static constructors and destructors for classes, the compiler uses the global, free-standing .cctor method to stick calls to module ctors and register ProcessExit events that call the module's static dtors.<br /><br /><br /><span style="font-style:italic;">Thanks to <a href="http://www.blogger.com/profile/13116517988033017470">BCSd</a> for prompting this post with his comment and code sample.</span>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com4tag:blogger.com,1999:blog-18241482.post-81471419477208864182009-04-14T01:22:00.000-07:002009-04-21T11:09:04.972-07:00Static Constructors in D.NETThe D programming language features <span style="font-style: italic;">static constructors</span> that are similar to <span style="font-style: italic;">class constructors</span> in C#: they are called automatically to initialize the static fields (shared data) of a class.<br /><br />At the IL level, static constructors are implemented by the special <span style="font-style: italic;">.cctor</span> methods. The experimental compiler for D that I am working on in my virtual garage groups together user-written static constructor code with static field initializers into <span style="font-style: italic;">.cctor</span>s (and I believe that the C# compiler does the same).<br /><pre><code><br />class Example {<br /> static int solution = 42; // assignment is moved inside .cctor<br /> static double pi;<br /><br /> static this() { // explicit static ctor ==> .cctor<br /> pi = 3.14159;<br /> }<br />}<br /></code></pre>The code above produces the same IL as:<br /><pre><code><br />class Example {<br /> static int solution = 42;<br /> static double pi = 3.14159;<br />}<br /></code></pre><br />Also, the compiler synthesizes one class per module to group all "free-standing"global variables (if any).<br /><br />For example, the IL code that is generated out of this D source<br /><pre><code><br />static int x = 42;<br /><br />void main() {<br /> writefln(x);<br />}<br /></code></pre><br />is equivalent to the code generated for:<br /><pre><code><br />class ModuleData {<br /> static int x = 42;<br />}<br />void main() {<br /> writefln(ModuleData.x);<br />}<br /></code></pre><br />only that in the first case the ModuleData class is implicit and not accessible from D code. This strategy allows for the initializers of global variables to be moved inside the <span style="font-style: italic;">.cctor</span> of the hidden module data class.<br /><br />IL guarantees that the class constructors are invoked right before any static fields are first referenced. If the compiler flags the class with the <span style="font-weight: bold;">beforefieldinit</span> attribute, then the class constructors are called even earlier, i.e. right when the class is referenced, even if no members of the class are ever accessed (the C# compiler sets the <span style="font-weight: bold;">beforefieldinit</span> attribute on classes without explicit class constructors).<br /><br />Serge Lidin explains all the mechanics in his great book <a href="http://www.amazon.com/gp/product/1590596463?ie=UTF8&tag=zerobugscom-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=1590596463">Expert .NET 2.0 IL Assembler</a><img src="http://www.assoc-amazon.com/e/ir?t=zerobugscom-20&l=as2&o=1&a=1590596463" alt="" style="border: medium none ! important; margin: 0px ! important;" width="1" border="0" height="1" />, and recommends avoiding beforefieldinit, on grounds that invoking a .cctor is a slow business. I am considering using it though, on the synthesized module data class.<br /><br />In conjunction with a compiler-generated reference to the module data class, the <span style="font-weight: bold;">beforefieldinit</span> attribute will guarantee that the global variables are initialized on the main thread, and will avoid strange race conditions and bugs.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com2tag:blogger.com,1999:blog-18241482.post-73660862145229313332009-04-04T21:31:00.000-07:002009-04-04T22:30:36.951-07:00No Teleprompter to BlameI will never run for President of the United States. Not because I wouldn't like to, but because I can't: I am a Naturalized Citizen, one step below the Natural Born One. As depressing as this can be, there's a good side to it, too: I can always recant.<br /><br />I have the luxury to lightheartedly declare "Folks, I don't know what I was smoking when I said that <a href="http://the-free-meme.blogspot.com/2009/02/destruct-d-struct.html">D structs cannot be implemented as value types in .net</a>", without being afraid of losing any points in any poll.<br /><br />Further research proved that my initial argument, <span style="font-style: italic;">in .net value types do not participate in garbage collection</span> was... er irrelevant. That's because Walter Bright' s D compiler front-end is smart enough to insert calls to the structs' destructors wherever necessary! Now that's what I call a bright design. It doesn't matter that the CLR does not garbage-collect <span style="font-style: italic;">new</span>-ed value types, because the front-end generates the code that deletes them.<br /><br />I was running some compiler back-end tests for the D language post-blit operator when I realized that copying value types in IL is straight-forward; you LOAD the source variable / field / argument and STORE into the destination (boom!) whereas bit-copying managed classes is not as trivial.<br /><br />I did not give up right away. Hanging on to my <span style="font-style: italic;">structs-as-classes</span> implementation, I wrote a run-time helper blitting routine:<br /><pre><code><br /> using System.Runtime.InteropServices;<br /><br /> // assumes src and dest are of the same type<br /> static public void blit(Object dest, Object src)<br /> {<br /> int size = Marshal.SizeOf(src.GetType());<br /> IntPtr p = Marshal.AllocHGlobal(size);<br /> try<br /> {<br /> Marshal.StructureToPtr(src, p, false);<br /> Marshal.PtrToStructure(p, dest);<br /> }<br /> finally<br /> {<br /> Marshal.FreeHGlobal(p);<br /> }<br /> }<br /></code></pre><br />It did not take long for the truth to dawn upon me: Wow, bit-blitting non-value types is a major pain in the (oh) bum (ah). Efficient that code ain't (or should I say ISN'T? man do those consonants hurt). Honestly, I am not even sure that code is kosher. Better not to get into a pickle if one can avoid it... so back to the <span style="font-style: italic;">struct-as-value type</span> implementation I am.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-18852633644623688472009-03-28T22:28:00.000-07:002009-03-31T21:10:02.116-07:00D for ProgrammersI <a href="http://the-free-meme.blogspot.com/2009/02/reaching-closure.html">wrote a while ago</a> about implementing thread support in the D .net compiler. The idea was to generate code that constructs delegates that are passed to the Start method of the <a href="http://msdn.microsoft.com/en-us/library/system.threading.thread.aspx">System.Threading.Thread class</a>. I discussed some details of constructing delegates out of nested functions, and I concluded that my next thread-related task was to implement support for the <a href="http://www.digitalmars.com/d/2.0/statement.html#SynchronizedStatement"><span style="font-style: italic;">synchronized</span> keyword</a>.<br /><br />Like the postman who goes for a walk in the park after coming home from work, I relax in the after hours by working on pet projects like C++ debuggers and D compilers. So this Saturday morning I sat down to implement the code generation for <span style="font-style: italic;">synchronized</span>. The D language accepts two statement forms:<br /><pre><code><span style="font-style: italic;">synchronized</span> ScopeStatement<br /><span style="font-style: italic;">synchronized</span> (Expression) ScopeStatement<br /></code></pre>The former can be easily reduced to the latter by synthesizing a global object and an expression that references it.<br /><br />Here is a sample of D code that illustrates the use of the synchronized keyword:<pre><code><br />import System;<br /><br />class Semaphore {<br /> bool go;<br />}<br />Semaphore sem = new Semaphore;<br /><br />void main() {<br /> void asyncWork() {<br /> while (true) { // busy wait<br /> synchronized(sem) {<br /> if (sem.go) break;<br /> }<br /> }<br /> }<br /> Threading.Thread t = new Threading.Thread(&asyncWork);<br /> t.Start();<br /> synchronized(sem) {<br /> sem.go = true;<br /> }<br /> t.Join();<br />}<br /></code></pre>A <span style="font-style: italic;">synchronized</span> statement can be transformed into the following pseudo-code:<br /><pre><code>object m = Expression();<br />try {<br /> lock(m);<br /> ScopeStatement();<br />}<br />finally {<br /> unlock(m);<br />}<br /></code></pre>Implementing lock / unlock maps naturally to the Enter / Exit methods of the <a href="http://www.blogger.com/System.Threading.Monitor">System.Threading.Monitor</a> class. That's really all there is to it, generating the method calls is trivial.<br /><br />I was a bit disappointed by how easy the task turned out to be, but on the bright side I had plenty of time left to spend with my kid. I took him to Barnes and Noble to check out the Thomas trains and board books and the computer section, where I found the most helpful book title ever: "C# for Programmers". I guess no lawyer accidentally wandering through the computer book section can claim that he bought the book because the title was misleading. I wish that all book titles be so clear: "Finance for Accountants" or "Elmo Board Book for Toddlers".Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-63899592786472932512009-03-25T23:44:00.000-07:002009-03-27T02:17:15.026-07:00Another Perl in the WallThe most successful computer languages out there were born out of concrete problems: Perl in the beginning was nothing more than a Reporting Language; C came out of the need of writing OS-es in a portable fashion; PHP emerged of somebody's need for expressing dynamic web content as server-side macros. C# solves the problem of doing component programming without intricate COM knowledge and 2 PhD-s per developer.<br /><br />Typically, after the problem is solved, and the engineers scratched their itch, wrote the code, and shipped the (working!) products, some rather academic type decides: "Now I am going to redo it the right way" (and that's how UNIX got rewritten as Plan 9, a great OS that nobody uses).<br /><br />Interestingly enough, the redesigned products rarely end up being as successful as the original. People have been trying for years to replace things such as Windows, Office and the C programming language with "better" rewrites, but the market does not seem to care much. If it was good enough the first time around, it got adopted and used. Who cares how neat (or messy) the internal plumbings are?<br /><br />The C and C++ languages are great for doing low level systems programming; they may be harder to use for constructing applications, and I would definitely advise against using C++ for web development. The D programming language is fancying itself as a better C++ and I think that is true in the application development area. But I do not see D as a systems language. I will never write a task scheduler in a garbage-collected language. When I write system level stuff, I want the good old WYSIWYG behavior: no garbage collector thread running willy-nilly and no strange array slices (that are like arrays except for when they aren't). And thanks but no thanks, I want no memory fences, no <span style="font-style: italic;">thingamajica</span> inserted with parental care by the compiler to protect me from shooting my own foot on many-core systems. That is the point of systems programming: I want the freedom to shoot myself in the foot.<br /><br />I have been trying (unsuccessfully) to argue with some folks on the digitalmars.d newsgroup that the new 2.0 D language should not worry much about providing support for custom allocation schemes. D is designed <span>to help productivity</span>: it relieves programmers from the grueling tasks of managing memory, and it encourages good coding practices, but a systems language it is not. We already have C, C++ and assembly languages to do that low-level tweak when we need it.<br /><br />Sadly, some of the people involved with the design of D 2.0 are aiming for the moral absolute, rather than focus on shipping something that works well enough. I think it is a bad decision to allow for mixing the managed and unmanaged memory paradigms; it is even worse that there are no separate pointer types to disambiguate between GC-ed and explicitly-managed objects. C++ went that route in its first incarnation, and it wasn't long before people realized that it was really hard to keep track of what objects live on the garbage collected heap and what objects are explicitly managed. A new pointer type had to invented (the one denoted by the caret) to solve the problem.<br /><br />If folks really want to use D to program OS-es and embedded devices and rewrite the code that controls the breaks in their cars, they should at least make a separate D dialect and name it for what it is, <span style="font-style: italic;">Systems D</span>, <span style="font-style: italic;">Embedded D</span> or something like that. The garbage collection and other non-WYSIWYG features should be stripped out from such a dialect.<br /><br />The ambition of making D 2.0 an all encompassing, moral absolute language may cause 2.0 to never ship, never mind get wide adoption. Perl started out with more modest goals and ended up enjoying a huge mind share.<br /><br />So the <span style="font-style: italic;">ship-it today if it works</span> hacker in me feels like dedicating a song to the language purists:<br /><blockquote>We don't need no education<br />Perl's best language of them all,<br />We don't need no education<br />Thanks a bunch to Larry Wall!<br /></blockquote>Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com7tag:blogger.com,1999:blog-18241482.post-63159425290234844522009-03-20T02:45:00.001-07:002009-03-25T10:43:53.834-07:00Associative Arrays in D.NETThe D Programming Language supports <span style="font-style: italic;">foreach</span> loops over associative arrays.<br /><br />Associative arrays are data structures that look much like "normal" arrays, but the index types are not integers. Here's an example of an array of doubles indexed by strings, expressed in D:<br /><br /><span style="font-family:courier new;">double [string] a = [ "pi" : 3.14159, "e" : 2.718281828, "phi" : 1.6180339 ];</span><br /><br />The D language does not explicitly specify how associative arrays should be implemented. In C++ associative arrays can be implemented as standard STL <span style="font-family: courier new;">map</span>s, <span style="font-family: courier new;">hash_map</span>s (to be replaced by <span style="font-family: courier new;">unordered_map</span>s in C++0x) or with <a href="http://code.google.com/p/google-sparsehash/">Google's sparse hash map</a>s, to name a few possibilities.<br /><br />In other languages such as Python, associative arrays are called <span style="font-style: italic;">dictionaries</span>. The family of .NET languages take advantage of the <a href="http://msdn.microsoft.com/en-us/library/xfhwa508.aspx">System.Collections.Generic.Dictionary</a> class (this is also what the D compiler for .NET does: it implements associative arrays as system dictionaries).<br /><br />D provides an easy way to iterate over an associative array, the <span style="font-style: italic;">foreach</span> keyword. This keyword should be familiar to anyone programming in C#, UNIX shell, or managed C++. Here is an example for how it is being used in D:<pre><code><br />foreach (string key, double value; a) {<br /> version(D_NET) {<br /> Console.WriteLine("{0}={1}".sys, key, value);<br /> }<br /> else {<br /> writefln("%s=%f", key, value);<br /> }<br />}<br /></code></pre><br />The types for the key and value arguments can be explicitly specified, but that is not necessary as the compiler can infer them automatically. The <span style="font-style: italic;">foreach</span> line can be re-written more compactly as:<br /><code><br />foreach (key, value; a) {<br /></code><br />Another legal form for the statement, used to iterate over the values (and ignore the keys) is:<br /><code><br />foreach (value; a) {<br /></code><br /><br />The current implementation of the compiler front-end synthesizes a nested function out of the loop's body. The .NET back-end constructs a delegate out of this nested function and its closure; then it "wimps out" and calls a run-time helper written in C#:<pre><code><br /> public class AssocArray<br /> {<br /> public delegate int Callback<V>(ref V value);<br /> public delegate int Callback<K, V>(K key, ref V value);<br /><br /> static public void Foreach<K, V>(Dictionary<K, V> aa,<br /> int unused,<br /> Callback<V> callback)<br /> /// ...<br /> static public void Foreach<K, V>(Dictionary<K, V> aa,<br /> int unused,<br /> Callback<K, V> callback)<br /> /// ...<br /> }<br /></code></pre><br />The generic <span style="font-family: courier new;">Foreach</span> function has two overloads, to accommodate both forms of the foreach statement.<br /><br />D rules do not allow an array to be modified from within the loop, but <span style="font-weight: bold;">the elements of the array can be modified</span> if the value argument has a <span style="font-weight: bold;">ref</span> storage class:<pre><code><br />foreach (key, ref value; a) {<br /> value = 0.0;<br />}<br /></code></pre>C#'s rules are stricter, one cannot modify neither the collection (by adding / removing elements) nor change the individual elements. To work around this restriction, the run-time helper code does two passes over the dictionary that corresponds to the D associative array:<br /><pre><code><br />static public void Foreach<K, V>(Dictionary<K, V> aa,<br /> int unused, Callback<K, V> callback)<br />{<br /> Dictionary<K, V> changed = new Dictionary<K, V>();<br /> foreach (KeyValuePair<K, V> kvp in aa)<br /> {<br /> V temp = kvp.Value;<br /> int r = callback(kvp.Key, ref temp);<br /> if (!kvp.Value.Equals(temp))<br /> {<br /> changed[kvp.Key] = temp;<br /> }<br /> if (r != 0)<br /> {<br /> break;<br /> }<br /> }<br /> foreach (KeyValuePair<K, V> kvp in changed)<br /> {<br /> aa[kvp.Key] = kvp.Value;<br /> }<br />}<br /></code></pre><br />The Callback delegate is constructed from the address of a closure object and a nested <span style="font-style:italic;">foreach</span> function, both synthesized in the compiler. The generated code looks something like this:<br /><pre><code><br /> newobj instance void 'vargs.main.Closure_2'::.ctor()<br /> stloc.s 1 // '$closure3'<br /> ldloc.1 // '$closure3'<br /> ldftn instance int32 'vargs.main.Closure_2'::'__foreachbody1' (float64& '__applyArg0')<br /> // construct Foreach delegate<br /> newobj instance void class [dnetlib]runtime.AssocArray/Callback`1<float64>::.ctor(object, native int)<br /> .line 14<br /> call void [dnetlib]runtime.AssocArray::Foreach<string, float64>(<br /> class [mscorlib]System.Collections.Generic.Dictionary`2<!!0,!!1>,<br /> int32,<br /> class [dnetlib]runtime.AssocArray/Callback`1<!!1>)<br /></code></pre><br /><span style="font-weight:bold;">Edit:</span> After writing this piece I noticed that I forgot to mention one interesting side effect of my implementation: because there is no try / catch around the Callback call in the C# run-time support code, the foreach loop has all-or-nothing transactional semantics.<br /><br />For example, this program has different outputs when compiled with DMD from when it is compiled with my D / .NET compiler:<pre><code><br />version(D_NET)<br />{<br /> import System;<br /> import dnet;<br />}<br />else<br />{<br /> import std.stdio;<br />}<br /><br />void main()<br />{<br /> int [string] x = ["one" : 1, "two" : 2, "three" : 3];<br /><br /> try<br /> {<br /> foreach (ref v; x) <br /> {<br /> if (v == 3)<br /> throw new Exception("kaboom");<br /> v = 0; <br /> }<br /> }<br /> catch (Exception e)<br /> {<br /> version(D_NET)<br /> {<br /> Console.WriteLine(e.toString().sys);<br /> }<br /> else<br /> {<br /> writefln("%s", e.toString());<br /> }<br /> }<br /> foreach (k, v; x) <br /> {<br /> version(D_NET)<br /> {<br /> Console.WriteLine("{0}, {1}".sys, k, v);<br /> }<br /> else<br /> {<br /> writefln("%s, %d", k, v);<br /> }<br /> }<br />}<br /></code></pre><br />Under D/.NET it prints:<br /><pre><br />kaboom<br />one, 1<br />two, 2<br />three, 3<br /></pre><br />while the native compilation gives:<br /><pre><br />object.Exception: kaboom<br />two, 0<br />three, 3<br />one, 1<br /></pre><br />It would be very easy to get my compiler to emulate the native behavior, but I kind of like the "transactional" flavor...Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com6tag:blogger.com,1999:blog-18241482.post-36940511900904808692009-03-15T22:08:00.000-07:002009-03-15T22:27:58.697-07:00D Conditional CompilationThe D programming language supports <a href="http://www.digitalmars.com/d/2.0/version.html">conditional compilation</a> using version identifiers and version numbers, a solution that is slightly better than the #ifdef, pre-processor driven, way of C/C++ that most of us are used to.<br /><br />When using the .NET compiler for D that I am developing, one will be able to import and take advantage of .NET assemblies. For example the System.Console.WriteLine family of functions may come in handy. But such code would not compile when fed to the native Digital Mars D compiler.<br /><br />Conditional compilation and the version identifier D_NET do the trick, like in this example:<br /><pre><code><br />version(D_NET)<br />{<br /> import System;<br /> import dnet;<br />}<br />else<br />{<br /> import std.stdio;<br />}<br /><br />void main()<br />{<br /> int [string] x;<br /><br /> x["one"] = 1;<br /> x["two"] = 2;<br /><br /> foreach (k, v; x)<br /> {<br /> version(D_NET)<br /> {<br /> Console.WriteLine("{0}, {1}".sys, k, v);<br /> }<br /> else<br /> {<br /> writefln("%s, %d", k, v);<br /> }<br /> }<br />}<br /></code></pre><br />So I hacked the front-end of the D for .NET compiler to predefine D_NET.<br /><br />Of course, abusing conditional compilation will yield code that is unreadable and hard to grasp as a C++ source littered with #ifdef ... #else ... (or the US tax code).<br /><br />But I am a strong supporter of The Second Amendment of the Internet Constitution: "<span style="font-style: italic;">the right of the People to keep and bear compilers that let them shoot themselves in the foot shall not be infringed</span>".Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-85317444844930508152009-03-11T18:14:00.000-07:002009-03-15T18:15:16.814-07:00Strumming Strings In the D ChordIn my <a href="http://www.infoq.com/news/2009/03/D-NET">recent interview</a> with the InfoQ technology magazine I was asked about compatibility issues between D and .NET. I replied with a brief description of how array slices in D raise a conceptual incompatibility: <span style="font-style: italic;">System.Array</span> and <span style="font-style: italic;">System.ArraySegment</span> are distinct, unrelated types. In D arrays slices are indistinguishable from arrays and this creates the problems that I mentioned in the interview.<br /><br />But there are other incompatibilities between D and .NET that I did not mention because I wanted to keep the interview lean and focused.<br /><br />Take for example the built-in support for strings.<br /><br />The keyword <span style="font-style: italic;">string</span> is shorthand in both IL and C# for <a style="font-style: italic;" href="http://www.yoda.arachsys.com/csharp/strings.html">System.String</a> (essentially a sequence of Unicode characters in the range U+0000 to U+FFFF).<br /><br />In the D programming language, <span style="font-style: italic;">string</span> is shorthand for <span style="font-style: italic;">invariant char[]</span> and characters are unsigned bytes.<br /><blockquote><span style="font-size:100%;"><br /></span><span style="font-size:85%;"><span style="font-weight: bold;">Side notes</span>: D uses UTF8 to support foreign languages, and also sports the types </span><span style="font-style: italic;font-family:times new roman;font-size:85%;" >wstring</span><span style="font-size:85%;"> (a sequence of 2 byte-wide characters, compatible with Microsoft's Unicode) and </span><span style="font-style: italic;font-family:times new roman;font-size:85%;" >dstring </span><span style="font-size:85%;">(for UTF-32 strings). Wide and double-wide (UTF-32) string literals are denoted by the "w" and "d" respective suffixes, as in: "Hello"w, "Good Bye"d (UTF-32 dchar works in the native D compiler, but is not currently supported in my .NET compiler).</span></blockquote><span style="font-size:85%;"><br /></span>When a variable of type <span style="font-style: italic;">string</span> is encountered in a D source, the compiler emits a corresponding IL variable with the type <span style="font-style: italic;">unsigned int8[]</span>.<br /><br />In IL there is a special instruction, <span style="font-style: italic;">ldstr</span>, for loading string literals on the evaluation stack. This code<br /><pre><code>ldstr "Hello"<br /></code></pre>loads a "Hello" <span style="font-style: italic;">[mscorlib]System.String</span>. If this literal is to be stored into a variable (say "x"), then my compiler will insert conversion code that looks somewhat like this:<br /><code></code><pre><br />call class [mscorlib]System.Text.Encoding<br /> [mscorlib]System.Text.Encoding::get_UTF8()<br />ldstr "Hello"<br />callvirt instance uint8[]<br /> [mscorlib]System.Text.Encoding::GetBytes(string)<br /><br />stloc 'x' // store byte array into variable x<br /></pre><br />For the cases where a D string (array of bytes) has to be converted to a <span style="font-style: italic;">System.String</span> I provide an explicit string property, called <span style="font-style: italic;">sys</span>, with the following D prototype:<br /><code><br />static public String sys(string x);<br /></code><br />The D programmer would write something like this:<br /><code><br />import System;<br />// ... snip ...<br />string x = "Hello";<br />Console.WriteLine(x.sys);<br />Console.WriteLine("Hello .NET".sys);<br /></code><br /><br />The compiler figures out that in the case of<code><br />Console.WriteLine("Hello .NET".sys);<br /></code>the call to the <span style="font-style: italic;">sys</span> function can be elided, and generates straightforwardly:<code><br />ldstr "Hello .NET"<br />call void [mscorlib]System.Console::'WriteLine' (string)<br /></code><br />Matters get more interesting when we consider associative arrays. D offers a great convenience to programmers by supporting associative arrays directly in the language, for example<br /><code><br />int [string] dict;<br /><br />dict["one"] = 1;<br />dict["two"] = 2;<br />// ...<br /></code><br />introduces an array of integers indexed by strings. By contrast, in other languages such data structures are implemented "externally" in a library; in C++ for example, std::map<std::string, int> is implemented in the <a href="http://en.wikipedia.org/wiki/Standard_template_library">STL</a>; the C# equivalent of an associative array is the <a href="http://msdn.microsoft.com/en-us/library/xfhwa508.aspx">System.Collections.Generic.Dictionary</a>. My friend and colleague Ionut Gabriel Burete contributed an implementation of associative arrays in the D compiler for .NET using exactly that class.<br /><br />An associative array / dictionary with string keys is an interesting case, because <span style="font-style: italic;">System.String::Equals</span> does the right thing out of the box, namely performs a lexicographical comparison of two strings; <span style="font-style: italic;">System.Array::Equals</span> however simply compares object references, it does not iterate over and compare elements. This means that a <span style="font-style: italic;">Dictionary(string, int) </span>will behave as you expect, but if the key is of the <span style="font-style: italic;">unsigned int8[]</span> type you may be in for a surprise.<br /><br />For this reason, I put a hack in the compiler back-end: for the case of associative arrays I break away from representing D strings as byte arrays in .NET, and use <span style="font-style: italic;">System.String </span>instead, which works great (or so I thought up until I ran into the problem of generating the code for a <span style="font-style: italic;">foreach</span> iteration loop).<br /><br />For D code such as:<br /><pre><code><br />import System;<br />int [string] x;<br />x["one"] = 1;<br />x["two"] = 2;<br />// ...<br />foreach (k, v; x) {<br /> Console.WriteLine("{0}, {1}", k, v);<br />}<br /></code></pre><br />the compiler synthesizes a function that corresponds to the body of the loop, and binds the key and value ("k" and "v" in the code snippet) to local variables in that function (this happens all inside the front-end).<br /><br />The back-end must be able to detect the variables bound to <span style="font-style: italic;">foreach</span> arguments and reconcile the data types where necessary. In the example above the type of the "k" variable in the IL will thus be <span style="font-style: italic;">System.String</span>, and not <span style="font-style: italic;">unsigned int8[]</span>.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com4tag:blogger.com,1999:blog-18241482.post-46932460293923156932009-02-22T00:17:00.000-08:002009-02-22T01:03:40.669-08:00Reaching Closure...A diligent reader commented on my <a href="http://the-free-meme.blogspot.com/2009/02/nested-functions-and-delegates.html">previous post</a> that the implementation of nested functions in D for .NET was buggy for multi-threaded programs.<br /><br />Indeed, in the code below <code>asyncWork()</code> never returned. That's because a copy by-value of the variable <code>go</code> was used in the closure.<br /><pre><code><br />void main()<br />{<br /> bool go;<br /> <br /> void asyncWork()<br /> {<br /> while (!go)<br /> {<br /> //busy wait<br /> }<br /> }<br /> Threading.Thread t = new Threading.Thread(&asyncWork);<br /> t.Start();<br /><br /> go = true;<br />}<br /></code></pre><br />I am trying to avoid generating unverifiable code in this compiler project: IL does not allow managed pointers as fields in a class; ILASM accepts unmanaged pointers but that yields unverifiable code. My first instinct for closures was to use a copy for all the referenced variables, but as observed by my reader that approach did not work for multi-threaded programs.<br /><br />One way to solve the problem is to use unmanaged pointers in the closure; under this implementation the example above runs correctly. There may be at least another solution: wrap each referenced variable into an object, and have both the nested function and the surrounding context share the object reference; I found it to convoluted and pursued the unmanaged pointers route instead.<br /><br />This is how the generated IL looks for the D code in the example:<br /><pre><code><br />.module 'example'<br />.custom instance void [mscorlib]System.Security.UnverifiableCodeAttribute::.ctor() = ( 01 00 00 00 )<br /><br /><br />//--------------------------------------------------------------<br />// main program<br />//--------------------------------------------------------------<br />.method public hidebysig static void _Dmain ()<br />{<br /> .entrypoint<br /> .maxstack 3<br /> .locals init (<br /> [0] bool pinned 'go',<br /> [1] class [mscorlib]System.Threading.Thread 't',<br /> [2] class example.main.closure1 '$closure3'<br /> )<br /> newobj instance void example.main.closure1::.ctor()<br /> stloc.s 2 // '$closure3'<br /> ldloc.2 // '$closure3'<br /> ldloca 0 // 'go'<br /> stfld bool* 'example.main.closure1'::go2<br /> ldloc.2 // '$closure3'<br /> dup<br /> ldvirtftn instance void example.main.closure1::'asyncWork' ()<br /> newobj instance void class [mscorlib]System.Threading.ThreadStart::.ctor(object, native int)<br /> newobj instance void [mscorlib]System.Threading.Thread::.ctor (ThreadStart)<br /> stloc.s 1 // 't'<br /> ldloc.1 // 't'<br /> callvirt instance void [mscorlib]System.Threading.Thread::'Start' ()<br /> ldc.i4 1<br /> stloc.s 0 // 'go'<br /> ret<br />}<br /><br />.class private auto example.main.closure1 extends [dnetlib]core.Object<br />{<br /><br /> .method public virtual newslot hidebysig instance void 'asyncWork' ()<br /> {<br /> .maxstack 2<br />L1_example:<br /> ldarg.0<br /> ldfld bool* 'example.main.closure1'::go2<br /> ldind.i1<br /> ldc.i4 0<br /> beq L1_example<br /> ret<br /> }<br /> .field public bool* go2<br /> // default ctor, compiler-generated<br /> .method public hidebysig instance void .ctor()<br /> {<br /> ldarg.0<br /> call instance void [dnetlib]core.Object::.ctor()<br /> ret<br /> }<br />} // end of example.main.closure1<br /></code></pre><br />Now there is only one more <em>small</em> problem to address: synchronization between threads...Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com3tag:blogger.com,1999:blog-18241482.post-59579648188660416122009-02-11T22:42:00.000-08:002009-02-12T13:03:08.993-08:00Nested Functions and DelegatesMy previous post missed one aspect of delegates in D: nested functions. Walter Bright gave me this example:<br /><pre><br />int delegate() foo(int i)<br />{<br /> int bar() { return i; }<br /> return &bar;<br />}<br /></pre><br />Function <em>bar</em> is nested inside <em>foo</em>; <em>foo</em> wraps <em>bar</em> into a delegate which is returned. My blog post is guilty of overlooking this use case for delegates; yet my compiler implementation is innocent: the example compiles and runs correctly.<br /><br />The code example may look like a new use case at first, but is in fact similar to making a delegate from an object instance and a method:<br /><pre><br />class Foo {<br /> int i;<br /> int bar() { return i; }<br />}<br />...<br />Foo f = new Foo;<br />int delegate() dg = &f.bar;<br /></pre><br />The reason is that there is an invisible object in the nested function case. In the D programming language, nested functions have access to the surrounding lexical scope (note how function <em>bar</em> uses <em>i</em> which is declared as a parameter of <em>foo</em>); the .NET D compiler represents internally the lexical <strong>context</strong> of the nested function as an object. The fields of the context object are shallow copies of the variables in the "parent" scope. The IL class declaration for the context is synthesized by the compiler, which also instantiates the context. The context is populated on the way in (before calling the nested function) and used to update the variables in the parent scope on the way out (after the call has completed).<br /><br />The constructor of a delegate object takes two parameters: an object reference and a pointer to a function; in the case of nested functions, the first parameter that the compiler passes under the hood is the context object. This is why constructing a delegate from a nested function is not different from using an object and one of its methods.<br /><br />What if the nested function is declared inside of a class method (you ask). In this case there is no need to synthesize a class declaration to model the context of the nested call. The class to which the method belongs is augmented with hidden fields that shadow the variables in the parent scope.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com3tag:blogger.com,1999:blog-18241482.post-9525934303215790862009-02-10T22:40:00.000-08:002009-02-12T13:03:38.932-08:00Delegates in D for .NETThis past weekend I typed "Joe Newman" in <a href="http://www.pandora.com">Pandora</a> and sat down for a couple of hours to implement delegates in my .NET back-end for the D compiler.<br /><br />I begun by studying the documentation on MSDN and I noticed some differences in the way delegates work in .NET and D.<br /><br />In .NET (and C#) delegates are objects that wrap pointers to functions so that they can be manipulated and invoked safely. The functions may be either standalone or members of a class. In D, the concept of delegates applies only to member functions. Delegates may be called asynchronously in .NET (I am not aware of a similar feature in the D programming language). The concept of delegates is thus simpler in D.<br /><br />The implementation that I came up with is straight-forward: classes that derive from [mscorlib]System.MulticastDelegate are generated for each delegate type. The classes are sealed and each have a virtual Invoke method that matches the signature of the D delegate.<br /><br />For the following D code snippet<br /><pre><br />class Test<br />{<br /> void fun(int i)<br /> { ...<br /> ...<br /> }<br />}<br />Test t = new Test;<br />void delegate(int) dg = &t.fun; <br /></pre><br />the generated IL looks like this:<br /><pre><br />.class sealed $Delegate_1 extends [mscorlib]System.MulticastDelegate<br />{<br /> .method public instance void .ctor(object, native int) runtime managed {}<br /> .method public virtual void Invoke(int32) runtime managed {}<br />}<br />...<br />...<br />.locals init (<br /> [0] class Test 't',<br /> [1] class $Delegate_1 'dg'<br /> )<br />newobj instance void delegate.Test::.ctor ()<br />stloc.s 0 // 't'<br /><br />ldloc.0 // 't'<br />dup<br />ldvirtftn instance void delegate.Test::'print' (int32 'i')<br />newobj instance void class $Delegate_1::.ctor(object, native int)<br />stloc.1<br /></pre><br />One small (and annoying) surprise that I had was that although <a href="http://www.ecma-international.org/publications/standards/Ecma-335.htm">the IL standard</a> contains code samples with user-defined classes derived directly from [mscorlib]System.Delegate, such code did not pass PEVERIFY and, more tragically, crashed at run-time. The error message ("Unable to resolve token", or something like that) was not helpful; but the ngen utility dispelled the confusion by stating bluntly that my class could not inherit System.Delegate directly. Replacing System.Delegate with System.MulticastDelegate closed the issue.<br /><br />Once I got delegates to work for class methods, I realized that the code can be reused to support D pointers to functions as well. In D pointers to functions are a different concept from delegates; in .NET however, a delegate can be constructed from a standalone function by simply passing a null for the object in the constructor. It is trivial for the compiler to generate code that instantiates .NET delegates in lieu of function pointers.<br /><br />One nice side-effect of representing pointers to functions as delegates is that they can be aggregated as class members, unlike pointers to other data types <a href="http://the-free-meme.blogspot.com/2008/12/is-there-point-in-using-pointers.html"> that cannot be aggregated</a> as struct or class fields (an IL-imposed restriction for managed pointers).<br /> <br />I hope that one day D decides to support asynchronous delegate calls. I have yet to imagine the possibilities for asynchronous, pure methods. <br /><br />Until then, the .NET back-end is moving along getting closer and closer to a public release.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0tag:blogger.com,1999:blog-18241482.post-85740166482880731472009-02-08T21:46:00.000-08:002009-02-08T23:12:04.121-08:00D-elegating ConstructorsThe D programming language allows a constructor of a class to call another constructor of the same class, for the purpose of sharing initialization code. This feature is called "delegating constructors"; it is also present in C# and in the emerging <a href="http://www-949.ibm.com/software/rational/cafe/blogs/cpp-standard/2008/12/04/c0x-delegating-constructors">C++ 0x</a>.<br /><br />C#'s syntax for delegating constructors resembles the initializer lists in C++, and strictly enforces that the delegated constructor is called before any other code in the body of the caller constructor; the feature is masterfully explained in <a href="http://www.amazon.com/gp/product/0321485890?ie=UTF8&tag=zerobugscom-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0321485890">More Effective C#: 50 Specific Ways to Improve Your C# (Effective Software Development Series)</a><img src="http://www.assoc-amazon.com/e/ir?t=zerobugscom-20&l=as2&o=1&a=0321485890" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />.<br /><br />D is more flexible, a constructor can be called from another constructor's body pretty much like any other "regular" method, provided that some <a href="http://www.digitalmars.com/d/2.0/class.html">simple rules</a> are observed (for example, it is not permitted to call a constructor from within a loop).<br /><br />A D compiler must detect constructor delegation and ensure that some initialization code is not executed more than once. Let's consider an example:<br /><pre><br />class Example<br />{<br /> int foo = 42;<br /> int bar;<br /><br /> this()<br /> { <br /> bar = 13; <br /> }<br /> this(int i)<br /> {<br /> foo = i;<br /> this();<br /> }<br />}<br /></pre><br />In the first constructor, before the field <em>bar</em> is assigned the value 13, some "invisible" code executes: first, the constructor of the base class is invoked. The <em>Example</em> class does not have an explicit base; but in D, similar to Java and C#, all classes have an implicit root Object base. It is as if we wrote:<pre><br />class Example : Object<br />{ ...<br />}<br /></pre><br />After generating the call to Object's constructor, the compiler generates the code that initializes <em>foo</em> to 42. The explicit assignment as written by the programmer executes after wards. <br /><br />The compiler must be careful so that the initializations steps described above happen only once in the second constructor. This is not simply a matter of efficiency; it is more importantly, a matter of correctness. If calling the base Object constructor and the initialization of foo where generated blindly <strong>inside the body of each constructor</strong>, then the following would happen in the second constructor's case:<br /><ol><br /><li>Object's ctor is invoked (compiler generated)</li><br /><li>foo = 42 (compiler generated)</li><br /><li>foo = i (programmer's code)</li><br /><li>constructor delegation occurs (programmer's code), which means that:</li><br /><li>Object's ctor is invoked</li><br /><li>foo = 42 (compiler generated)</li><br /></ol><br />This is obviously incorrect, since it leaves the <em>Example</em> object in a different state than the programmer intended.<br /><br />Such scenario is very easily avoided by a native compiler. Object creation is translated to several distinct steps:<br /><ol><br /><li>memory for the object is allocated</li><br /><li>invocation of base ctor is generated</li><br /><li>initializers are generated (this is where foo = 42 happens)</li><br /><li>constructor as written by programmer is invoked</li><br /></ol><br />The important thing to note is that in the native compiler's case the compiler leaves the constructors alone, as written by the programmer, and inserts its magic "pre-initializaton" steps in between the memory allocation and constructor invocation.<br /><br />When writing a compiler back-end for .NET things are slightly different: the creation of an object is expressed in one compact, single line of MSIL (Microsoft Intermediary Language) assembly code:<br /><pre><br />newobj <constructor call><br /></pre><br />In our example, that would be<br /><pre><br />newobj void class Example::.ctor()<br /></pre><br />and<br /><pre><br />newobj void class Example::.ctor(int32)<br /></pre><br />respectively. So the compiler-generated magic steps of calling the base constructor, etc have to happen <strong>inside</strong> the constructor body. To prevent the erroneous scenario of double-initialization from happening, I had to generate a hidden, "guard" Boolean field for classes that use constructor delegation. The variable is set when entering a constructor's body; it is checked inside each constructor before calling the base constructor and stuff. Here's how the generated IL code looks like:<pre><br />//--------------------------------------------------------------<br />// ctor.d compiled: Sun Feb 08 23:04:49 2009<br />//--------------------------------------------------------------<br />.assembly extern mscorlib {}<br />.assembly extern dnetlib {}<br />.assembly 'ctor' {}<br /><br />.module 'ctor'<br /><br /><br />.class public auto ctor.Example extends [dnetlib]core.Object<br />{<br /> .field public int32 foo<br /> .field public int32 bar<br /> .method public hidebysig instance void .ctor ()<br /> {<br /> .maxstack 3<br /> ldarg.0<br /> ldfld bool 'ctor.Example'::$in_ctor<br /> brtrue L0_ctor<br /> ldarg.0<br /> call instance void [dnetlib]core.Object::.ctor()<br /> ldarg.0<br /> ldc.i4 42<br /> stfld int32 'ctor.Example'::foo<br />L0_ctor:<br /> ldarg.0 // 'this'<br /> ldc.i4 13<br /> stfld int32 'ctor.Example'::bar<br /> ret<br /> }<br /> .method public hidebysig instance void .ctor (int32 'i')<br /> {<br /> .maxstack 3<br /> ldarg.0<br /> call instance void [dnetlib]core.Object::.ctor()<br /> ldarg.0<br /> ldc.i4 42<br /> stfld int32 'ctor.Example'::foo<br /> ldarg.0 // 'this'<br /> ldarg.1 // 'i'<br /> stfld int32 'ctor.Example'::foo<br /> ldarg.0 // 'this'<br /> ldc.i4 1<br /> stfld bool 'ctor.Example'::$in_ctor<br /> ldarg.0<br /> call instance void ctor.Example::.ctor ()<br /> ret<br /> }<br /> .field bool $in_ctor<br />} // end of ctor.Example<br /></pre><br />As a side note, in the second constructor's case a small redundancy still exists: <em>foo</em> is assigned to 42 only to be set to another value right away. I am hoping that this isn't much of an issue if the JIT engine detects it and optimizes it out. I'd be happy to hear any informed opinions.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com1tag:blogger.com,1999:blog-18241482.post-57192813107851745652009-02-01T12:49:00.000-08:002009-02-02T10:15:49.390-08:00Stepping Over STL Code<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBnTURT3yRbY_vDAhREmW2vgeLK5vs6XVRInMaa-deeeQmy23w9T98XLl1uiJ4FxCEK_X2RZhzoh8lMdETMZyaksxA1oaIx1utxN5ikNSyHPDYe278JkT7nB_10kJaXVPAbTZpUw/s1600-h/step.png"><img style="cursor: pointer; width: 400px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBnTURT3yRbY_vDAhREmW2vgeLK5vs6XVRInMaa-deeeQmy23w9T98XLl1uiJ4FxCEK_X2RZhzoh8lMdETMZyaksxA1oaIx1utxN5ikNSyHPDYe278JkT7nB_10kJaXVPAbTZpUw/s400/step.png" alt="" id="BLOGGER_PHOTO_ID_5297933972183716562" border="0" /></a><br /><br />When debugging C++ code written using the Standard Template Library (STL) it is not unusual to find yourself stepping through STL code. Most of the time, this is not very useful: The STL implementation typically comes bundled with the C++ compiler, and it has been thoroughly tested by the vendor; it is unlikely that the bug you are after is caused by the STL.<br /><br />So when a statement such as <code>myVector.push_back(x)</code> is encountered while tracing with the debugger, you normally want to step <strong>over</strong> it, not <strong>into</strong> it. Most debuggers offer a "step over" and a "step into" function. So you would chose "step over". <br /><br />But how about this? You want to debug a routine named <code>my_func(size_t containerSize)</code> and want to step into the body of <code>my_func</code> when this statement is hit: <code>my_func(myVector.size())</code>. If you select "step into", the debugger will first take you into the guts of STL's <code>vector<T>::size()</code> implementation before stepping into <code>my_func</code>.<br /><br />The ZeroBUGS debugger allows you to avoid such annoyances. Once inside size(), you can right click, and select to "Always step over..." that function, all functions in that file, or all files in the same directory. The debugger will remember your option, and you don't have to see the guts of size(), or any other vector function, or any other STL function, respectively. <br /><br />The functionality can be used not just with the STL but any code. If you later change your mind, the "Manage" menu allows you to remove functions, files or directories from the step-into blacklist.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com3tag:blogger.com,1999:blog-18241482.post-30844054548759114712009-02-01T00:02:00.000-08:002009-02-11T22:39:50.084-08:00To Destruct a D StructI wrote <a href="http://the-free-meme.blogspot.com/2008/12/is-there-point-in-using-pointers.html"><span style="text-decoration: underline;">a while ago</span></a> about similarities between D and .NET (and implicitly C#). My interest in mapping D features to .NET is driven by a research project that I took on a few months ago: a D 2.0 language compiler for .NET (<a href="http://en.wikipedia.org/wiki/D_(programming_language)">D 2.0 is a branch version of D that includes experimental features</a>). I was mentioning how in both D and C# structs are lightweight, value types.<br /><br />After working on struct support in more detail, I have come to the realization that D structs cannot be implemented as .NET value type classes. Rather, they have to be implemented as reference type classes.<br /><br />The short explanation is that while in IL value classes do not participate in garbage collection, D expects the GC to reap structs after they are no longer in use.<br /><br />Interestingly enough, value types may be newobj-ed (not just created on the stack).<br /><br />We can use a simple example to demonstrate the difference between value classes and reference classes. If we compile the following program using the IL assembler (ILASM) and run it, nothing gets printed on the screen:<br /><code><pre><br />.assembly extern mscorlib {}<br />.assembly 'test' {}<br /><br />.class public value auto Test<br />{<br /> .field public int32 i<br /><br /> .method public void .ctor()<br /> {<br /> ret<br /> }<br /> .method virtual family void Finalize()<br /> {<br /> ldstr "finalizing..."<br /> call void [mscorlib]System.Console::WriteLine(string)<br /> ret<br /> }<br />}<br />//--------------------------------------------------------------<br />// main program<br />//--------------------------------------------------------------<br />.method public static void main ()<br />{<br /> .entrypoint<br /> .locals init (<br /> <strong>class</strong> Test t<br /> )<br /> newobj instance void Test::.ctor()<br /> stloc 't'<br /> ret<br />}<br /></pre><br /></code><br />But if we changed the declaration of the Test class from a value type to class, like this:<br /><code><pre><br />.class public auto Test<br /></pre></code><br />we could see "finalizing..." printed, a confirmation that the destructor (the Finalize method) is being invoked by the garbage collector. All it takes is removing "value" from the declaration.<br /><br />In IL, value types have no self-describing type information attached. I suspect that the reason for not having them being garbage collected is that, without type information, the system cannot possibly know which (virtual) Finalize method to call (note that although C# struct are implemented as sealed value classes, "sealed" and "value" are orthogonal).<br /><br />D supports the <a href="http://en.wikipedia.org/wiki/Design_by_contract">contract programming</a> paradigm, and <a href="http://www.digitalmars.com/d/2.0/class.html#invariants">class invariants</a> is one of its core concepts.<br /><br />The idea is that the user can write a special method named "invariant", which tests that certain properties of a class or struct hold. In debug mode, the D compiler inserts "probing points" throughout the lifetime of the class (or struct), ensuring that this function is automatically called: after construction, before and after execution of public methods, and <strong>before destruction</strong>. <br /><br />The natural mechanism for implementing the last statement is to generate a call to the invariant method at the top the destructor function body. But if the destructor is never called then we've got a problem.<br /><br />So having destructors work correctly is not just a matter of collecting memory after the struct expires, but it is also crucial to contract programming in D.<br /><br />Assignment to structs and passing in and to functions may become heavier weight in D.NET than in the native, Digital Mars D compiler (albeit this is something that I have to measure) by implementing structs as reference type classes, but it is necessary in order to support important D language features.Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com3tag:blogger.com,1999:blog-18241482.post-42811788579596923662009-01-22T19:42:00.000-08:002009-01-22T22:30:08.647-08:0042Yesterday night, at the monthly <a href="http://nwcpp.org/">NWCPP</a> meeting Walter Bright gave a <a href="http://nwcpp.org/Meetings/2009/01.html">presentation</a> on meta-programming using the D language. Once again, D put C++ to shame.<br /><br />Because of transportation arrangements I could not accompany Walter et. Co to the watering hole after the lecture. Instead I went home and decided to test how my D.NET work-in-progress compiler handles templates, and what kind of code it generates.<br /><br />I picked a variadic template for my test, which computes the maximum of an arbitrarily long list of numbers (adapted from a version written by Andrei Alexandrescu) :<br /><br /><pre>import System;<br /><br />auto max(T1, T2, Tail...)(T1 first, T2 second, Tail args)<br />{<br /> auto r = second > first ? second : first;<br /> static if (Tail.length == 0) {<br /> return r;<br /> }<br /> else {<br /> return max(r, args);<br /> }<br />}<br /><br />void main()<br />{<br /> uint k = 42;<br /> auto i = max(3, 2, k, 2.5);<br /> Console.WriteLine(i);<br />}<br /></pre><br /><br />The program above prints 42 (of course), and here's how the generated IL looks like:<br /><br /><pre><br />//--------------------------------------------------------------<br />// max.d compiled: Thu Jan 22 19:38:26 2009<br />//--------------------------------------------------------------<br />.assembly extern mscorlib {}<br />.assembly extern dnetlib {}<br />.assembly 'max' {}<br /><br />.module 'max'<br /><br />//--------------------------------------------------------------<br />// main program<br />//--------------------------------------------------------------<br />.method public hidebysig static void _Dmain ()<br />{<br />.entrypoint<br />.maxstack 4<br />.locals init (<br />[0] unsigned int32 'k',<br />[1] float64 'i'<br />)<br />ldc.i4 42<br />stloc.s 0 // 'k'<br />ldc.i4 3<br />ldc.i4 2<br />ldloc.0 // 'k'<br />ldc.r8 2.5<br />call float64 _D3max16__T3maxTiTiTkTdZ3maxFiikdZd (<br /> int32 'first', int32 'second', unsigned int32, float64)<br />stloc.s 1 // 'i'<br />ldloc.1 // 'i'<br />call void [mscorlib]System.Console::'WriteLine' (float64)<br />ret<br />}<br />.method public hidebysig static float64 _D3max16__T3maxTiTiTkTdZ3maxFiikdZd (<br /> int32 'first', int32 'second', unsigned int32, float64)<br />{<br />.maxstack 4<br />.locals init (<br />[0] int32 'r'<br />)<br />ldarg.1 // 'second'<br />ldarg.0 // 'first'<br />bgt L0_max<br />ldarg.0 // 'first'<br />br L1_max<br />L0_max:<br />ldarg.1 // 'second'<br />L1_max:<br />stloc.s 0 // 'r'<br />ldloc.0 // 'r'<br />ldarg.2 // '_args_field_0'<br />ldarg.3 // '_args_field_1'<br />call float64 _D3max14__T3maxTiTkTdZ3maxFikdZd (<br />int32 'first', unsigned int32 'second', float64)<br />ret<br />}<br />.method public hidebysig static float64 _D3max14__T3maxTiTkTdZ3maxFikdZd (<br /> int32 'first', unsigned int32 'second', float64)<br />{<br />.maxstack 3<br />.locals init (<br />[0] unsigned int32 'r'<br />)<br />ldarg.1 // 'second'<br />ldarg.0 // 'first'<br />conv.u4<br />bgt L2_max<br />ldarg.0 // 'first'<br />conv.u4<br />br L3_max<br />L2_max:<br />ldarg.1 // 'second'<br />L3_max:<br />stloc.s 0 // 'r'<br />ldloc.0 // 'r'<br />ldarg.2 // '_args_field_0'<br />call float64 _D3max12__T3maxTkTdZ3maxFkdZd (unsigned int32 'first', float64 'second')<br />ret<br />}<br />.method public hidebysig static float64 _D3max12__T3maxTkTdZ3maxFkdZd (<br /> unsigned int32 'first', float64 'second')<br />{<br />.maxstack 2<br />.locals init (<br />[0] float64 'r'<br />)<br />ldarg.1 // 'second'<br />ldarg.0 // 'first'<br />conv.r8<br />bgt L4_max<br />ldarg.0 // 'first'<br />conv.r8<br />br L5_max<br />L4_max:<br />ldarg.1 // 'second'<br />L5_max:<br />stloc.s 0 // 'r'<br />ldloc.0 // 'r'<br />ret<br />}<br /></pre><br /><strong>Edit:</strong> One more reason for loving D templates: pasting D code into HTML does not require replacing angular brackets with &lt; and &gt; respectively!Cristachehttp://www.blogger.com/profile/08287129746971472910noreply@blogger.com0