= Code Generation =

Although it's possible to generate parametrised code using [DSpec2x:template]s and [DSpec2x:template-mixin]s, it's not easy to do anything particularly advanced with them.

The alternative is to use [DSpec2x:mixin]s with a const string. While this string can be generated using templates, it's easier to use compile-time functions (note: this probably does mean that the functions used will get compiled in to the binary even if they're not used after compilation, thus bloating executables).

= Binary Search =

One useful application of this is to create a coded binary-search algorithm, which works in a similar way to a switch statement but is much faster (see [MetaSwitchBench] for a speed comparison).

=== Example 1 ===

An example using compile-time functions to generate a binary-search algorithm. Note that although the output can be adjusted by changing ''codeFunc'', it probably makes more sense to modify ''binarySearch'' directly (I could not find a way to properly decouple the two functions to truly generalise ''binarySearch'').

{{{
#!d
/** Module for binarySearch meta-code.
*
* This is used to generate some code:
*   Currently codeFunc and KEYS are to produce an escape-sequence replacing block of code (it needs
*   a little modification after generation though).
*
* Just complie; it will output the code.
*/
module meta_binarySearch;

char[] codeFunc (char[] str) {
    return "return '\\"~ (str[1] == '\\' ? str[2] : str[1]) ~"';";
}
/+char[] codeFunc (char[] str) {
    return "return '"~str[2]~"';";
}+/

// Purely to add indentation. Could just return "" without affecting functionality.
char[] indent (uint i) {
    char[] ret;
    for (; i > 0; --i) ret ~= "    ";
    // This is not executable at compile time:
    //ret.length = i * 4;		// number of characters for each indentation
    //ret[] = ' ';		// character to indent with
    return ret;
}

/* Generates a binary search algorithm.
*
* Intended to be somewhat generic. */
char[] binarySearch (char[] var, char[][] consts, int indents = 0) {
    if (consts.length > 3) {
        return indent(indents) ~ "if (" ~ var ~ " <= " ~ consts[$/2 - 1] ~ ") {\n" ~
            binarySearch (var, consts[0 .. $/2], indents + 1) ~
        indent(indents) ~ "} else {\n" ~
            binarySearch (var, consts[$/2 .. $], indents + 1) ~
        indent(indents) ~ "}\n";
    } else {
        char[] ret;
        ret ~= indent(indents);
        foreach (c; consts) {
            ret ~= "if (" ~ var ~ " == " ~ c ~ ") {\n" ~
                indent(indents+1) ~ codeFunc(c) ~ "\n" ~
            indent(indents) ~ "} else ";
        }
        ret = ret[0..$-6] ~ '\n';  // remove last else
        return ret;
    }
}

const char[][] KEYS = ["'\\\"'", "'\\\''", "'\\\\'", "'a'", "'b'", "'f'", "'n'", "'r'", "'t'", "'v'"];
//const char[][] KEYS = ["'\\a'", "'\\b'", "'\\t'", "'\\n'", "'\\v'", "'\\f'", "'\\r'", "'\\\"'", "'\\''", "'\\\\'"];

const code = binarySearch ("c", KEYS, 1);

pragma (msg, code);
static assert (false, "Code generation completed.");
}}}

=== Example 2 ===

Another example, this time using templates to generate the code. You can see from all the special cases and much greater code length that this example is much less simple than the compile-time functions version. It does however have two advantages: it can be properly generalised via templates (''printIt'' and ''printErr''), and no extra functions get compiled into the binary.

