# evan_tech

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.

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.

•  Wow. I can read that expression, but I don't understand OCaml well enough to know why this hurts it so bad. reply to this
•  (a, b) in Caml is a tuple-- I never understood the difference between a tuple and a list until it was explained as a struct where all of the fields are unnamed (or are named by their position in the struct). So basically they're like fixed-sized arrays or something. You can't go out of bounds in a tuple for the same reason you can't on a struct: there's no way to refer to stuff outside of a struct. (Of course, I ignore C-style pointers 'cause you can do anything with those; OCaml is safe, but no level of safety can make it so you can't write an out-of-bounds expression on an array. Though Cyclone actually sorta does that... heh.)Anyway, 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. reply to this
•  Oh, duh! It just completely failed to click that exponential and twenty steps out means really big. reply to this
•  it's a finite fork-bomb for the type inferencer: it asks the inferencer to build a term with around a million subterms. reply to this