Coding

This is my favorite utility when monkeying around with (ie, testing) generic exception-handling code:

class Poop : Exception { this() { // It's a bird! It's a plane! No, it's... super("POOP!"); } } @property auto POOP() { return new Poop(); }

As if you haven't already figured out this utility's obvious benefit:

throw POOP;

Of course, if you're using a language that allows any old type of crap to be thrown (which I don't ordinarily prefer), it's even easier:

// Cut the crap and just throw it! throw "POOP!";

Read more

Note: See the updates at the bottom of this article.

First, a little teaser (in the D programming language):

// testInputVisitor.d // Requires DMD compiler v2.059 or up import std.algorithm; import std.range; import std.stdio; import libInputVisitor; struct Foo { string[] data = ["hello", "world"]; void visit(InputVisitor!(Foo, string) v) { v.yield("a"); v.yield("b"); foreach(str; data) v.yield(str); } void visit(InputVisitor!(Foo, int) v) { v.yield(1); v.yield(2); v.yield(3); } } void main() { Foo foo; // Prints: a, b, hello, world foreach(item; foo.inputVisitor!string) writeln(item); // Prints: 1, 2, 3 foreach(item; foo.inputVisitor!int) writeln(item); // It's a range! Prints: 10, 30 auto myRange = foo.inputVisitor!int; foreach(item; myRange.filter!( x => x!=2 )().map!( x => x*10 )()) writeln(item); }

Rewinding back to the start, here's our original problem: We want to iterate over a collection.

Ever since the D1 days, D has had foreach's parter, opApply, as the standard way to do this:

// testOpApply.d import std.stdio; struct Foo { string[] data = ["hello", "world"]; int opApply(int delegate(string) dg) { int result=0; result = dg("a"); if(result) return result; result = dg("b"); if(result) return result; foreach(str; data) { result = dg(str); if(result) break; } return result; } } void main() { Foo foo; // Prints: a, b, hello, world foreach(item; foo) writeln(item); }

The logic within opApply is mostly natural and straightforward, but it is complicated a bit by dealing with that result variable.

Later on, D2 came along and introduced ranges - D's clean, powerful answer to C++/STL's iterators. The concept of ranges and their motivations and benefits are well explained in Andrei Alexandrescu's classic article On Iteration (and further information is in this article), so I won't go into that.

Here's an input range version of the above examples:

// testInputRange.d import std.stdio; struct Foo { string[] data = ["hello", "world"]; @property auto inputRange() { struct FooRange { private Foo foo; private size_t index=0; @property bool empty() { return index >= foo.data.length + 2; } @property string front() { if(index == 0) return "a"; if(index == 1) return "b"; return foo.data[index-2]; } void popFront() { index++; } } return FooRange(this); } } void main() { Foo foo; // Prints: a, b, hello, world foreach(item; foo.inputRange) writeln(item); }

Unfortunately, that's more complex than the old opApply style, but it provides some very good benefits, particularly when used together with Phobos's std.algorithm and std.range.

But if all you need is basic foreach-style input range capabilities, that can be a lot of boilerplate. Plus, it doesn't lend itself to complex internal logic quite as naturally as opApply does. And opApply itself could stand to be easier to write.

If you've looked carefully, you may have noticed that opApply is essentially a poor man's coroutine. That's why the flow of logic is more natural in opApply than in the range version. For those unfamiliar with coroutines, see this old-but-excellent set of slides and the accompanying video. Here's the upshot: Coroutines are like a combination of traditional iterators and the visitor pattern - combining the best of both worlds.

D offers coroutines via Fiber. Looking at the docs, one of the two main ways to use Fiber is by subclassing it. Hmm...a class...easy coroutine iteration...What if we designed a Fiber subclass that was also a range?

As it turns out, fiber coroutines and input ranges make a fantastic combination that combines the power and flexibility of an input range with opApply's natural flow of logic, but without the boilerplate of opApply's messy result variable. You've already seen in the first example how easy it is to use this InputVisitor, as I call it. The source is very short, and available in the file libInputVisitor.d.

There is one small enhancement we can make to the original example, though. Compared to the opApply version, the foreach when using InputVisitor is a little more verbose:

foreach(item; foo.inputVisitor!string)

We can trim that down by adding one member to the Foo struct:

... struct Foo { ... @property auto visitor() { return this.inputVisitor!string; } ... } void main() { Foo foo; // Prints: a, b, hello, world foreach(item; foo.visitor) writeln(item); ... }

Another member can also be added to handle the int version.

The downside of this is that it doesn't lend itself very well - if even at all - to any ranges more powerful than the basic input range. Execution of a function doesn't flow in reverse, so bidirectional ranges are out. And certainly no random access. Forward range might be possible in theory, but it would depend on being able to clone a halted fiber - I don't know whether that's possible.

Beware, I haven't done any benchmarks on this, so I have no idea how much of an overhead this InputVisitor might have over the opApply or input range versions. Could be a lot, could be minimal - I don't know.

UPDATE (2012-05-01): Changed libInputVisitor license to WTFPL. For something this trivial, even the super-permissive zlib/libpng license is overkill.

Read more

While generics have become fairly common in many languages, the similar (but more general) concept of templates are fairly uncommon among languages. As such, many people have only a passing familiarity with them. It doesn't help that the most well-known example of templates, those in C++, have...well...they're earned a reputation for being an advanced concept.

This is unfortunate, because at their core, templates are really both very simple and very powerful. Especially if you use D.

Here's a little template primer I initially wrote in response to a newsgroup post:

A template is just a clean way of generating code instead of manually copy-pasting a bunch of times (which would end up being a maintenance nightmare).

Suppose you have this:

int add(int a, int b) { return a + b; }

That's called, of course, like this:

add(7, 42);

Suppose you then want another version of the same function, but with double instead of int:

double add(double a, double b) { return a + b; }

Called like this:

add(3.14, 5.73);

Now you have two functions that are exactly the same, just with one little thing changed. If you need to modify one function, you'll have to remember to modify the other, too. God help you if it's a really big function and you accidentally make a mistake copying it. It just gets to be a big problem. It violates what we call DRY: "Don't Repeat Yourself".

Some languages, like Java or C#, try to solve this issue by making everything an object (or in dynamic languages, a variant). Then they pass around those "boxed" versions instead. This might be done manually, or it may be automatic via autoboxing or generics. Either way, there's a problem: performance. These boxed types, whether objects or variants, are not free: They require extra time and memory. In same cases, the difference is negligible, but in critical sections it can easily add up. So you have to be careful about where and when you use this form of generic code.

Let's step back into first grade for a minute: Have you ever drawn or painted with stencils? You make one design, once, by cutting it out of paper. Then you can easily draw and redraw the same design with different colors: Just place the stencil on a new piece of paper, choose a color, fill it in, lift the stencil, and boom! Suddenly there's another copy of your design, no matter how intricate, in whatever color variation you want.

Templates are stencils for code. Heck, even outside of code this is true, too: "Template" is just another word for "stencil".

So here's how you make a stencil for an add() function. Just "punch out" whatever you want to change, by making it a template parameter:

// Make a "stencil" template myTemplate(T) { // This is what's inside the "stencil" T add(T a, T b) { return a + b; } }

Notice how the add() function is exactly the same as before, but the ints were changed to T (for "Type").

Now let's stamp down some add() prints:

// The dot in between is because "add" is *inside* the template "myTemplate" myTemplate!(int).add(7, 42); myTemplate!(double).add(3.14, 5.73);

That too, is almost exactly the same as before. I've only added that myTemplate!(int) and the similar myTemplate!(float). The compiler turns those into:

int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; }

And then calls them:

add(7, 42); add(3.14, 5.73);

Those are exactly the functions we were manually writing before! Not only that, but unlike generics or dynamic types, there's no time or memory overhead, so it's perfectly safe to use this in performance-critical sections!

A technical side-note: Truthfully, there is a small amount of extra memory used simply because we're generating code for another whole function. But that's much less of an issue than it may seem. First of all, a Java-style or dynamic-style "generics" version of the function would involve extra code being generated, too - the extra code to detect and handle the types of the variables at runtime. Secondly, the extra memory here is "per function generated", not "per variable". You could juggle millions of variables in template version, and it still wouldn't increase memory usage. But that's not necessarily true of a non-template "generics" version.

Suppose now we want to use add() with ulong and BigInt, too. Instead of manually copying the function and changing the type, we can just let the compiler copy the function and change the type:

myTemplate!(ulong).add(7, 42); myTemplate!(BigInt).add(BigInt(7), BigInt(42));

The compiler, of course, automatically generates:

ulong add(ulong a, ulong b) { return a + b; } BigInt add(BigInt a, BigInt b) { return a + b; }

And then calls them:

add(7, 42); add(BigInt(7), BigInt(42));

You can also add more stuff to the template:

// A bigger "stencil" template myTemplate(T) { T add(T a, T b) { return a + b; } T mult(T a, T b) { return a * b; } }

So now the compiler will turn this:

myTemplate!(int) myTemplate!(double)

Into this:

int add(int a, int b) { return a + b; } int mult(int a, int b) { return a * b; } double add(double a, double b) { return a + b; } double mult(double a, double b) { return a * b; }

And you can use them like this:

myTemplate!(int).add(7, 42); myTemplate!(double).add(3.14, 5.73); myTemplate!(int).mult(7, 42); myTemplate!(double).mult(3.14, 5.73);

You can put other things inside the template, too, like structs and classes, or even variables:

template anotherTemplate(T, int initialValue) { struct Foo { T value; int someInt = initialValue; } T[] myArray; } // Use the array: anotherTemplate!(string, 5).myArray = ["abc", "def", "g"]; // Declare a variable "myFoo" of type "Foo": // Foo's "value" should be a string // And Foo's "someInt" should start out as 5 anotherTemplate!(string, 5).Foo myFoo; if(myFoo.someInt == 5) myFoo.value = "Hello";

Notice that we've added another parameter to the template this time. But this one's an int, rather than a type! Templates can take any type as a parameter like that. You also use alias (as in template(alias foo) ... ) which will accept any symbol: The name of a type, a variable of any type, a literal, or even another template!

Admittedly, this all gets rather wordy, so D offers some convenient tricks:

Using that myTemplate and anotherTemplate all over is a bit of a bother. Why should we have to? D has a shortcut for making and using templates:

T add(T)(T a, T b) { return a + b; }

That's nothing more than a convenient shortcut for:

template add(T) { T add(T a, T b) { return a + b; } }

Or we can define the struct like:

struct Foo(T, int initialValue) { T value; int someInt = initialValue; }

Which is a convenient shortcut for:

template Foo(T, int initialValue) { struct Foo { T value; int someInt = initialValue; } }

The same trick doesn't work for variables like myArray though (but that will likely get fixed in the future). For now, you'll have to manually write them as:

template myArray(T) { T[] myArray; }

Note that (as was true before) each instance of this template is a different array. So myArray!(int).myArray and myArray!(double).myArray are two different arrays. (If you want a single array that can hold anything, you can just simply make an array of Variants: Variant[] variantArray;)

Here's an even handier trick: Since the name of the template and the "thing" inside the template is the same, you don't have to repeat their names (The technical term for this is an "eponymous template"). To use them, all you have to write is:

add!int(7, 42); add!double(3.14, 5.73); add!BigInt(BigInt(7), BigInt(42)); mult!int(7, 42); mult!double(3.14, 5.73); mult!BigInt(BigInt(7), BigInt(42)); myArray!string = ["abc", "def", "g"]; myArray!int = [1, 2, 3]; myArray!double = [1.5, 2.70, 3.14]; Foo!(string, 5) myFoo; if(myFoo.someInt == 5) myFoo.value = "Hello"; Foo!(float, 1) bar; if(bar.someInt == 1) bar.value = 3.14;

This, in fact, is how templates are usually used in D. Looks pretty simple, doesn't it? Barely any different from the non-template versions. That's because it really is simple, as it should be. After all, they're just stamps.

And there's yet one more frequently used convenience: A special thing D has called IFTI: Implicit Function Template Instantiation. It sounds intimidating, but again, it's really very simple. It just means D lets you call the functions above like this:

add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); mult(7, 42); mult(3.14, 5.73); mult(BigInt(7), BigInt(42));

