Concatenative programming and stack-based languages
summary
Shows a concrete claim and demonstrations: a formal semantics for a tiny stack language, reductions from C → Lambda → SK → stack code proving Turing completeness, and a surprising minimal basis built from cake and K as a two‑primitive basis. Shows compilation to x86 fragments that compose associatively (enabling parallel compilation), uses Lambda8cc, SK translations and the Uxn VM running on a laptop and a Pi badge to run real programs.
AI-written summary · about
chapters (7)
- 0:00Stack-based languages intro
- 2:12Name-based vs stack-based
- 5:41Pythagorean theorem stack
- 13:05Stack programs meaning
- 21:58Stack languages Turing complete
- 32:08Associativity and parallelism
- 36:46Uxn stack example
related talks
41mConcatenative programming and stack-based languages
35mStrongly-Typed Multi-View Stack-Based Computations
01h 05mMuch Still to Do in Compiler Verification (A Perspective from the CakeML Project)
40mAn Introduction to Combinator Compilers and Graph Reduction Machines
18mSuperStack: Superoptimization of Stack-Bytecode via Greedy, Constraint-Based, and SAT(…)
30mCalculating Compilers for Concurrency
16mCompiling Symbolic Execution with Staging and Algebraic Effects
20mStacKAT: Infinite State Network Verification