04:05 pm, 15 Jan 04

### breaking ocaml

The guy next to me was learning SML for his intro to programming languages class, so I tried to impress on him how awesome and fundamentally mind-altering it was. But he hadn't encountered a functional language before so he couldn't see why type inference was so neat.

Note that we never actually use x, and instead just assign to q. So the ensuing grinding is just a product of the type-inferencer.

Reminds me a lot of that "million laughs" XML attack, where you create entities that expand recursively.

**chris_one**pointed me at a paper that eventually led to me producing this OCaml gem:Note that we never actually use x, and instead just assign to q. So the ensuing grinding is just a product of the type-inferencer.

let q = let x = 1 in let x1 = (x, x) in let x2 = (x1, x1) in let x3 = (x2, x2) in let x4 = (x3, x3) in let x5 = (x4, x4) in let x6 = (x5, x5) in let x7 = (x6, x6) in let x8 = (x7, x7) in let x9 = (x8, x8) in let x10 = (x9, x9) in let x11 = (x10, x10) in let x12 = (x11, x11) in let x13 = (x12, x12) in let x14 = (x13, x13) in let x15 = (x14, x14) in let x16 = (x15, x15) in let x17 = (x16, x16) in let x18 = (x17, x17) in let x19 = (x18, x18) in let x20 = (x19, x19) in x20 in 1

Reminds me a lot of that "million laughs" XML attack, where you create entities that expand recursively.

confusemeevanAnyway, the type inferencer wants to figure out the types of each of these variables x, x1, x2. x is clearly an integer, and x1 a tuple of two integers (written "(int * int)"; think cartesian product if that star looks weird). Then each later variable has a type that's twice as big as the one above it-- x3 is ((int * int) * (int * int)). That blows up exponentially, so x20 is some gory type that has 2^20 "int"s in it.

confusemereally big.graydon