Look ma! No types!

• D already knows that 7 and 43 are int, so it automatically uses the add!int version.
• D already knows that 3.14 and 5.73 are double, so it automatically uses the add!double version.
• D already knows that BigInt(7) and BigInt(42) are BigInt, so it automatically uses the add!BigInt version.

Now these really are identical to using the old non-template versions!

So ultimately, if we start with this copy-paste mess:

int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; } add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); // ERROR! You have to write a BigInt version *manually*!

We can turn it into a convenient "stencil" with just a trivial little change:

T add(T)(T a, T b) { return a + b; } add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); add( /+ anything else! +/ );

That will automatically stamp out any add() function you need, when you need it. And we can do the same for structs, classes and variables!

For more details on templates and D, check out:

• Philippe Sigaud's "D Templates: A Tutorial"
• Ali Çehreli's "Programming in D"
• The official D website
• The official D book: The D Programming Language

UPDATE (2012-05-12): Added a couple paragraphs about the non-template approaches used in most languages, basic syntax highlighting, and a few minor updates and wording tweaks.

Read more

Sometimes the output from a command line tool can be so large it doesn't all fit on the screen, even with scrolling. Or you may want to preserve the output for later study.

For instance:

> wget --help

That's a lot of output!*

On both Windows and Linux, you can easily save the output of a command to a file like this:

