You write the rules a function has to follow. Flexigen picks an implementation that fits, and picks a different one when the input changes.
// Declare what must hold. The compiler decides how. adaptive fn sort(xs: List<Int>) -> List<Int> { spec { ensure sorted(xs) // invariant the runtime cannot break optimize speed // what to optimize for keep stable // extra constraint } baseline { merge_sort(xs) } variant timsort when mostly_sorted(xs) variant insertion when len(xs) < 32 }
A function written today gets shipped against the data, hardware, and workload that exist today. When any of those change, the function is wrong without warning. Flexigen lets the function carry its own decisions about how to run.
spec block names what the function has to guarantee, what to optimize for, and any extra constraints. The compiler enforces it. A variant that violates it gets rejected before it can run.Every adaptive function has four parts. The first two define what is allowed to happen. The third lists alternative implementations. The fourth records what actually ran.
when guard. At call time the runtime evaluates the guards, picks the first variant whose guard matches, and falls back to baseline if none do.// Picks a scan strategy by input shape adaptive fn has_duplicates(a: List<Int>) -> Bool { spec { ensure exact; optimize speed } // O(n^2). The reference. baseline { nested_scan(a) } // O(n) hash. Default fast path. variant hashset_scan // O(n) bitmap when values fit in memory. variant bitmap_scan when max(a) < 1_000_000 }
Hello world, FizzBuzz, list operations, an adaptive Fibonacci, and a duplicate-detection report. All run by the same interpreter, all in the same .flex syntax.
let name: String = "World" let limit: Int = 90 let scores = List<Int>[88, 92, 75, 61, 99] fn greet(who: String) -> String { return "Hello, " + who + "!" } fn clamp(x: Int) -> Int { if x > limit { return limit } else { return x } } print(greet(name)) for n in scores { print(clamp(n)) }
adaptive fn fibonacci(n: Int) -> Int { spec { ensure exact; optimize speed } baseline { fib_recursive(n) } variant fib_iterative when n > 10 variant fib_memoized when n > 30 }
let numbers = List<Int>[3,7,2,9,4,6,1,8,5,10] fn is_even(n: Int) -> Bool { return n % 2 == 0 } fn double(n: Int) -> Int { return n * 2 } adaptive fn sort(xs: List<Int>) -> List<Int> { spec { ensure sorted(xs); keep stable } baseline { merge_sort(xs) } variant insertion when len(xs) < 32 }
fn fizzbuzz(n: Int) -> String { if n % 15 == 0 { return "FizzBuzz" } if n % 3 == 0 { return "Fizz" } if n % 5 == 0 { return "Buzz" } return n } let i: Int = 1 while i <= 30 { print(fizzbuzz(i)) i = i + 1 }
adaptive fn has_duplicates(a: List<Int>) -> Bool { spec { ensure exact; optimize speed } baseline { nested_scan(a) } variant hashset_scan variant bitmap_scan when max(a) < 1_000_000 } let dataset_a = List<Int>[10,25,37,42,58...] let dataset_b = List<Int>[5,12,33,12,47...] print(has_duplicates(dataset_a)) print(has_duplicates(dataset_b))
The interpreter is the core. The rest is what a real version of Flexigen would need to be useful: a way to compile, a way to measure, a way to inspect, and a way to audit. The current prototype implements flexc. The others are described here as proposed work.
CS 420, Programming Language Design, SDSU, Spring 2026.