No account? Create an account

The '99 Bottles of Beers' of Type Systems in D - leonardo
 View: Recent Entries. View: Archive. View: Friends. View: Profile. View: Website (My Website).

 Security: Subject: The '99 Bottles of Beers' of Type Systems in D Time: 12:32 am
A nice blog post, ""The "99 Bottles of Beers" of Type Systems"":

http://gelisam.blogspot.ca/2014/12/the-99-bottles-of-beers-of-type-systems_21.html

The problem is to manage integers, pairs of integers, pairs of pairs of integers, and so on, to represent them in the type system, and to print the n-th iteration of them:

0. Int
1. (Int,Int)
2. ((Int,Int),(Int,Int))
3. (((Int,Int),(Int,Int)),((Int,Int),(Int,Int)))
4. ...

An Haskell solution from that blog:
```printTree :: Show a => a -> Int -> IO ()
printTree v 0 = print v
printTree v n = printTree (v,v) (n-1)

main :: IO ()
main = readLn >>= printTree 42
```

This Haskell solution is short, and it's also efficient at run-time (quite faster than the Java solution shown in that blog).

One D language solution uses the static (monomorphization) version of D generics, similar to C++ templates:
```import std.stdio, std.conv, std.typetuple;

// For higher maxDepth increase stack with -L/STACK:10000000
enum maxDepth = 14;

template Iota(uint stop) {
static if (stop <= 0)
alias Iota = TypeTuple!();
else
alias Iota = TypeTuple!(Iota!(stop - 1), stop - 1);
}

struct Pair(T) {
T x, y;

string toString() {
return text('(', x, ',', y, ')');
}
}

void printTree(uint depth, T)(T v) {
static if (depth == 0)
writeln(v);
else
printTree!(depth - 1)(Pair!T(v, v));
}

void main(in string[] args) {
immutable depth = (args.length == 2) ? args.to!uint : 5;
enum value = 42;

switch (depth) {
foreach (immutable d; Iota!maxDepth)
case d: return printTree!d(value);
default: return writeln("Too much large depth.");
}
}
```

This gives efficient code, and the Pairs are stack-allocated, but the compiler allows only a limited amount of nesting. The foreach inside the switch generates the switch cases statically. This works up to a depth of 13.

To reach higher levels of nesting in D language I use dynamic (runtime) polymorphism:
```import std.stdio, std.conv, std.format;

interface Value {
void toString(scope void delegate(const(char)[]) sink) const;
}

final class Integer : Value {
immutable int x;

this(int x_) pure nothrow @safe @nogc {
this.x = x_;
}

override void toString(scope void delegate(const(char)[]) sink) const {
static fmt = singleSpec("%d");
sink.formatValue(x, fmt);
}
}

final class Pair : Value {
const Value fst, snd;

this(Value fst, Value snd) pure nothrow @safe @nogc {
this.fst = fst;
this.snd = snd;
}

override void toString(scope void delegate(const(char)[]) sink) const {
sink("(");
fst.toString(sink);
sink(",");
snd.toString(sink);
sink(")");
}
}

struct PairWrapper {
Value v;
void toString(scope void delegate(const(char)[]) sink) const {
v.toString(sink);
}
}

void printTree(Value v, in uint n) {
if (n == 0)
writeln(PairWrapper(v));
else
printTree(new Pair(v, v), n - 1);
}

void main(in string[] args) {
import core.memory, core.stdc.stdlib;
GC.disable;
immutable depth = (args.length == 2) ? args.to!uint : 5;
printTree(new Integer(42), depth);
exit(0);
}
```

The toString() inside the interface and PairWrapper are used because D classes don't yet support the sink. The sink is important to increase performance, avoiding allocating lot of strings. This version is more efficient also because it leads to more coherence for the L1 code cache. This D solution is just a little slower than the Haskell solution (perhaps because the Haskell solution caches the formatting of the integer 42, I don't know. If I perform such caching the D code becomes faster than the Haskell code), and it's much faster than the Java version (despite currently the D garbage collector is less efficient than the OracleVM ones).
comments: Leave a comment   The '99 Bottles of Beers' of Type Systems in D - leonardo
 View: Recent Entries. View: Archive. View: Friends. View: Profile. View: Website (My Website). 