FP²: Fully in-Place Functional Programming
summary
Formal system proves a large class of pure functions can run with no allocation or deallocation and constant stack space when their arguments are unique, and it gives a syntactic check to certify that property via the FIP calculus. The ideas are implemented in Koka and dynamically applied using Perceus reference counting, with worked examples (splay/finger trees, merge/quick sort, a generic map for any polynomial type). Benchmarks show reuse often wins but one map case is slower due to zipper overhead while guaranteeing bounded stack.
AI-written summary · about
chapters (14)
- 0:00Introduction to fully in-place functional programming
- 2:06FP vs in-place mutation
- 6:17Splay trees in FP²
- 13:42Merge sort in FP²
- 16:30Non-unique arguments in FP
- 19:17Benchmarking FIP vs traditional
- 21:23FP² in Coka
- 21:45Q&A: Ownership annotations
- 23:11Q&A: FIP fragility
- 24:57Q&A: Linux RCU in FIP
- 25:39Q&A: FIP in parallel systems
- 26:22Q&A: Memory fragmentation in FIP
- 28:12Q&A: Reuse policy in FIP
- 29:16Q&A: Error messages for non-FIP
related talks
36mConcrete Functional Programming
42mFunctional Programming in 40 Minutes
33mEXPLAIN FP LIKE RICHARD FEYNMAN
26mFusing Session-Typed Concurrent Programming into Functional Programming
32mFunctional Programming in 40 Minutes
41mFunctional Programming for Pragmatists
49mFunctional Programming Essentials
44mFunctional Programming You Already Know