// RUN: @caesar @file

// Optional stopping proves a lower bound on the expected value of count on termination.
// The annotation checks the subinvariant, the expected number of iterations, and bounded differences.
@wp
proc geometric(init_count: UInt, init_running: Bool) -> (count: UInt, running: Bool)
    pre init_count + [init_running]
    post count
{
    count = init_count
    running = init_running
    // count + [running] changes by -1 after heads and +1 after tails.
    // Its expectation is unchanged, and at termination it equals count.
    // 2 * [running] bounds the expected number of remaining coin flips.
    // Each active iteration changes the subinvariant by exactly 1 in absolute value.
    @ost(count + [running], 2 * [running], 1, count)
    while running {
        var stop: Bool = flip(0.5)
        if stop {
            running = false
        } else {
            count = count + 1
        }
    }
}
