stutter 0.1.0

An API capturing computations which can be subdivided into smaller steps
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/// Captures the output from a steppable function.  In the future,
/// this should become an associated type.
pub enum Output<S, T> {
    /// Indicates the given computation has yet to reach a terminal
    /// state.
    More(S),
    /// Indicates the given computation has reached a terminal state.
    Done(T),
}

impl<S, T> Output<S, T> {
    //
    pub fn more(self) -> S {
        match self {
            Output::More(s) => s,
            Output::Done(_) => {
                panic!("no more as computation done!");
            }
        }
    }
    //
    pub fn done(self) -> T {
        match self {
            Output::More(_) => {
                panic!("computation is not yet done!");
            }
            Output::Done(t) => t,
        }
    }
}

/// A trait capturing the essence of a steppable computation.  We can
/// take a single step on a computation with a given state `S` which
/// either produces an updated state `S` or a terminal state `T`.
pub trait StepFn<S, T> {
    /// Take a single step in the computation.
    fn step(&self, state: S) -> Output<S, T>;

    /// Take at most `n` steps in the computation.
    fn nstep(&self, state: S, n: u64) -> Output<S, T> {
        let mut st = state;
        // Iterate at most n steps
        for _i in 0..n {
            match self.step(st) {
                Output::More(s) => {
                    st = s;
                }
                Output::Done(t) => {
                    return Output::Done(t);
                }
            }
        }
        // Done!
        Output::More(st)
    }

    /// Take a _big step_ in the computation (i.e. attempt to reduce
    /// all the way to a terminal state).
    fn bigstep(&self, state: S) -> T {
        let mut st = state;
        // Obviously, this could cause an infinite loop.
        loop {
            match self.step(st) {
                Output::More(s) => {
                    st = s;
                }
                Output::Done(t) => {
                    return t;
                }
            }
        }
    }
}

/// A trait capturing the essence of a steppable computation over
/// _mutable_ state.  We can take a single step on a computation with
/// a given state `S` which either produces an updated state `S` or a
/// terminal state `T`.
pub trait StepMutFn<S, T> {
    /// Take a single step in the computation.
    fn step(&mut self, state: S) -> Output<S, T>;

    /// Take at most `n` steps in the computation.
    fn nstep(&mut self, state: S, n: u64) -> Output<S, T> {
        let mut st = state;
        // Iterate at most n steps
        for _i in 0..n {
            match self.step(st) {
                Output::More(s) => {
                    st = s;
                }
                Output::Done(t) => {
                    return Output::Done(t);
                }
            }
        }
        // Done!
        Output::More(st)
    }

    /// Take a _big step_ in the computation (i.e. attempt to reduce
    /// all the way to a terminal state).
    fn bigstep(&mut self, state: S) -> T {
        let mut st = state;
        // Obviously, this could cause an infinite loop.
        loop {
            match self.step(st) {
                Output::More(s) => {
                    st = s;
                }
                Output::Done(t) => {
                    return t;
                }
            }
        }
    }
}