A self-improving programming language.

-- Factorial with cost annotation
let rec factorial n : Int -> Int [cost: Linear(n)] =
  if n <= 1 then 1
  else n * factorial (n - 1)

-- GCD via Euclid's algorithm
let rec gcd a b : Int -> Int -> Int [cost: Unknown] =
  if b == 0 then a
  else gcd b (a % b)

-- Sum a list using fold
let sum xs : List Int -> Int [cost: Linear(xs)] =
  fold 0 (+) xs

-- Filter, transform, and sum with pipes
let process xs : List Int -> Int [cost: Linear(xs)] =
  xs |> filter (\x -> x > 0)
     |> map (\x -> x * x)
     |> fold 0 (\acc x -> acc + x)

-- Nested lambdas capture outer scope
let scale_all xs factor : List Int -> Int -> List Int =
  map (\x -> x * factor) xs

-- Programs that rewrite themselves
let mutate program new_op : Program -> Int -> Program =
  let root = graph_get_root program in
  graph_set_prim_op program root new_op