Chesskell: A Two-Player Game at the Type Level
summary
A full type-level Haskell model of FIDE 2018 chess is implemented as a composition of first-class families and a continuation-passing-style EDSL where a central type family move transforms board states; it compiles but stresses GHC: an 8-move test with naive move-list check costs 1m37s and 23 GB, removing that check drops to 24s and 8 GB. Algorithmic fixes (ray-based check, finger trees) sometimes cut memory and time (one case: 30.4 GB and 110s → ~half memory and one‑fifth time) but results are unpredictable; adding move numbers to type errors spikes to ~26 GB.
AI-written summary · about
chapters (10)
- 0:00Start
- 8:37Start Continuation
- 10:59Algorithmic Improvements
- 15:04Memory Usage
- 15:47Descriptive Error Messages
- 16:13Board Decorator
- 16:27Custom Type Errors
- 20:21Avoiding the Move List Approach
- 24:20Conclusion
- 26:12Jeremy Gibbons
related talks
49mMaking sense of the Haskell type system
01h 38mGHC Core Optimisations
01h 07mHaskell The Legend of DSLs
01h 35mSecrets of the GHC Typechecker in 100 Type Declarations
59mKeynote: Dependently-Typed Haskell
01h 28mInto the Core Squeezing Haskell into nine Constructors
01h 04mHaskell - A Peek Inside the Ivory Tower
55mBeauty and the Beast: Haskell for JVM