Angenommen, wir erhalten über eine Schnittstelle eine Zeichenkette die aus genau vier dezimalen Ziffern bestehen soll. Diese Zeichenkette wird später in eine Zahl umgewandelt und für einen Datenbankindex verwendet. Nun ist es aber so, dass diese Zeichenkette von einem Client zu einem Server kommt. Das Client-Programm übergibt jedoch eine Zeichenkette die eine falsche Zahl von Ziffern besitzt oder Buchstaben enthält. Dies führt dazu, dass das Datenbanksystem in einen invaliden Zustand gerät und ein über Monate lang unbemerktes Datenleck entsteht.
Das Problem hier ist, dass einer der Programmierer vielleicht nicht gewusst hat, dass die Daten vor der Benutzung hätten validiert werden müssen.
In Rust kann eine solche Validierung vom Typsystem erzwungen
werden, indem für die validierten Daten ein eigener Datentyp definiert
wird, nennen wir ihn DatabaseIndex. Die Idee dabei ist,
dass erstens die betroffenen Unterprogramme nur Werte vom Typ
DatabaseIndex entgegennehmen und zweitens
ein solcher Wert nur über eine Validierung erzeugt werden kann.
mod db {
#[derive(Clone, Copy)]
pub struct DatabaseIndex {
index: u16
}
impl DatabaseIndex {
pub fn new(s: &str) -> Option<Self> {
let a: Vec<char> = s.chars().collect();
return if a.len() == 4 &&
a[0].is_digit(10) && a[1].is_digit(10) &&
a[2].is_digit(10) && a[3].is_digit(10)
{
Some(DatabaseIndex {
index: s.parse::<u16>().unwrap()
})
} else {
None
};
}
pub fn get(&self) -> u16 {
self.index
}
}
}
use std::{io, io::Write};
fn main() {
loop {
print!("Index: ");
if io::stdout().flush().is_err() {println!();}
let mut s = String::new();
io::stdin().read_line(&mut s).unwrap();
s.pop();
match db::DatabaseIndex::new(&s) {
Some(index) => {
database_access(index)
},
None => {
println!("Fehler: ungültiger Datenbankindex.");
continue;
}
};
}
}
fn database_access(index: db::DatabaseIndex) {
println!("Validierter Index: {}", index.get());
}
Hierzu ist zu bemerken, dass das Feld index
von Datenbankindex privat ist. Daher besteht der Zugang
zu Werten vom Typ Datenbankindex nur über die öffentlichen
Funktionen new und get.
Die Idee ist nun, die Steuerung der Datenbank von ihrem Kernel zu abstrahieren. Bei der Ansteuerung der Datenbank sollte es nie zu einem invaliden Zustand kommen. Lediglich im Kernel besteht Zugriff auf die private Funktionalität, bei der das System auch zerstört werden kann, wenn man nicht vorsichtig ist.
In Verbindung hiermit kann gesagt werden, dass die Maxime eine möglichst strenge Typisierung der gesamten Datenverarbeitung sein sollte.
Ein abstrakter Datentyp, kurz ADT, ist ein Datentyp mit Operationen, bei dem die interne Struktur und die interne Implementation der Operationen vor der Öffentlichkeit verschwiegen wird. Bei einem abstrakten Datentyp kann es sich um einen einfachen Datentyp oder auch um eine komplizierte Datenstruktur handeln. Wichtig ist nur, dass nur solche Operationen öffentlich sind, die eine Schnittstelle zur Außenwelt repräsentieren.
Es ist möglich, dass ein abstrakter Datentyp eine vollkommen typsichere Schnittstelle besitzt, obwohl dem bei der internen Implementation nicht so ist. Man spricht von einer sicheren Kapselung oder sicheren Abstraktion.
Rust bietet die Mittel zur Darstellung von abstrakten Datentypen,
indem Variablen und Funktionen per Vorgabe zunächst privat sind.
Möchte man etwas zur öffentlichen Schnittstelle hinzufügen, so muss es
mit dem Schlüsselwort pub als public deklariert werden.
Rust bietet außerdem Zero-Cost-Abstractions, die eine Spezialisierung von allgemeinen abstrakten Datentypen zu spezielleren ermöglichen, ohne dass es dabei zu Laufzeiteinbußen kommt. Zur Umsetzung wird die Inline-Ersetzung von Funktionsaufrufen genutzt.
Als einfachstes Beispiel soll ein Stapelspeicher formuliert
werden, der nur die Operationen push und pop
unterstützt.
mod stack {
pub struct Stack<T>(Vec<T>);
impl<T> Stack<T> {
pub fn new() -> Self {
Stack(Vec::new())
}
pub fn push(&mut self, x: T) {
self.0.push(x);
}
pub fn pop(&mut self) -> T {
match self.0.pop() {Some(x) => x, None => panic!()}
}
}
}
use stack::Stack;
fn main() {
let mut a: Stack<i32> = Stack::new();
a.push(1);
a.push(2);
println!("{}", a.pop());
println!("{}", a.pop());
}
Der Konstruktor new und die Methoden
push und pop können mit
#[inline(always)] annotiert werden, um Inline-Ersetzung
zu erzwingen. Die Funktionen sind aber so kurz, dass der Compiler
das in aller Wahrscheinlichkeit automatisch macht, sofern die
Optimierungen eingeschaltet werden.
Das Konzept der Schnittstelle lässt sich aber auch noch schärfer umsetzen. Spezifiziert man die Schnittstelle durch einen Trait, dann lassen sich abstrakte Programme schreiben, welche nur noch auf die Schnittstelle zugreifen, aber nicht mehr auf konkrete Datentypen.
mod stack {
pub trait Stack<T> {
fn new() -> Self;
fn push(&mut self, x: T);
fn pop(&mut self) -> T;
}
pub struct VecStack<T>(Vec<T>);
impl<T> Stack<T> for VecStack<T> {
fn new() -> Self {
VecStack(Vec::new())
}
fn push(&mut self, x: T) {
self.0.push(x);
}
fn pop(&mut self) -> T {
match self.0.pop() {Some(x) => x, None => panic!()}
}
}
}
use stack::{Stack, VecStack};
fn routine<S: Stack<i32>>() {
let mut a: S = S::new();
a.push(1);
a.push(2);
println!("{}", a.pop());
println!("{}", a.pop());
}
fn main() {
routine::<VecStack<i32>>();
}
Oft möchte man bei Datenstrukturen von außen nur Lesezugriff auf Komponenten zulassen. Ein solcher Schreibschutz gehört neben Privatheit zum Konzept der Kapselung. Würde man eine Schnittstelle zulassen, die Manipulation interner Variablen erlaubt, ließe sich damit die Integrität der Datenstruktur zerstören. Mit dem Schreibschutz können wir eine konforme Benutzung der Datenstruktur erzwingen.
Als Beispiel wählen wir eine Datenstruktur, welche eine Liste von Obst in verschiedenen Sorten und ihr Gesamtgewicht speichert. Sowohl die Liste als auch das Gesamtgewicht müssen von außen schreibgeschützt sein.
Der Grundaufbau der Obstkiste sieht so aus:
struct Fruit {kind: String, weight: u32}
struct FruitCrate {list: Vec<Fruit>, total_weight: u32}
Die Zahlen speichern sinnvollerweise die Masse in Gramm. Die Datenstruktur wird nun eingekapselt. Die problematischen Komponenten – das sind hier sämtliche – lassen wir privat. Ausgelesen werden die Komponenten stattdessen mit Methoden, wobei man der Methode auch den gleichen Bezeichner wie der Komponente geben kann.
pub mod fruit_crate {
pub struct Fruit {
pub kind: String,
pub mass: u32
}
pub struct FruitCrate {
list: Vec<Fruit>,
total_mass: u32
}
impl FruitCrate {
pub fn new() -> Self {
Self {list: Vec::new(), total_mass: 0}
}
pub fn push(&mut self, kind: &str, mass: u32) {
self.list.push(Fruit {kind: kind.to_string(), mass});
self.total_mass += mass;
}
pub fn total_mass(&self) -> u32 {self.total_mass}
pub fn list(&self) -> &Vec<Fruit> {&self.list}
}
}
use fruit_crate::FruitCrate;
fn main() {
let mut fc = FruitCrate::new();
fc.push("Äpfel", 1000);
fc.push("Birnen", 1000);
println!("Die Obstkiste wiegt {}g.", fc.total_mass());
}
In Rust gestaltet sich dazu nun noch eine kleine technische
Schwierigkeit. Nämlich wird mit dem Methodenaufruf list
die gesamte Datenstruktur ausgeborgt. Gäbe es noch eine frei
beschreibbare Komponente, könnte man auf diese während des Ausborgens
nicht mehr zugreifen. Als Beispiel sei der Obstkiste eine boolesche
Variable hinzugefügt, die angibt ob die Kiste geöffnet ist.
pub mod fruit_crate {
#[derive(Debug)]
pub struct Fruit {
pub kind: String,
pub mass: u32
}
pub struct FruitCrate {
list: Vec<Fruit>,
total_mass: u32,
pub open: bool
}
impl FruitCrate {
pub fn new() -> Self {
Self {list: Vec::new(), total_mass: 0, open: true}
}
/* Der Rest wie zuvor */
}
}
use fruit_crate::FruitCrate;
fn main() {
let mut fc = FruitCrate::new();
fc.push("Äpfel", 1000);
fc.push("Birnen", 1000);
let a = fc.list();
fc.open = false;
println!("{:?}", a);
}
Der Compiler würgt das ab, da open nicht überschrieben
werden kann während fc ausgeborgt ist. Es gibt nun
zwei Ansätze, wie sich dieses Problem lösen ließe.
Natürlich ließe sich hier auch Cell<bool> benutzen.
Für allgemeineres müsste man dann aber RefCell heranziehen,
was weniger effizient ist.
Der erste Ansatz besteht darin, das Ausborgen mit einer Methode
aufzuteilen. Hierbei werden Teil-borrows als Tupel oder Struktur
zurückgeben. Zu FruitCrate müssen wir lediglich die
folgende Methode hinzufügen:
pub fn borrow_parts(&mut self) -> (&mut bool, &Vec<Fruit>) {
(&mut self.open, &self.list)
}
So wird es vom Compiler akzeptiert:
fn main() {
let mut fc = FruitCrate::new();
fc.push("Äpfel", 1000);
fc.push("Birnen", 1000);
let (open, list) = fc.borrow_parts();
*open = false;
println!("{:?}", list);
}
Beim zweiten Ansatz hüllt man die schreibgeschützten
Komponenten in eine Struktur ReadOnly ein.
pub mod fruit_crate {
pub struct ReadOnly<T>(T);
impl<T> std::ops::Deref for ReadOnly<T> {
type Target = T;
fn deref(&self) -> &T {&self.0}
}
#[derive(Debug)]
pub struct Fruit {
pub kind: String,
pub mass: u32
}
pub struct FruitCrate {
pub list: ReadOnly<Vec<Fruit>>,
pub total_mass: ReadOnly<u32>,
pub open: bool
}
impl FruitCrate {
pub fn new() -> Self {
Self{
list: ReadOnly(Vec::new()),
total_mass: ReadOnly(0),
open: true
}
}
pub fn push(&mut self, kind: &str, mass: u32) {
self.list.0.push(Fruit {kind: kind.to_string(), mass});
self.total_mass.0 += mass;
}
}
}
use fruit_crate::FruitCrate;
fn main() {
let mut fc = FruitCrate::new();
fc.push("Äpfel", 1000);
fc.push("Birnen", 1000);
let list = &*fc.list;
fc.open = false;
println!("{:?}", list);
}
Da ReadOnly nicht aus dem Modul heraus genommen
werden kann, definiert man dafür am besten ein Makro:
macro_rules! define_read_only {
() => {
pub struct ReadOnly<T>(T);
impl<T> std::ops::Deref for ReadOnly<T> {
type Target = T;
fn deref(&self) -> &T {&self.0}
}
}
}
Manchmal müssen Methoden in einer bestimmten Reihenfolge aufgerufen werden. Dass die Reihenfolge schon zur Kompilierzeit bekannt ist, weist darauf hin, dass sich ein entsprechender Formalismus mittels des Typsystems formulieren lassen müsste. Man spricht von Typzuständen, engl. typestates. Rust bietet mit seinem affinen Typsystem (Move-Semantik) die Möglichkeit, Typzustände bis zu einem gewissen Ausmaß zu modellieren.
Ohne affines Typsystem sind Typzustände nicht möglich, da die fehlende Move-Semantik dazu führt, dass sich Variablen noch nach dem Methodenaufruf benutzen lassen bis sie out of scope sind. Der springende Punkt ist aber, dass die Methode die Variable »aufessen« soll.
Ein einfaches Beispiel. Angenommen, es gibt einen Typ A
mit den Methoden f1, f2a, f2b
und f3. Wir würden nun gern haben, dass f2x
nur nach f1 aufgerufen werden kann und f3
nur nach f2x.
Zur Umsetzung werden drei Typzustände A, A2
und A3 definiert. Die Daten der Typzustände bleiben
privat, damit sich die Objekte ausschließlich über Methoden konstruieren
lassen. Jeder Typzustand bekommt jeweils seine erlaubten Methoden.
pub mod a_state {
pub struct A {data: ()}
impl A {
pub fn new() -> A {A {data: ()}}
pub fn f1(self) -> A2 {A2 {data: self.data}}
}
pub struct A2 {data: ()}
impl A2 {
pub fn f2a(self) -> A3 {A3 {data: self.data}}
pub fn f2b(self) -> A3 {A3 {data: self.data}}
}
pub struct A3 {data: ()}
impl A3 {
pub fn f3(self) {let _ = self.data;}
}
}
use crate::a_state::A;
fn main() {
let a = A::new();
let a = a.f1();
let a = a.f2a();
a.f3();
}
Als Nebeneffekt sind hier syntaktisch angenehme Methodenketten erlaubt:
A::new().f1().f2a().f3();
Dass jeder Typzustand ein eigenständiger Datentyp ist, kann
unpraktisch sein, etwa wenn Methoden für einige oder alle Typzustände
gültig sein sollen. Tatsächlich können wir die Typzustände
zusammenfassen, indem der Zustand als Typparameter kodiert wird.
Die Zustände sollen hierbei keinerlei Daten tragen, weswegen wir
PhantomData heranziehen.
pub mod a_state {
use std::marker::PhantomData as Ph;
pub trait State {}
pub struct A1; impl State for A1 {}
pub struct A2; impl State for A2 {}
pub struct A3; impl State for A3 {}
pub struct A<S: State> {
data: (), marker: Ph<S>
}
pub fn new_a() -> A<A1> {A {data: (), marker: Ph}}
impl A<A1> {
pub fn f1(self) -> A<A2> {A {data: self.data, marker: Ph}}
}
impl A<A2> {
pub fn f2a(self) -> A<A3> {A {data: self.data, marker: Ph}}
pub fn f2b(self) -> A<A3> {A {data: self.data, marker: Ph}}
}
impl A<A3> {
pub fn f3(self) {}
}
}
use a_state::new_a;
fn main() {
new_a().f1().f2a().f3();
}
Einheiten beugen bei technischen oder physikalischen Rechnungen gegen Missverständnisse vor. Zur Schaffung einer erhöhten Sicherheit würden wir dieses Konzept nun auch gerne in die Programmierung einbringen.
Zunächst ließe sich mehr Klarheit schaffen durch Definition der Einheiten als Konstanten:
pub mod unit {
#![allow(non_upper_case_globals)]
pub const km: f64 = 1000.0;
pub const m: f64 = 1.0;
pub const cm: f64 = 0.01;
pub const mm: f64 = 0.001;
}
use unit::{cm, mm};
use std::f64::consts::PI;
fn circumference(radius: f64) -> f64 {
2.0*PI*radius
}
fn main() {
let r = 4.0*cm + 2.0*mm;
println!("{} m", circumference(r));
}
Hierbei verbleibt aber das Problem, dass sich Größen verschiedener Einheit beliebig addieren und multiplizieren lassen. Das würde man jedoch gerne auf erlaubte Operationen beschränken. Hierzu muss für Größen offenbar ein Datentyp definiert werden.
Man könnte nun für alle möglichen Einheiten einen separaten Datentyp definieren. Wesentlich günstiger ist aber die Definition der Dimension als Datentyp. Die Einheiten normalisieren den Zahlenwert dann bloß, dergestalt dass dieser nur in kohärenter Einheit gespeichert wird.
Weiterhin könnte man nun für alle möglichen Größenarten einen
separaten Datentyp definieren bzw. diese mit ihrer Dimension
zusammenfallen lassen. Jedoch ließen sich die Implementationen
wiederkehrender Operationen dann nicht faktorisieren. Daher macht
man die Dimension am besten zu einem Typargument der Größe. Da die
Dimension lediglich zur Kompilierzeit existieren soll, nutzt man
PhantomData. Eine Größe besteht nun aus einem Zahlenwert
value (in kohärenter Einheit) und einer dazugehörigen
Dimension dim.
Wir gehen wie erläutert vor und definieren regelkonform die Multiplikation einer Zahl mit einer Größe und die Addition von zwei Größen gleicher Dimension. Die Einheiten modellieren wir einfach als konstante Größen:
pub mod quantities {
use std::marker::PhantomData as Ph;
use std::ops::{Mul, Add};
use std::fmt;
pub trait Dimension {}
#[derive(Clone,Copy)]
pub struct Quantity<D: Dimension> {
value: f64, dim: Ph<D>
}
impl<D: Dimension> Mul<Quantity<D>> for f64 {
type Output = Quantity<D>;
fn mul(self, y: Quantity<D>) -> Quantity<D> {
Quantity {value: self*y.value, dim: Ph}
}
}
impl<D: Dimension> Add<Quantity<D>> for Quantity<D> {
type Output = Quantity<D>;
fn add(self, y: Quantity<D>) -> Quantity<D> {
Quantity {value: self.value + y.value, dim: Ph}
}
}
pub struct Length;
impl Dimension for Length {}
impl fmt::Display for Quantity<Length> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} m", self.value)
}
}
pub mod unit {
#![allow(non_upper_case_globals)]
use crate::quantities::{Quantity, Length};
use std::marker::PhantomData as Ph;
pub const km: Quantity<Length> = Quantity {value: 1.000, dim: Ph};
pub const m: Quantity<Length> = Quantity {value: 1.0, dim: Ph};
pub const cm: Quantity<Length> = Quantity {value: 0.01, dim: Ph};
pub const mm: Quantity<Length> = Quantity {value: 0.001, dim: Ph};
}
}
use quantities::{Quantity, Length};
use quantities::unit::{cm, mm};
use std::f64::consts::PI;
fn circumference(radius: Quantity<Length>) -> Quantity<Length> {
2.0*PI*radius
}
fn main() {
let r = 4.0*cm + 2.0*mm;
println!("{}", circumference(r));
}
Manchmal möchte man bestimmte Einheiten pedantisch einfordern oder die Umrechnung in kohärente Einheiten herauskürzen. Die Größe bekommt dann als Typargument die konkrete Einheit anstelle der abstrakten Dimension.
pub mod quantities {
use std::marker::PhantomData as Ph;
use std::ops::{Mul, Add};
use std::fmt;
pub trait Unit {
const NAME: &'static str;
}
#[derive(Clone,Copy)]
pub struct Quantity<U: Unit> {
value: f64, unit: Ph<U>
}
impl<U: Unit> Mul<Quantity<U>> for f64 {
type Output = Quantity<U>;
fn mul(self, y: Quantity<U>) -> Quantity<U> {
Quantity {value: self*y.value, unit: Ph}
}
}
impl<U: Unit> Add<Quantity<U>> for Quantity<U> {
type Output = Quantity<U>;
fn add(self, y: Quantity<U>) -> Quantity<U> {
Quantity {value: self.value + y.value, unit: Ph}
}
}
impl<U: Unit> From<f64> for Quantity<U> {
fn from(x: f64) -> Quantity<U> {Quantity {value: x, unit: Ph}}
}
impl<U: Unit> fmt::Display for Quantity<U> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} {}", self.value, U::NAME)
}
}
#[allow(non_camel_case_types)]
#[derive(Clone, Copy)]
pub struct cm;
impl Unit for cm {const NAME: &'static str = "cm";}
}
use quantities::{Quantity, cm};
use std::f64::consts::PI;
fn circumference(radius: Quantity<cm>) -> Quantity<cm> {
2.0*PI*radius
}
fn main() {
let r = Quantity::<cm>::from(4.0);
println!("{}", circumference(r));
}
Programme können die Ausdrücke panic!() und
unreachable!() enthalten. Diese sind überall erlaubt,
da sie den leeren Typ haben und somit als divergent betrachtet
werden können. Enthält eine Funktion einen solchen Ausdruck direkt
oder indirekt über ihre transitiven Abhängigkeiten, ist die
normale Terminierung der Funktion nicht mehr gesichert, sie muss
vom Programmierer verifiziert werden. Es gibt zwar auch noch andere
Möglichkeiten der Divergenz – etwa wenn der Kontrollfluss
semantisch in eine unendliche Schleife gerät – das lassen
wir aber zunächst außen vor.
Betrachten wir das folgende Programm das einen divergenten
Ausdruck unreachable!() enthält.
enum Symbol {Identifier, Number, Add}
struct Token {symbol: Symbol, data: Option<String>}
fn tokens_to_string(a: &[Token]) -> String {
let mut buffer = String::new();
for t in a {
match t.symbol {
Symbol::Identifier | Symbol::Number => {
if let Some(data) = &t.data {
buffer.push_str(data);
} else {
unreachable!();
}
},
Symbol::Add => {
buffer.push('+');
}
}
buffer.push(' ');
}
buffer
}
fn main() {
let a = vec![
Token {symbol: Symbol::Identifier, data: Some("x".to_string())},
Token {symbol: Symbol::Add, data: None},
Token {symbol: Symbol::Number, data: Some("1".to_string())}
];
println!("{}", tokens_to_string(&a))
}
Man verifiziert leicht, dass das Programm terminiert, falls die Token-Liste denn korrekt erzeugt wurde. Umstrukturierung der Datenstruktur gestattet aber eine Entfernung des missliebigen divergenten Ausdrucks, die Terminierung des Programms ist dann sicher.
enum Symbol {
Identifier(String),
Number(u32),
Add
}
fn tokens_to_string(a: &[Symbol]) -> String {
let mut buffer = String::new();
for t in a {
match t {
Symbol::Identifier(id) => {
buffer.push_str(id);
},
Symbol::Number(x) => {
buffer.push_str(&format!("{}",x));
},
Symbol::Add => {
buffer.push('+');
}
}
buffer.push(' ');
}
buffer
}
fn main() {
let a = vec![
Symbol::Identifier("x".to_string()),
Symbol::Add,
Symbol::Number(1)
];
println!("{}", tokens_to_string(&a))
}
Terminierung von Programmen unter allen Umständen ist unter gewissen Anforderungen wichtig. Zwar ist Divergenz keine Sicherheitslücke – explizite Divergenz wird vielmehr eingesetzt um logische Fehler und Sicherheitslücken zu verhindern – jedoch bleibt dabei die Möglichkeit bestehen, dass das Programm irgendwann mit einer Fehlermeldung abstürzt. Das ist meist ein eher gutes Verhalten – je früher die Fehlermeldung kommt, desto besser – aber kein optimales. Für ausfallsichere Systeme ist so eine Divergenz jedoch verboten; etwa will man nicht, dass einfach die Avionik eines Flugzeuges abstürzt.
Freiheit von Divergenz kann in Rust leider nicht vollständig kodiert
werden, das Typsystem ist dafür nicht reichhaltig genug und die
standardmäßig verwendeten Datenstrukturen geben das aufgrund
der Speicherallokation zudem auch nicht her. Die normale implizite
Speicherallokation in Rust kann zu panic!() führen. Man
müsste stattdessen sogenannte fehlbare Speicherallokation
benutzen oder aber den Speicher ganz am Anfang des Programms allozieren.
Wie gesagt stellen sich einem bei der Programmierung von ausfallsicheren Systemen gewisse Schwierigkeiten. Dies fängt schon bei den arithmetischen Operationen an, denn nicht einmal diese sind total. Kommt es zum arithmetischen Überlauf, bricht das Programm ab – zumindest wenn die Erzeugung von automatischen Überlauf-Prüfungen aktiviert ist, andernfalls kommt es zu einer Verschleierung der Fehlerursache, was man als Verschlimmerung empfinden kann. Die Division durch null führt bei Ganzzahlen immer zu einem Programmabbruch.
Wie im Abschnitt ›Monaden‹ im Kapitel ›Funktionale Programmierung‹ erläutert, lassen sich mit einem Wrapper-Typ totale Funktionen aus partiellen gewinnen. Unter Beschränkung auf solche monadischen Typen erreicht man dann sichere Terminierung, da schlicht keine partiellen Funktionen mehr zur Verfügung stehen, vorausgesetzt man benutzt die normalen Datentypen nicht mehr. Das folgende Beispiel zeigt eine ausfallsichere Umwandlung einer Zeichenkette in eine Ganzzahl – ein recht kurzes Beispiel, wobei aber auch ein kompletter mit monadischen Typen arbeitender Parser denkbar und machbar ist.
mod ru32 {
trait Monad<T> where Self: Sized {
fn unit(x: T) -> Self;
fn bind(self, f: impl Fn(T)->Self) -> Self;
}
#[derive(Debug, Clone, Copy)]
pub struct Ru32 (Option<u32>);
impl Ru32 {pub fn err() -> Self {return Ru32(None);}}
impl From<u32> for Ru32 {
fn from(x: u32) -> Self {Self(Some(x))}
}
impl From<char> for Ru32 {
fn from(c: char) -> Self {Self(Some(u32::from(c)))}
}
impl Monad<u32> for Ru32 {
fn unit(x: u32) -> Self {Self::from(x)}
fn bind(self, f: impl Fn(u32)->Self) -> Self {
match self.0 {
Some(x) => f(x), None => Self(None)
}
}
}
impl std::ops::Add<Self> for Ru32 {
type Output = Self;
fn add(self, y: Self) -> Self {
self.bind(|x| y.bind(|y| Self(x.checked_add(y))))
}
}
impl std::ops::Sub<Self> for Ru32 {
type Output = Self;
fn sub(self, y: Self) -> Self {
self.bind(|x| y.bind(|y| Self(x.checked_sub(y))))
}
}
impl std::ops::Mul<Ru32> for u32 {
type Output = Ru32;
fn mul(self, y: Ru32) -> Ru32 {
y.bind(|y| Ru32(self.checked_mul(y)))
}
}
}
use ru32::Ru32;
fn str_to_u32(s: &str) -> Ru32 {
let mut acc = Ru32::from(0);
for digit in s.chars() {
if !digit.is_digit(10) {return Ru32::err();}
acc = 10*acc + (Ru32::from(digit) - Ru32::from('0'));
}
acc
}
fn main() {
println!("{:?}", str_to_u32("1440"));
println!("{:?}", str_to_u32("10000000000"));
}
Nun kann man einwenden, dass das Programm ineffizient ist weil es unnötigen Aufwand enthält. Das ist ein gutes und richtiges Argument, der springende Punkt soll hier aber darin bestehen, das Programm erst einmal sicher zu machen. Nach dieser mentalen Trennung kümmern wir uns um Optimierungen bezüglich Laufzeit und Speicherverbrauch nun im Nachhinein. Dabei kann man die Korrektheit von Optimierungen auch mit dem Hoare-Kalkül beweisen oder nicht, je nachdem wie pedantisch man es halten will.
Die Bedingung digit.is_digit(10) liefert z. B. die
Einschränkung '0' ≤ digit ≤ '9',
infolge ist 0 ≤ digit-'0'. Demnach darf man
Ru32::from(digit) - Ru32::from('0')
ersetzen gegen:
Ru32::from(u32::from(digit) - u32::from('0'))
Bei der vertragsbasierten Programmierung, engl. contract programming, sichern Laufzeitprüfungen das korrekte Arbeiten von Algorithmen ab. Die Prüfungen haben eine strukturierte Form, sie kommen als Prüfung von Vorbedingungen, Nachbedingungen und Invarianten vor.
Nehmen wir als Beispiel eine Funktion zip, welche
zwei Arrays a,b entgegennimmt und ein Array
von Paaren (ak,bk) zurückgibt.
Die Vorbedingung ist, dass beide Arrays die gleiche Länge haben
müssen, die Nachbedingung, dass das Ergebnis ebenfalls diese Länge
besitzt.
Die Vor- und Nachbedingung kann man mittels assert-Anweisungen formulieren.
fn zip<X: Clone, Y: Clone>(a: &[X], b: &[Y]) -> Vec<(X, Y)> {
let n = a.len();
// Precondition
assert!(n == b.len(), "zip(a, b): a.len() == b.len()");
let mut acc = Vec::with_capacity(n);
for k in 0..n {
acc.push((a[k].clone(), b[k].clone()));
}
// Postcondition
assert!(n == v.len());
acc
}
fn main() {
let a = vec![1, 2, 3, 4];
let b = vec!["a", "b", "c", "d"];
let c = zip(&a, &b);
println!("{:?}", c);
}
Ein Nachteil bei dieser Formulierung ist, dass eine return-Anweisung die Nachbedingung unterdrücken würde. Eine Konstruktion zur Entfernung dieses Schönheitsfehlers ist die Verhüllung in einer inneren Funktion, wobei ein Makro für hübsche Syntax sorgt. Die Verhüllung ist auch unter der Bezeichnung IIFE bekannt, das steht für Immediately invoked function expression.
macro_rules! contract {
(precondition $pre:tt $body:tt
postcondition($arg:ident) $post:tt)
=> {
$pre;
let value = (|| $body)();
let $arg = &value;
$post;
value
}
}
fn zip<X: Clone, Y: Clone>(a: &[X], b: &[Y]) -> Vec<(X, Y)> {
let n = a.len();
contract! {
precondition {
assert!(n == b.len(), "zip(a, b): a.len() == b.len()");
}{
let mut acc = Vec::with_capacity(n);
for k in 0..n {
acc.push((a[k].clone(), b[k].clone()));
}
acc
} postcondition(acc) {
assert!(n == acc.len());
}
}
}
Zuweilen findet man auch die Benennung der Zusicherungen als Verben vor. Dann wird die Vorbedingung durch require eingeleitet, die Nachbedingung durch ensure.
Erlaubt eine Funktion beliebige Rekursionstiefe, kommt es irgendwann zu einem Überlauf des Laufzeitstapels, es kommt zum Abbruch des laufenden Programms. Wir würden für bestimmte Anwendungen aber gerne haben, dass das Programm nicht abstürzt bzw. so terminiert wie wir es wollen. Man kann sich dabei z. B. eine Flugzeugavionik vorstellen oder einen Parser für unbekannte Daten aus dem Internet.
Eine Möglichkeit wäre es, rekursive Funktionen schlicht zu verbieten, wie in MISRA-C gefordert. Dies kann man aber als zu einschränkend empfinden, da viele praktische Verfahren wie der rekursive Abstieg mittels wechselseitiger Rekursion formuliert sind.
Eine weitere Überlegung bestünde darin, das Programm in einem extra vorgesehenen Thread auszuführen. Beim Überlauf des Laufzeitstapels kommt es jedoch unweigerlich zum Abbruch des gesamten Programms, nicht nur des aktuellen Threads.
Wir können das Problem umgehen, indem die maximale Rekursionstiefe vorab beschränkt wird. Betrachten wir exemplarisch die rekursive Berechnung der Addition:
fn add(x: u32, y: u32) -> u32 {
if y == 0 {x} else {add(x, y - 1) + 1}
}
Auf meinem Computer lag die maximale Rekursionstiefe
für fn main() {add(0,N);} bei N=174551.
Der genaue Wert ist von unbekannten technischen Details der
Laufzeitumgebung abhängig und muss nicht unbedingt eine feste
Konstante sein. Wenn man unbedingt möchte, kann man diesen Wert durch
Vergrößerung des Laufzeitstapels erhöhen, der Compiler oder das
Laufzeitsystem sollte dafür eine Konfiguration bereithalten.
Man modifiziert die Funktion nun so:
fn add(x: u32, y: u32, depth_max: u32) -> Result<u32,()> {
if depth_max == 0 {return Err(());}
if y == 0 {Ok(x)} else {Ok(add(x, y - 1, depth_max - 1)? + 1)}
}
Ausreizen des Typsystems gestattet es, so viele Implementierungsfehler wie möglich vom Compiler abfangen zu lassen. Trotzdem verbleibt dann immer noch Programmverhalten das sich einer Beschreibung durch das Typsystem entzieht. Das hat unter anderem damit zu tun, dass das Typsystem der Programmiersprache nicht reichhaltig genug ist, um die benötigten logischen Zusammenhänge vollständig beschreiben zu können. Außerdem kann der Compiler keinesfalls feststellen ob ein Algorithmus korrekt implementiert ist, denn dazu müsste der Compiler zunächst eine formale Spezifikation bekommen die der Algorithmus zu erfüllen hat. Diese Spezifikation liegt aber offensichtlich oft noch nicht einmal vor.
Ein anderer Weg zum Abfangen von fehlerhaften Algorithmen sind automatische Tests. Umso ausgiebiger diese Tests ausfallen, umso besser.
Tests sind gewöhnliche Funktionen, die man am besten ordentlich
in einem Modul ansammelt. Einem solchen Modul gibt man das Attribut
#[cfg(test)],
dies sorgt dafür, dass das Modul nur beim Testen kompiliert wird.
Tests sind gewöhnliche Funktionen. Auch bei Tests gibt es
Hauptfunktionen wie main. Im Unterschied zum Programm
kann es aber bei den Tests mehrere unterschiedliche Testläufe geben.
Aus diesem Grund gibt man den Hauptfunktionen gewöhnliche Namen und
markiert sie mit dem Attribut #[test].
Angenommen, jemand hat einen neuen Algorithmus geschrieben.
Mir ist dazu kein besseres Beispiel eingefallen als ein Primzahltest
is_prime, das ist ein recht kurzer Algorithmus.
Der Algorithmus wird mit einem schon bekannten einfacheren Algorithmus
is_prime_basic überprüft. Zur Sicherheit wird der
einfache Algorithmus zusätzlich mit einem unabhängig ermittelten
Resultat überprüft.
fn is_prime(n: u32) -> bool {
if n < 2 {return false;}
let mut i: u32 = 2;
while i*i <= n {
if n%i == 0 {return false;}
i += 1;
}
true
}
#[cfg(test)]
mod tests {
use crate::is_prime;
fn is_prime_basic(n: u32) -> bool {
n > 1 && (2..n).all(|k| n%k != 0)
}
#[test]
fn test0() {
let s: u32 = (0..10000).filter(|&n| is_prime_basic(n)).sum();
assert_eq!(s, 5736396);
}
#[test]
fn test1() {
for n in 0..10000 {
assert_eq!(is_prime(n), is_prime_basic(n));
}
}
}
fn main() {
let a: Vec<u32> = (1..).filter(|&n| is_prime(n))
.take(100).collect();
println!("{:?}", a);
}
Das ist natürlich kein Beweis, dass der Algorithmus in jedem Fall das richtige Ergebnis liefert. Tatsächlich wurde hier der arithmetische Überlauf nicht berücksichtigt, der erst bei viel größeren Zahlen auftritt. Im Release-Modus würden Overflow-Checks entfernt werden, ein Überlauf bliebe also im schlimmsten Fall unentdeckt.
Oft stellt es einen logischen Fehler dar, wenn der Rückgabewert einer Funktion einfach verworfen wird. Bspw. ergibt das Aufrufen einer reinen Funktion wie
fn even(x: i32) -> bool {x%2 == 0}
ohne Verwendung des Rückgabewertes keinen Sinn. Zur Vorbeugung
gegen diese Art von logischen Fehlern steht das Attribut
must_use zur Verfügung.
#[must_use]
fn even(x: i32) -> bool {x%2 == 0}
Die Anweisung
even(0);
führt dann bei der Kompilation zu einer Warnung. Möchte man den Wert trotzdem verwerfen, muss man dies nun explizit tun:
let _ = even(0);
Neben den Funktionen sind auch die Definitionen von Strukturen,
Enumerationen und Traits mit dem Attribut must_use
behaftbar. So hat der Typ Result dieses bekommen,
damit die Err-Variante nicht versehentlich ignoriert wird,
auch wenn die Ok-Variante nicht gebraucht wird. Ein solcher Fall
zeigt sich ganz klar etwa bei Result<(),E>.
Einigen mag must_use nicht genügen, da diese Festlegung
bei der Definition der Funktion vergessen werden kann. Erwähnenswert
ist hierzu, dass sich mit
#![deny(unused_results)]
implizites Verwerfen für sämtliche Funktionen eines Moduls
oder gar im ganzen Crate unterbinden lässt. Allerdings gilt dies
anders als bei must_use nur innerhalb des Moduls. Die
Schnittstellen zur Außenwelt sind nicht betroffen.