Push Ifs Up and Fors Down: The Idiom, Its Algebra, and Its Limits
a day ago
- The idiom 'push ifs up and fors down' suggests moving conditional logic upward to callers and iterative loops downward to batch processing for clarity and performance.
- In TigerBeetle, centralizing control flow in a parent function while moving non-branchy logic to helpers exemplifies this idiom.
- matklad's example: replace `frobnicate(Option<Walrus>)` with the caller handling None and the callee taking a plain Walrus; also replace looped calls with a batch function `frobnicate_batch` that runs a tight loop.
- In database query optimization, the principle appears as pushing projections and selections early (down the tree) and deferring joins (up), analogous to 'push ifs up' and 'fors down'.
- Vectorized execution in databases (batch processing) is the 'fors down' counterpart, reducing per-call overhead.
- In category theory, pushing ifs up corresponds to restricting input to a subobject (e.g., using a type instead of an Option), eliminating branching.
- The filter/map law `filter p . map f == map f . filter (p . f)` shows when rearranging operations is valid; it saves work when the composed predicate simplifies.
- The legality of rewrites depends on algebraic constraints: loop-invariant conditions, predicates referencing one side of a join, etc.