HeyVL Examples
The examples below cover probability bounds, expected costs, termination, and Boolean correctness. Start with First Example: Expected Runtime for a short walkthrough, then Geometric Loop to compare proof techniques. Browse by program family, or filter by topic and technique.
Random Walks and Countdowns
Geometric Loop
Count tails until a fair coin first shows heads. Prove that the expected number of tails is one, and refute a proposed upper bound of .
One-Sided Random Walks
Move toward a target with random pauses or steps of one or two. Compare almost-sure termination, finite expected numbers of coin flips, and numerical bounds on those expectations.
Two-Sided Random Walks
Move toward or away from a target, with positive drift, adversarial choice, or parity-dependent steps. Caesar bounds the expected number of flips for positive drift and proves almost-sure termination for the adversarial and parity-dependent walks.
Escaping Spline
Move to zero with probability , otherwise increase the current state. Caesar verifies almost-sure termination even though the probability of reaching zero in one iteration decreases as the state grows.
Sampling and Probabilistic Models
Coupon Collector
Draw independently from equally likely coupons until the collection is complete. Caesar bounds the expected number of draws by , where is the -th harmonic number.
Reservoir Sampling
Keep one uniformly chosen item from a stream without storing the whole stream. Caesar proves matching probability bounds and termination, establishing a selection probability of for every position.
Fast Dice Roller
Compare rejection sampling with Fast Dice Roller, which reuses the randomness in rejected values. The fast sampler's proof uses one invariant for matching bounds on each result.
Morris Approximate Counting
Count events by incrementing a small counter with a probability that decreases as it grows. Caesar verifies that the expected estimate is at most the number of events.
Continuous Tortoise–Hare Race
A hare chooses continuous random jumps while a tortoise advances one step per round. Caesar checks an upper bound on the expected final round count through a Riemann approximation of continuous sampling.
Conditioning on Queue Completion
A queue receives new jobs while a server processes existing ones and may fail. Conditioned on emptying before failure, Caesar bounds the expected number of rounds by for every initial queue size , without bounding the queue's growth.
Die Sampling with Conditioning
Simulate a six-sided die with three fair coin flips, conditioning on a result at most six. Caesar verifies that the expected die result under this condition is at most .
Noisy-OR Bayesian Network
Sample a Boolean Bayesian network whose nodes combine causes by disjunction. Caesar verifies lower bounds on the probabilities that the output is true or false.
Rewards and Resource Consumption
Retry Latency and Higher Moments
Compare database retries with a caching alternative that has the same mean latency. Caesar bounds their second moments using incremental rewards, supporting a comparison of latency variance.
Finite Expected Runtime Does Not Compose
A randomized generator and a deterministic countdown each have finite expected runtime for every fixed input. Their composition terminates almost surely but has infinite expected runtime.
Protocols
Zeroconf Address Allocation
Probe one candidate network address for a conflict. Caesar verifies an upper bound on the probability of avoiding an undetected collision using recursive specifications.
Bounded Retransmission Protocol
Send packets over a lossy channel, retrying each packet up to a fixed limit. Caesar bounds success and failure probabilities and the expected numbers of attempts, failed attempts, and sent packets.
Rabin’s Mutual-Exclusion Algorithm
Contenders repeatedly flip coins to decide whether to withdraw, aiming to leave one survivor. For multiple contenders, Caesar proves that the probability of ending with no survivors is at most .
Data Structures
Selection Sort
Sort an integer list by repeatedly selecting the smallest remaining element. Caesar uses Boolean loop invariants to prove that the result is nondecreasing and has the original length on termination.
Symbolic List Operations
Update, append to, and read the last element of a symbolic linked list. Caesar uses recursive specifications to prove that the operations return the specified lengths and elements on termination.
Left Padding
Prepend a chosen value until a list reaches the requested width. Caesar verifies the output length, padding values, and preservation of the original list as a suffix.
Lossy List Traversal
Traverse a list while each step has a chance of a memory fault. For a list of length , Caesar verifies a success probability of at least .
Binary Search Trees
Look up and insert values, and find the minimum and maximum in a binary search tree. Under the domain axioms, Caesar proves that queries return the specified values and insertion preserves tree ordering on termination.