# Forth Language Review and Stack Based Tree Sort, for numbers and Strings # Forth Tree-Sort: A Combined Laboratory Report ### Language, Build Pipeline, and Stack-Machine Architecture of a Binary-Tree Sort **Author:** Paul Richeson **Platform:** Raspberry Pi (Linux 6.18, aarch64) · pforth 2.2.0 (version code 34) **Date:** 2026-06-01 **License:** MIT — see [`LICENSE`](../LICENSE). Copyright (c) 2026 Paul Richeson. --- ## Combined Abstract This combined report studies a binary search-tree (BST) sort implemented in Forth on the *pforth* engine, from three complementary angles. **Part I** introduces the Forth language itself — its two-stack execution model, postfix syntax, dictionary of words, and interactive compilation — and verifies the model with small programs. **Part II** documents how the application is turned into a runnable binary: in Forth, "compiling" means loading source into a live interpreter and snapshotting the dictionary to an image (`treesort.dic`) with `save-forth`, a process orchestrated by GNU Make. **Part III** analyses the architecture of the tree-sort from a computer-engineering standpoint: a single index-addressed node arena, iterative insertion carried on the data stack, recursive in-order traversal carried on the return stack, yielding a stable, swap-free, exactly-N-allocated sort with average O(N log N) comparisons. A character-sorting sibling (`treesortstring.fth`) demonstrates that the mechanism is independent of element representation. *Index Terms* — Forth, stack machine, postfix notation, dictionary image, `save-forth`, GNU Make, binary search tree, tree sort, data stack, return stack, in-order traversal, stability, pforth. --- ## Table of Contents - [Part I — An Introduction to the Forth Programming Language](#part-i--an-introduction-to-the-forth-programming-language) - [Part II — Building the `treesort` Binary: The Make Process](#part-ii--building-the-treesort-binary-the-make-process) - [Part III — Architecture of a Binary-Tree Sort on a Stack Machine](#part-iii--architecture-of-a-binary-tree-sort-on-a-stack-machine) - [Consolidated References](#consolidated-references) --- ## Part I — An Introduction to the Forth Programming Language ### Abstract This report introduces Forth, a stack-oriented, extensible, interactively compiled programming language, and demonstrates its core mechanics on the *pforth* engine running under Linux on a Raspberry Pi. We describe the two-stack execution model, postfix (Reverse Polish) syntax, the dictionary of *words*, and the read–evaluate loop that lets a programmer extend the language itself. Worked examples (`hello.fth`, `demo.fth`) confirm the expected behaviour of arithmetic, user-defined words, and counted loops. We conclude that Forth's minimal, self-hosted design makes it a useful pedagogical and embedded-systems tool that exposes the machine-level notion of a stack directly to the programmer. *Index Terms* — Forth, stack machine, postfix notation, threaded code, interpreter, embedded systems, pforth. --- ### I. Introduction Most mainstream languages hide the evaluation stack behind an expression parser. Forth, designed by Charles Moore in the late 1960s, does the opposite: the *data stack* is the central, visible object of computation, and the program is written in the order the stack is manipulated. This makes Forth unusually small (a complete system fits in a few kilobytes) and unusually transparent — there is almost no distance between the source text and the operations the processor performs. Forth is consequently popular in firmware, bootloaders (Open Firmware), and resource-constrained embedded systems. The objective of this lab is to (1) state Forth's execution model, (2) explain its syntax and extensibility, and (3) verify both with small programs on the pforth engine. ### II. Background and Theory ### A. The two stacks A Forth system maintains two LIFO stacks: * the **data stack** (or *parameter stack*), which holds operands and results; * the **return stack**, which holds return addresses for nested word calls and loop indices. All arithmetic and logic consume their operands from the data stack and push their results back onto it. This is the same discipline a compiler's code generator uses internally, exposed here as the programming model itself. ### B. Postfix (Reverse Polish) notation Because operands must already be on the stack before an operator runs, Forth is written postfix: ``` 3 4 + \ push 3, push 4, add -> 7 on the stack ``` There is no operator precedence and there are no parentheses; evaluation order is simply left-to-right. The phrase `3 4 + .` pushes 3 and 4, replaces them with their sum, then `.` prints and pops the top of the stack. ### C. Words and the dictionary Every token in Forth is a **word**. A word is an entry in the **dictionary**, a linked list of named, executable definitions. Built-in words such as `+`, `dup`, `.`, and `cr` are present at start-up; the programmer adds new words with the *colon definition*: ```forth : square ( n -- n^2 ) dup * ; ``` `:` begins a definition, `square` names it, the body `dup *` duplicates the top of stack and multiplies, and `;` ends the definition. The comment `( n -- n^2 )` is a **stack effect diagram**: inputs left of `--`, outputs right. New words are indistinguishable from built-ins and may be used to build further words — Forth programs are deep towers of tiny definitions. ### D. Interactive compilation pforth runs a read–evaluate loop (the *outer interpreter*). In *interpret* state it executes each word as it is read; on encountering `:` it switches to *compile* state and appends the following words to a new dictionary entry until `;`. The same text stream therefore both defines and runs code, which is why Forth is described as *interactively compiled* rather than purely interpreted or purely compiled. ### III. Materials and Method * **Hardware:** Raspberry Pi, Linux 6.18 (aarch64). * **Engine:** `pforth_standalone`, a portable ANS-style Forth written in C (pforth 2.2.0). It is driven through the convenience wrapper `./forth`, which simply executes the engine with the `-q` (quiet) flag. * **Programs under test:** * `hello.fth` — minimal output program. * `demo.fth` — a tour of arithmetic, colon definitions, composition, and a counted loop. Each file was executed with `./forth `. ### IV. Procedure and Observations ### A. Program 1 — `hello.fth` ```forth ." Hello, world!" cr bye ``` `."` compiles a string literal that is printed when reached; `cr` emits a newline; `bye` exits the interpreter. **Observed output:** `Hello, world!` followed by a newline, then a clean exit. ### B. Program 2 — `demo.fth` Key fragments and their behaviour: | Source | Stack action | Output | |---|---|---| | `3 4 + .` | push 3, push 4, add, print | `7` | | `: square ( n -- n^2 ) dup * ;` then `9 square .` | define, then 9·9 | `81` | | `: average ( a b -- avg ) + 2 / ;` then `10 20 average .` | (10+20)/2 | `15` | | `5 0 do i . loop` | counted loop, index `i` | `0 1 2 3 4` | The `do … loop` construct uses the return stack to hold its limit and index; `i` copies the current index to the data stack. All results matched the predicted values, confirming the stack model. ### C. Discussion Two observations are worth emphasising from an engineering standpoint: 1. **Composition without syntax.** `average` is built from `+` and `/` with no declaration overhead — the cost of an abstraction in Forth is one dictionary entry, not a function-call frame as in conventional ABIs. This is why Forth scales *down* so well onto small processors. 2. **The stack is the contract.** The stack-effect comment is not enforced by a type system; correctness depends on each word leaving the stack as advertised. This places discipline on the programmer but removes an entire layer of machinery (parser tables, type checker, register allocator) from the system. ### V. Conclusion Forth's identity is its visible two-stack machine, postfix evaluation, and a dictionary of composable words extended through interactive compilation. The test programs behaved exactly as the model predicts. Because the language is self-hosted and minimal, it doubles as a clear teaching model of how a stack machine evaluates expressions — the same foundation reused in the companion labs on building (Lab 2) and on the binary-tree sort (Lab 3). --- ## Part II — Building the `treesort` Binary: The Make Process ### Abstract This report documents how the `treesort` program is turned from Forth source into a runnable binary on the pforth engine. Unlike a C tool-chain, "compiling" in Forth means loading source into a live interpreter and then *snapshotting the resulting dictionary* to disk as a saved image (`treesort.dic`). We analyse the project `Makefile`, the dependency graph it encodes, the role of the C-compiled engine `pforth_standalone`, and the shell launcher that assembles a one-shot Forth driver at run time. We verify that `make` produces a 122,776-byte dictionary image and that `./treesort 5 3 8 1 5 9` runs against it. The exercise illustrates the *image-based* execution model that distinguishes Forth (and Smalltalk/Lisp) from conventional ahead-of-time compilation. *Index Terms* — build system, GNU Make, Forth dictionary image, `save-forth`, incremental dependencies, embedded tool-chain. --- ### I. Introduction A "binary" in a C project is machine code emitted by a compiler and linked against libraries. In a Forth project there are *two* artefacts: 1. the **engine** — `pforth_standalone`, native ARM machine code produced once from the pforth C sources; and 2. the **dictionary image** — `treesort.dic`, a saved snapshot of the Forth interpreter's memory *after* our source has been loaded into it. The application is the image; the engine is the virtual machine that loads and runs it. This lab traces how the project `Makefile` orchestrates both, and how a thin shell script presents the result as an ordinary command-line tool. ### II. Materials * **Build tool:** GNU `make`. * **Forth wrapper:** `./forth` → `pforth/platforms/unix/pforth_standalone -q`. * **Sources / artefacts:** * `treesort.fth` — application source (the tree-sort words). * `pforth_standalone` — the native engine (423,928 bytes). * `treesort.dic` — the saved dictionary image (122,776 bytes). * `treesort` — shell launcher that feeds command-line numbers to the image. ### III. The Dependency Graph The `Makefile` declares the following targets and prerequisites: ``` all ──► treesort.dic treesort.dic : treesort.fth pforth_standalone (rebuild image) pforth_standalone : (build engine from C) run : treesort.dic (build, then demo) clean / distclean (remove artefacts) ``` The arrows are Make's notion of *staleness*: `treesort.dic` is rebuilt whenever either the application source `treesort.fth` **or** the engine binary changes, because both are listed as prerequisites on line 27. This guarantees the image always reflects the current source and is never linked against a stale engine. ### IV. How the Binary Is Created ### A. Building the engine (one-time) If `pforth_standalone` is missing, the rule ```make $(ENGINE): $(MAKE) -C pforth/platforms/unix pforth_standalone ``` recurses into the pforth platform directory and performs a *conventional* C build (the `.o`/`.eo` object files visible there are its intermediate output). This is the only step that produces native ARM machine code. On this system the engine was already present (423,928 bytes), so this rule was satisfied. ### B. Compiling the application into a dictionary image The central rule is: ```make $(DIC): $(SRC) $(ENGINE) @printf 'include $(SRC)\nc" $(DIC)" save-forth\nbye\n' | $(FORTH) >/dev/null ``` Three Forth commands are piped into the engine on standard input: 1. **`include treesort.fth`** — the outer interpreter reads the source and *compiles every colon definition into the live dictionary* (`init`, `feed`, `inorder`, `report`, etc.). After this line, the running image "knows" the tree-sort vocabulary. 2. **`c" treesort.dic" save-forth`** — `c"` pushes the counted-string filename; `save-forth` serialises the **entire current dictionary** (built-ins + our new words) to that file. *This is the act of "creating the binary."* No code generation or linking occurs; memory is written verbatim to disk. 3. **`bye`** — exit the engine. The result, `treesort.dic`, is a self-contained image that, when loaded by the engine, restores the interpreter to exactly the state it had immediately after `include` — with all of our words defined and ready to call. ### C. Verification ``` $ make Compiling treesort.fth -> treesort.dic ... Built treesort.dic $ ls -l treesort.dic # 122776 bytes ``` The image is ~123 KB, larger than the 3.4 KB source because it contains the full base dictionary plus our additions — the snapshot is of the *whole interpreter*, not just our file. ### V. Running the Binary The application is presented to the user by the `treesort` shell script, which performs three jobs: 1. **Validate input** — prints usage and exits if no numbers are supplied. 2. **Synthesise a driver** — writes a temporary `.fth` file (auto-deleted via a `trap … EXIT`) containing: ``` init \ size the tree to N nodes feed feed … \ insert each command-line number report \ draw the tree and print the sorted output bye ``` where `N = $#` is the argument count. 3. **Execute against the image** — runs `pforth_standalone -q -d treesort.dic `; the `-d` flag tells the engine to **load our saved dictionary** instead of the default. A `grep` filter suppresses pforth's harmless include/level banner so only the program output is shown. Thus `./treesort 5 3 8 1 5 9` boots the saved image, runs the generated driver, and prints the narrated tree and sorted result. (An alternate launcher, `treesortold`, skips the saved image and `include`s the source at run time instead — slower to start, but needing no `make` step.) ### VI. Discussion From a computer-engineering standpoint this build pipeline is an example of **image-based deployment**: program state, not just program text, is the shippable artefact. Advantages observed: * **Fast start-up** — the application is already compiled inside the image, so no parsing happens at launch; the `-d` load is essentially an `mmap`-and-go. * **Reproducibility** — the same source + engine always yields an equivalent image, and Make's prerequisite list enforces that invariant. * **Separation of concerns** — the native engine (portable C, built rarely) is cleanly decoupled from the application image (built on every source edit). A limitation is portability of the image: a `.dic` is tied to the engine's word layout and host word size, so it is not interchangeable across architectures — the source and a matching engine are the true portable units. ### VII. Conclusion "Compiling" the Forth tree-sort means loading `treesort.fth` into the pforth interpreter and saving the resulting dictionary with `save-forth`, producing the 122,776-byte `treesort.dic` image. GNU Make sequences the optional engine build and the image build via an explicit dependency graph, and a shell launcher turns the image into a normal CLI tool by generating a per-invocation Forth driver. The process cleanly demonstrates Forth's image-based execution model. --- ## Part III — Architecture of a Binary-Tree Sort on a Stack Machine ### Abstract This report analyses, from a computer-engineering perspective, the architecture of a binary search-tree (BST) sort implemented in Forth (`treesort.fth`) and its character-sorting sibling (`treesortstring.fth`). We examine the in-memory data structure (a single contiguous arena of fixed-width nodes addressed by integer indices), the mapping of tree operations onto Forth's data and return stacks, and the cost of each primitive in terms of stack traffic and memory accesses. We show that the algorithm performs **zero element swaps**, is **stable**, and allocates **exactly N nodes** with no resizing, and we relate these properties to the underlying stack-machine execution model. Empirical runs confirm O(N log N) average comparison counts (e.g. 9 comparisons for the 6-element input `sortme`) and worst-case O(N²) on sorted input. The study illustrates how a pointer-based algorithm is expressed on a machine whose only addressable working storage is two LIFO stacks plus a heap allocated explicitly by the program. *Index Terms* — binary search tree, tree sort, stack machine, data stack, return stack, recursion, in-order traversal, stability, memory arena, pforth. --- ### I. Introduction Sorting on a stack machine raises an architectural question: the natural working store is a LIFO stack, yet a tree is a pointer structure with arbitrary, non-LIFO access. This lab dissects how `treesort.fth` resolves that tension. The algorithm builds a binary search tree by *insertion* and then performs an *in-order traversal* to emit a sorted sequence. We treat the implementation as a small machine architecture: a memory subsystem (the node arena), an addressing scheme (integer indices), a control unit (the colon-defined words), and a working-register set (the two Forth stacks). ### II. Data Structure and Memory Architecture ### A. The node arena All nodes live in **one contiguous block** obtained from the Forth heap with `ALLOCATE`, sized once for exactly *N* inputs: ```forth : init ( n -- ) 3 * cells allocate ... base ! 0 #nodes ! -1 root ! 0 #cmp ! ; ``` Each node is **three cells wide**: ``` index i → [ value | left-child-index | right-child-index ] +0 +1 +2 (cells) ``` A child field holding **-1** denotes *nil* (no child). The root index is held in the variable `root` (also -1 when the tree is empty), and `#nodes` is both the count of nodes used and the **next free index** — allocation is a simple bump of this counter. ### B. Index-based addressing Children are referenced by **small integer indices**, not full machine addresses. The accessor words convert an index to the address of a field: ```forth : n>val ( i -- a ) 3 * cells base @ + ; : n>left ( i -- a ) 3 * 1+ cells base @ + ; : n>right ( i -- a ) 3 * 2 + cells base @ + ; ``` Architecturally this is **base-plus-scaled-index addressing**: `address = base + (3·i + field)·cellsize`. Two engineering benefits follow: 1. **Compactness** — an index is typically smaller than a pointer and is independent of where the arena was mapped, which matters on memory-constrained embedded targets. 2. **Locality** — because all nodes share one block, traversal touches a dense region of memory, friendly to the data cache, rather than chasing heap-scattered pointers. ### C. Allocation policy `new-node` writes the value, sets both child links to -1, and bump-allocates: ```forth : new-node ( val -- i ) #nodes @ -1 over n>left ! -1 over n>right ! 2dup n>val ! nip 1 #nodes +! ; ``` There is **no free list and no resizing**: the arena is sized once to N, and exactly N nodes are consumed. Memory use is therefore deterministic and known before the first insert — a desirable property for real-time/embedded use. ### III. Mapping the Algorithm onto the Stack Machine ### A. Insertion (`feed`) — iterative, stack-resident state `feed ( val -- )` inserts one key. Its control state — the value being inserted and the "current node" walking pointer (`cur`) — lives on the **data stack** and in a variable, not on a call stack: * If `root = -1`, the value becomes the root (one `new-node`, store to `root`). * Otherwise a `begin … again` loop walks down the tree: * each iteration increments `#cmp` (a comparison counter) and compares the key with `cur`'s value; * `key < node` → go **LEFT**; otherwise go **RIGHT**. Equal keys go right, which is what makes the sort **stable** (an earlier-inserted equal key is encountered first by the in-order walk and therefore emitted first); * when the chosen child link is -1, a new node is attached there and the loop exits via `drop exit`. Because insertion is written as an explicit loop, it uses **bounded stack depth** regardless of tree height — only a few cells of data-stack scratch are live at a time. This is the architecturally interesting choice: descent is expressed as *data-stack manipulation*, not recursion. ### B. Traversal (`inorder`, `show-tree`) — recursion via the return stack Emitting the sorted output is naturally recursive (left subtree, self, right subtree). Here the implementation **does** use recursion, and Forth's `recurse` word calls the current definition again: ```forth : inorder ( i -- ) dup -1 = if drop exit then dup n>left @ recurse \ visit left subtree dup n>val @ . \ emit this node (emit/.ch in the string version) n>right @ recurse ; \ visit right subtree ``` Each `recurse` pushes a **return address onto the return stack**; the maximum return-stack depth equals the height *h* of the tree. This is the clearest illustration in the project of the **two-stack architecture at work**: operands and the node index ride the *data stack*, while the *return stack* records the suspended traversal frames. `show-tree` uses the same recursive pattern but visits right-before-left and indents by depth to draw the tree rotated 90°. ### C. Why no swaps Classical comparison sorts (quicksort, heapsort) move array elements. This sort **never moves a value after it is placed** — ordering is encoded entirely in the `left`/`right` link fields written once at insertion. The reported metric "0 swaps" is therefore exact: total writes to value fields = N, and they are all initial writes. ### IV. Cost Analysis (Computer-Engineering View) Let *N* be the input size and *h* the resulting tree height. | Operation | Work | Stack traffic | Memory accesses | |---|---|---|---| | `new-node` | O(1) | a few data-stack ops | 3 writes (value + 2 links) | | one `feed` | O(depth of insert) | bounded data-stack scratch | ~1 value read + 1 link read per level | | full build | Σ depths | — | average O(N log N), worst O(N²) | | `inorder` | O(N) | return-stack depth = h | 1 value read + 2 link reads per node | * **Comparisons** are tracked live in `#cmp`. Measured example: input `sortme` (6 chars) built with **9 comparisons** — consistent with average-case O(N log N). * **Worst case** is *already-sorted input*, which degenerates the BST into a linked list: insertion becomes O(N²) comparisons and the return-stack depth of `inorder` reaches *N*. This is the standard architectural caveat of an unbalanced BST and would, on a deeply nested input, stress the return stack. * **Space** is exactly `3·N` cells of arena plus a handful of variables — allocated once, never grown. ### V. The Character Variant (`treesortstring.fth`) The string sorter is the *same architecture* with one substitution: a node's `value` cell holds a **character code** instead of an integer. Only the I/O boundary changes — values are read with `KEY`-style byte codes supplied by the launcher and printed with `EMIT` / a quoting helper `.ch` rather than the numeric `.`. The tree, the index addressing, the stability rule (equal characters go right), and the stack usage are byte-for-byte identical. This demonstrates a clean **separation between the sorting mechanism and the element's representation**: the data structure is type-agnostic because a Forth cell is just a machine word. Verified: `./treesortstring sortme → emorst` (6 characters, 9 comparisons, 0 swaps, stable). ### VI. Discussion The design choices map directly onto stack-machine strengths and weaknesses: * **Strength — explicit memory.** Forth has no garbage collector; by sizing one arena up front and addressing it by index, the program achieves deterministic, cache-friendly memory behaviour appropriate for embedded targets. * **Strength — minimal working set.** Iterative insertion keeps live data-stack depth tiny; recursion is confined to traversal, where its depth (tree height) is the genuinely required state. * **Weakness — no self-balancing.** Height is input-dependent; adversarial (sorted) input makes both time and return-stack depth linear. A production design would add balancing (AVL/red-black), at the cost of rotation logic and more link writes — trading the "0 swaps / 0 rotations" simplicity for worst-case guarantees. ### VII. Conclusion The Forth tree-sort is a compact, pointer-structured algorithm realised on a two-stack machine: a single index-addressed node arena provides the heap, the **data stack** carries iterative insertion state, and the **return stack** carries recursive-traversal frames. The architecture yields a stable, swap-free, exactly-N-allocated sort with average O(N log N) comparisons (empirically 9 for N=6) and the well-understood O(N²) unbalanced-BST worst case. The string variant shows that the mechanism is independent of element representation. The result is an instructive bridge between abstract data-structure theory and the concrete behaviour of a stack-based processor. --- ## Consolidated References [1] L. Brodie, *Starting Forth*, 2nd ed. FORTH, Inc. [2] L. Brodie, *Thinking Forth*. Punchy Publishing. [3] ANSI X3.215-1994, *Programming Language — Forth*. [4] P. Burk et al., *pforth — a Portable Forth in C*, v2.2.0. [Online]. Available: https://github.com/philburk/pforth [5] R. M. Stallman et al., *GNU Make Manual*. Free Software Foundation. [6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, *Introduction to Algorithms*, 4th ed. MIT Press. [7] D. E. Knuth, *The Art of Computer Programming, Vol. 3: Sorting and Searching*, 2nd ed. Addison-Wesley. [8] P. J. Koopman, *Stack Computers: The New Wave*. Ellis Horwood. --- ## Appendix A — Build System (`Makefile`) The project is built with GNU Make. Note that the pforth engine itself was **compiled from C source** (`make engine`, which invokes the engine's own Makefile under `pforth/platforms/unix/`); the resulting `pforth_standalone` binary is then used to "compile" the Forth source by loading it and saving the dictionary image `treesort.dic`. In Forth, "compiling" means loading source into the interpreter and snapshotting the resulting dictionary as a binary image — that image is the compiled program. ```make # Makefile for the Forth tree-sort. # # "Compiling" in Forth means loading your source into the interpreter and # saving the resulting dictionary as a binary image. That image (treesort.dic) # is the compiled program; you then run it on the pforth engine. # # Targets: # make build treesort.dic (the compiled Forth image) # make run build, then run the demo numbers # make engine (re)build the pforth engine from C source # make clean remove the compiled image # make distclean also clean the pforth engine build # Where things live. (Keep these clean: a trailing comment would leak # whitespace into the value, so comments go on their own lines.) FORTH := ./forth ENGINE := pforth/platforms/unix/pforth_standalone SRC := treesort.fth DIC := treesort.dic DEMO := 5 3 8 1 5 9 # Default: build the compiled image. all: $(DIC) # Compile the Forth source into a saved dictionary image. # Feed three lines to the engine: include the source, save the image, quit. $(DIC): $(SRC) $(ENGINE) @echo "Compiling $(SRC) -> $(DIC) ..." @printf 'include $(SRC)\nc" $(DIC)" save-forth\nbye\n' | $(FORTH) >/dev/null @echo "Built $(DIC)" # Build the pforth engine from its C sources if it is missing. $(ENGINE): @echo "Building pforth engine ..." $(MAKE) -C pforth/platforms/unix pforth_standalone engine: $(ENGINE) # Run the demo. run: $(DIC) ./treesort $(DEMO) # Cleanup. clean: rm -f $(DIC) distclean: clean -$(MAKE) -C pforth/platforms/unix clean .PHONY: all engine run clean distclean ``` > **Note on the toolchain:** pforth was not installed from a package — it was > built from sources shipped in the `pforth/` subtree. The `$(ENGINE)` target > above delegates to pforth's own Unix-platform Makefile to produce the > `pforth_standalone` C binary, which serves as the host interpreter for every > subsequent Forth compile/run step in this report. --- ## Appendix B — Integer Tree-Sort Source (`treesort.fth`) ```forth \ treesort.fth - stable binary-tree sort with a visible, narrated process. \ \ Why tree sort fits the request: \ * 0 swaps - elements are never swapped; they are linked into a tree. \ * stable - equal keys are sent RIGHT, so earlier inputs stay earlier \ in the in-order traversal. \ * RAM-efficient- we ALLOCATE exactly N nodes (3 cells each), no slack, \ no resizing. Pointers are small integer indices, not \ full addresses. \ \ A node lives at index i in one contiguous block, 3 cells wide: \ [ value | left-child-index | right-child-index ] \ A child index of -1 means "no child" (nil). variable base \ address of the node block variable #nodes \ nodes used so far (also the next free index) variable root \ index of the root node, -1 when tree is empty variable cur \ walking pointer used during insertion variable #cmp \ total key comparisons performed \ ---- field accessors: index -> address of that field ------------------ : n>val ( i -- a ) 3 * cells base @ + ; : n>left ( i -- a ) 3 * 1+ cells base @ + ; : n>right ( i -- a ) 3 * 2 + cells base @ + ; \ ---- set up storage for exactly n inputs ------------------------------ : init ( n -- ) 3 * cells allocate ( a-addr ior ) if ." !! ALLOCATE failed" cr then base ! 0 #nodes ! -1 root ! 0 #cmp ! ; \ ---- create a fresh leaf node holding val, return its index ----------- : new-node ( val -- i ) #nodes @ ( val i ) -1 over n>left ! -1 over n>right ! 2dup n>val ! nip 1 #nodes +! ; \ ---- insert one value, narrating every comparison --------------------- : feed ( val -- ) dup ." . add " . ." :" cr root @ -1 = if new-node root ! ." tree was empty -> becomes the root" cr exit then root @ cur ! begin 1 #cmp +! ." compare " dup . ." with node " cur @ n>val @ . dup cur @ n>val @ < if ." -> smaller, go LEFT" cr cur @ n>left @ -1 = if dup new-node cur @ n>left ! ." attached as LEFT child of " cur @ n>val @ . cr drop exit else cur @ n>left @ cur ! then else ." -> not smaller, go RIGHT (equal keys stay stable)" cr cur @ n>right @ -1 = if dup new-node cur @ n>right ! ." attached as RIGHT child of " cur @ n>val @ . cr drop exit else cur @ n>right @ cur ! then then again ; \ ---- draw the tree sideways (rotate 90 deg): root at far left, -------- \ ---- larger values toward the top. Indentation = depth. -------- : show-tree ( i depth -- ) over -1 = if 2drop exit then 2dup swap n>right @ swap 1+ recurse \ right subtree above dup 4 * spaces over n>val @ . cr \ this node over n>left @ over 1+ recurse \ left subtree below 2drop ; \ ---- in-order walk: left, self, right -> ascending, stable ----------- : inorder ( i -- ) dup -1 = if drop exit then dup n>left @ recurse dup n>val @ . n>right @ recurse ; : report cr ." ===== binary tree (rotated 90 deg: root at left, larger on top) =====" cr root @ 0 show-tree cr ." ===== in-order traversal = sorted output =====" cr ." sorted: " root @ inorder cr #nodes @ . ." numbers, " #cmp @ . ." comparisons, 0 swaps, stable" cr ; ``` --- ## Appendix C — String (Character) Tree-Sort Source (`treesortstring.fth`) ```forth \ treesortstring.fth - stable binary-tree sort of the CHARACTERS of a string, \ with a visible, narrated process. This is the sibling of treesort.fth: same \ tree, same algorithm, same guarantees - only the "value" in each node is now \ a character code instead of a number, and it is shown as the character. \ \ Why tree sort fits the request: \ * 0 swaps - characters are never swapped; they are linked into a tree. \ * stable - equal characters are sent RIGHT, so an earlier occurrence \ stays earlier in the in-order traversal. \ * RAM-efficient- we ALLOCATE exactly N nodes (3 cells each), no slack, \ no resizing. Pointers are small integer indices, not \ full addresses. \ \ A node lives at index i in one contiguous block, 3 cells wide: \ [ char-code | left-child-index | right-child-index ] \ A child index of -1 means "no child" (nil). variable base \ address of the node block variable #nodes \ nodes used so far (also the next free index) variable root \ index of the root node, -1 when tree is empty variable cur \ walking pointer used during insertion variable #cmp \ total key comparisons performed \ ---- print a character code as a quoted character, e.g. 'a' ---------- : .ch ( c -- ) [char] ' emit emit [char] ' emit space ; \ ---- field accessors: index -> address of that field ------------------ : n>val ( i -- a ) 3 * cells base @ + ; : n>left ( i -- a ) 3 * 1+ cells base @ + ; : n>right ( i -- a ) 3 * 2 + cells base @ + ; \ ---- set up storage for exactly n inputs ------------------------------ : init ( n -- ) 3 * cells allocate ( a-addr ior ) if ." !! ALLOCATE failed" cr then base ! 0 #nodes ! -1 root ! 0 #cmp ! ; \ ---- create a fresh leaf node holding the char code, return its index -- : new-node ( c -- i ) #nodes @ ( c i ) -1 over n>left ! -1 over n>right ! 2dup n>val ! nip 1 #nodes +! ; \ ---- insert one character, narrating every comparison ----------------- : feed ( c -- ) dup ." . add " dup .ch ." :" cr root @ -1 = if new-node root ! ." tree was empty -> becomes the root" cr exit then root @ cur ! begin 1 #cmp +! ." compare " dup .ch ." with node " cur @ n>val @ .ch dup cur @ n>val @ < if ." -> smaller, go LEFT" cr cur @ n>left @ -1 = if dup new-node cur @ n>left ! ." attached as LEFT child of " cur @ n>val @ .ch cr drop exit else cur @ n>left @ cur ! then else ." -> not smaller, go RIGHT (equal chars stay stable)" cr cur @ n>right @ -1 = if dup new-node cur @ n>right ! ." attached as RIGHT child of " cur @ n>val @ .ch cr drop exit else cur @ n>right @ cur ! then then again ; \ ---- draw the tree sideways (rotate 90 deg): root at far left, -------- \ ---- larger characters toward the top. Indentation = depth. -------- : show-tree ( i depth -- ) over -1 = if 2drop exit then 2dup swap n>right @ swap 1+ recurse \ right subtree above dup 4 * spaces over n>val @ .ch cr \ this node over n>left @ over 1+ recurse \ left subtree below 2drop ; \ ---- in-order walk: left, self, right -> ascending, stable ----------- : inorder ( i -- ) dup -1 = if drop exit then dup n>left @ recurse dup n>val @ emit n>right @ recurse ; : report cr ." ===== binary tree (rotated 90 deg: root at left, larger on top) =====" cr root @ 0 show-tree cr ." ===== in-order traversal = sorted output =====" cr ." sorted: " root @ inorder cr #nodes @ . ." characters, " #cmp @ . ." comparisons, 0 swaps, stable" cr ; ```