--- name: concatenative description: "Forth/Factor/Joy: stack-based concatenative programming where composition replaces application." version: 1.0.0 --- # Concatenative Programming Skill > *"Programs are composed by concatenation. The stack is the only state."* ## Core Concept In concatenative languages: 1. **Stack** is the implicit data structure 2. **Words** (functions) transform the stack 3. **Composition = Concatenation** — `f g` means "do f, then g" 4. **No variables** (mostly) — data flows through stack ```forth 3 4 + \ Push 3, push 4, add → 7 on stack dup * \ Duplicate top, multiply → 49 ``` ## Why It's Strange 1. **No application** — `f(x)` becomes `x f` 2. **No variables** — use stack manipulation 3. **Point-free by default** — everything is tacit 4. **Quotations** — code as data `[ ... ]` 5. **Extreme composability** — every word combines freely ## Forth Basics ```forth \ Comments start with backslash 3 4 + \ → 7 10 3 / \ → 3 (integer division) 1 2 3 + * \ 1 * (2 + 3) = 5 \ Stack manipulation DUP \ a → a a DROP \ a b → a SWAP \ a b → b a OVER \ a b → a b a ROT \ a b c → b c a \ Defining words : SQUARE DUP * ; 5 SQUARE \ → 25 : CUBE DUP DUP * * ; 3 CUBE \ → 27 ``` ## Factor (Modern Forth) ```factor ! Stack effect declarations : square ( n -- n^2 ) dup * ; : cube ( n -- n^3 ) dup dup * * ; ! Quotations (anonymous functions) { 1 2 3 } [ 2 * ] map ! → { 2 4 6 } { 1 2 3 4 } [ even? ] filter ! → { 2 4 } ! Cleave combinator (apply multiple quotations) 5 [ 1 + ] [ 2 * ] bi ! → 6 10 ! Spread combinator 1 2 [ 1 + ] [ 2 * ] bi* ! → 2 4 ``` ## Joy (Functional Concatenative) ```joy # No mutable state, pure functional # Quotations are first-class [dup *] square define 5 square # → 25 # Combinators [1 2 3] [2 *] map # → [2 4 6] [1 2 3 4 5] 0 [+] fold # → 15 # Recursion via Y combinator [dup 0 = [pop 1] [dup 1 - factorial *] ifte] factorial define 5 factorial # → 120 ``` ## Stack Effect Notation ``` ( before -- after ) dup ( a -- a a ) drop ( a -- ) swap ( a b -- b a ) over ( a b -- a b a ) rot ( a b c -- b c a ) + ( a b -- a+b ) ``` ## Quotations and Combinators | Combinator | Stack Effect | Meaning | |------------|--------------|---------| | `call` | `( quot -- ... )` | Execute quotation | | `dip` | `( x quot -- ... x )` | Run quot, restore x | | `keep` | `( x quot -- ... x )` | Run quot, keep x | | `bi` | `( x p q -- ... )` | `p(x) q(x)` | | `tri` | `( x p q r -- ... )` | `p(x) q(x) r(x)` | | `cleave` | `( x [p q ...] -- ... )` | Apply all to x | ## Point-Free Style ```factor ! Instead of: : sum-of-squares-bad ( seq -- n ) 0 swap [ sq + ] each ; ! Point-free: : sum-of-squares ( seq -- n ) [ sq ] map sum ; ! Even more point-free: : sum-of-squares ( seq -- n ) [ sq ] [ + ] map-reduce ; ``` ## Implementation ```python class ConcatVM: def __init__(self): self.stack = [] self.words = { '+': self.add, '*': self.mul, 'dup': self.dup, 'drop': self.drop, 'swap': self.swap, } def push(self, val): self.stack.append(val) def pop(self): return self.stack.pop() def add(self): b, a = self.pop(), self.pop() self.push(a + b) def mul(self): b, a = self.pop(), self.pop() self.push(a * b) def dup(self): self.push(self.stack[-1]) def drop(self): self.pop() def swap(self): self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1] def define(self, name, body): """Define new word as sequence of words.""" def new_word(): for word in body: self.run(word) self.words[name] = new_word def run(self, program): if isinstance(program, (int, float)): self.push(program) elif program in self.words: self.words[program]() else: raise ValueError(f"Unknown: {program}") # Usage vm = ConcatVM() vm.define('square', ['dup', '*']) for token in [5, 'square']: vm.run(token) print(vm.stack) # [25] ``` ## GF(3) Integration ```python # Trit stack with GF(3) operations class TritStack: def __init__(self): self.stack = [] # Stack of trits: -1, 0, +1 def push(self, trit): assert trit in (-1, 0, 1) self.stack.append(trit) def gf3_add(self): """( a b -- (a+b) mod 3 )""" b, a = self.stack.pop(), self.stack.pop() result = (a + b) % 3 result = result if result != 2 else -1 self.stack.append(result) def trit_sum(self): """Conservation check.""" return sum(self.stack) % 3 ``` ## Categorical Semantics Concatenative languages are **Cartesian closed categories** where: - Objects = stack types - Morphisms = stack transformations - Composition = concatenation - Identity = empty program ``` f : A → B g : B → C g ∘ f = "f g" : A → C ``` ## Languages | Language | Era | Features | |----------|-----|----------| | **Forth** | 1970 | Original, minimal | | **PostScript** | 1982 | Graphics, stacks | | **Joy** | 2001 | Pure functional | | **Factor** | 2003 | Modern, typed | | **Cat** | 2006 | Statically typed | | **Kitten** | 2016 | Effect system | ## When to Use - **Embedded systems** — Forth is tiny - **DSLs** — Easy to extend - **Calculators** — RPN style - **Compilers** — Stack machines as target ## Literature 1. **Moore (1970)** - Forth invention 2. **von Thun (2001)** - "Joy: Forth's Functional Cousin" 3. **Pestov (2010)** - Factor language 4. **Diggins (2008)** - "Cat: A Typed Concatenative Language" ## Related Skills - `stack-machines` - Implementation target - `tacit-programming` - Point-free style - `rank-polymorphism` - Also combinator-based - `postfix-notation` - RPN ## Scientific Skill Interleaving This skill connects to the K-Dense-AI/claude-scientific-skills ecosystem: ### Graph Theory - **networkx** [○] via bicomodule - Universal graph hub ### Bibliography References - `category-theory`: 139 citations in bib.duckdb ## SDF Interleaving This skill connects to **Software Design for Flexibility** (Hanson & Sussman, 2021): ### Primary Chapter: 2. Domain-Specific Languages **Concepts**: DSL, wrapper, pattern-directed, embedding ### GF(3) Balanced Triad ``` concatenative (+) + SDF.Ch2 (−) + [balancer] (○) = 0 ``` **Skill Trit**: 1 (PLUS - generation) ### Secondary Chapters - Ch1: Flexibility through Abstraction - Ch9: Generic Procedures ### Connection Pattern DSLs embed domain knowledge. This skill defines domain-specific operations. ## Cat# Integration This skill maps to **Cat# = Comod(P)** as a bicomodule in the equipment structure: ``` Trit: 0 (ERGODIC) Home: Prof Poly Op: ⊗ Kan Role: Adj Color: #26D826 ``` ### GF(3) Naturality The skill participates in triads satisfying: ``` (-1) + (0) + (+1) ≡ 0 (mod 3) ``` This ensures compositional coherence in the Cat# equipment structure.