Recursion schemes in OCaml: An experience report
summary
A compiler for a Bloomberg DSL for bilateral financial contracts uses recursion schemes in OCaml to factor traversal code and add optimizations. Claims: recursion schemes in OCaml let programmers integrate hash-consing and memoization with only a few small changes (weak hash set reused, wrapper storing hash and tag), runtime performance is satisfactory, and developers accept the abstractions. Limits: operators are not data type generic and memoization breaks for higher‑order carrier types so custom variants are needed.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:23Bloomberg project context
- 1:49Motivation for recursion schemes
- 3:16Expression types limits
- 4:20Open recursive types and expr_node
- 5:03Category theory basics
- 6:07Catamorphisms and traversals
- 7:12Deriving catamorphism operator
- 8:14Variable substitution example
- 8:55Collecting free variables
- 9:37Hash consing optimization
- 11:21Hash consing implementation
- 12:05Memoization trade-offs
- 12:48Benefits of recursion schemes
- 13:52Challenges and limitations
- 15:21Q&A
related talks
40mRetrofitting Concurrency – Lessons from the Engine Room
18mMelocoton: A Program Logic for Verified Interoperability Between OCaml and C
17mCrane Lowers Rocq Safely into C++
01h 02mMelocoton: A Program Logic for Verified Interoperability Between OCaml and C (I...
18mSemantic-Type-Guided Bug Finding
23mSpecifying and Verifying Future Conditions
45mFunctional programming vs. Object-oriented Programming
32mFrameworks: No, Libraries: Yes. Developing a product in OCaml from Scratch