{{{
#!d
/**  This roughly generates a binary search algorithm. */
module tp_binarySearch;

/* Note: this uses tango, but if you don't want to use tango just replace "Stdout" with an
* alternate output method, or halt execution before main() with "static assert(false);" (you will
* still see the algorithm generated).
*/
import tango.io.Stdout;

//BEGIN Binary-Search template
/* Try to create binary-search code.
*
* Mixin the code: mixin(bSearch!(...));
* The list of arguments should be sorted.
*
* Generates code to find x among list T1,A... and calls (mixes in) Match!(T) when done.
* Fail is mixed in if no match is found (should be a const string).
*
* This is designed to match a string against a list of types, then call a templated function of the
* given type, although it could be adapted to other purposes.
*
* For correct indentation, both Match!(T) and Fail should be one-line statements ending with a
* newline.
*/
template bSearch(alias Match, alias Fail, alias x, A...) {
    const bSearch = bSearchAlg!(0,Match,Fail,x,A);
}

// Utility templates:

// For correct indentation. Adjust the indent string if you wish!
private template indent(int n) {
    static if (n > 0) const char[] indent = "  " ~ indent!(n-1);
    else const char[] indent = "";
}

// For checking equality.
// Trailing else, to ensure if/else if blocks end with an else Fail!().
private template checkEq(int d, alias Match, alias x, T) {
    const checkEq = 
    indent!(d) ~ `if (`~x.stringof~` == "`~T.stringof~`") {
` ~ indent!(d+1) ~ Match!(T) ~
    indent!(d) ~ `} else `;
}

// For checking if less than or equal to a certain string.
private template checkLtEq(int d, alias x, T) {
    const checkLtEq = 
    indent!(d) ~ `if (`~x.stringof~` <= "`~T.stringof~`") {
`;
}
private template checkLtEqElse(int d) {
    const checkLtEqElse =
    indent!(d) ~ `} else {
`;
}
private template checkLtEqEnd(int d) {
    const checkLtEqEnd =
    indent!(d) ~ `}
`;
}

/* To split correctly.
* (This isn't quite a binary split since we cannot assume, once we have narrowed it down to one
* possibility, that this is correct.)
* This algorithm is intended to keep the maximum number of checks as low as possible.

Number of arguments to check against (second column):
0	1-3	if (T1) ... else if (T2) ... else if (T3) ...
1	4-5	if (<= T2) { handle T1-T2 }
1		else { handle T3-Tn }
2	6-11	T1-T4; T5-Tn
3	12-23	T1-T8; T9-Tn
4	24-47	T1-T16; T17-Tn
N	3*2^(N-1) - 3*2^N-1	T1-T(2^N); T...

* This only implements up to N=4. For more arguments, it will still work but be less optimal.
*/
private template bSearchAlg(int d, alias Match, alias Fail, alias x, A...) {
    static if (A.length <= 3) const bSearchAlg = bSearchAlg0!(d, Match, Fail, x, A);
    else static if (A.length <= 5) const bSearchAlg = bSearchAlg1!(d, Match, Fail, x, A);
    else static if (A.length <= 11) const bSearchAlg = bSearchAlg2!(d, Match, Fail, x, A);
    else static if (A.length <= 23) const bSearchAlg = bSearchAlg3!(d, Match, Fail, x, A);
    else const bSearchAlg = bSearchAlg4!(d, Match, Fail, x, A);
}

private template bSearchAlg0(int d, alias Match, alias Fail, alias x, T1) {
    const bSearchAlg0 = checkEq!(d,Match,x,T1) ~ Fail!();
}
private template bSearchAlg0(int d, alias Match, alias Fail, alias x, T1, T2) {
    const bSearchAlg0 = checkEq!(d,Match,x,T1) ~ checkEq!(d,Match,x,T2) ~ Fail!();
}
private template bSearchAlg0(int d, alias Match, alias Fail, alias x, T1, T2, T3) {
    const bSearchAlg0 = checkEq!(d,Match,x,T1) ~ checkEq!(d,Match,x,T2) ~ checkEq!(d,Match,x,T3) ~ Fail!();
}

private template bSearchAlg1(int d, alias Match, alias Fail, alias x, T1, T2, A...) {
    const bSearchAlg1 =
    checkLtEq!(d,x,T2) ~
        bSearchAlg!(d+1,Match,Fail,x,T1,T2) ~
    checkLtEqElse!(d) ~
        bSearchAlg!(d+1,Match,Fail,x,A) ~
    checkLtEqEnd!(d);
}

private template bSearchAlg2(int d, alias Match, alias Fail, alias x, T1, T2, T3, T4, A...) {
    const bSearchAlg2 =
    checkLtEq!(d,x,T4) ~
        bSearchAlg!(d+1,Match,Fail,x,T1,T2,T3,T4) ~
    checkLtEqElse!(d) ~
        bSearchAlg!(d+1,Match,Fail,x,A) ~
    checkLtEqEnd!(d);
}

private template bSearchAlg3(int d, alias Match, alias Fail, alias x, T1,T2,T3,T4,T5,T6,T7,T8,A...) {
    const bSearchAlg3 =
    checkLtEq!(d,x,T8) ~
        bSearchAlg!(d+1,Match,Fail,x,T1,T2,T3,T4,T5,T6,T7,T8) ~
    checkLtEqElse!(d) ~
        bSearchAlg!(d+1,Match,Fail,x,A) ~
    checkLtEqEnd!(d);
}

private template bSearchAlg4(int d, alias Match, alias Fail, alias x, T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11,T12,T13,T14,T15,T16,A...) {
    const bSearchAlg4 =
    checkLtEq!(d,x,T16) ~
        bSearchAlg!(d+1,Match,Fail,x,T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11,T12,T13,T14,T15,T16) ~
    checkLtEqElse!(d) ~
        bSearchAlg!(d+1,Match,Fail,x,A) ~
    checkLtEqEnd!(d);
}
//END Binary-Search template


template printIt(T) {
    const printIt = `Stdout ("Type is `~T.stringof~`").newline;
`;
}
template printErr() {
    const printErr = `Stdout ("Error: no match").newline;
`;
}
char[] z = "double[][]";

const code = bSearch!(printIt,printErr,z, bool, double, double[], double[][], float, int, int[]);
pragma (msg, "{{{");
pragma (msg, code);
pragma (msg, "}}}\n");

void main() {
    mixin (code);
}
}}}

= Source =
|| Posted by || Cyborg16 ||
|| Date ||  March 15, 2008 ||