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

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

\ 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)

! 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)

# 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

! 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

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

# 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