↑Programmieren in Rust

Unendliche Datenstrukturen

Inhaltsverzeichnis

1. Lazy Evaluation
2. Sharing

Lazy Evaluation

Bei Lazy Evaluation, auch Bedarfsauswertung genannt, wird ein Ausdruck nicht sofort ausgewertet, sondern erst dann, wenn der Wert auch benötigt wird.

Wir können Closures zur Implementation von Lazy Evaluation heranziehen.

macro_rules! lazy {
    ($x:expr) => {Lazy {value: Box::new(move || $x)}}
}

struct Lazy<T> {
    value: Box<dyn Fn()->T>
}

impl<T> Lazy<T> {
    fn force(&self) -> T {(self.value)()}
}

Als konkretes Beispiel soll ein unendlicher Baum formuliert werden.

struct Tree{
    left: Lazy<Tree>,
    right: Lazy<Tree>,
    value: i32
}

fn tree(x: i32) -> Tree {
    Tree {
        value: x,
        left: lazy!{tree(x)},
        right: lazy!{tree(x + 1)}
    }
}

fn main() {
    println!("{}",
        tree(0).right.force().left.force().value
    );
}

Der Baum hat demnach die folgende Gestalt:

                    0
                   / \
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            /               \
           /                 \
          /                   \
         0                     1
        / \                   / \
       /   \                 /   \
      /     \               /     \
     /       \             /       \
    0         1           1         2
   / \       / \         / \       / \
  0   1     1   2       1   2     2   3
 / \ / \   / \ / \     / \ / \   / \ / \
.. ... .. .. ... ..   .. ... .. .. ... ..

Auch if-Ausdrücke lassen sich mit Lazy Evaluation darstellen:

fn if_cond<T>(cond: bool, a: Lazy<T>, b: Lazy<T>) -> T {
    (if cond {a} else {b}).force()
}

fn fac(n: u32) -> u32 {
    if_cond(n == 0, lazy!{1}, lazy!{n*fac(n - 1)})
}

Sharing

Betrachten wir das folgende Programm:

fn log(value: i32) -> i32 {
    println!("Auswertung");
    value
}

fn main() {
    let x = lazy!{log(0)};
    println!("{}", x.force());
    println!("{}", x.force());
}

Hier findet die Berechnung des Wertes x zweimal statt. Bei referentiell transparenten Funktionen ist die Wiederholung von Berechnungen eigentlich nicht notwendig. Diesem Umstand könnte man so Rechnung tragen:

use std::cell::RefCell;

macro_rules! lazy {
    ($x:expr) => {Lazy {cell: RefCell::new(
        Thunk::Calc(Box::new(move || $x))
    )}}
}

enum Thunk<T> {
    Calc(Box<dyn Fn() -> T>),
    Value(T)
}

struct Lazy<T> {
    cell: RefCell<Thunk<T>>
}

impl<T: Clone> Lazy<T> {
    fn force(&self) -> T {
        let mut cell = self.cell.borrow_mut();
        match &*cell {
            Thunk::Calc(calc) => {
                let value = calc();
                *cell = Thunk::Value(value.clone());
                value
            },
            Thunk::Value(value) => {
                value.clone()
            }
        }
        
    }
}

Es verbleiben noch zwei Probleme. Zum einen würde man Fn gerne durch FnOnce ersetzen. Zum anderen muss man T: Clone entferenen und stattdessen x.force() vom Typ &T bzw. &mut T haben.