Das Rechnen mit Restklassen ist in der Algebra zentral und kommt auch in manchen Bereichen der Informatik vor. Möchte man nun die Arithmetik mit Restklassen auf ordentliche Art implementieren, muss man einen Datentyp für den Restklassenring Z/mZ formulieren. Dieser ist nun allerdings vom Modul m abhängig. Das bereitet uns zwei Probleme:
Hat man 1., ließe sich 2. durch eine Zusicherung zur Laufzeit prüfen. Eigentlich möchten wir dies alles aber schon zur Kompilierzeit haben. Die nähere Betrachtung dieser Komplikation bringt uns zu einer mysteriösen Einsicht: Der Typ muss vom Modul, einem Wert, abhängig sein. Einen solchen Typ nennt man abhängigen Typ, ein Typsystem das mit diesen umgehen kann abhängiges Typsystem.
Rust enthält eine recht eingeschränkte Form von abhängigen
Typen, die sich Const Generics nennen. Eine wesentliche
Notwendigkeit für die Einführung dieser ist der Umgang mit Arrays vom
Typ [T;N], wo N eine schon zur Kompilierzeit
bekannte Konstante ist. Man kam dabei zu der Einsicht, dass sich einige
Algorithmen ohne Const Generics nicht vernünftig formulieren
ließen. Das ist deshalb problematisch, weil solche Arrays Bestandteil
vieler laufzeitkritischer Programme sind.
Soll ein Typ abhängig von einem Wert sein bzw. polymorph über Werte,
wird der Typvariable bei der Definition und Implementation das
Schlüsselwort const vorangestellt. Den Restklassenring
zum Modul M schreiben wir Z<M>.
Die Umsetzung gestaltet sich nun wie folgt.
use std::fmt;
#[derive(Clone, Copy)]
struct Z<const M: u32> (u32);
impl<const M: u32> fmt::Display for Z<M> {
fn fmt(&self, f: &mut fmt::Formatter) ->fmt::Result {
write!(f, "{}", self.0 % M)
}
}
impl<const M: u32> std::ops::Add for Z<M> {
type Output = Self;
fn add(self, y: Self) -> Self {
Z((self.0 + y.0) % M)
}
}
impl<const M: u32> std::ops::Sub for Z<M> {
type Output = Self;
fn sub(self, y: Self) -> Self {
Z((self.0 - y.0) % M)
}
}
impl<const M: u32> std::ops::Add<u32> for Z<M> {
type Output = Self;
fn add(self, y: u32) -> Self {
Z((self.0 + y) % M)
}
}
impl<const M: u32> std::ops::Sub<u32> for Z<M> {
type Output = Self;
fn sub(self, y: u32) -> Self {
Z((self.0 - y) % M)
}
}
impl<const M: u32> std::ops::Mul for Z<M> {
type Output = Self;
fn mul(self, y: Self) -> Self {
Z((self.0*y.0) % M)
}
}
impl<const M: u32> std::ops::Mul<Z<M>> for u32 {
type Output = Z<M>;
fn mul(self, y: Z<M>) -> Z<M> {
Z((self*y.0) % M)
}
}
fn main() {
let x: Z<5> = Z(4);
let y: Z<5> = Z(3);
println!("{}", x*x + 2*y + 1);
}
Die Implementierung der Vektorrechnung aus dem Abschnitt
›Effiziente Programmierung: Nochmals Verkettung‹
ist in der Hinsicht makelhaft, dass intern der Typ
Vec<f64> zur Anwendung kommt, womit zumindest für
die Initialisierung der Puffervariablen eine Heap-Allokation
stattfinden muss. Somit kommt es außerdem zu einer Zeigerindirektion
und einer Cache-unfreundlichen Fragmentierung der
Speicherbereichs-Nutzung.
Man kann das Programm von diesem Makel befreien, indem
Vec<f64> gegen [f64; N] ausgetauscht
wird. Nämlich beobachten wir, dass die Array-Länge bei der
Vektorrechnung bereits zur Kompilierzeit feststeht. Die
Anpassung des Programms fällt erfreulicherweise fast trivial aus,
– man muss an den entsprechenden Stellen lediglich
N einfügen.
pub mod vector {
use std::ops::{Add, Sub, Mul};
pub struct Vector<const N: usize>(pub [f64; N]);
pub struct Addition<A: Get, B: Get>(A, B);
pub struct ScalarMul<A: Get>(f64, A);
impl<const N: usize> Vector<N> {
pub fn flush<A: Get>(&mut self, a: A) {
for i in 0..N {
self.0[i] = a.get(i);
}
}
}
impl<const N: usize> std::fmt::Display for Vector<N> {
fn fmt(&self, f: &mut std::fmt::Formatter)
-> std::fmt::Result
{
write!(f, "{:?}", self.0)
}
}
pub trait Get {
fn len(&self) -> usize;
fn get(&self, i: usize) -> f64;
}
impl<const N: usize> Get for &Vector<N> {
fn len(&self) -> usize {self.0.len()}
fn get(&self, i: usize) -> f64 {self.0[i]}
}
impl<A: Get, B: Get> Get for Addition<A, B> {
fn len(&self) -> usize {self.0.len()}
fn get(&self, i: usize) -> f64 {
self.0.get(i) + self.1.get(i)
}
}
impl<A: Get> Get for ScalarMul<A> {
fn len(&self) -> usize {self.1.len()}
fn get(&self, i: usize) -> f64 {
self.0*self.1.get(i)
}
}
impl<'a, B: Get, const N: usize> Add<B> for &'a Vector<N> {
type Output = Addition<&'a Vector<N>, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<'a, B: Get, const N: usize> Sub<B> for &'a Vector<N> {
type Output = Addition<&'a Vector<N>, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<A0: Get, A1: Get, B: Get> Add<B> for Addition<A0, A1> {
type Output = Addition<Self, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<A0: Get, A1: Get, B: Get> Sub<B> for Addition<A0, A1> {
type Output = Addition<Self, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<A: Get, B: Get> Add<B> for ScalarMul<A> {
type Output = Addition<Self, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<A: Get, B: Get> Sub<B> for ScalarMul<A> {
type Output = Addition<Self, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<'a, const N: usize> Mul<&'a Vector<N>> for f64 {
type Output = ScalarMul<&'a Vector<N>>;
fn mul(self, a: &'a Vector<N>) -> Self::Output {
ScalarMul(self, a)
}
}
impl<A: Get, B: Get> Mul<Addition<A, B>> for f64 {
type Output = ScalarMul<Addition<A, B>>;
fn mul(self, a: Addition<A, B>) -> Self::Output {
ScalarMul(self, a)
}
}
impl<B: Get, const N: usize> Mul<B> for &Vector<N> {
type Output = f64;
fn mul(self, b: B) -> f64 {
let a = &self.0;
let mut acc = 0.0;
for i in 0..a.len() {
acc += a[i]*b.get(i);
}
acc
}
}
impl<A0: Get, A1: Get, B: Get> Mul<B> for Addition<A0, A1> {
type Output = f64;
fn mul(self, b: B) -> f64 {
let mut acc = 0.0;
for i in 0..self.len() {
acc += self.get(i)*b.get(i);
}
acc
}
}
pub fn norm<A: Get>(v: A) -> f64 {
let mut s = 0.0;
for i in 0..v.len() {
let a = v.get(i);
s += a*a;
}
s.sqrt()
}
}
use vector::Vector;
fn main() {
let v = &Vector([1.0, 2.0]);
let w = &Vector([3.0, 4.0]);
let mut buf = Vector([0.0, 0.0]);
buf.flush(2.0*v + 4.0*w + 5.0*(v - 2.0*w));
println!("{}", buf);
println!("{}", (v + w)*(v - w));
println!("{}", v*v - w*w);
}
Betrachten wir nochmals die Schaffung von Einheiten aus dem Abschnitt ›Sichere Programmierung: Einheiten‹. Ein über Konstanten generischer Typ eröffnet uns die Möglichkeit einer etwas eleganteren Umsetzung.
Jede Größenart besitzt im MKS-System (Meter-Kilogramm-Sekunde)
ein Tripel (L,M,T) zur Kodierung der Dimension
LängeL × MasseM × ZeitT.
Es liegt in der Natur der Sache, dieses Tripel
nun als über Konstanten generischen Typ Quantity
zu konstruieren. Dies bietet den Vorteil, die arithmetischen
Operationen generisch formulieren zu können. Wie früher
trägt Quantity nur Werte in kohärenten Einheiten.
Bei nicht-kohärenten Einheiten findet intern eine Umrechnung
in kohärente Einheiten statt.
pub mod quantities {
use std::ops::{Add, Mul};
#[derive(Clone, Copy)]
pub struct Quantity<const L: i32, const M: i32, const T: i32> {
value: f64
}
impl<const L: i32, const M: i32, const T: i32>
Add<Quantity<L, M, T>> for Quantity<L, M, T>
{
type Output = Quantity<L, M, T>;
fn add(self, y: Quantity<L, M, T>) -> Quantity<L, M, T> {
Quantity {value: self.value + y.value}
}
}
impl<const L: i32, const M: i32, const T: i32>
Mul<Quantity<L,M,T>> for f64
{
type Output = Quantity<L, M, T>;
fn mul(self, y: Quantity<L, M, T>) -> Quantity<L, M, T> {
Quantity {value: self*y.value}
}
}
// Leider ist der Compiler bisher (Stand Januar 2021)
// nicht fortgeschritten genug, um die generische
// Multiplikation von Größen kompilieren zu können.
// Wir implementieren die benötigten Multiplikationen
// im Folgenden daher einzeln.
// Geschwindigkeit*Geschwindigkeit
impl Mul<Quantity<0, 1, -1>> for Quantity<0, 1, -1> {
type Output = Quantity<0, 2, -2>;
fn mul(self, y: Quantity<0, 1, -1>) -> Self::Output {
Quantity {value: self.value*y.value}
}
}
// Masse*Geschwindigkeitsquadrat
impl Mul<Quantity<0, 2, -2>> for Quantity<1, 0, 0> {
type Output = Quantity<1, 2, -2>;
fn mul(self, y: Quantity<0, 2, -2>) -> Self::Output {
Quantity {value: self.value*y.value}
}
}
// Impuls*Geschwindigkeit
impl Mul<Quantity<0, 1, -1>> for Quantity<1, 1, -1> {
type Output = Quantity<1, 2, -2>;
fn mul(self, y: Quantity<0, 1, -1>) -> Self::Output {
Quantity {value: self.value*y.value}
}
}
// Masse*Geschwindigkeit
impl Mul<Quantity<0, 1, -1>> for Quantity<1, 0, 0> {
type Output = Quantity<1, 1, -1>;
fn mul(self, y: Quantity<0, 1, -1>) -> Self::Output {
Quantity {value: self.value*y.value}
}
}
pub type Mass = Quantity<1, 0, 0>;
pub type Speed = Quantity<0, 1, -1>;
pub type Energy = Quantity<1, 2, -2>;
use std::fmt;
impl fmt::Display for Energy {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} Joule", self.value)
}
}
pub mod unit {
use std::ops::Mul;
use super::{Mass, Speed};
pub struct Kilogramm;
pub struct MeterPerSecond;
impl Mul<Kilogramm> for f64 {
type Output = Mass;
fn mul(self, _y: Kilogramm) -> Self::Output {
Mass {value: self}
}
}
impl Mul<MeterPerSecond> for f64 {
type Output = Speed;
fn mul(self, _y: MeterPerSecond) -> Self::Output {
Speed {value: self}
}
}
}
}
macro_rules! quantity {
($v:tt kg) => {$v*unit::Kilogramm};
($v:tt m/s) => {$v*unit::MeterPerSecond}
}
use quantities::{unit, Mass, Speed, Energy};
fn kinetic_energy(m: Mass, v: Speed) -> Energy {
0.5*m*v*v
}
fn main() {
let m = quantity!{1.0 kg};
let v = quantity!{2.0 m/s};
println!("{}", kinetic_energy(m, v));
}
Die Nutzung von Vec zur Erstellung von
Stapelspeichern ist mit dem Nachteil der Haldenspeicher-Allokation
behaftet. Ein Ausweg besteht darin, Stapelspeicher stattdessen mit
Feldern fester Länge zu erstellen, sofern eine Beschränkung der
Kapazität tolerierbar erscheint.
Für diesen Stapel wünscht man sich darüber hinaus einen
eigenen abstrakten Datentyp. Weil dieser Typ allerdings über seine
Kapazität zu parametrisieren ist, benötigen wir eine Konstante
als Typparameter. Die folgende Darstellung zeigt einen Prototyp,
bei dem der Elementtyp zur Vereinfachung durch die Traits
Copy und Default beschränkt wurde.
struct Stack<T, const N: usize> {
sp: usize, buff: [T; N]
}
impl<T: Copy + Default, const N: usize> Stack<T, N> {
fn new() -> Self {
Self {sp: 0, buff: [T::default(); N]}
}
fn try_push(&mut self, value: T) -> Result<(), ()> {
match self.buff.get_mut(self.sp) {
Some(p) => {*p = value; self.sp += 1; Ok(())},
None => Err(())
}
}
fn push(&mut self, value: T) {
self.try_push(value).unwrap()
}
fn pop(&mut self) -> Option<T> {
match self.buff.get(self.sp - 1) {
Some(value) => {self.sp -= 1; Some(*value)},
None => None
}
}
}
fn main() {
let mut stack = Stack::<i32, 10>::new();
stack.push(1);
stack.push(2);
println!("{}", stack.pop().unwrap());
println!("{}", stack.pop().unwrap());
}
Der Typ ArrayVec aus dem Paket
»arrayvec«
bietet eine vollständige Implementierung der benötigten
Funktionalität. Im Wesentlichen handelt es sich hierbei um ein Analogon
zu Vec.
Angenommen, es besteht die Situation wo ein Programm Bytes aus gegebenen Daten herauslesen soll. Das kann beispielsweise so aussehen:
let a: &[u8] = &data[i..i+8]; let y1 = f(a[0], a[1], a[2], a[3]); let y2 = f(a[4], a[5], a[6], a[7]);
Wenn der Compiler smart genug ist, erzeugt er vor den Zugriffen einmal die Prüfung
assert!(a.len() == 8);
und erspart dem Programm infolge die Bounds checks. Wir können die Entfernung der Bounds checks erzwingen ohne uns auf den Compiler zu verlassen, indem der Ausschnitt als Array begriffen wird. Das ist deshalb möglich, weil der Ausschnitt von der festen Länge acht ist. Über die Länge parametrisiert ergibt sich dafür:
trait SubArray<T> {
fn slice<const N: usize>(&self, i: usize) -> &[T; N];
}
impl<T> SubArray<T> for [T] {
fn slice<const N: usize>(&self, i: usize) -> &[T; N] {
self[i..i+N].try_into().unwrap()
}
}
Der Ausschnitt lässt sich nun durch
let a: &[u8; 8] = data.slice::<8>(i);
ersetzen. Freilich sollte der Compiler überdies die Implementierung
von slice optimieren, oder man kümmert sich selbst
darum. Entscheidend ist aber, dass diese Implementierung
vom Rest des Programms abgekapselt vorliegt.
Nebenbei bemerkt ist es wohl noch besser, die acht Bytes gleich
in einer Operation in ein Register zu schieben, um aufwändige
Speicherzugriffe zu sparen. Gehen wir davon aus, der Compiler ist
smart genug und behandelt [u8;8] wie u64,
dann dürfte es kein Nachteil sein, den Ausschnitt per
let a: [u8; 8] = *data.slice::<8>(i);
als Wert zu handhaben. Es mag wohl auch günstig sein, wenn
man erzwingen kann, dass die Adresse von data und
der Index i ein ganzzahliges Vielfaches der Wortgröße
sind. Dann fügt sich der Ausschnitt in die Speicherausrichtung ein und
kann als ein oder zwei Worte gelesen werden. Ich will an dieser Stelle
nicht näher darauf eingehen.
Manchmal möchte man den Bereich einer Parametrisierung
auf einzelne Konstanten einschränken. Das ist erreichbar, indem
für diese konkreten Konstanten ein Trait implementiert wird.
Man stößt hierbei jedoch auf die Komplikation, dass Traits lediglich
für reguläre Typen implementierbar sind, nicht aber für Konstanten.
Dieses Problem lässt sich allerdings durch den folgenden Trick
umgehen. Wir definieren einen Typkonstruktor U32,
der eine Konstante N des Typs u32 in einen
gewöhnlichen Typ U32<N> umwandelt. Der Trait wird
dann stattdessen für diesen Typ implementiert.
Das folgende Beispiel verdeutlicht das Vorgehen anhand eines Linksshifts, der nur für solche Distanzen definiert sein soll, welche nichtnegative ganzzahlige Vielfache von acht sind.
struct U32<const N: u32>;
macro_rules! implement {
($t:ty, for ($tc:ident) [$($value:expr),*]) => {
$(impl $t for $tc<$value> {})*
}
}
trait ShiftAmount {}
implement!(ShiftAmount, for (U32) [0, 8, 16, 24]);
fn shift_left<const N: u32>(x: u32) -> u32
where U32<N>: ShiftAmount
{
x << N
}
fn main() {
println!("{}", shift_left::<8>(1));
}
Es tut sich die Frage auf, ob sich eine Parametrisierung allgemeiner
durch logische Prädikate einschränken lässt. Eine Vorgehensweise
dazu geht wie folgt. Der boolesche Wert des Prädikates ist ebenfalls
eine Konstante, da das Prädikat auf eine Konstante angewendet wird.
Analog wie zuvor muss ein Typkonstruktor Bool den
booleschen Wert in einen gewöhnlichen Typ umwandeln. Um das Prädikat
nun als erfüllt voraussetzen zu können, definiert man einen Trait
True, der ausschließlich für den Wert true
implementiert ist.
struct Bool<const B: bool>;
trait True {}
impl True for Bool<true> {}
fn shift_left<const N: u32>(x: u32) -> u32
where Bool<{N%8 == 0}>: True
{
x << N
}
Zu bemerken ist, dass dafür Ausdrücke mit Parametern auswertbar sein müssen. Im Jahr 2021 war das noch experimentell gewesen.
Die Umwandlung einer booleschen Konstante in einen gewöhnlichen Typ befähigt uns darüber hinaus, eine bereits zur Kompilierzeit ausgeführte Zusicherung an eine Konstante konstruieren zu können. Es gibt zwar auch Tricks, wie man das ohne Konstanten als Typparameter erreichen kann, aber die sind nicht sonderlich ästhetisch.
Als Beispiel wird an ein Feld zugesichert, sortiert zu sein. Fügt man zusätzliche Elemente hinzu, können diese dann nicht versehentlich an der falschen Stelle eingefügt werden. Das ist beispielsweise wichtig, damit eine binäre Suche, die ein sortiertes Feld voraussetzt, korrekt abläuft.
macro_rules! const_assert {
($cond:expr) => {
#[allow(dead_code)]
const _: () = {
struct Bool<const B: bool>;
const _: Bool<true> = Bool::<{$cond}>;
};
}
}
const fn is_sorted(a: &[i32]) -> bool {
let mut i = 1;
while i < a.len() {
if a[i-1] >= a[i] {return false;}
i += 1;
}
true
}
const A: [i32; 4] = [1, 2, 3, 4];
const_assert!(is_sorted(&A));
Alternativ ginge es auch so:
macro_rules! const_assert {
($cond:expr) => {
#[allow(dead_code)]
const _: () = {
if !$cond {panic!("Compile time assertion failed");}
};
}
}
Manchmal möchte man konstante Parameter oder aus ihnen berechnete Konstanten in der öffentlichen Schnittstelle verfügbar machen. Obzwar diese Funktionalität entbehrlich erscheint, bietet sie unter Umständen ein wenig Komfort. Erreichbar ist dies, indem die gewünschten Konstanten als assoziierte Konstanten definiert werden.
pub struct Array<const L: usize>([u32; L]);
impl<const L: usize> Array<L> {
pub const LEN: usize = L;
}