Lambdas in Forth ════════════════ 🚀 FORTH DAY 🚀 November 18, 2023 Lambda Expressions ══════════════════ • Practical variant on lambda calculus • Represent an abstract function • Ideally a "closure" on its environment Lambda Calculus ═══════════════ • Invented by Alonzo Church (1930) • Complete model of computation x - a variable (λx. M) - a lambda abstraction (M N) - an application Lisp ════ • Lambda calculus inspired Lisp (lambda (x) (* x x )) Python: lambda x: x * x Java: (x) -> x * x C++: [](int x) { return x * x ; } Rust: |x| -> x * x Forth: ? Closure ═══════ • Ideally lambdas capture their environment • Historically dynamically, now lexically • Important to make lambdas most useful (define (adder n) (lambda (x) (+ x n))) ((adder 3) 4) --> 7 How to do this in Forth? ════════════════════════ • Expand the behavior of locals • Add a syntax for starting a closure • Sort out the memory management implications : squarer [: { x } x x * :] ; 4 squarer invoke --> 16 : adder { n } [: { x } x n + :] ; 3 adder constant x 4 x invoke --> 7 Locals ══════ • Standardized, but implementation specific innards • µEforth and others use the return stack - but other approaches possible • Issue: local scopes go away on word return • Consequence: locals need to move elsewhere Where to put the locals? ════════════════════════ • Can live long after return • Might hold address of lambdas • Need to know when to free them What do others do? ══════════════════ • Lisp - Garbage Collector • Python - Garbage Collector • Java - Garbage Collector + optimizer • C++ - Stack/Heap + careful lifetimes • Rust - Stack/Heap + careful lifetimes Garbage Collection ══════════════════ • Free data only when it can't be reached Three types: • Moving / copy collectors (Cheney) • Stationary / Mark and Sweep collectors • Hybrid collectors Trade-offs ══════════ • Careful lifetimes - Requires compile-time types • Garbage Collector - Requires runtime types • Conservative Collector - Might live leak ✅🤷 Conservative Collection ═══════════════════════ • Boehm GC - 1988 • Treat any value that might be a pointer to a GC-ed object as if it is • Requires static allocation schemes • Allows C garbage collector Interface ═════════ pair ( a d -- c ) unpair ( c -- a d ) collect ( -- ) pair? ( c -- f ) Locals in an Environment ════════════════════════ • Instead of allocating stack offset, allocate IDs • Create an environment as a chain of pairs of (ID, value) 0 value environment : init-local! ( id -- ) pair environment swap pair to environment ; : get-local ( id -- n ) >r environment begin dup while unpair unpair r@ = if nip rdrop exit then drop repeat rdrop ( zero on stack ) ; Implementing [: :] ══════════════════ • [: - save scope, jump over code • :] - exit, land from jump, bind code + environment : adder { n } [: { x } x n + :] ; ((n-val . n-id) . xt) Filling it Out ══════════════ • Make TO work, setting the environment • Make RECURSE work, saving the environment (define (factorial n) (define (fact! n) (if (= n 0) 1 (* (factorial (- n 1)) n))) (fact! n)) : factorial { n } 0 { fact! } [: { n } n 0= if 1 else n 1- fact! invoke n * then :] to fact! n fact! invoke ; (define (factorial2 n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) : factorial2 { n } 0 { iter } [: { product counter } counter n > if product else counter product * counter 1+ iter invoke then :] to iter 1 1 iter invoke ; : cons { a d } [: if d else a then :] ; : car ( c ) 0 swap invoke ; : cdr ( c ) 1 swap invoke ; : gcd2 { a b } b 0= if a else b a b mod recurse then ; : make-rat { n d } n d gcd2 { g } n g / d g / cons ; : numer ( r ) car ; : denom ( r ) cdr ; : print-rat { x } x numer . ." / " x denom . ; : add-rat { x y } x numer y denom * y numer x denom * + x denom y denom * make-rat ; : sub-rat { x y } x numer y denom * y numer x denom * - x denom y denom * make-rat ; : mul-rat { x y } x numer y numer * x denom y denom * make-rat ; : div-rat { x y } x numer y denom * x denom y numer * make-rat ; : equal-rat? { x y } x numer y denom * y numer x denom * = ; DEMO QUESTIONS❓ 🙏 Thank you!