Postanowiłem ostatnio w ramach ćwiczenia "przetłumaczyć" symulator czarnej dziury na Rusta. Na początek zdecydowałem się stworzyć bibliotekę obsługującą geometrię różniczkową (rachunek tensorowy, metrykę itp.). Natknąłem się przy tym dość szybko na pewien problem.
Rust i tablice
Tensory są obiektami mającymi pewną ustaloną liczbę współrzędnych, zależną od wymiaru przestrzeni, na której funkcjonują. Np. w przestrzeni n-wymiarowej wektory mają 
współrzędnych, tensory rzędu 2 (np. metryka) mają ich 
itp. Do reprezentacji takich obiektów idealne są tablice.
Rust radzi sobie z tablicami bez problemu. N-elementową tablicę z elementami typu T zapisuje się w Ruście jako [T; N]. I wszystko byłoby fajnie, gdyby nie drobny szczegół - chciałbym, żeby mój kod był niezależny od wymiaru przestrzeni.
Problem
Rust posiada możliwość tworzenia tzw. typów generycznych. Są to typy danych, w których możemy określić, jakiego typu mają być ich wewnętrzne szczegóły. Np., moglibyśmy łatwo stworzyć generyczny wektor 3-wymiarowy:
|
1 2 3 |
struct Vector3<T> { coords: [T; 3] } |
Co jednak, gdybyśmy chcieli stworzyć wektor n-wymiarowy?
|
1 2 3 |
struct Vector<T,N> { coords: [T; N] // nie zadziała } |
Nic z tego. Nie ma w Ruście sposobu na wyrażenie tego, żeby parametrem typu była długość tablicy.
Sprawa wydawała się beznadziejna, ale przypadkiem natknąłem się na kod, który zasugerował, że rozwiązanie może istnieć.
dimensioned i typy Peano
W bibliotece dimensioned autor zaimplementował arytmetykę liczb naturalnych... na typach danych. Podstawa wygląda tak:
Po pierwsze, definiujemy zero:
|
1 |
struct Zero; |
Po drugie, określamy, że zero jest liczbą naturalną:
|
1 2 |
trait Natural {} impl Natural for Zero {} |
Po trzecie, definiujemy następnik liczby naturalnej:
|
1 2 3 |
struct Succ<N: Natural> { _marker: PhantomData<N> // tylko dla zapobiegania ostrzeżeniom kompilatora } |
Po czwarte: następnik liczby naturalnej też jest liczbą naturalną
|
1 |
impl<N: Natural> Natural for Succ<N> {} |
I to w zasadzie tyle. Jeśli chcemy, możemy jeszcze ponazywać typy:
|
1 2 3 |
type One = Succ<Zero>; type Two = Succ<One>; // itd... |
Może się jeszcze przydać zdefiniowanie funkcji, która zwraca faktyczną liczbę:
|
1 2 3 4 5 6 7 8 9 10 11 |
trait ToInt : Natural { fn to_int() -> i32; } impl ToInt for Zero { fn to_int() -> i32 { 0 } } impl<N: ToInt> ToInt for Succ<N> { fn to_int() -> i32 { 1 + N::to_int() } } |
Tym sposobem zdefiniowaliśmy typy danych odpowiadające liczbom naturalnym. Są to już prawdziwe typy - więc można ich używać jako parametrów w typach generycznych. Niestety, [T; Two] nadal nie zadziała.
Możemy zrobić jednak coś takiego: dla typu oznaczającego zero zdefiniować pustą strukturę, a dla każdego następnika strukturę z dwoma polami - strukturą poprzednika i jedną wartością typu T. W ten sposób struktura zdefiniowana dla typu odpowiadającego np. liczbie 5 będzie miała w sobie miejsce na 5 elementów typu T - a więc można będzie ją traktować jak 5-elementową tablicę! Do roboty.
Po pierwsze, musimy jakoś określić strukturę stowarzyszoną z danym typem:
|
1 2 3 |
trait ArrayType<T> : ToInt { type Array; } |
To teraz struktury dla zera i następników:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
struct EmptyArray<T> { _marker: PhantomData<T> // przeciw ostrzeżeniom } // EmptyArray jest tablicą dla zera impl<T> ArrayType<T> for Zero { type Array = EmptyArray<T>; } struct SuccArray<T, N: ArrayType<T>> { previous_data: N::Array, // tablica poprzednika data: T // ... i dodatkowy element } // przypisanie tablicy do następników impl<T, N: ArrayType<T>> ArrayType<T> for Succ<N> { type Array = SuccArray<T, N>; } |
Mamy zdefiniowane tablice stowarzyszone z typami liczbowymi, co już w zasadzie by wystarczyło. Fajnie jednak będzie mieć składnię podobną do [T; N]:
|
1 2 3 |
struct GenericArray<T, N: ArrayType<T>> { data: N::Array } |
I w tym momencie GenericArray już zadziała. Moglibyśmy zdefiniować również Vector. Mamy prawdziwe generyczne tablice :)
Kolejny problem
Okazuje się, że taki system ma jedno poważne ograniczenie. Typy liczbowe są zdefiniowane rekurencyjnie i bardzo szybko osiągają limit systemu typów kompilatora - a mianowicie, w okolicach liczby 64. Można co prawda ten limit zwiększyć, ale nadal nawet nie do wielkości rzędu 1000, poza tym jest to duże obciążenie dla kompilatora. Należałoby to jakoś zmienić.
W wątku na reddicie użytkownik llogiq zasugerował zastosowanie systemu binarnego, podobnego do tego z biblioteki shoggoth.rs. Po przyjrzeniu się temu sposobowi, postanowiłem go spróbować.
Początek jest podobny, z tym że definiujemy nie jeden, a dwa typy:
|
1 2 3 4 5 6 |
struct _0; struct _1; trait Natural {} impl Natural for _0 {} impl Natural for _1 {} |
Następnie, zamiast następników, definiujemy liczby binarne:
|
1 2 |
impl<N: Natural> Natural for (N, _0) {} impl<N: Natural> Natural for (N, _1) {} |
W tym momencie jako liczby naturalne mamy _0, _1, (_1, _0), (_1, _1), ((_1, _0), _0), ... - czyli zaimplementowaliśmy system binarny! Oczywiście, przyda się znowu konwersja na liczbę całkowitą:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
trait ToInt : Natural { fn to_int() -> i32; } impl ToInt for _0 { fn to_int() -> i32 { 0 } } impl ToInt for _1 { fn to_int() -> i32 { 1 } } impl<N: ToInt> ToInt for (N, _0) { fn to_int() -> i32 { 2 * N::to_int() } } impl<N: ToInt> ToInt for (N, _1) { fn to_int() -> i32 { 2 * N::to_int() + 1 } } |
Dalszy ciąg jest podobny. Zeru przypisujemy pustą strukturę, jedynce - strukturę z jednym polem. Następnie każdej parze (N, _0) strukturę z dwoma polami typu N::Array, a parze (N, _1) - z dwoma polami N::Array i jednym dodatkowym elementem. I tak oto mamy generyczne tablice opisywane binarnie.
Faktyczna implementacja w repozytorium nieco różni się od tej przedstawionej tutaj (głównie nazwami struktur) - zapraszam do przeglądania! :)