> wget --help > output.txt

But that has two problems:

1. It only saves stdout, not stderr.
2. It no longer shows you the output. And that can be especially annoying if it's a command that takes a long time (like compiling GCC).

How to fix? On Linux, use this script I've named teelog:

#!/bin/sh progpath=$1 progname=$(basename $1) shift $progpath "$@" 2>&1 | tee $progname.log

That redirects stderr into stdout, and then sends stdout to tee. The tee command saves it to a file while also sending it back out to stdout so you can still see it.

Don't forget to set the executable bit with chmod +x teelog. Then put that script somewhere on your PATH and just run:

$ teelog wget --help

You'll see everything just like normal, but everything will also get saved to ./wget.log.

On Windows, things are a bit more difficult. First of all, there's this little snippet that people on the internet keep repeating:

> wget --help 2>&1 > output.txt

That does not work reliably on Windows. It should work, and it does work on Linux. But on Windows, there's what appears to be a race condition: Whenever the command outputs to both stdout and stderr, the order is likely to get screwed up resulting in mixed-up, possibly-garbled, output. Interestingly, in my experience it does seem to work if you pipe to another program instead of redirecting straight to a file. But that leads to the second problem:

The second problem is that Windows (surprise, surprise) doesn't have a built-in tee utility like Linux. Fortunately, people have gone ahead and made such a tool for Windows. There's a port of the GNU tee to Windows which seems to be pretty good. There's also another open-source one here, but it's very slow. The GNU one seems a bit better.

