Lil' Fun Langs
I adore small programming languages. Iota is two combinators. tinylisp is 99 lines of C. milliForth is 340 bytes. Fractran multiplies fractions. Oh, K?
I've encountered tiny implementations of Forth, Lisp, C, Prolog, etc., but never "milliHaskell".
ML-style languages carry a pungent monad odor that attracts mathochists. Notable examples include Haskell, Elm, F#, Scala, and OCaml. They're "Lambda Calculus with syntactic sugar", i.e. functional and statically-typed. Most implementations extend Hindley-Milner type inference with algebraic data types, pattern matching, and closures:
Feature LOC Dependencies References Integer arithmetic ~50 Parser, codegen MinCaml Floating-point ~100 Parser, codegen (SSE/NEON) MinCaml Booleans + if/then/else ~50 Parser, codegen Everything Let bindings ~30 Parser, normalization Everything First-class functions (closures) ~200 Closure conversion, runtime MinCaml Recursive functions (let rec) ~50 Type inference (occurs check), codegen MinCaml Tuples ~100 Parser, type inference, codegen MinCaml Arrays ~100 Parser, runtime (bounds checking) MinCaml Monomorphic type inference ~100 Unification MinCaml Polymorphic type inference (HM) ~300 Generalization, instantiation Algorithm W, PLZoo Algebraic data types ~200–400 Parser, type checker, runtime (tagging) HaMLet, Tao Pattern matching (basic) ~200 Exhaustiveness check, case trees Tao, Ante Pattern matching (optimized) ~400–600 Maranget's algorithm OCaml, Rust Type classes ~500–2000 Dictionary passing, instance resolution MicroHs, Ben Lynn Modules (basic) ~500–1000 Namespace management HaMLet Modules (functors/signatures) ~2000–5000 Type-level computation HaMLet, 1ML Row polymorphism ~300–800 Extended unification EYG, type-systems Algebraic effects ~500–1500 Effect typing, runtime support Eff, Frank, Ante Algebraic subtyping ~500 Polar types, biunification Simple-sub Linear types ~600 Linearity checker Austral Lazy evaluation ~300–500 Thunks, memoization runtime MicroHs, Ben Lynn Garbage collection (Cheney) ~200 Runtime system Most Tail call optimization ~50–100 Codegen (jump instead of call) MinCaml Inline expansion ~100 Normalization pass MinCaml Dead code elimination ~50 Free variable analysis MinCaml Totality checking ~300–500 Coverage analysis, termination checker Tao, Dhall
Further reading:
If you want a milliHaskell, all your inspiration/ingredients are right here.
Hirrolot's CoC
🤖 The most extreme capability-to-size ratio in this list — a complete Calculus of Constructions (the type theory at the top of the lambda cube) with bidirectional typing, dependent function types, and a type-in-type universe, all in a single OCaml gist of ~60–80 lines. It can express length-indexed vectors and other dependently typed programs. Not ML-family per se, but it demonstrates that full dependent types need not be complex to implement.
Harrop MiniML
... continue reading