• 36. Empirical Pi

You’ve finally snuck into the evil mastermind’s billiards room. You’re only one door away from his office and the Big Red Button that stops the moon laser from vaporizing the Great Barrier Reef.

What is the value of $$\pi$$?”, beeps the security panel.

“Huh. Easy”, you think as you type $$2.71$$.

“Mhm. Maybe it needs more digits?” You type $$2.71828$$.

You feel a cold sweat coming on as you scan the room for something to use. You could try to calculate $$\pi$$ with a series expansion, but you don’t trust yourself anymore. No, with one chance to go, you want something foolproof. Billiards table. Chairs. Dartboard. Liqueur cabinet. Dartboard!

A dartboard is just a square with an inscribed circle. If the side of the square is $$L$$, the radius of the circle is $$\frac{1}{2} L$$. So, the ratio of the surfaces of the circle and the square are:

$\frac{S_C}{S_S} = \frac{\pi * (\frac{1}{2} L)^2}{L^2} = \frac{1}{4}\pi$

But you can also find that ratio by throwing darts randomly and counting how many land in the circle. A simple program to do this is here:

#!/usr/bin/python

from __future__ import print_function
import math, random

acErr = 1e-5

def inCircle(x, y):
"""inCircle(x, y) iff (x, y) is in the circle of radius 1 centered at
origin"""
return (math.sqrt(x**2 + y**2) - 1.0) <= acErr

def piGen():
"""Generates increasingly accurate values for Pi"""
S_circle, S_square = 0.0, 0.0
while True:
x, y = random.random(), random.random()
S_circle += (1 if inCircle(x, y) else 0)
S_square += 1
yield (4*S_circle/S_square)

def run_pi():
random.seed()
print("Pi is 0.00000", end="")
i = 0
for p in piGen():
i += 1
if i % 25 == 0:
print("\rPi is %1.5f" % p, end="")

if __name__ == "__main__":
run_pi()

Alternatively, you could use the Gregory-Leibniz series which is easy to remember but much harder to derive:

$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$

• 35. OCaml's Compare

Programming languages often have features which are not necessary but which are a boon to working with them. For example, Haskell compilers can automagically derive pretty-printers for user-defined datatypes which is a great help when debugging. Unfortunately, things don’t always go the way the language authors intended, and such features end up being more confusing than helpful. Take, for instance, the following implementation of a doubly-linked list in OCaml.

(** A circular doubly-linked list in OCaml.  See:
*)
data         : 'a;
}

type 'a t = {
}

(** [create ()] makes a new doubly-linked list. *)
let create () =
;;

(** [cons t data] prepends [data] to the doubly-linked
list [t]. *)
let cons t data =
let rec new_node =
{ data; prev = new_node; next = new_node; }
in
| None ->
| Some node ->
new_node.next <- node;
new_node.prev <- node.prev;
new_node.next.prev <- new_node;
new_node.prev.next <- new_node;
;;

(** [iter t ~f] executes [f] on each of the values
stored in the doubly-linked list [t]. *)
let iter t ~f =
let rec go ~start node =
f node.data;
if node.next <> start then
go ~start node.next
in
| None      -> ()
| Some node -> go ~start:node node
;;
end

(* Create a doubly-linked list and print its contents. *)
let main () =
let list = Doubly_linked_list.create () in

print_endline "Count-up timer go!";
print_endline "Done!";
;;

let () = main ();;

Seems innocuous, doesn’t it? But, running it fails with Fatal error: exception Out_of_memory; we’re actually causing the runtime to error out here. And it could be worse: I’ve seen code like this put the runtime into an infinite loop, and if the code is any more complicated, it’s a pain to debug.

The problem is our choice of comparison operator in iter: we used (<>), but we meant to use (!=).

val (<>) : 'a -> 'a -> bool
val (!=) : 'a -> 'a -> bool

Looking at the types of these comparison functions, we see something strange: since they’re polymorphic, they can’t be written in pure OCaml as anything other than constant functions. In fact, they’re both written in C, and they both on rely on information not normally available to OCaml code: (!=) does a pointer comparison of the given OCaml values, and (<>) does a structural comparison by recursively walking the pointers of the given OCaml values and comparing any binary blobs encountered.

The reasoning behind this is that we almost always want comparison functions for new data types and writing them is usually automatic. The problem here is that that OCaml allows mutable data, so it’s possible to create a circular data-structure which causes structural comparison to recurse infinitely.

What I find particularly annoying about all this is that everything happens automatically and the programmer is at no point forced to pause and think about what they’re doing; had we written the above code in Haskell, we would’ve had to “opt-in” to the automatic comparison generation and we would’ve probably noticed that structural comparison doesn’t really make sense for doubly_linked_node values.

Luckily, we can now do the above in OCaml too. By opening something like Core’s no_polymorphic_compare.mli in each module, we guarantee that we’ll get a type-error whenever we try to use polymorphic comparison. Then, we can generate comparison functions on a type-by-type basis with a syntax extension like comparelib.