I read Sean Leffler's article on Rust's type system being turing complete and that's when I lost my weekends for the next few months.
dg $ /usr/bin/time rustc play.rs 2>&1 | sed -e 's/((/X((/g' -e's/, (N//g' |tr 'X' '\012'
error[E0599]: no function or associated item named `foo` found for type `
((N1111111111222222bbbbb11111111111, FalseT)))))))))))))))))))))))))))))))),
((N1111111122222222bbbbbbb111111111, FalseT)))))))))))))))))))))))))))))))),
((N111111b222222222bbbbbbbbb1111111, FalseT)))))))))))))))))))))))))))))))),
((N11111bb2222222222bbbbbbbbb111111, FalseT)))))))))))))))))))))))))))))))),
((N1111bbb2222222222bbbbbbbbbb11111, FalseT)))))))))))))))))))))))))))))))),
((N111bbb2222222cc222bbbbbbbbbb1111, FalseT)))))))))))))))))))))))))))))))),
((N11bbbb22222c333cc2bbbbbbbbbbb111, FalseT)))))))))))))))))))))))))))))))),
((N11bbb22222cddd333c2bbbbbbbbbb111, FalseT)))))))))))))))))))))))))))))))),
((N1bbbb2222cd4eee43322bbbbbbbbbb11, FalseT)))))))))))))))))))))))))))))))),
((N1bbb2222334fg66_74322bbbbbbbbb11, FalseT)))))))))))))))))))))))))))))))),
((Nbbb222233d58_____edc222bbbbbbbb1, FalseT)))))))))))))))))))))))))))))))),
((Nbb222233346_______6c22222bbbbbb1, FalseT)))))))))))))))))))))))))))))))),
((Nb22223334f________6dc222222bbbb1, FalseT)))))))))))))))))))))))))))))))),
((N222c333e6__________4cc2222222bb1, FalseT)))))))))))))))))))))))))))))))),
((N2cc3d4f9___________d3cc222222221, FalseT)))))))))))))))))))))))))))))))),
((N__________________75433222222221, FalseT)))))))))))))))))))))))))))))))),
((N2cc3d4f9___________d3cc222222221, FalseT)))))))))))))))))))))))))))))))),
((N222c333e6__________4cc2222222bb1, FalseT)))))))))))))))))))))))))))))))),
((Nb22223334f________6dc222222bbbb1, FalseT)))))))))))))))))))))))))))))))),
((Nbb222233346_______6c22222bbbbbb1, FalseT)))))))))))))))))))))))))))))))),
((Nbbb222233d58_____edc222bbbbbbbb1, FalseT)))))))))))))))))))))))))))))))),
((N1bbb2222334fg66_74322bbbbbbbbb11, FalseT)))))))))))))))))))))))))))))))),
((N1bbbb2222cd4eee43322bbbbbbbbbb11, FalseT)))))))))))))))))))))))))))))))),
((N11bbb22222cddd333c2bbbbbbbbbb111, FalseT)))))))))))))))))))))))))))))))),
((N11bbbb22222c333cc2bbbbbbbbbbb111, FalseT)))))))))))))))))))))))))))))))),
((N111bbb2222222cc222bbbbbbbbbb1111, FalseT)))))))))))))))))))))))))))))))),
((N1111bbb2222222222bbbbbbbbbb11111, FalseT)))))))))))))))))))))))))))))))),
((N11111bb2222222222bbbbbbbbb111111, FalseT)))))))))))))))))))))))))))))))),
((N111111b222222222bbbbbbbbb1111111, FalseT)))))))))))))))))))))))))))))))),
((N1111111122222222bbbbbbb111111111, FalseT)))))))))))))))))))))))))))))))),
((N1111111111222222bbbbb11111111111, FalseT)))))))))))))))))))))))))))))))),
((N11111111111111111111111111111111, FalseT)))))))))))))))))))))))))))))))), FalseT))))))))))))))))))))))))))))))))` in the current scope
--> play.rs:776:5
|
776 | <(range, FalseT, FalseT) as ListWalkScan2D>::Res :: foo;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
error: aborting due to previous error(s)
Command exited with non-zero status 101
2571.20user 5.96system 42:57.19elapsed 99%CPU (0avgtext+0avgdata 11843648maxresident)k
0inputs+0outputs (0major+705802minor)pagefaults 0swaps
The basic trick is that rust has associated types where a trait has a type that can be different in different implementations of that trait. Implementations are parameterised to take different types and you can place requirements on them. So that means you've got a thing with an output type and an input that can be compared - so that's enough to do whatever we want. e.g. here we have a CondNeg that takes a boolean and a value, and if the boolean is true it negates it:
trait CondNeg { type Res : Digit8; }
impl CondNeg for (FalseT,A) {
type Res = A;
}
impl CondNeg for (TrueT,A) {
type Res = ::Res;
}
When I started writing this I hadn't heard of typenum that implements compile time arithmetic, so I ended up implementing my own. And once I found out, I was already quite deep so just kept digging.
My arithmetic is basically recursive, starting with a 2-bit half-digit, building a 4 bit digit out of that, then a 8 bit Digit2, then a Digit4 all the way upto a Digit16. At the 2-bit level I define a 4x4 table giving the result of addition and multiplication and everything works up from there. For each level there's a trait (DigitH,Digit,Digit2,Digit4,Digit8,Digit16), implementations that let you build them from smaller parts (e.g. EightDigit lets you build a Digit8 from 8 digits or EightDigitL lets you build it from a pair of Digit4.
Similarly arithmetic works it's way up, AddH is defined in a table (2 bit), AddD, Add2, Add4, Add8, Add16 build that all the way upto 64bit arithmetic. A few macros help along the way (I could do with more). Multiply works the same way going up through MulH, MulD, Mul8 (which gives a 64bit result). Those multiplies are unsigned.
On top of that is hacked a signed fixed point multiply, SMul is built by removing the sign, mutliplying two Digit8's then extracting a 32 bit chunk out of the result so we end up with 8 bits of integer, 24bits of fraction and then conditionally adds the sign back. There's also some conditionals for Abs, and a comparison we need. We've also got 'constants' for each of the digits 0..f so we can easily build constants (we also use those in the output).
I need to loop through a range both for X and Y. I've got a macro ListWalkGen which generates an iterator that walks a list, applying an operation to each element, keeping track of some state as it goes. It takes an initial input list like:
type empty=(X,(X,(X,(X,(X,(X,(X,(X,(X,(X,FalseT))))))))));
(Yes, I should use a procedural macro to autogenerate that). It has a pair of impl's, one that walks it and one when it hits the end:
impl $name for ((L,FalseT), Init, Step)
...
impl $name for ((L, (A, B)), Init, Step)
List walk produces an output list as it's Res associated type, but each result on that list comes from invoking another trait. This gets layered, so we start with ListWalkInc, which we call like:
type range = <(empty, minus2, eigth) as ListWalkInc>::Res;
That produces a list that counts from -2 up in 1/8 steps, and I'm running this with a larger version of emptywith 32 entries. We pass that list to two separate places; initially we use it at the top level as a parameter to ListWalkScan2D:
ListWalkGen!(ListWalkScan2D, Scan2D);
...
<(range, FalseT, FalseT) as ListWalkScan2D>::Res :: foo;
The :: foo there is an evil trick - see later the bit on output. But what we're doing here is evaluating the Scan2Dtrait for every element of range which is our first list. That forms the 'Y' step. Scan2D then invokes ListWalkMand using the current Y step and range again, so that the MandPoint gets called for each X,Y point.
Being compile time, we're a bit stuck for output options; we could form something and end up with it in a binary that we could dump the binary. There's a dev features rustc_on_unimplemented that's for adding nice output data at compile time, but it's not there yet.
So our output is an error message, we need it to include the type name,
so we just add a dummy :: foo like: then rustc helpfully dumps the whole of the type to tell us it hasn't got
a foo member:
well, that's not very pretty is it? So I clean up the output with a little bit of our friends sed and tr: The main trick is we insert an 'X' at double brackets that correspond
to the start of a row, then we remove the ', (N', and finally replace that
X by a line feed.
OK, so all the above was just crazyness of doing all this in Rust, so we're now left with the actual mandelbrot,
which is a set of impl's of MandPoint. Again we iterate along a list, but this list
is a set of types to use as the final output during the iteration: In a mandelbrot, for each point we've got a choice of three things to do, either we
iterate again, we stop because the result passes the threshold or we stop because
we run out of iterations. We use a set of 3 impls, one which recurses passing a flag
to indicate whether the result is greater than the threshold, one which stops with the
flag is true, and one when we hit the end of the iteration list. Running with a 32x32 res, and ~20 iterations it peaks at about 20G virtual, 11G resident RAM on rustc 1.19.0. So you do want plenty of RAM. BUT I hit a lot of problems; firstly if you screw up a big iterative set like this, rustc just eats ram for breakfast, I filed
when I caught rustc using 75G of RAM for that. Really simple
screwups in when clauses for example and rustc just takes off. The other problem was during normal running, I lost a few
months to this, but in the end I got down to: Interestingly the RAM usage and time doesn't go up vastly with resolution or iteration depth, most of it is a fixed overhead. is VASTLY more efficient than.
I was pretty desperate before I found that, I was running out of RAM on my 32G machine (which I bought after running out of 8G...)
even before adding the mandelbrot iteration.
The code is here - note it's a bit of a mess and needs a clean up; heck when I got the
output above I was just happy :-) I really should do something *useful* in rust instead of screwing around like this! Potentially we might get to
the point where this lot could be done efficiently using associated constants, but as of 0.21 I couldn't find a way
to where based on the value even indirectly. Feel free to use the code and quote this page as long as you acknowledge me; but note the code is VERY untested. (c)David Alan Gilbert 2017 mail: fromwebpage@treblig.org irc: penguin42 on freenode | matrix: penguin42 on matrix.org | mastodon: penguin42 on mastodon.org.uk
<(range, FalseT, FalseT) as ListWalkScan2D>::Res :: foo;
error[E0599]: no function or associated item named `foo` found for type `((N2, (N2, (N2, (N2, (N3, (N3, (N4, (N9, FalseT)))))))), ((N2, (N2, (N3, (N3, (N3, (N4, (N9, (N9, FalseT)))))))), ((N2, (N3, (N3, (N4, (N4, (N4, (N9, (N9, FalseT)))))))), ((N2, (N4, (N4, (N4, (N4, (N9, (N9, (N9, FalseT)))))))), ((N4, (N4, (N4, (N4, (N9, (N9, (N9, (N9, FalseT)))))))), ((N4, (N4, (N4, (N9, (N9, (N9, (N9, (N9, FalseT)))))))), ((N4, (N4, (N9, (N9, (N9, (N9, (N9, (N9, FalseT)))))))), ((N4, (N4, (N4, (N9, (N9, (N9, (N9, (N9, FalseT)))))))), FalseT))))))))` in the current scope
rustc play.rs 2>&1 | sed -e 's/((/X((/g' -e's/, (N//g' |tr 'X' '\012'
The mandelbrot iteration itself
type Iter = (N0,(N1,(N2,(N3,(N4,(N9, FalseT))))));
/* Normal iterative case */
impl
RAM, oh god RAM
trait foo {
type bob : brian;
}
impl ...
trait foo {
type bob;
}
impl ...
where ....::bob : brian
{
...
}
The code
The future