With a third-party Windows tee under out belt, we can now make it a teelog.bat for Windows:

@echo off set TEELOG_PROGNAME=%~nx1 %* 2>&1 | tee.exe %TEELOG_PROGNAME%.log

Make sure both teelog.bat and tee.exe are somewhere on your PATH (The Windows directory works well enough, as long as you have admin rights on your system.) Then just like on Linux:

> teelog wget --help

Whee!

*: Yes, I know the output of "wget --help" does fit with scrolling. And yes, I know Windows doesn't come with wget. But you can get it for Windows.

Read more

EDIT 2011.10.27: I'll cut to the chase: You can do it in D, it'll work, but it will be slow because whenever you pop and then push, it will reallocate and copy. And stacks do that frequently. For more details and a solution, read on:

The D programming language has fantastic array features. The ease of using D's arrays makes it very tempting to use them as stacks:

int[] stack = [1, 2, 3]; stack ~= 7; // Push auto x = stack[$-1]; // Peek stack = stack[0..$-1]; // Pop (Uses slicing, so it *doesn't* copy any data)

Brilliant! Right? It is, as long as you want an array. But if what you really want is a stack (that is, whenever you'll be doing a lot of pushing and popping), then this is unnecessarily slow. Why? Because of excess allocations.

"Poppycock! Arrays have a reserve capacity which prevents excess allocations."

Yes, but slicing can get in the way of that. Consider this example of using an array as a stack:

import std.stdio; void info(ref int[] stack) { writefln("length %s, capacity %s", stack.length, stack.capacity); } void push(ref int[] stack) { stack ~= 7; write("Push: "); stack.info(); } void pop(ref int[] stack) { stack = stack[0..$-1]; write("Pop: "); stack.info(); } void main() { int[] stack = [1, 2, 3]; stack.info(); stack.push(); stack.push(); stack.pop(); stack.push(); stack.pop(); stack.pop(); stack.push(); }

That produces the following output with DMD 2.055 Windows:

length 3, capacity 3 Push: length 4, capacity 7 Push: length 5, capacity 7 Pop: length 4, capacity 0 Push: length 5, capacity 7 Pop: length 4, capacity 0 Pop: length 3, capacity 0 Push: length 4, capacity 7

The first three lines look ok: The stack starts with three elements and no extra reserve space. A fourth element is added, but there isn't enough room, so it bumps the capacity up to 7. So there's four elements, with room for three more. Then, when a fifth element is added (sans Bruce Willis, unfortunately), there's already enough space for it, so we get that fifth element without another allocation. Joy!

Then we pop an element off...and the capacity plummets to zero?! WTF?! The reason for this is aliasing. For all the array knows, we might still have a reference somewhere to the full original array, including that fifth element:

int[] stack = [1, 2, 3, 7, 7]; auto stackOriginal = stack; stack = stack[0..$-1]; // Pop assert(stack == [1, 2, 3, 7]); assert(stackOriginal == [1, 2, 3, 7, 7]);

Suppose we now append another value to the stack:

stack ~= 20; assert(stack == [1, 2, 3, 7, 20]); assert(stackOriginal == [1, 2, 3, 7, 7]);

In this case, the append must allocate new memory and copy the old data into it. Otherwise, it would clobber the last value of stackOriginal with 20. In other words: After being popped, the stack can no longer guarantee it will still be able to accommodate up to 7 elements without allocating, so its capacity is set to zero [1].

The end result is: Slicing an array is fast, and appending is usually fast [2], but slicing the end off and then appending is slow. But since that's how a stack is normally used, arrays make for slow stacks.

How can you have a fast stack? By handling an array's length and capacity manually. The basic principle works like this:

int[] stack = new int[100]; stack[0..3] = [1, 2, 3]; size_t stackLength = 3; // Push stackLength++; stack[stackLength-1] = 7; // Peek auto x = stack[stackLength-1]; // Pop stackLength--;

That's not as nice, but fortunately those details can be hidden in a templated struct that provides the same syntax as arrays. I've already written such a struct, available in my SemiTwist D Tools project. It's perhaps not as fully-featured as it could be, but it should work in most cases as a drop-in replacement for an array. When I dropped it into the parsing engine for my Goldie Parsing System I got an instant 5x-6x boost in parsing speed [3].

So don't use a plain old array when you want a stack. A proper stack will give you far better performance and memory usage.

One caveat about this method: If you save a slice of the stack, pop elements off the stack, and then push new values back on, the old slice you took will likely [4] reflect the new values, not the original ones.

Note that Phobos's development has been accelerating for the past year or so, so I wouldn't be surprised to see a superior stack implementation in std.container sometime in the not-so-distant future.

For more information about D's arrays and slicing, see Steven Schveighoffer's award-winning article, D Slices.

---

[1] Why is the capacity set to zero instead of the actual length of four? I'm not certain, but my guess is that zeroing the value is slightly faster than copying the length. Either that, or perhaps it has to do with the fact that the slice doesn't actually "own" the data. Update 2011.09.26: Steven has explained why it's zero.

[2] If you're doing a lot of appending, you may be better off using D's Appender.

[3] This figure is parsing speed alone, not lexing and parsing combined. Your mileage may vary.

[4] I say "likely" instead of "definitely" because of an unfortunate indeterminism inherent in D's array/slice system. This quirk is explained in the "Determinism" section of Steven Schveighoffer's article mentioned above.

Read more

2010.10.24: Update: Umm, yea, so turns out Haxe does have a much simpler syntax if you just need a default getter/setter. Didn't realize that when I wrote this. But I do still think people should be careful not to let code snippet support become a substitute for proper DRY.

Originally posted: March 25th, 2009

Code snippet support in an editor can be very useful, but it does seem to carry a certain risk of discouraging advancements in DRY practices. For example, I was just working on a Haxe class (I refuse to use the goofy "haXe" capitalization) that has 14 (and that number is growing) accessors like this:

private var _assetBaseUrl:String;
public var assetBaseUrl(get_assetBaseUrl, null):String;
private function get_assetBaseUrl():String
{
    return _assetBaseUrl;
}

Might not seem like much to someone who's accustomed to Haxe, but that's an enormous amount of code just for a single privately-writable, publically-read-only member variable (For the record, Haxe has the ugliest, most verbose accessor definition syntax I've ever seen). Considering I have 14 of these (so far), just in this one class alone, that's a lot of mess.

Of course, this is where the code snippet users come in and say "Just use a code snippet!". I don't know for certain, of course, but I can't help suspect that the existence of code snippets is part of why Haxe's creators allowed the accessor syntax to be so verbose in the first place. And considering that most of those differ only by name and type, well shit, so much for the idea of "Don't Repeat Yourself"!

Contrast that with the same code in C#:

private String _assetBaseUrl;
public String assetBaseUrl()
{
    get { return _assetBaseUrl; }
}

Or better yet, D programming language:

// getter is defined in a utility module I wrote
mixin(getter!(char[], "assetBaseUrl"));

And holy crap, all of a sudden we have actual DRY!

Problem is, code snippets tend to get used as an excuse to ignore DRY (it's really only about one small step above outright copy-and-paste coding). If the early programmers used editors with code snippet support, we probably wouldn't even have functions today.

Of course, I'm not suggesting that we get rid of code snippets, or stop using them. We just shouldn't be considering them a proper substitute for real DRY.

Read more