PL Resources Everywhere
In playing around with OCaml, I’ve spent some spare time perusing more programming language resources. There are a bunch out there, especially in this era of online learning; for instance, Cornell has made some great resources available. In looking specifically for more MLish^{1} flavored ones, I came across this fun undergrad homework set. In the second problem, it asks you to implement a tiny (recursively defined) language of expressions encoding functions from the unit square to the unit interval, \( [0, 1]^2 \mapsto [0, 1] \).
type expr = VarX
 VarY
 Sine of expr
 Cosine of expr
 Average of expr * expr
 Times of expr * expr
 Thresh of expr * expr * expr * expr
After you learn to build them up randomly, you can evaluate them across the unit square to generate pictures—have each output value encode either a greyscale value, or one of an RGB triple. Note to undergrads: please don’t cheat off me; you’ll only rob yourself of a fun learning experience.
No Peeking!
This was a fun exercise in OCaml, but I also found it instructive to tackle it in Rust and compare. Besides the superficial differences, Rust’s concern with and ability to control memory usage is apparent. I defined the core enumeration thusly:
pub enum Expr {
X,
Y,
SinPi(Box<Expr>),
CosPi(Box<Expr>),
Mul(Box<Mul>),
Avg(Box<Avg>),
Thresh(Box<Thresh>),
}
I renamed some variants to more accurately express their intent; e.g.
SinPi(expr)
evaluates to \( sin(\pi \cdot \) expr
\(\!)\).
More importantly, I reworked the recursive variants to each contain (at most) a
single Box
(i.e. unique pointer to a heap allocated value); for instance,
Expr::Mul
contains a Box<Mul>
, where Mul
is defined as
pub struct Mul {
e1: Expr,
e2: Expr,
}
I took up this trick after
learning
more about it from the inimitable matklad.
As the linked response says, this keeps the size of the base enum smaller.
In the source code, I’ve got a property
test
that asserts the size of an arbitrary^{2} Expr
is exactly 16 bytes^{3}:
#[test]
fn size_of(e in arb_expr()) {
assert_eq!(size_of_val(&e), 16)
}
If we instead went with a more direct translation of the OCaml code, like
diff git a/src/lib.rs b/src/lib.rs
index 3b04a74..68c600c 100644
 a/src/lib.rs
+++ b/src/lib.rs
@@ 7,9 +7,9 @@ pub enum Expr {
Y,
SinPi(Box<Expr>),
CosPi(Box<Expr>),
 Mul(Box<Mul>),
 Avg(Box<Avg>),
 Thresh(Box<Thresh>),
+ Mul { e1: Box<Expr>, e2: Box<Expr> },
+ Avg { e1: Box<Expr>, e2: Box<Expr> },
+ Thresh { e1: Box<Expr, e2: Box<Expr>, e3: Box<Expr>, e4: Box<Expr> },
}
then this property test would no longer pass, as the enum needs to be large enough to contain its largest variant.
Pretty Pics Plz
Once I coded up the library, I also put together a small
executable to
take in some parameters and generate greyscale or RGB pictures, similar to the
original exercise.
With that defined, I could run it a bunch of times using
jot
to
generate random seeds and parallel
to use multiple cores:
jot w %i r 20 0 1000000000  parallel bar ./target/release/ra s {} d 7 r
Here are some gems I found combing through the PNGs:

I really like propertybased testing, in this case with
proptest
. ↩︎ 
Since
size_of_val
returns the size of the pointedto value in bytes, this test returns 16 on my 64bit laptop; it will probably fail on a 32bit architecture. Be sure to check out this awesome article for more on Rust enums. ↩︎