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 ML-ish¹ 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² Expr is exactly 16 bytes³:

#[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: