Multi-stage programming vs. defunctionalization

Defunctionalization typically refers to a technique to eliminate higher-order functions (ie when you pass functions as arguments) by replacing them by a fixed sum type enumerating the possible closure shapes at every callsite. This requires making a global control flow analysis to get an exhaustive list of all functions that may “flow” to a given callsite.

Multi-stage programming, on the other hand, is a technique for runtime code generation. As such, it is not directly related to defunctionalization, at least superficially.

In fact, the standard example of meta-programming, the power function, is perfectly first-order and does not involve any higher-order construct, so would not benefit from defunctionalization in any obvious manner.

let square x = x * x
let rec power n x =
  if n = 0 then 1
  else if n mod 2 = 0 then square (power (n/2) x)
  else x * (power (n-1) x)

Cheers,
Nicolas