How to Design Knowledge Programs — in Axioma

© 2026 Vlad Evenhar.

Created and designed by Vlad Evenhar. Implemented by AI agents.

A unified textbook for the Axioma programming language — covering a learning path from 1 + 2 through data structures and knowledge representation. The title plays on Felleisen, Findler, Flatt, and Krishnamurthi’s How to Design Programs (HtDP, MIT Press, 2018, 2nd ed.), whose design-recipe pedagogy the early chapters follow faithfully (all prose, examples, and exercises here are original) — but the book’s scope grows past traditional HtDP to cover data structures, knowledge representation, and a separately maintained AxiomaCascade application route.

What this book is

A textbook in the HtDP tradition: design recipes drive everything; data definitions come before code; examples become tests; the structure of the data shapes the structure of the program. The book is organized into Volumes:

• Volume I — Foundations (Chapters 1–22, plus addendum Chapter 54). The CS1-level material — arithmetic, variables, functions, the design recipe, conditionals, arrays, recursion, trees, higher-order functions, lambdas, mutual recursion, generative recursion, accumulators, mutation, streams, Concepts, enums and subranges, multi-valued logic, logic programming, and the meta-circular evaluator. Chapter 54 is the closed Hindley–Milner island (read after Chapter 19).
• Volume II — Data Structures and Beyond (Chapters 23+). The CS2-level material — linked lists, stacks, queues, hash tables, balanced trees, graphs. Followed (as the volume grows) by algorithm analysis, stateful systems, knowledge representation, and the neuro-symbolic frontier.
• Volume III — AxiomaCascade (draft; review deferred). Chapters covering the Cascade reasoning-engine layer that uses Axioma as one of its substrates.

It is not an Axioma reference manual — that already exists at ../../manual/Axioma Manual.md. This book is a learning path. The manual is the look-up index.

Revision coverage

This is a reviewed working edition, checked against the interpreter at revision 19a9398d6 (September 6, 2026). The language is still evolving. The current pass repairs older examples and covers the recent numeric, collection, control-flow, type-contract, metaprogramming and discovery changes. It also corrects mathematical explanations, documented outputs and prerequisites.

The automated suite inventories chapter and solution fences and exercise starters. It executes the declared standalone and contextual examples, compares documented output, and checks intentional failures. Exercise holes, foreign code and external integrations have explicit classifications. A successful test run does not mean every unfinished exercise was solved or every function’s possible inputs were tested.

Deferred route: Cascade product integration, the MCP bridge and associated external-service examples require their own repository and environment review. Those chapters remain marked as drafts. Chapter 53 documents a current SQL NULL limitation instead of presenting its failing example as successful. See CURRENCY_AUDIT.md for scope, corrections and remaining boundaries. This is not yet a final print edition.

Audience

Two audiences, depending on entry point:

• First-time programmers (CS1 audience) — start at Chapter 1. High-school students who have used a calculator can begin here. No prior programming experience assumed.
• Programmers exploring Axioma’s KR features — already comfortable with one language, want to learn Axioma’s signature material. Skim Volume I for orientation, dive into Volume II.

Reading formats

The book ships in three formats, all generated from the same markdown sources:

• Markdown — every .md file in this directory is readable on its own.
• HTML — HtDKP-in-Axioma.html, single-file with table of contents.
• PDF — HtDKP-in-Axioma.pdf, growing with each chapter.

After editing any markdown source, regenerate the HTML and PDF with:

./build.sh

Requires pandoc, LuaLaTeX, STIX Two Text/Math, and the fallback fonts named in fonts-fallback.tex. The build uses LuaLaTeX so Unicode symbols in code remain readable; see build.sh for the platform font requirements.

How to read the book

Use the main sequence when learning programming from the beginning. The optional extensions can wait until the canonical form feels familiar. Chapters sometimes reuse earlier helpers; load the named prelude rather than treating every code fence as an independent file. Independent alternatives and language-mode changes are identified in the text.

A first programming course. Start with Chapters 1–9, then abstraction in 10–15. Continue with state and data modeling in 16–21. Return to Chapter 22’s interpreter and macro material after writing several small programs.

Axioma as an additional language. Start with the numeric distinctions in 1–2, calls and receivers in 3, collections and matrices in 6, and higher-order functions/broadcasting in 10. Then study binding and mutation in 16, Concepts and schemas in 18–19, and logic in 20–21. Appendix E is the working companion for inspecting values and diagnosing errors. Familiarity with another language does not settle Axioma’s indexing, exact-number or scope rules.

Optional application routes. For data structures, read 23–27 alongside algorithm analysis in 35–37. For stateful systems, read 38–39 and the stack chapter 41. Knowledge representation in 28–33 and SQL in 53 build on the logic chapters. Read the Hindley–Milner addendum 54 as a separate language mode. The Cascade route can be skipped entirely without losing the core course.

Each chapter follows the same shape:

1. Concept — the new idea, motivated by something you already know.
2. Worked example — a small problem solved step-by-step.
3. Design recipe stages where they apply (data → signature → examples → template → body → tests).
4. Exercises — graduated difficulty; the last one is always open.
5. Reflection — why we did it this way, what comes next.

You’ll need a running Axioma installation. Throughout the book we assume you’re using the beginner subset:

axioma --learn                          # interactive single-shot tutor
axioma --recipe                         # six-stage Design Recipe wizard
axioma --language axioma/beginner ex.ax # restricts to canonical forms
axioma --typecheck ex.ax                # static type check before run

If you write #language axioma/beginner at the top of a file, the beginner restrictions apply automatically for that file. Most exercises in this book are written that way. Other real dialects show up later, each as a language, not a flag on the host:

• Chapter 21 — #language axioma/knowledge-core (monotonic Horn proof-core)
• Chapter 41 — #language axioma/rpn (additive Forth return stack; infix still runs)
• Chapter 54 — #language axioma/hm (closed Hindley–Milner island; println is out, expect is in, untypable programs exit 1)

axioma/core and axioma/functional are known names with no AST gate — they run as host. This book does not teach them. AppA lists the full roster. Bare #language axioma is not a name.

Keeping examples current

From the repository root, make test-textbook builds the current interpreter and runs the source-linked checks. The manifest in verification/examples.json records each code block’s role and the case that exercises runnable material. Editing code requires reviewing its expected behavior, not merely replacing a hash. Contributor instructions require a textbook impact decision alongside the Manual, quick reference, website and editor for language changes.

make textbook creates HTML, PDF and a build receipt. The commit check compares those hashes with the staged sources; CI repeats the example checks. This keeps missing updates visible while leaving explanatory quality to editorial review.

Table of contents

The generated table of contents links directly to the chapters. The repository also keeps an editorial outline; its draft-status tracker is not repeated in the reader edition. A quick map:

Volume I — Foundations

Volume II — Data Structures and Beyond

Volume III — AxiomaCascade

Status

Volume I complete (Ch. 1–22) + Volume II drafted (Ch. 23–42) + Volume III complete (Ch. 43–52) + Ch. 53 (the SQL surface) + Ch. 54 (the closed Hindley–Milner island, a Volume I addendum). Chapters 1–27 and 35–52 have full prose, exercises, runnable scaffolds, and per-chapter solutions. Chapters 28–33 are pilot drafts (concept overview + worked example + 2–3 inline exercises); each can be promoted to a full chapter in a later session. Appendices A, B, C (auto-assembled from the per-chapter solutions files), D, E, and F are complete.

• Part I (1–5): Arithmetic; Variables and Naming; Functions; The Design Recipe; Conditionals and Booleans.
• Part II (6–9): Arrays as Lists; Recursion on Lists; Trees via Concepts; Mutual Recursion.
• Part III (10–12): Higher-Order Functions; Lambda; Local Definitions.
• Part IV (13–14): Mutually Recursive Data Designs; Generative Recursion.
• Part V (15–17): Accumulator-Style Recursion; Mutation; Streams.
• Part VI (18–22): Concepts vs Sum Types; Enums and Subranges as Invariants; Multi-Valued Logic; Logic Programming; The Meta-Circular Evaluator. Ch. 54 returns to types with #language axioma/hm (closed Hindley–Milner island).
• Part VII (23–27): Linked Lists from Concepts; Stacks, Queues, Deques; Hash Tables and Dictionaries; Balanced Trees; Graphs as Reified Relationship Concepts.
• Part X pilots (28–33): The Graphs Landscape; Conceptual Spaces (Gärdenfors); Gödelization; Lojban-in-Axioma; NSM (Wierzbicka); Schank’s Conceptual Dependency. Pilot-depth introductions to Axioma’s signature knowledge-representation formalisms.
• Ch. 34: The MCP Bridge — Axioma tools inside Cascade’s server.
• Parts VIII–XI (35–42): Big-O and Empirical Complexity; the Sorting Showcase; Graph Algorithms; State Machines; Event Loops; the Cascade Reactor; Stack Programming; Neuro-Symbolic Patterns.
• Volume III (43–52): Cascade Architecture; the KG Schema; the Ingest Pipeline; the Truth-Value Lifecycle; Reasoning Algorithms; Axioma Rule Firing; Writing Custom .ax Rules; the Agent Swarm; Reactor Internals; Operating Cascade at Scale. Ch. 53 adds the SQL surface. Ch. 54 is the closed Hindley–Milner island (read after Ch. 19).
• Appendices: A (Quick Syntax Reference), B (Design Recipe One-Pager), C (Solutions, auto-assembled), D (Where to Read Next), E (Introspection and Debugging), F (Cross-Language Translation).

Relationship to HtDP

This is an original textbook inspired by HtDP, not a translation or a chapter-by-chapter adaptation. It adopts the design recipe and data-driven progression, then develops its own Axioma examples, exercises, and knowledge-programming material.

HtDP itself is freely available online at https://htdp.org/ and is the canonical reference for the underlying pedagogy. Anyone reading this book seriously should also read the original.

License

The textbook prose is © 2026 Vlad Evenhar, available under the same license as the rest of the Axioma project. HtDP itself is © Felleisen et al.; we neither copy nor displace it.

Chapter 1 · Arithmetic

What this chapter is. Your first encounter with Axioma. By the end you can use it as a calculator, you know what kinds of numbers it handles, and you’ve seen your first type error — Axioma telling you that something doesn’t fit.

A note on faithfulness to HtDP. The original How to Design Programs introduces several things in its first chapter that we’ll defer here: an image library (circles, squares, overlays), strings, and the design recipe itself. We delay those to keep the first three chapters lower-friction. The full design recipe lands in Chapter 4 — early enough to drive the rest of the book.

1.1 The REPL as a calculator

A calculator lets you type 2 + 3 and shows you 5. Axioma can do the same — and a lot more — through what’s called the REPL (read – evaluate – print – loop). Open a terminal and start it:

$ axioma
Axioma programming language and environment v0.9
Calculemus! (Let us calculate) - Leibniz.
Type ':help' for commands, ':exit' to quit
axioma>

The axioma> prompt is asking what you’d like to compute. Try typing 2 + 3 and pressing Enter:

axioma> 2 + 3
5
axioma>

That’s the whole loop: it read your line, evaluated the expression 2 + 3, printed the result 5, and looped back to the prompt for another. We’re going to live in this REPL for the rest of the chapter.

A subtle thing about the prompt

Axioma’s REPL can detect when an expression looks incomplete — for example, if you type a single line that has an open parenthesis but never closes it. When that happens, the prompt changes from axioma> to ... to tell you “I’m waiting for more”:

axioma> (2 + 3
...     ) * 4
20
axioma>

You can submit a half-finished line by hitting Enter on an empty ... line. If you ever see ... and don’t remember why, that’s the escape hatch: a blank line on the ... prompt either submits what you have (if it’s now complete) or returns to axioma> empty-handed.

For every REPL example in this book, we’ll show the prompt that’s asking, so you can match what’s on your screen.

Beginner mode. Throughout this book we’ll usually invoke Axioma in the beginner subset — a restricted version that allows exactly one way of doing each thing, so you don’t get distracted by alternatives:

$ axioma --language axioma/beginner

Or, equivalently, you can put #language axioma/beginner at the top of any script file. The REPL prompt looks the same, but Axioma will refuse some of its more advanced features. That’s intentional — we’ll unlock them chapter by chapter.

Two ways to see a value: println and the trailing dot

The REPL prints every result automatically. Script files don’t — type 2 + 3 in a script and run it, and you’ll see nothing on screen. Axioma gives you two ways to make a value visible:

println(2 + 3)         # the function call: prints 5
2 + 3 .                # the trailing-dot sigil: also prints 5

The trailing . (read it as “show me this”) is Axioma’s inspect-print operator. It works exactly the way the REPL does — evaluate the expression, then print the result — but inside a script file. Compare:

# Verbose script style
x: 5
y: 10
println(x)
println(y)
println(x + y)

# Same thing, terser
x: 5 .
y: 10 .
x + y .

Both print 5, 10, 15. The dot version reads almost like a Prolog or Smalltalk dialect — every “sentence” ends with a period, and the period asks Axioma to show you what just happened.

The dot works at the top level of a script, and also inside the bodies of loops, conditionals, and functions — so it’s particularly handy when you want to peek at intermediate values without cluttering your code with println calls:

total: 0
i: 1
while (i <= 5) [
  i .                          # show me i each iteration
  total = total + i
  i = i + 1
]
total .                        # show me the final total

That prints 1 2 3 4 5 15 — the loop variable for each iteration, then the final running total.

For most of this book we’ll use println(...) because it’s explicit and works the same way in every language you’ve used; the trailing dot is here so you can recognize it when you see it, and use it yourself once you find it more comfortable.

In the REPL transcripts in this book, binding acknowledgements and the none returned by output commands are omitted to keep attention on the value being discussed. Strings displayed as values keep their quotes; println and printf print the text itself. Error excerpts retain the meaning but may omit the source frame and hint.

1.2 Numbers come in two flavors

You can type whole numbers and Axioma understands them as integers:

axioma> 42
42

axioma> -7
-7

axioma> 1000000
1000000

Or numbers with a decimal point — those are floats (short for “floating-point”):

axioma> 3.14159
3.14159
axioma> -0.5
-0.5

Floats also accept scientific notation: write 1.5e6 to mean “1.5 times ten to the sixth power” (1,500,000), or 3.14e-2 to mean “3.14 times ten to the negative second” (0.0314):

axioma> 1.5e6
1.5e6
axioma> 1e9
1.0e9
axioma> 3.14e-2
0.0314

Notice that 3.14e-2 prints back as 0.0314 — scientific notation is just a way of writing a number, not a separate kind of number. Axioma reads 3.14e-2 and 0.0314 as the very same float.

(For very small or very large magnitudes Axioma keeps the scientific form when printing back — 3.4e-10 is easier to read than a string of ten zeros. The switch happens around one ten-thousandth: 0.0314 stays decimal, but 0.00000000034 prints as 3.4e-10.)

You’ll see floats whenever you write a number with a decimal point or an exponent — and whenever one enters a computation, because floats are contagious. (An all-integer division that comes out uneven gives you an exact fraction instead — 7 / 2 is the rational 7/2, not a float; §1.5 tells that story.)

Controlling how a value prints — printf and stringf

println shows you a value the way Axioma chooses to. Most of the time that is exactly what you want. But sometimes you want to decide the layout yourself — for instance, to see 0.00000000034 written out in full instead of as 3.4e-10. For that, Axioma gives you a format string.

printf (“print formatted”) takes a format string followed by the values to drop into it. The format string contains slots — a % followed by a letter — and each slot is filled, in order, by one of the values:

axioma> printf("%d items cost $%.2f\n", 3, 7.5)
3 items cost $7.50

The common slots:

Two things to remember. First, printf does not add a newline of its own — write \n in the format string wherever you want a line to end. Second, %.Nf lets you ask for exactly N digits after the decimal point. That is the answer to the puzzle from the last section:

axioma> printf("%.11f\n", 3.4e-10)
0.00000000034

The value never changed — 3.4e-10 and 0.00000000034 are the same float. printf just let us choose the long spelling. You can also pad a number to a fixed width, which is handy for lining up columns: %05d prints an integer in 5 columns, padded with zeros (00042).

stringf (“string formatted”) takes the same format strings and the same slots, but instead of printing, it hands the finished text back to you as a value:

label: stringf("item-%d", 7)     # label is now the string "item-7"
println(label + "!")                  # prints: item-7!

Use printf when you just want to show something on screen; use stringf when you want to keep the formatted text — to store it in a variable, join it with another string, or return it from a function. They are the same tool, differing only in where the result goes.

If you come from Lua, Ruby, Java, or C#, the name you already know for this is format — and Axioma accepts it as an exact alias of stringf: format("item-%d", 7) also returns "item-7" (it never prints, just like string.format in Lua). Printing stays printf.

1.3 The four operators — plus two more

Axioma has the same operators as your calculator, with the same symbols:

Plus two that calculators don’t always have:

Try each of these in the REPL:

axioma> 7 % 2
1

axioma> 7 % 3
1

axioma> 100 % 7
2

axioma> 2 ^ 10
1024

axioma> 10 ^ 6
1000000

Modulo is how you check whether a number is even (n % 2 == 0) or how you wrap an hour around the clock (hour % 24). We’ll use it a lot.

1.4 Order of operations

Mathematics gives multiplication and division priority over addition and subtraction. Axioma agrees:

axioma> 2 + 3 * 4
14

axioma> (2 + 3) * 4
20

In the first line, 3 * 4 happens first, giving 2 + 12 = 14. In the second, the parentheses force the addition first, giving 5 * 4 = 20.

The full precedence (high → low, paraphrased from the manual):

1. Function calls and parentheses
2. ^ (exponent)
3. unary - (negation)
4. *, /, %
5. +, -

When in doubt, parenthesize.

Associativity. Like most math textbooks, Axioma treats the exponent as right-associative: 2^3^2 means 2^(3^2) = 512, not (2^3)^2 = 64. Every other arithmetic operator (+, -, *, /) is left-associative, as usual. If you want the left grouping, write (2 ^ 3) ^ 2 explicitly. This appears in Exercise 1.3.

Negation vs. exponent. Unary - binds looser than ^, so -2^2 means -(2^2) = -4, not (-2)^2 = 4 — again the math-textbook reading. To square a negative base, parenthesize: (-2)^2.

1.5 Division has a surprise

Here’s the first thing that might surprise you:

axioma> 7 / 2
7/2

7 / 2 should be 3.5, right? Axioma is telling us 7/2. What happened?

When both operands are integers, Axioma keeps division exact: the answer is a rational number — a true fraction, not a rounded decimal. When the division comes out even, you get a plain integer back; when it doesn’t, you get the exact fraction:

axioma> 6 / 2
3

axioma> 7 / 2
7/2

axioma> type(7 / 2)
Rational

Addition, subtraction, multiplication, and division of rational numbers remain exact when all operands are exact:

axioma> 1/3 + 1/6
1/2

axioma> 7/2 + 1/2
4

axioma> 7/2 == 3.5
true

This is the same design choice HtDP’s teaching languages make: Racket’s (/ 7 2) is the exact rational 7/2 too. Exact answers stay exact until you decide to leave the world of fractions. When you want the decimal, bring a float into the expression — or convert at the end:

axioma> 7.0 / 2
3.5

axioma> 7 / 2.0
3.5

axioma> float(7 / 2)
3.5

For these arithmetic operations, mixing a Float with an Integer or Rational chooses approximate floating-point arithmetic. Other operations have their own result rules: for example, sqrt(2) produces a Float even though its input is an Integer.

Asking for a Float explicitly: fdiv

Sometimes the required output type is part of the task: you need a floating-point result even when both inputs are exact integers. Use fdiv, either as a function or between its operands:

println(fdiv(1, 8))           # 0.125
println(1 fdiv 8)             # 0.125
println(type(fdiv(1, 8)))     # Float
println(1 / 8)               # 1/8

The ordinary slash keeps an exact integer or rational quotient when its operands are exact. fdiv explicitly chooses a Float. A zero divisor raises an error in either form. The interpreter supports fdiv; VM support is deferred and unsupported uses refuse.

Asking for the floor quotient: div and ÷

To find how many whole groups fit, use div. Its glyph spelling is ÷:

println(7 div 2)              # 3
println(7 ÷ 2)                # 3
println(7.0 div 2.0)          # 3.0
println(-7 div 3)             # -3
println(-7.0 div 3.0)         # -3.0

Both spellings round the quotient down, toward negative infinity. For example, negative seven divided by three is between -3 and -2; its floor is -3. Integer inputs give an Integer; Float inputs give a whole-valued Float, which is why the third result prints as 3.0.

// starts a line comment in Axioma. It is not an operator: 7 // 2 evaluates the expression 7 and ignores the rest of that line. Use div or ÷ when you mean floor division.

The remainder operator has aliases too: % and mod

You met % (modulo) in §1.3. It also has a keyword spelling, mod:

axioma> 100 % 7
2
axioma> 100 mod 7
2
axioma> 100 modulo 7
2

All three give 2. modulo is just a longer alias for mod — it exists because some people find the longhand more readable.

The pair div (or ÷) and % (or mod) are related by a useful identity: for any integers a and nonzero b,

(a div b) * b + (a % b) == a

That is, quotient times divisor plus remainder equals dividend — the same fact you learned in grade-school long division. Try it:

axioma> (100 div 7) * 7 + (100 % 7)
100

Two halves in one shot: divmod, quotient, remainder

Sometimes you want both the quotient and the remainder. You could write 100 div 7 and 100 % 7 separately, but that does the division twice. Axioma gives you a combined builtin:

axioma> divmod(100, 7)
(14, 2)

divmod returns a tuple — a pair of values bundled together. You can pull them apart with index access ([1] is the first item, [2] is the second):

axioma> r: divmod(100, 7)
axioma> r[1]
14
axioma> r[2]
2

If you only want one half, the prefix forms quotient and remainder exist and read as English:

axioma> quotient(100, 7)
14
axioma> remainder(100, 7)
2

These are exact synonyms for 100 div 7 and 100 % 7 respectively — pick the form that reads best in the sentence you’re writing.

Extension: exact inputs and complex values

An exact input does not make every operation exact. Rational arithmetic such as 1/3 + 1/6 keeps a fraction; a transcendental function such as sin returns an approximation. Complex numbers extend the numeric domain: im names the imaginary unit, and multiplication remains explicit.

println(1/3 + 1/6)        # 1/2
println(sin(1/2))         # 0.479425538604203
println((1 + im)^2)       # 2.0 * im
println((1 + im)^2 is Complex)  # true

The printed 2.0 * im is valid Axioma syntax. It records the Float component used by the complex calculation; it is not a new kind of imaginary unit. These examples distinguish three questions: what value was computed, what type represents it, and whether the result is exact. For a first reading, ordinary integers and fractions are enough; return here when a problem actually needs complex arithmetic.

1.6 Your first type error

Try this in the REPL:

axioma> "hello" / 2
ERROR at <stdin>:1:9: unknown operator: STRING / INTEGER

Axioma stopped you. The reason: division isn’t defined between a string (the quoted text "hello") and an integer (2). Axioma calls this an error because there’s no sensible answer.

The error identifies an operation that is not defined for these inputs. Check the values and the operation before changing the program.

A subtle warning. Axioma is permissive about some mixed-type arithmetic. "hello" + 1 produces "hello1" (it converts the integer to a string and concatenates). 2 * "hi" produces "hihi" (repetition, Python-style). These are not errors — they’re features. Division is the one that has no string interpretation, so it’s the one that errors. We’ll see more of this in Chapter 2.

1.7 A worked example: area of a circle

You probably know the formula: a circle’s area is π times the radius squared. Let’s compute the area of a circle with radius 5.

Step 1: write down what you know. Radius = 5. π ≈ 3.14159.

Step 2: translate to Axioma.

axioma> 3.14159 * 5 ^ 2
78.53975

That’s it. Axioma evaluated 5 ^ 2 first (= 25), then multiplied by 3.14159, giving 78.53975. About 78.5 square units.

A small refinement. If you want a more precise answer, use more digits of π:

axioma> 3.141592653589793 * 5 ^ 2
78.53981633974483

A peek ahead. Typing π’s digits every time is tedious. In Chapter 2 you’ll learn to give names to values (pi: 3.14159) so you can write pi * 5 ^ 2 instead. In Chapter 3 you’ll learn to package the whole computation into a function (circle_area(5)).

1.8 Exercises

Try each of these. After each, predict what Axioma will say before running it; then check. The predict-then-check habit is the most important habit you’ll build this term.

Exercise 1.1

Compute the circumference of a circle with radius 7 (the formula is 2 × π × r). Use 3.14159 for π.

Exercise 1.2

What does Axioma give you for 2 ^ 16? What about 2 ^ 32? What about 2 ^ 64? Try them and see when (if ever) Axioma stops giving you exact answers.

Exercise 1.3

Predict each answer before typing it:

• (2 + 3) * (4 - 1)
• 10 - 2 * 3
• 2 ^ 3 ^ 2 (this one is sneaky)
• (2 ^ 3) ^ 2
• 100 / 7
• 100 % 7
• 100.0 / 7
• 100 div 7
• 100 fdiv 7
• 100 mod 7
• 100.0 div 7.0
• -7.0 div 3.0 (this one is also sneaky — recall the floor rule)

Exercise 1.4

Modulo trick. For each of these, predict whether the answer is 0, and check (% and mod are interchangeable — try both spellings):

• 12 % 3
• 12 mod 4
• 12 % 5
• 2 ^ 10 mod 7

What do all the zero results have in common with 12?

Exercise 1.5

Type-error exploration. Without looking at section 1.6, try to predict which of these will error and which won’t:

• "5" + 3
• 5 + "3"
• 5 - "3"
• 5 * "3"
• 5 / "3"
• "hi" * 4
• "hi" / 4
• "hi" - "bye"

What rule (if any) can you guess about when Axioma errors and when it just gives you something?

Exercise 1.6 — open

Find an expression that uses all four arithmetic operators (+, -, *, /) AND modulo (%) AND an exponent (^), evaluates without error, and produces an answer between 0 and 100. There are many possible answers — find one of yours.

(After you find one, find a second one that’s structurally different from the first.)

1.9 Reflection

Why did we start with arithmetic? Two reasons.

One, every computer program — every spreadsheet formula, every video-game scoreboard, every weather model — is at its core calculation on data. Arithmetic is the smallest possible example of that. If you understand it, you understand the seed from which the rest grows.

Two, arithmetic lets us meet the REPL — the read-evaluate-print loop — without anything else getting in the way. The REPL is where you’ll do most of your exploration in this book. Every chapter starts in the REPL; only after you’ve explored an idea interactively do we move to writing files.

In the next chapter we’ll learn to name values you’ve computed, so a long expression becomes a short name and your work compounds.

Looking ahead — what you’ll be able to do by Chapter 5:

• Define your own functions (func)
• Make decisions with if … then … else …
• Use the Design Recipe — the six-step process that turns “I need a program for X” into actual working code

By Chapter 9 you’ll have built a small interpreter for arithmetic expressions, written in Axioma. The arithmetic you typed in Chapter 1 will literally be the data your Chapter 9 program processes.

What we used from Axioma

A one-line index for future lookup (the full reference is in the manual):

• The REPL, started by axioma or axioma --language axioma/beginner
• Integer literals: 42, -7, 1000000
• Float literals: 3.14159, 1.5e6
• Operators: +, -, *, /, %, ^, div (or ÷), fdiv, mod (or modulo, both alias %)
• Prefix builtins for integer division: quotient(a, b), remainder(a, b), divmod(a, b) → (q, r)
• Grouping with ( )
• Formatted output: printf(fmt, ...) and stringf(fmt, ...) (alias format) with %d / %f / %.Nf / %s / %t / %% slots
• The first error format: ERROR at <stdin>:line:col: …

Solutions to selected exercises

Solutions to selected exercises: Chapter 1 · Solutions in Appendix C. (Repo file: exercises/solutions/ch01_solutions.md.)

Chapter 2 · Variables and Naming

What this chapter is. Naming values. Once you can give a number (or a string, or any value) a name, you stop retyping it and start thinking with it.

2.1 Why name a value?

Chapter 1 ended with the area of a circle:

axioma> 3.141592653589793 * 5 ^ 2
78.53981633974483

That works, but two things bother us. First, the digits of π are tedious to retype. Second, the 5 is the radius — but nothing in the expression says that. A reader has to guess.

Both problems disappear when we name things:

axioma> pi: 3.141592653589793
axioma> radius: 5
axioma> pi * radius ^ 2
78.53981633974483

The expression now reads aloud the way we’d say it: pi times radius squared. Names are how programs become explanations.

2.2 Declaring with :

The declaration form is:

<name>: <expression>

Three things happen when Axioma sees this:

1. It evaluates the expression on the right.
2. It binds the resulting value to the name on the left.
3. From then on, that name is that value, until you rebind it.

axioma> x: 5
axioma> x
5
axioma> x + 3
8
axioma> y: x * 2
axioma> y
10

You can use names inside other declarations — that’s how y: x * 2 works. Axioma had already bound x to 5, so the right-hand side reduced to 5 * 2 = 10 before binding y.

This name: value shape — read aloud as “name gets value” — is the preferred Axioma idiom. It’s short, it scans well, and it puts the name first (which is what your eye looks for). You’ll see it everywhere in this book.

Naming rules

• Names start with a letter or underscore.
• After the first character they can have letters, digits, or underscores.
• Names are case-sensitive: radius, Radius, and RADIUS are three different variables.
• By convention in this book (and in HtDP), lowercase is for values and TitleCase for Concepts. Since June 2026 this is a convention, not a hard rule: both : and = accept a name of any case — the right-hand side decides (a concept { ... } RHS makes a Concept; any other value makes a variable, so B = {2,4,6} is a perfectly good set). We keep the lowercase-for-values style throughout the book for readability.

These names are fine: pi, radius, total_so_far, n, is_done. These will error or surprise you: 2pi (starts with a digit), total-so-far (the - is the subtraction operator).

2.3 The REPL vs. a script file

So far we’ve been typing one line at a time at the REPL. That’s great for exploring, but a real program is more than one line. You’ll want to put your code in a file and run it from your shell.

Create a file called hello.ax:

#language axioma/beginner
pi: 3.141592653589793
radius: 5
area: pi * radius ^ 2
println("Area for radius", radius, "=", area)

Run it:

$ axioma hello.ax
Area for radius 5 = 78.53981633974483

Three new things appeared:

1. #language axioma/beginner at the top of the file. This pins the file to the beginner subset. Like --language axioma/beginner from Chapter 1, but written inside the file so anyone running it gets the same restrictions.
2. println is a built-in that prints its arguments separated by spaces, then ends the line. Spaces inside a string remain part of that string. We use it because a script doesn’t auto-print results the way the REPL does.
3. Strings — text in double quotes — get treated like any other value. You can pass them, name them, and combine them. Most characters can appear directly (the source file is UTF-8), so "hello", "naïve", and "∀ x. P(x)" all just work. For the few characters that resist direct typing — line breaks, tabs, or rare codepoints — Axioma uses the universal escape forms "\n" (newline), "\t" (tab), "\\" (literal backslash), and "\u{2203}" (the Unicode codepoint U+2203, which is ∃). The full table lives in Appendix A. We won’t need them in this chapter.

Everything else is what you already know.

2.4 A subtle point: reassignment

What happens if you bind the same name twice?

axioma> x: 5
axioma> x: 10
axioma> x
10

Axioma lets it happen — silently. x: value means “bind x to this value”: it creates the name if it’s new and updates it if it already exists. There is no separate declaration step, and no warning. The math-style spelling does exactly the same thing:

axioma> x: 5
axioma> x = 10
axioma> x
10

x = 10 is a synonym of x: 10 — the bind-or-update behavior is identical. It’s there so a line that reads like an update (or like textbook mathematics, B = {2, 4, 6}) can be written that way.

Because rebinding is silent, the discipline has to live in you, not in the interpreter. In the beginner mindset, every name is bound exactly once and never changes; a name that gets rebound mid-program is almost always a bug-in-waiting — either it’s really Chapter 16’s topic (deliberate mutation) arriving early, or it’s a second value that deserves a second name (total_after_tax, not a new total). For this chapter and the next several: one name, one value.

2.5 One form, by design

In some languages you choose between several binding keywords — let pi = 3.14159 in ML, Scheme, or JavaScript; pi := 3.14159 in Pascal, Ada, or Go; val / var in Scala or Kotlin. Axioma deliberately ships with one canonical value form:

pi: 3.14159

Three reasons:

• It’s the shortest of any binding form. Two characters of overhead (:).
• It puts the name first. Your eye looks for the name; the form shouldn’t get in the way.
• It composes with type annotations. radius :: Integer: 5 reads naturally as “radius (of type Integer) gets 5.” We don’t use type annotations in Part I, but they show up in Part VI.

The textbook spelling pi = 3.14159 is the same operator (find-or-update), kept so math examples can read unaltered. There is no separate “assignment only” :=, and no val — the immutable binding is let NAME = … itself, read exactly as in a proof: it declares a fresh binding that shadows an outer name, and the name then stays fixed. Its mutable twin is var NAME = …, and a program-wide constant is const NAME = … — tools for later chapters, not for Part I.

Binding model (map for later chapters)

Part I only needs name: value. The full model shows up when you write functions, loops, and closures. One table (full detail: Axioma Manual §3, “Binding model at a glance”):

So: beginners learn one form (:). The keywords mark directions the default doesn’t take — let fixes fresh, var varies fresh, rebind writes the nearest outer cell, global writes this file (Julia) — (Chapter 16 / the manual) — and := stays gone. The _ / default forms are not needed until you deliberately leave a name unfilled or start a container empty; Chapter 16 explains why Integer is not silently 0.

Old code may use other forms. Earlier versions of Axioma accepted let pi = 3.14159 and pi := 3.14159 as synonyms of the canonical bind; both were retired in May 2026. := stays a syntax error with a hint pointing at x: value. The let spelling returned in August 2026 with different semantics: let pi = 3.14 now parses, but it declares a fresh binding (shadowing any outer pi) rather than updating one. For a top-level constant in old example code the result is the same value; inside functions and loops the difference is real — see the fresh-declaration row above and the manual’s §3.

The fix is mechanical: replace let X = V with X: V, and replace X := V with X: V.

For the rest of this book we use name: value almost exclusively. The = spelling appears in math-style lines and in later chapters; treat it as the same bind/update as :, not as a second language.

Persistence (advanced — skip on first read). If you want a variable to survive between REPL sessions or between script runs — useful when you’re slowly building up a knowledge base — the canonical form for that is declare/persist x = 42 (using =, not :). This is the one place where : doesn’t suffice, because the REBOL : binder deliberately has no refinement slot. Most code never needs persistence, so don’t worry about it now — Part VI covers it.

2.6 A worked example: from radius to several quantities

Say we have a circle of radius 5. We want to compute:

• its diameter (2 * radius),
• its circumference (2 * pi * radius),
• its area (pi * radius * radius),
• the area of a slightly larger circle (radius 6).

Without names, that’s four sprawling expressions. With names, it’s clean:

#language axioma/beginner
pi: 3.14159
radius: 5
diameter: 2 * radius
circumference: 2 * pi * radius
area: pi * radius * radius
println("radius =", radius)
println("diameter =", diameter)
println("circumference =", circumference)
println("area =", area)

Run it. You get:

radius = 5
diameter = 10
circumference = 31.4159
area = 78.53975

Why not just r: 5? It works — but silently steps on a built-in. Axioma starts every session with r already bound to a module (the bridge to the R statistical language), and r: 5 simply shadows it: no warning, and the module is unreachable for the rest of your session. That’s the flip side of §2.4’s silent rebinding — nothing protects an existing name, not even a built-in, from being rebound. Habit to build: pick names that say what they mean (radius) rather than single-letter abbreviations. The full word also reads better when someone else (or future-you) opens the file.

Notice that we computed area using a name (pi) that we’d computed earlier. Names compose. This is the seed of the next chapter, where we’ll learn to compose entire computations.

2.7 Seeing the value and its type

A whole-valued Float keeps a decimal marker when printed. The values 32 and 32.0 compare equal numerically, but their types differ:

println(32)                 # 32
println(32.0)               # 32.0
println(type(32))           # Integer
println(type(32.0))         # Float
println(32 == 32.0)         # true
println(32.0 / 1.0)         # 32.0

Use type(value) when you want to inspect the type directly. Adding a fraction does not prove what the original type was: an Integer can also participate in a calculation whose result is a Float.

Float output keeps enough significant digits to recover the stored value when read back. It is not necessarily the short decimal you would write by hand. To present a rounded amount, use Chapter 1’s printf or stringf; formatting the output does not change the stored value.

Extension: formatting a value for a reader

Use formatting when the presentation needs rounding. It does not change the stored number. Ordinary strings interpolate ${expression}; an f-prefixed string uses {expression} and optional format specifications.

price: 12.345
customer: "Ada"
println(f"Total: {price:.2f}")   # Total: 12.35
println(f"{42:05d}")            # 00042
println(f"{{{customer}}}")      # {Ada}
println(rf"C:\reports\{customer}")  # C:\reports\Ada
println(price)                  # 12.345

The r in rf preserves backslashes; the f still evaluates fields. Double braces produce literal braces. Expressions in fields run once, from left to right. Formatting is Axioma syntax, not a call into Python; not every Python format extension is accepted. When a colon is part of the expression itself, put that expression in parentheses.

Extension: Time is a relative amount of time

Axioma’s Time follows a duration-like convention. Hours can exceed 23, overflow carries into the next unit, and negative values are useful. It is not a validator for a clock face. Two integer fields mean hours and minutes; three fields include seconds. The special two-field form with a fractional second field means minutes and seconds.

println(23:61)           # 24:01
println(23:59:61)        # 24:00:01
println(-1:30)           # -1:30
println(1:02.5)          # 0:01:02.5
println(1:30 - 0:40)     # 0:50
println(1:00 * 2.5)      # 2:30
println(0:01 / 0:03)     # 1/3
println(float(1:30))     # 5400.0

Adding a number to a Time adds seconds. A ratio of two Times is numeric; dividing a Time by a number produces a Time. Storage has nanosecond resolution, so this is not arbitrary-precision fractional time. time(seconds) constructs a Time explicitly. The separate datetime package offers DateTime and Duration; a Duration converts back with time(duration_value). Calendar dates and time zones are separate questions from this relative-time arithmetic.

2.8 Exercises

Exercise 2.1

Set r: 7 and compute the four quantities in §2.6: diameter, circumference, area, and the area of a circle one unit larger (radius 8). Print each with a clear label.

Exercise 2.2

Distance between two points. Bind x1: 0, y1: 0, x2: 3, y2: 4. The Pythagorean theorem says the distance is sqrt((x2-x1)^2 + (y2-y1)^2). Compute it.

Hint. Axioma has a built-in sqrt. Use it: sqrt(25) returns the Float 5.0.

Predict first. The points (0,0) and (3,4) form a famous right triangle. What should the answer be?

Exercise 2.3

Body Mass Index (BMI). BMI = weight / height², where weight is in kg and height is in meters. Compute the BMI of someone who weighs 70 kg and is 1.75 m tall. The answer should be about 22.86.

Hint. You can write the division in one line (bmi: weight / (height * height)), or give the denominator a name first — the named version reads better:

height_squared: height * height
bmi: weight / height_squared

Exercise 2.4

Predict, then check. What does each print? (You’ll need to think about types — see §2.7.)

a: 7
b: 2
println(a / b)
println(a + 0.0)
println((a + 0.0) / b)

Exercise 2.5

Silent rebinding. Type this at the REPL exactly:

axioma> n: 1
axioma> n: n + 1

What does n end up being? Predict before checking. Axioma does this without any warning — why might that be dangerous in a long program?

Exercise 2.6 — open

Pick a real-world calculation you’ve done in the last week — a tip on a restaurant bill, the area of a wall you want to paint, the time remaining on a charging laptop. Write it as a short script with well-named bindings, ending in a println of the answer.

2.9 Reflection

We did two things this chapter.

One, we gave values names. Names let us reuse work (the pi we bound once is the pi we used three times) and they let us say what we mean (the radius is named radius, not 5).

Two, we moved from one-line REPL exploration to multi-line script files. The shape of all your programs from here on is the same: declare some inputs at the top, declare derived quantities below that, print the answer at the end.

In Chapter 3 we’ll take the next step: when a calculation is shaped like a recipe — input goes in, answer comes out — we’ll learn how to package the recipe into a function, so we can run it on many inputs without rewriting it.

Looking ahead — what you’ll be able to do by Chapter 5:

• Define your own functions (func)
• Make decisions with if … then … else …
• Apply the Design Recipe to turn any problem statement into working code

What we used from Axioma

• <name>: <expr> — declaration (the single canonical form)
• <name> = <new value> — assignment (we’ll come back to this in Ch.16)
• declare/persist <name> = <expr> — declaration that survives between sessions (advanced; covered in Part VI)
• The println built-in
• Strings: "text in double quotes"
• sqrt(x) — square root (also: abs, min, max, in the manual)
• The #language axioma/beginner pragma at the top of a file
• Rebinding is silent: x: v and x = v both create-or-update a name

Solutions to selected exercises

Solutions to selected exercises: Chapter 2 · Solutions in Appendix C. (Repo file: exercises/solutions/ch02_solutions.md.)

Chapter 3 · Functions

What this chapter is. When a computation reads “input goes in, answer comes out”, that computation is a function. Naming a function is even more powerful than naming a value: a value works once, but a function works on any input you give it.

3.1 Why give a computation a name?

Chapter 2 taught us to name values. But look at this script:

#language axioma/beginner
pi: 3.14159
radius_a: 5
area_a: pi * radius_a * radius_a
radius_b: 7
area_b: pi * radius_b * radius_b
radius_c: 12
area_c: pi * radius_c * radius_c

We computed the area of three circles, and we copy-pasted the formula three times. That’s a clear sign we should name the formula itself. Then we can use the name three times and write the formula exactly once.

The thing we want to name is a recipe: “given a radius, compute the area”. In Axioma, that’s a function.

3.2 Defining a function

The shape:

<name>: func(<parameter>) [ <body> ]

Read it left-to-right: “name gets the function that takes parameter and computes body.”

#language axioma/beginner
pi: 3.14159
area: func(radius) [pi * radius * radius]
println(area(5))
println(area(7))
println(area(12))

Output:

78.53975
153.93791
452.38896

We defined area once. We called it three times. Each call passes a different radius. The function does the same thing in every case — it multiplies pi by that radius squared.

What just happened in func(radius) [pi * radius * radius]

• func — keyword saying “what follows is a function definition”.
• (radius) — the parameter list. This one has a single parameter named radius. The parameter is a placeholder — it gets bound to whatever value is passed in.
• [pi * radius * radius] — the body, between square brackets. The body is an expression; its value is what the function returns.

When you write area(5): 1. Axioma evaluates 5. 2. It binds radius to 5 inside the function’s body. 3. It evaluates the body — pi * 5 * 5 = 78.53975. 4. That value is the result of the call.

The radius binding only exists inside the body; once the function returns, it’s gone. Functions have their own little namespace.

3.3 Functions with more than one parameter

Most useful functions take more than one input. The parameter list is comma-separated:

#language axioma/beginner
distance: func(x1, y1, x2, y2) [
  dx: x2 - x1
  dy: y2 - y1
  sqrt(dx ^ 2 + dy ^ 2)
]
println(distance(0, 0, 3, 4))
println(distance(1, 1, 4, 5))

Output:

5.0
5.0

Two things to notice.

One, the body is now several lines. When a body has multiple statements, only the value of the last one is the return value. The intermediate dx: ... and dy: ... are setup; the final sqrt(...) is the answer.

Two, rather than writing sqrt((x2-x1)^2 + (y2-y1)^2) in one line — which works — we extract dx and dy as names. Each line does one thing, and the intermediate quantities get meaningful names. That’s just better style.

3.4 A worked example: Celsius to Fahrenheit

The formula: F = C × 9/5 + 32.

#language axioma/beginner
c_to_f: func(c) [
  scaled: c * 9.0 / 5.0
  scaled + 32.0
]
println(c_to_f(0))
println(c_to_f(100))
println(c_to_f(-40))
println(c_to_f(37))

Output:

32.0
212.0
-40.0
98.6

The c * 9.0 / 5.0 uses 9.0 and 5.0 instead of 9 and 5 so the answer comes back as a decimal. Nothing would be wrong with c * 9 / 5 — Axioma’s division is exact, so 100 * 9 / 5 is 180 and 37 * 9 / 5 is the exact rational 333/5 (which is 66.6) — but a temperature that prints as 333/5 reads like a math worksheet, not a thermometer. A float literal anywhere in the expression keeps the whole result in decimal-land. Habit: for measurement-flavored functions, write the fraction as 9.0 / 5.0.

The -40 line is famous — it’s the only temperature at which Celsius and Fahrenheit agree. Try predicting that before running.

3.5 Functions are values too

A function bound to a name is just another value. You can pass it around like any other:

#language axioma/beginner
double: func(x) [x * 2]
triple: func(x) [x * 3]
same_as_double: double
println(same_as_double(7))

Output:

14

The line same_as_double: double doesn’t call double — it just binds another name to the same function. From then on, both names refer to the same recipe.

This is a small thing in Chapter 3. In Chapter 10 it becomes the foundation of higher-order functions — functions that take functions as inputs and return them as outputs. That’s what unlocks patterns like map and filter.

Looking ahead. In the full Axioma language there’s also a shorter syntax for one-line functions:

double: lambda x => x * 2

The lambda form is disabled in beginner mode. We’ll unlock it in Chapter 11. For now, func(x) [body] is the only form, and that’s intentional — one tool, one job.

The textbook spelling. There is one more form, and unlike lambda it does work in beginner mode — because it is simply how mathematics writes a definition:

double(x) = 2 * x

That is exactly double: func(x) [x * 2] — same function, same everything, just written the way you would write it on paper. It also takes the pattern and guard forms you will meet in Chapters 5 and 8:

fact(0) = 1                  # one clause per case …
fact(n) = n * fact(n - 1)    # … tried in order
sign(x) when x > 0 = 1       # a guard sits before the `=`
sign(x) = 0

We will keep writing name: func(args) [body] through this book. It is the form that makes “a function is a value you bind to a name” visible on the page, and that idea is doing real work in §3.5 and again in Chapter 10. Reach for the equation form when you are transcribing mathematics and want the page to match the source. Appendix A has the full rules.

3.6 Calling a function

Calling a function is so simple it’s easy to miss. To call f with arguments a and b, write f(a, b). The parentheses are required, and they go immediately after the function’s name (no space — well, spaces are tolerated by the parser, but the convention is no space).

If you write f without parentheses, you’re not calling it — you’re referring to the function itself, as a value.

axioma> double: func(x) [x * 2]
axioma> double
func (x) [x * 2]
axioma> double(5)
10

The first double printed the function object (the recipe). The second printed 10 — the result of applying the recipe to 5.

3.7 A peek at the Design Recipe

The full version is Chapter 4. Here’s the spoiler: every function you write follows the same six steps, and doing them in order is the single biggest skill-builder in this book.

1. Data definition. What kind of input? What kind of output?
2. Signature comment. Write the types down. (area: Float -> Float)
3. Examples. Write area(5) = 78.53975 before you write the code. Multiple examples.
4. Template. What’s the shape of the body, given the shape of the input?
5. Body. Fill the template in.
6. Tests. Re-check your examples by running the function.

Watch this happen for our Celsius converter:

# Data:  Celsius temperature (Float)
# Signature:  c_to_f: Float -> Float
# Examples:
#   c_to_f(0)    = 32
#   c_to_f(100)  = 212
#   c_to_f(-40)  = -40
# Template:
#   c_to_f: func(c) [
#     ... c ...  # some expression in c
#   ]
# Body:
c_to_f: func(c) [
  c * 9.0 / 5.0 + 32.0
]
# Tests:
println(c_to_f(0))     # expect 32
println(c_to_f(100))   # expect 212
println(c_to_f(-40))   # expect -40

That’s the recipe applied informally. Chapter 4 makes it the primary way you think about programming. The point isn’t bureaucracy. The point is: most “bugs” are really unfinished thinking, and the recipe forces you to finish the thinking before the code.

Axioma even includes a guided wizard for the recipe. Try it:

$ axioma --recipe

It walks you through the six steps for whichever function you choose.

3.8 Exercises

Exercise 3.1

Write circle_area and call it on radii 1, 5, and 100. (Use pi = 3.14159.)

Exercise 3.2

Write f_to_c — Fahrenheit to Celsius. The formula is C = (F - 32) × 5/9. Test it on:

• f_to_c(32) should be 0
• f_to_c(212) should be 100
• f_to_c(98.6) should be about 37

Tip. Same as §3.4: use 5.0/9.0 to keep the arithmetic in floats.

Exercise 3.3

Write bmi(weight, height) using the formula from Exercise 2.3. Then call it on three people:

• bmi(70.0, 1.75)
• bmi(85.0, 1.80)
• bmi(55.0, 1.65)

Exercise 3.4

Write a function tip(bill, percent) that takes a bill amount and a tip percentage (e.g., 20) and returns the dollar amount of the tip. Test it on:

• tip(50.0, 20) should be 10
• tip(100.0, 15) should be 15
• tip(42.50, 18) should be about 7.65

Exercise 3.5

Write a function is_even(n) that returns true if n is even and false otherwise. (Hint: n % 2 == 0.) Test it on a few integers. This is a sneak preview of Chapter 5.

Exercise 3.6 — open

Pick a calculation you do often (or imagine you might): converting a recipe between metric and imperial units, computing your monthly salary from an hourly rate, computing how many hours of streaming you can do per day on a metered internet plan. Whatever it is, package it as a function with sensible parameter names, and call it twice with different inputs.

Extension: defaults and named arguments

A default belongs to the function’s interface: callers may omit that argument. Both the equation form and func can express defaults.

scale_number(x, factor = 2) = x * factor
println(scale_number(3))             # 6
println(scale_number(3, 4))          # 12
println(scale_number(3, factor: 5))   # 15

Choose a default that makes sense for the problem, and test both omission and an explicit value. A named argument uses name: value at the call.

Later reading: collection receivers and refinements

After Chapter 6 introduces arrays, a collection can be placed before a dot. For a user function, the receiver becomes the first argument and all supplied arguments participate in one call, including overload choice.

xs: [1, 2, 3]
scale_values(values, factor = 2) = values .* factor
println(xs.scale_values(3))       # [3, 6, 9]
println(scale_values(xs, 3))      # [3, 6, 9]
println(xs.length)               # 3
println(xs.length())             # 3

This is a call rule, not a stored method added to each array. Built-in collection methods have a receiver-position table: xs.map(f) means map(f, xs), while a user scale_values receives xs first. Existing properties take precedence; a callable field keeps its own call behavior. To call a function returned by another call, make both calls explicit: maker(xs)(argument). A dot is not a request for broadcasting: that is the separate f.(xs) form taught in Chapter 10.

A refinement selects an optional behavior explicitly. This example uses the full language and can be saved as a separate file:

combine: func(a, b, /times amount) [
  if times then (a + b) * amount else a + b
]
println(combine(1, 2))                       # 3
println(combine/times(1, 2, amount: 10))      # 30

The declaration names the switch and its argument; an arbitrary suffix does not invent a behavior. User refinements remain an interpreter feature; the VM refuses unsupported refinement calls.

3.9 Reflection

A function bundles a recipe. We learned three things:

One, the syntax: name: func(params) [body]. The body is an expression; its value is what the function returns.

Two, multi-parameter functions; multi-line bodies; the fact that the last line of a multi-line body is the return value.

Three, functions are values — they can be bound to names just like numbers and strings. (We didn’t use this much yet. Chapter 10 will return to it.)

In Chapter 4 we’ll slow down and learn the Design Recipe — the six-step process that turns “I need a function for X” into actual working code, every time.

Looking ahead — what you’ll be able to do by Chapter 5:

• Apply the Design Recipe end-to-end
• Make decisions inside a function with if … then … else …
• Build small functions that combine arithmetic and conditional logic

What we used from Axioma

• <name>: func(<params>) [ <body> ] — function definition
• <name>(<args>) — function call
• Multi-line function bodies with intermediate bindings
• The last expression of a body is the return value
• sqrt(x) — square root from the standard library
• axioma --recipe — the interactive Design Recipe wizard

Solutions to selected exercises

Solutions to selected exercises: Chapter 3 · Solutions in Appendix C. (Repo file: exercises/solutions/ch03_solutions.md.)

Chapter 4 · The Design Recipe

What this chapter is. The single most important idea in this book. Not a feature of Axioma — a habit — that turns “I need a program for X” into a tested implementation. Six steps. Do them in order.

4.1 Why a recipe?

Most beginners — and a lot of professionals — sit down at a blank screen and start typing the body of a function. They have a vague sense of what it should do. They guess at the body. They run it. It fails. They edit. They run again. They debug. They edit. Eventually something works, sort of.

This is exhausting, and the resulting code is hard to trust. Most “bugs” are really unfinished thinking — the programmer never quite sat down and said exactly what the function takes and exactly what it returns. The recipe forces you to finish the thinking before you write the body.

Six steps. Each one builds on the previous one. With practice the sequence becomes a habit. It will not eliminate errors; it gives you a way to locate them and revise your design.

The six steps:

1. Data definition. What’s the input? What’s the output? Be precise about types.
2. Signature. A one-line comment of the function’s type: # name: InputType -> OutputType.
3. Examples. Two or three concrete name(input) = output lines, before writing any code.
4. Template. What’s the shape of the body, given the shape of the data?
5. Body. Fill the template in.
6. Tests. Re-check your examples by running them.

Stages 1–3 happen before you write any code. Stage 4 is mechanical. Stage 5 is “the actual work” — which is now small, because every other stage has prepared you. Stage 6 confirms.

4.2 The six stages, illustrated

We’ll work the recipe for f_to_c (Fahrenheit to Celsius) from Chapter 3 — but this time, every step is written down.

Stage 1 — Data definition

A Celsius (or Fahrenheit) temperature is a Float. Possibly negative (it gets cold).

That’s it. One sentence. Sometimes the data definition is more complex (a list of integers, a tree of strings), but for now it’s a single primitive type.

Stage 2 — Signature

Write the type of the function as a comment, in the form

# fname: InputType -> OutputType

# f_to_c: Float -> Float

For multi-parameter functions, the input types are space-separated:

# distance: Float Float Float Float -> Float

The arrow -> is the universal “produces” symbol — input goes on the left, output on the right. It’s borrowed from mathematicians’ notation for functions (f : ℝ → ℝ).

Stage 3 — Examples

Write concrete input/output pairs. Two minimum. Three is better. Pick:

• one easy case (round numbers, obvious answer)
• one edge case (zero, negatives, boundary values)
• one representative case (something realistic)

# Examples:
#   f_to_c(32)   = 0       (freezing point — easy case)
#   f_to_c(212)  = 100     (boiling point — easy case)
#   f_to_c(98.6) = 37      (body temperature — representative)
#   f_to_c(-40)  = -40     (the famous fixed point — edge)

Notice: we wrote the expected answer for each one. Where did the answers come from? From the formula C = (F - 32) × 5/9, computed by hand or in our head. The point is to commit to what the answer should be — so when the function is wrong, we’ll catch it.

Why this matters. “Examples first” looks like extra work. It isn’t. It saves time three times over. First, writing examples forces you to clarify what the function actually does — many vague specifications collapse here. Second, the examples become your tests in stage 6. Third, the worked examples often suggest the formula. If you couldn’t compute f_to_c(32) = 0 by hand, you probably don’t yet know the formula well enough to write it as code.

Stage 4 — Template

The template is the shape of the body, determined by the shape of the data. For a function over a single primitive, the template is boring:

# Template:
# f_to_c: func(f) [
#   ... f ...
# ]

That’s it. The body uses f somehow.

This stage feels silly for primitives. Don’t skip it anyway. The template will save your life in Chapter 7, where the data is a list and the template has two cases (empty / non-empty), and in Chapter 8 where the data is a tree.

For now, the template just says “the body is an expression in f.”

Stage 5 — Body

Now — and only now — write the actual code.

f_to_c: func(f) [
  (f - 32) * 5.0 / 9.0
]

We wrote 5.0/9.0 (not 5/9) for float division, as in Chapter 3.

Stage 6 — Tests

Run the examples and check they match.

println(f_to_c(32))      # 0.0
println(f_to_c(212))     # 100.0
println(f_to_c(98.6))    # 37.0
println(f_to_c(-40))     # -40.0

Run the file. All four match. Done.

The full file, in order, looks like:

#language axioma/beginner
# Data: a Celsius or Fahrenheit temperature is a Float.
# Signature: f_to_c: Float -> Float
# Examples:
#   f_to_c(32)   = 0
#   f_to_c(212)  = 100
#   f_to_c(98.6) = 37
#   f_to_c(-40)  = -40
# Template:
#   f_to_c: func(f) [
#     ... f ...
#   ]
# Body:
f_to_c: func(f) [
  (f - 32) * 5.0 / 9.0
]
# Tests:
println(f_to_c(32))      # 0.0
println(f_to_c(212))     # 100.0
println(f_to_c(98.6))    # 37.0
println(f_to_c(-40))     # -40.0

This is the shape of every function file from here on. The comments aren’t decoration — they’re the recipe, written down, so a future reader can see your thinking. They also help you when you return to your own code a week later and have no idea what you were trying to do.

Stage 6, mechanized — doctests

Notice what Stage 6 made us do: re-type each Stage-3 example as a println and eyeball the output. Axioma can do the checking for you. Inside a /**md … */ documentation block (or any .md file), open a fence with the info string axioma doctest, and every line of the form expr # → value becomes a checked assertion — the examples are the tests, in the exact shape you wrote them in Stage 3:

f_to_c: func(f) [ (f - 32) * 5.0 / 9.0 ]
f_to_c(32)        # → 0.0
f_to_c(212)       # -> 100.0
f_to_c(98.6)      # → 37.0
f_to_c(-40)       # -> -40.0
f_to_c("cold")    # raises: unknown operator

Two spellings of the arrow are equivalent: the glyph # → (the convention used throughout this book) and the plain-keyboard ASCII # -> — both lines above are checked the same way. A line expr # raises: substr asserts that the expression errors with a message containing substr, and any other line (like the f_to_c definition) is setup, run for effect. Run them with:

$ axioma --doctest myfile.ax     # ok: / not ok: per example, exit 1 on any miss

or the Playground’s ✓ Doctest button. If a doctest fails, the recipe’s diagnosis applies unchanged: the bug is in the body, the template, or the data definition — and now a machine tells you which example broke instead of you re-reading println output.

4.3 The recipe wizard

Axioma ships with an interactive wizard that walks you through the six stages. Try it:

$ axioma --recipe

It asks for your function name, then offers prompts for each stage in order. At each stage you type your answer; the wizard saves it and moves on. At the end it writes a starter file with everything in place — you only have to fill in the body.

The wizard is especially helpful when you’re stuck. If you can’t get past stage 3 (examples), you don’t understand the problem yet. Walk away, think, come back. The recipe is also a diagnostic.

There are also --recipe show to list the five worked recipes built into the wizard, and --recipe replay <name> to step through one end-to-end. The five built-in recipes (chosen to match this book) are:

• circle_area — single-parameter arithmetic
• f_to_c — domain-specific formula
• bmi — multi-parameter arithmetic with intermediate names
• is_even — Boolean-returning function (preview of Chapter 5)
• tip — money math

Use them as crib sheets. The wizard never writes the body for you — it writes the scaffolding and asks you to finish.

4.4 The recipe applied: tip_total

Let’s design a function that takes a bill amount and a tip percentage and returns the total you owe (bill + tip).

Stage 1 — Data definition

A bill amount and a tip percentage are both Floats. The result is a Float (the total to pay).

Stage 2 — Signature

# tip_total: Float Float -> Float

Stage 3 — Examples

Pick three cases:

# Examples:
#   tip_total(100.0, 0)    = 100      (zero tip — edge)
#   tip_total(100.0, 20)   = 120      (clean numbers — easy)
#   tip_total(42.50, 18)   = 50.15    (realistic — representative)

We computed 42.50 + 42.50 * 18 / 100 = 42.50 + 7.65 = 50.15 by hand.

Stage 4 — Template

# Template:
# tip_total: func(bill, percent) [
#   ... bill ... percent ...
# ]

The body uses both parameters somehow.

Stage 5 — Body

tip_total: func(bill, percent) [
  tip: bill * percent / 100
  bill + tip
]

Stage 6 — Tests

println(tip_total(100.0, 0))    # expect 100
println(tip_total(100.0, 20))   # expect 120
println(tip_total(42.50, 18))   # expect 50.15

Run it. All three match. Done.

Notice the pattern. Stage 5 was easy because stages 1–3 already told us what the function had to do. The body has zero guesswork left in it. That’s the payoff.

4.5 What to do when the recipe gets stuck

The recipe can fail at any stage. Each kind of failure is informative.

• Stuck at Stage 1 (Data). You don’t yet understand what the function is supposed to do. Walk away. Talk to whoever assigned the problem. Don’t write code yet.
• Stuck at Stage 2 (Signature). The data isn’t a single primitive type — it’s a list, or a record, or one of several alternatives. You don’t have the tools yet (those land in Chapters 6–9). For Part I, every signature is (some primitives) -> (some primitive).
• Stuck at Stage 3 (Examples). You can’t compute the answer by hand. That means you can’t write the formula yet either. Find the formula (in a textbook, in a calculator, on Wikipedia, by asking someone). The examples come second; the formula comes first.
• Stuck at Stage 4 (Template). Almost never for primitives. For lists and trees (Chapters 6+), this is where you’ll spend real time.
• Stuck at Stage 5 (Body). Now you’ve finally hit the actual programming problem. With everything else nailed down, the body is small — usually a single expression.
• Stuck at Stage 6 (Tests fail). The body is wrong. Compare what the function did with what your example said it should do; the difference is the bug.

4.6 Exercises

For each of these, do all six stages. Don’t skip stages even when they feel obvious. The point is to build the habit.

Exercise 4.1 — triple

Design a function that triples its argument. Inputs are integers.

Exercise 4.2 — discount

Design a function discount(price, percent_off) that returns the discounted price. For example, discount(100.0, 25) should be 75.

Exercise 4.3 — dollars_to_cents

Design a function dollars_to_cents(dollars) that converts a dollar amount (Float) to integer cents. dollars_to_cents(1.50) should be 150. Hint: think about what Axioma’s * does to a Float, and whether you want the result as an Integer.

Exercise 4.4 — rectangle_perimeter

Design a function that computes the perimeter of a rectangle given its width and height. (Perimeter = 2 * (width + height).)

Exercise 4.5 — is_positive

Design a Boolean-returning function is_positive(n). Returns true when n > 0, false otherwise. (This is a preview of Chapter 5.)

Exercise 4.6 — open

Pick a calculation you’ve done in the last week that wasn’t already a function. Apply the recipe to it from scratch — write down all six stages, then run it.

4.7 Reflection

The Design Recipe is the most important habit in this book. Everything that follows — recursion, higher-order functions, mutual recursion, generative recursion — gets easier when you have the recipe, and much harder when you don’t.

What the recipe really gives you is structure for thinking:

• Data first forces you to know what you’re operating on.
• Signature forces you to commit to types.
• Examples force you to know the answer in concrete cases — which often reveals you don’t yet understand the problem.
• Template prepares the shape of the code from the shape of the data.
• Body is now a small fill-in.
• Tests confirm.

By the end of Chapter 9 you’ll have used the recipe on dozens of functions and stopped thinking of it as a chore. By the end of the book, you’ll do it in your head, and you’ll do it faster than the people who insist they “don’t need to plan.”

In Chapter 5 we’ll add conditionals to your vocabulary — if then else — and we’ll redo the recipe for functions that have to make decisions.

Looking ahead — what you’ll be able to do by Chapter 5:

• Apply the Design Recipe even when the function has multiple cases (e.g., one answer when n > 0, another otherwise)
• Use Boolean values and Boolean-returning functions as building blocks

What we used from Axioma

• # comment for the signature, examples, and template
• axioma --recipe — the interactive Design Recipe wizard
• axioma --recipe show — list the five worked recipes
• axioma --recipe replay <name> — step through a built-in recipe end-to-end

Solutions to selected exercises

Solutions to selected exercises: Chapter 4 · Solutions in Appendix C. (Repo file: exercises/solutions/ch04_solutions.md.)

Chapter 5 · Conditionals and Booleans

What this chapter is. How a function makes decisions. Up to here, our functions did the same thing for every input. Now we’ll ask them to inspect the input and pick a branch.

5.1 Two values: true and false

There is a type called Boolean (named after the 19th-century logician George Boole). It has exactly two values:

axioma> true
true
axioma> false
false

That’s the whole type. No other values are Booleans. (Some languages use 1 and 0, or T and nil. Axioma uses words.)

You already produced Booleans without realizing in Chapters 1 and 3:

axioma> 5 > 3
true
axioma> 5 == 4
false
axioma> 7 % 2 == 0
false

Comparison operators take numbers (or other values) and return Booleans. The comparison 5 > 3 is asking “is 5 greater than 3?” — true or false.

5.2 Comparison operators

The double == is intentional. Single = is for assignment (as in x: 5); double == is for comparison. Most beginners accidentally write = once when they meant ==, get a strange error, and learn the lesson.

axioma> 7 == 7
true
axioma> 7 != 8
true
axioma> 100 >= 100
true
axioma> 100 > 100
false

Comparisons work on numbers, and == and != also work on strings and Booleans:

axioma> "apple" == "apple"
true
axioma> "apple" == "banana"
false
axioma> true == true
true

(< and > on strings is not currently supported in Axioma — we’ve logged it as a gap for a future version. Sorting strings is a Part-II topic anyway.)

Predicate functions

A comparison produces a Boolean. So does a predicate function — a function whose whole job is to answer a yes/no question. By long Lisp/Scheme tradition (the one this book follows) their names end in a question mark, which Axioma reads as part of the name:

#language axioma/beginner
zero?(0)          # true        even?(4)      # true        odd?(3)   # true
positive?(5)      # true        negative?(-2) # true
empty?([])        # true        empty?("")    # true

zero?(n) is clearer than n == 0, and even?(n) says what you mean better than n mod 2 == 0 — reach for the predicate when one exists. You’ll use these constantly in conditionals and (Chapter 7) as the base-case test in recursion.

5.3 Boolean operators: and, or, not, xor

Compose Booleans into bigger Booleans with and, or, not, and xor.

axioma> true and true
true
axioma> true and false
false
axioma> false or true
true
axioma> not (5 > 3)
false
axioma> true xor false
true
axioma> true xor true
false

Watch the difference between or and xor. Plain or is inclusive: it is true when at least one side is true — including when both are. xor (exclusive or) is true when exactly one side is true — the “soup or salad, not both” reading that English often intends. When a menu, a coin flip, or a light switch is involved, xor is usually the operator you mean.

These read like English. “Is n between 1 and 10?” becomes:

axioma> n: 7
axioma> n >= 1 and n <= 10
true

“Is the year a leap year?” (we’ll do this carefully in §5.7) becomes a slightly longer combination of and and or.

5.4 if ... then ... else ...

The main decision tool:

if <boolean-expression> then
  <expression-when-true>
else
  <expression-when-false>

Two flavors of use.

As an expression (returns a value)

axioma> n: 5
axioma> label: if n > 0 then "positive" else "non-positive"
axioma> label
"positive"

The whole if ... then ... else ... is an expression — it has a value. We can bind that value to a name, return it from a function, or pass it to println.

As a statement (decides what to do next)

n: 5
if n > 0 then
  println("n is positive")
else
  println("n is not positive")

Same form, but here we don’t capture the result — we use the chosen branch for its side effect (the println). The whole construct is still technically an expression; we just don’t use the value.

Why beginner mode requires then

Some other languages let you write if cond { ... } else { ... } with curly braces or parentheses and no then keyword. Axioma requires then. The reason is to make the structure visible at a glance — the words if, then, else read aloud as the structure they encode. Beginner mode keeps this; the full Axioma language allows alternate forms, but we won’t reach for them in this book.

5.5 else if for multiple branches

Sometimes there are more than two cases. Chain else if:

#language axioma/beginner
letter_grade: func(score) [
  if score >= 90 then "A"
  else if score >= 80 then "B"
  else if score >= 70 then "C"
  else if score >= 60 then "D"
  else "F"
]
println(letter_grade(95))
println(letter_grade(85))
println(letter_grade(72))
println(letter_grade(50))

Output:

A
B
C
F

The cascade is read top-to-bottom: the first condition that’s true wins. So letter_grade(95) doesn’t accidentally trigger the score >= 80 branch — once the first condition matches, the others are skipped.

Convention. Lay out the conditions in decreasing order of threshold (90, 80, 70, 60), and the cases read like a table from top to bottom. You’d usually align the else ifs for visual rhythm, as above.

5.6 A worked example: shipping cost

Suppose a shipping company charges by weight:

Apply the Design Recipe.

#language axioma/beginner
# Data: weight in kilograms (Float)
# Signature: shipping: Float -> Float
# Examples:
#   shipping(0.5)  = 5      (small)
#   shipping(3)    = 8      (medium)
#   shipping(15)   = 15     (large)
#   shipping(30)   = 25     (very large)
# Template:
# shipping: func(weight) [
#   if ... weight ... then ...
#   else if ... weight ... then ...
#   else if ... weight ... then ...
#   else ...
# ]
# Body:
shipping: func(weight) [
  if weight <= 1 then 5.0
  else if weight <= 5 then 8.0
  else if weight <= 20 then 15.0
  else 25.0
]
# Tests:
println(shipping(0.5))     # 5.0
println(shipping(3))       # 8.0
println(shipping(15))      # 15.0
println(shipping(30))      # 25.0

Notice that we test the boundary values — and you should choose extras like shipping(1) and shipping(5) to confirm which side of the boundary they’re on. (Our <= chose “1 kg is in the small tier,” “5 kg is in the medium tier.”)

5.7 A worked example: leap year

Why do leap years exist at all? A calendar year is 365 days, but the Earth takes about 365.25 days to circle the Sun — so about every four years we add an extra day (February 29th) to let the calendar catch up. That was the old Julian calendar’s whole rule: every fourth year. But a day every four years is a tiny bit too much catching up, so our modern Gregorian calendar skips a few. (The skips keep the average year at 365.2425 days — almost exactly the Earth’s pace.)

Think of leap years as a club with three door rules, where the last rule that applies to you wins:

• Rule 1 — you’re in. A year divisible by 4 (year % 4 == 0) is a leap year.
• Rule 2 — the exception. Except when it’s also divisible by 100 — then it’s back out. (Sorry, 1900.)
• Rule 3 — the exception to the exception. Unless it’s also divisible by 400 — then it’s back in after all! (Welcome, 2000.)

To judge a year, find the last rule that talks about it: 2024 only matches Rule 1, so it’s a leap year. 1900 gets caught by Rule 2 — not a leap year. 2000 goes all the way to Rule 3 — a leap year. And 2023 matches no rule at all, so it’s an ordinary year.

Translate the rule into Booleans:

#language axioma/beginner
# Data: a year (Integer)
# Signature: is_leap: Integer -> Boolean
# Examples:
#   is_leap(2000)  = true     (divisible by 400)
#   is_leap(2024)  = true     (div by 4, not by 100)
#   is_leap(1900)  = false    (div by 100, not by 400)
#   is_leap(2023)  = false    (not div by 4)
#   is_leap(2100)  = false    (div by 100, not by 400)
# Body:
is_leap: func(year) [
  (year % 4 == 0 and year % 100 != 0) or year % 400 == 0
]
# Tests:
println(is_leap(2000))     # true
println(is_leap(2024))     # true
println(is_leap(1900))     # false
println(is_leap(2023))     # false
println(is_leap(2100))     # false

The body reads as: “(divisible by 4 and not divisible by 100) or divisible by 400.”

A teaching trick. When the natural-English specification has the words and, or, not, you’ll usually translate them directly to Axioma’s and, or, not. The hard part is figuring out which English connectives are which. The phrase “except when” in the leap-year rule is and not — “is leap” and “not the century exception”. And “unless it’s also divisible by 400” opens a second route to qualifying — an or.

A sneak peek: the same shape, written as rules

Axioma has a whole second style of programming — relations and rules — that you’ll meet properly in Chapter 21. It’s a natural fit for rules-with-exceptions, so here’s a taste. Take an everyday rule with the same shape as the leap-year rule: you can play outside on a weekend — except when it’s raining — unless you’ve packed your raincoat.

relation weekend(d)
relation rainy(d)
relation has_raincoat(d)

assert weekend("saturday")       # a dry Saturday
assert weekend("sunday")         # a rainy Sunday - raincoat packed!
assert rainy("sunday")
assert has_raincoat("sunday")
assert rainy("monday")           # rainy Monday - a school day anyway

# Door 1: a weekend day with no rain
can_play(D) whenever weekend(D) and not rainy(D)
# Door 2: rain can't stop a raincoat
can_play(D) whenever weekend(D) and rainy(D) and has_raincoat(D)

println({D | D <- can_play(D)})  # {"saturday", "sunday"}

Read each whenever line as “…is true in every case where…” — the rule connective is literally the word whenever, so the code says exactly what the English says. (Axioma also accepts if here, and Prolog readers can write can_play(D) :- weekend(D) and not rainy(D) — the same connective in Prolog dress.) There are two doors into the can_play club, and a day only needs one of them to be open. Notice how the English “except when it’s raining” became and not rainy(D) on Door 1, and the “unless” clause became a door of its own. The leap-year rule fits the same two-door shape:

relation year(y)

assert year(1900)
assert year(2000)
assert year(2023)
assert year(2024)
assert year(2100)

# Door 1: divisible by 4 - except when divisible by 100
leap(Y) whenever year(Y) and Y % 4 == 0 and Y % 100 != 0
# Door 2: divisible by 400 - the exception to the exception
leap(Y) whenever year(Y) and Y % 400 == 0

println({Y | Y <- leap(Y)})      # {2000, 2024}

This is the same logic as is_leap above — “(divisible by 4 and not divisible by 100) or divisible by 400” — just wearing different clothes: the or became two separate doors, and the and not became a guard on Door 1.

5.8 Some patterns

A safe divider

#language axioma/beginner
safe_div: func(a, b) [
  if b == 0 then "undefined"
  else a / b
]
println(safe_div(10, 2))    # 5
println(safe_div(10, 0))    # undefined

Notice: safe_div returns either a number or a string. The signature is technically Integer Integer -> Integer | String. We’ll formalize the “or” of types in Chapters 8 and 18 — for now, just notice that the function has two kinds of result.

Absolute value

#language axioma/beginner
absolute: func(n) [
  if n < 0 then -n
  else n
]
println(absolute(7))      # 7
println(absolute(-3))     # 3
println(absolute(0))      # 0

(Axioma also has a built-in abs — but writing your own version is a fine exercise.)

Three-way classification

#language axioma/beginner
sign_label: func(n) [
  if n > 0 then "positive"
  else if n < 0 then "negative"
  else "zero"
]
println(sign_label(5))     # positive
println(sign_label(-3))    # negative
println(sign_label(0))     # zero

A pitfall to avoid. Some words in Axioma are reserved — classify, match, axiom, postulate, and a few others can’t be used as variable names. If you try classify: ..., you’ll get a “reserved keyword” error. The fix: rename. The convention in this book is to add a noun-like suffix: sign_label, bucket_for, category_of. Reading aloud-ability tends to improve as a side effect.

Optional spelling: the ternary expression

In the full language (a separate file without the beginner pragma), condition ? yes : no has the same purpose as if condition then yes else no. Only the selected branch is evaluated.

denominator: 0
answer: denominator == 0 ? none : 10 / denominator
println(answer)                  # none
println(true ? "yes" : "no")     # yes

The unselected division does not run. Use the longer if form when branches need explanation or several statements; nested ternaries can hide the decision structure you are trying to teach.

5.9 Exercises

Apply the Design Recipe to each. Don’t skip examples.

Exercise 5.1 — max_of_two

Write max_of_two(a, b) that returns the larger of two numbers. Examples: max_of_two(3, 7) = 7, max_of_two(5, 5) = 5, max_of_two(-2, -8) = -2.

Exercise 5.2 — temperature_category

Write temperature_category(c) (Celsius) that returns:

• "freezing" when c <= 0
• "cold" when 0 < c <= 15
• "comfortable" when 15 < c <= 25
• "hot" when c > 25

Exercise 5.3 — is_in_range

Write is_in_range(n, low, high) that returns true if low <= n <= high.

Exercise 5.4 — tip_smart

Modify Exercise 3.4’s tip so that:

• if bill < 10, the tip is a flat $2
• otherwise, it’s percent of the bill, as before.

Show three examples.

Exercise 5.5 — quadrant

Write quadrant(x, y) that returns "I", "II", "III", or "IV" based on which quadrant of the Cartesian plane (x, y) is in. Quadrant I is both positive; Quadrant II is x<0, y>0; III is both negative; IV is x>0, y<0. (What about points on the axes — x=0 or y=0? Decide before writing code. Document your decision in the examples.)

Exercise 5.6 — open

Pick a real-world decision you’ve made recently — what to wear given the weather, whether to bring an umbrella, whether to take a cab — and encode it as a function with if/else if/else. Make sure all branches are reachable (every combination of inputs lands in some branch).

5.10 Reflection

Two related ideas this chapter:

Booleans — a tiny type with exactly two values — let us capture the answer to a yes/no question. Every comparison operator (<, >, ==, etc.) produces a Boolean.

if ... then ... else ... — the main decision form. The whole construct is an expression (returns a value) that picks between two alternatives. Chain it with else if when there are more than two cases.

You now have everything you need to write Part I’s worth of single-value functions. The next chapters open the door to structures — collections of values, like lists and trees — and that’s where the language earns its keep.

In Chapter 6 we’ll meet arrays (the Axioma word for what HtDP calls lists) and start writing functions that work on collections, not just on single numbers.

Looking ahead — what you’ll be able to do by Chapter 9:

• Define your own data shapes with Concepts
• Process arbitrarily-long lists with recursion
• Build a small interpreter for arithmetic expressions, written in Axioma, processing trees of +, -, *, / nodes

What we used from Axioma

• Boolean literals: true, false
• Comparison operators: ==, !=, <, >, <=, >=
• Boolean operators: and, or, not, xor
• if <bool> then <expr> else <expr> as an expression
• Multi-branch else if cascades
• The list of reserved-keyword names that aren’t usable as variables (we hit classify)

Solutions to selected exercises

Solutions to selected exercises: Chapter 5 · Solutions in Appendix C. (Repo file: exercises/solutions/ch05_solutions.md.)

Chapter 6 · Arrays as Lists

What this chapter is. Up to here, every function we wrote took a fixed number of inputs: one temperature, two points, three arguments at most. Now we’ll handle many at once — a list of grades, a sequence of measurements, all the words in a sentence. The data shape we’ll use is called an array.

6.1 Why a new shape?

Suppose you want a function sum_three(a, b, c) that adds three numbers:

sum_three: func(a, b, c) [a + b + c]
println(sum_three(1, 2, 3))   # 6

Easy. But what about sum_five? Five parameters. sum_ten? Ten parameters. Sum of however-many numbers the user gives you? You can’t write sum_n_for_any_n with this style — the parameter list has to be fixed at the time you write the function.

This is the wall that arbitrary-size data breaks through. We package “many things” into a single value — an array — and pass one parameter that happens to be the array.

total: func(numbers) [
  ...
]
println(total([1, 2, 3]))           # 6
println(total([1, 2, 3, 4, 5]))     # 15
println(total([42]))                # 42
println(total([]))                  # 0

That ... body is what Chapter 7 will fill in. This chapter is about the shape — how to make arrays, how to look inside them, how to take them apart.

6.2 Creating an array

The literal form is comma-separated values inside square brackets:

axioma> [10, 20, 30]
[10, 20, 30]
axioma> [true, false, true]
[true, false, true]
axioma> ["red", "green", "blue"]
["red", "green", "blue"]

Axioma arrays are heterogeneous — different element types are allowed:

axioma> [1, "hello", true]
[1, "hello", true]

You usually don’t mix types in practice (it makes the function that processes the array more painful), but the language permits it.

The empty array is []:

axioma> []
[]
axioma> len([])
0

6.3 Looking inside: len, first, rest

Three primitive operations let us inspect an array. They’re enough for everything in this part of the book.

axioma> nums: [10, 20, 30, 40]
axioma> len(nums)
4
axioma> first(nums)
10
axioma> rest(nums)
[20, 30, 40]
axioma> first(rest(nums))
20

The pair first / rest is the same idea as Lisp’s car / cdr (if you’ve heard those terms) or “head” / “tail” in other languages. HtDP teaches recursion in terms of cons / first / rest; we’ll use Axioma’s first and rest and play the same game.

Notice that first(nums) returns the element itself (the integer 10), while rest(nums) returns a smaller array. That asymmetry is exactly what makes recursion on arrays work — rest(rest(...)) keeps shrinking the array until eventually it’s empty.

6.4 Indexing: 1-based

You can also fetch elements by position, using square brackets:

axioma> nums[1]
10
axioma> nums[2]
20
axioma> nums[4]
40

Axioma indexes from 1, not from 0. This is the same convention as Lua, Julia, Pascal, COBOL, and standard mathematical notation. Most other languages (C, Python, JavaScript) use 0. If you’re coming from one of those, the first few weeks will feel uncomfortable; after that it stops mattering.

Out-of-bounds access is an error, not a silent surprise:

axioma> nums[0]
ERROR: index out of bounds: 0 (indices start at 1)
axioma> nums[99]
ERROR: index out of bounds: 99

We’ll prefer first / rest over nums[i] for most of Part II, because recursion on the structure — not on an index counter — is the design recipe’s natural fit.

6.5 Putting arrays together

Two arrays glue together with +:

axioma> [1, 2, 3] + [4, 5]
[1, 2, 3, 4, 5]
axioma> [] + [99]
[99]
axioma> [10] + []
[10]

You can also use push(arr, x) to add one element at the end:

axioma> push([1, 2, 3], 4)
[1, 2, 3, 4]

push grows the original Array in place and returns that same Array. This is mutation, a topic we study in Chapter 16. If you want a new Array while preserving the input, use concatenation instead.

axioma> original: [1, 2, 3]
axioma> push(original, 99)
[1, 2, 3, 99]
axioma> original
[1, 2, 3, 99]
axioma> combined: original + [100]
axioma> original
[1, 2, 3, 99]
axioma> combined
[1, 2, 3, 99, 100]

6.6 Brackets do two jobs: arrays and blocks

In ordinary positions — bindings, arguments, +-chains — the single-element form [x] means exactly what you’d guess: a one-element array.

axioma> a: 5
axioma> single: [a]
axioma> single
[5]
axioma> type(single)
Array
axioma> [1] + [2, 3]
[1, 2, 3]

But brackets in Axioma do two jobs: they hold array literals and they delimit blocks of code — you’ve been using the second job all along, as function bodies (func(x) [x * 2]). In positions where the parser expects a block — an if/else branch, a function body — a bare [x] is read as a one-statement block whose value is x, not as an array (the block reading is what lets a branch hold several statements):

axioma> f: func(x) [ if x then ["yes"] else ["no"] ]
axioma> f(true)
"yes"
axioma> type(f(true))
String

The branch produced the string "yes", because ["yes"] there was a block. The spelling that always means “one-element array”, in every position, is a trailing comma:

axioma> g: func(x) [ if x then ["yes",] else ["no",] ]
axioma> g(true)
["yes"]
axioma> type(g(true))
Array

[x,] is the canonical singleton spelling. (You may still meet the older workaround push([], x) in the wild — it works, but [x,] has replaced it.)

“In every position” is worth checking rather than taking on trust, because a function body is a block just as much as a branch is:

axioma> h: func(x) [x,]
axioma> h(3)
[3]
axioma> type(h(3))
Array

One gotcha while you are here. A bare comma run inside a body is not an array — it comes back as a tuple:

axioma> k: func(x) [x, 1]
axioma> k(3)
(3, 1)
axioma> type(k(3))
Tuple

That trips people who expect [x, 1] to mean one thing everywhere. It doesn’t, and the reason is the same block-vs-array split as above: a body is a sequence of statements, so its commas build a sequence of values, while an if branch and the right-hand side of a plain binding are expression positions, where commas separate array elements. (In a body that sequence is doing real work: it is Axioma’s Pop-11-style postfix notation, where func f() [2, 3, +] returns 5. With no operator in it, as here, it simply hands back the values.)

The fix is the one you already know. Add the trailing comma and a body gives you the array too:

axioma> m: func(x) [x, 1,]
axioma> m(3)
[3, 1]

So the rule to carry forward is short: if you mean an array, write the trailing comma. It is the one spelling that never changes meaning with position.

6.7 Worked example: top three

Suppose scores is an array of test scores. We want the first three — say, to highlight in a podium graphic.

1. Data. An array of at least three numbers.

scores: [88, 72, 95, 60, 81]

2. Signature.

# top_three: Array -> Array

3. Examples.

# top_three([88, 72, 95, 60, 81])  = [88, 72, 95]
# top_three([10, 20, 30])           = [10, 20, 30]

4. Template. Pluck three elements out by index.

5. Body.

top_three: func(arr) [
  [arr[1], arr[2], arr[3]]
]

6. Tests.

println(top_three([88, 72, 95, 60, 81]))    # [88, 72, 95]
println(top_three([10, 20, 30]))            # [10, 20, 30]

This works — but it has an obvious shortcoming. What if the array has fewer than three elements? Then arr[3] is out of bounds and the program crashes. A proper version would check len(arr) >= 3 first and return something sensible otherwise. That’s the kind of defensive coding Chapter 7 will set up cleanly.

6.8 The two cases: empty vs. non-empty

Every function that processes an array has to handle two cases:

1. The array is empty: len(arr) == 0 (or equivalently arr == []).
2. The array is non-empty: there’s at least one element to look at.

Why? Because first(arr) and rest(arr) require a non-empty array. If you call them on [] they fail. So the very first thing your function does must be: “Is the array empty?”

describe: func(arr) [
  if len(arr) == 0 then "empty"
  else "non-empty"
]
println(describe([]))           # empty
println(describe([1, 2, 3]))    # non-empty

That two-case structure is the template for almost every list-processing function in Part II. Chapter 7 will turn it into a recipe.

6.9 Reflection

We’ve widened the type system from one value per input to a container with many values. The cost is small — three new operations to memorize (len, first, rest) plus one syntax (brackets) — and the payoff is enormous: from now on, no function we write has a hard-coded number of inputs.

The pattern for Chapter 7 is already visible:

• Empty array? Return some base-case answer.
• Non-empty? Look at first(arr), recur on rest(arr), combine the two.

That’s it. That’s recursion on lists. The whole next chapter is worked examples of that one shape.

6.10 Ranges describe values; collect gathers them

A range stores a rule for producing values. An array stores the values. This matters when the sequence is large, or you only need its beginning.

println(collect(1..5))                 # [1, 2, 3, 4, 5]
println(collect(5..1 by 2))            # [5, 3, 1]
println(collect(0.0..1.0 by 0.25))     # [0.0, 0.25, 0.5, 0.75, 1.0]
println(collect(0.0..<0.3 by 0.1))     # [0.0, 0.1, 0.2]
println(collect(5..1..2))              # []
println(first(1.., 4))                # [1, 2, 3, 4]

.. includes an endpoint when the step reaches it; ..< excludes it. With by, the step is a positive magnitude and the bounds determine direction. In start..end..step, the step is signed; a direction that does not approach the end gives an empty range. A zero step is an error. Float ranges use a rounding-aware sample grid, rather than promising exact decimal arithmetic. Ordinary scalar Float indexing remains distinct from slicing: an array can accept a whole-valued scalar index such as 1.0, but a Float range is not an array slice index.

collect(range) returns an Array, as does array(range). collect emphasizes consuming an iterable; when given a one-shot generator it exhausts it. Constructing or indexing a large range stays compact, while collecting it allocates storage and is subject to a materialization limit. An open-ended range cannot be collected in full: request a bounded prefix.

Try it. Predict the difference between collect(1..8 by 3) and collect(1..<7 by 3), then run both. Which endpoint can appear?

6.11 Numerical extension: matrices are two-dimensional

A nested Array and a Matrix solve different problems. Use a Matrix when rows and columns are part of the mathematical meaning. Axioma preserves Integer and Rational matrix elements for exact arithmetic; it does not silently turn every entry into a Float. This optional preview includes a for loop: use a separate full-language file, without the beginner pragma.

m: matrix([[1, 2, 3], [4, 5, 6]])
println(shape(m))                  # [2, 3]
println(m[2, 3])                   # 6
println(m[1, 2] is Integer)        # true
println(m[:])                      # [1, 2, 3, 4, 5, 6]
println(shape(m[1, :]))            # [1, 3]
println(shape(m[:, 2]))            # [2, 1]
for cell in m [println(cell)]      # prints 1 through 6, in that order
fractions: matrix([[1/3, 1/6]])
println(fractions[1, 1] + fractions[1, 2])  # 1/2
println(float(m)[1, 1] is Float)    # true

Indices start at one. Linear access and direct iteration use row-major order: finish one row before starting the next. Row and column slices remain matrices, retaining their axes. Use m[:] when a flat Array is the intended result. len(m) is deliberately refused: ask shape(m) for dimensions, or len(m[:]) when you specifically mean the count of flattened cells. The latter materializes an array.

Explicit float(m) opts into approximate cells for a numerical algorithm. An exact representation does not imply that every linear-algebra routine has an exact implementation. Tensor operations and broadcasting build on the same need to specify axes; Chapter 10 introduces that next layer.

Try it. Build a two-by-two matrix containing 1/3. Compare the type of that cell before and after float(m), and explain why the conversion is a choice rather than a formatting change.

Exercises

Reminder: every solution file in this chapter should start with #language axioma/beginner so you stay in the safe subset.

Exercise 6.1 — count_zeros

Write a function count_zeros(arr) that returns how many elements of arr equal 0. Use if, comparison, and the operations from this chapter. Don’t use recursion yet — write a version that works for arrays of length 0, 1, 2, or 3 only, by explicit case-analysis on len(arr).

Test cases:

• count_zeros([]) → 0
• count_zeros([0]) → 1
• count_zeros([5]) → 0
• count_zeros([0, 0, 5]) → 2

Exercise 6.2 — is_short

Write is_short(arr) that returns true when arr has fewer than 3 elements, false otherwise.

• is_short([]) → true
• is_short([1, 2]) → true
• is_short([1, 2, 3]) → false

Exercise 6.3 — swap_first_last

Given an array of exactly 3 elements, return a new array with the first and last swapped.

• swap_first_last([1, 2, 3]) → [3, 2, 1]
• swap_first_last(["a", "b", "c"]) → ["c", "b", "a"]

(Use indexing. Don’t worry about the general case.)

Exercise 6.4 — second_or_zero

Return the second element of the array, or 0 if the array has fewer than 2 elements.

• second_or_zero([]) → 0
• second_or_zero([10]) → 0
• second_or_zero([10, 20]) → 20
• second_or_zero([10, 20, 30]) → 20

Exercise 6.5 — glue_with_separator

Given two arrays a and b, return a single array that has all of a, then a separator element, then all of b. The separator value is up to you (use a string like "-").

• glue("abc", [1, 2], [3, 4]) … design your own signature.

(This exercise is intentionally a little open. Pick a separator, write down the signature first, then implement.)

Exercise 6.6 (open) — three things to know about an array

Pick any array, say [14, 7, 22, 7, 100, 7]. Write three functions that each compute one statistic from it:

• the first element
• the last element
• the length

The point is to wire up three tiny functions and have them all operate on the same array. Bonus: write a fourth function describe(arr) that returns a String summarizing all three.

Next chapter — recursion turns “the first element plus a smaller problem” into a complete algorithm.

Solutions to selected exercises: Chapter 6 · Solutions in Appendix C. (Repo file: exercises/solutions/ch06_solutions.md.)

Chapter 7 · Recursion

What this chapter is. The most important chapter in Part II. Recursion is not a trick and it is not “loops wearing a costume.” It is the way you write a function whose input can be any size, once you can name a smallest case and a strictly smaller case. Master the two-case pattern here and the rest of the book — trees, mutually recursive data, generative algorithms, even logic rules — is the same idea on a new shape.

7.1 A definition that uses the thing being defined

A to-do list is either empty, or it is one item plus a to-do list. That sentence is legal. It is also slightly startling the first time you take it seriously, because the word “to-do list” appears on both sides. That is not a bug in the sentence. It is the sentence telling you the shape of the data.

Open a to-do list.

• If there is nothing on it, you are done.
• If there is something on it, do the first item, then you are left with — a to-do list. Smaller. Same kind of thing.

A function that processes a to-do list has the same two sentences inside it. That is recursion: a function that solves a problem by solving a strictly smaller problem of the same kind, then combining. The empty list is how the process stops. The smaller list is how it continues.

Three questions, in this order, write every recursive function you will need for the next several chapters:

1. When do I stop? (the base case — the smallest input)
2. What is the smaller problem? (the recursive case — a strictly smaller input of the same type)
3. How do I combine this piece with the answer to the smaller problem? (the combining rule)

Write the base case first. Always. A recursive function with no base case is a picture frame that contains a picture frame that contains a picture frame, forever. Axioma will not hang your machine; it will stop you with a clear error. But the function is still wrong. The base case is the off switch.

A useful mental habit, borrowed from the way experienced functional programmers actually work: assume the function already works for every smaller input, and only write what this call has to add. You are not “thinking about all the calls at once.” You are writing one step, plus the promise that the same step works one size down.

7.2 How Axioma spells a recursive function

The beginner form is the same func you have been writing since Chapter 3. There is no extra keyword. If the body mentions the name being defined, the function is recursive.

#language axioma/beginner
sum_list: func(arr) [
  if len(arr) == 0 then 0
  else first(arr) + sum_list(rest(arr))
]
println(sum_list([1, 2, 3]))   # 6

Three things that look like they should work, and one of them does not.

Python, JavaScript, and Java all let a function call itself by name with no extra keyword — def f(…): … f(…) , function f(…) { f(…); }, int f(…) { return f(…); }. Axioma’s func and = work the same way. let is the exception: it is a fresh cell whose body closes over the environment from before the binding, so let f = func() [f()] does not see f. There is no rec keyword to opt in. Use : or = (find-or-update) or a func name clause when the body has to call itself.

Bodies are square brackets, [ … ]. Curly braces { … } are sets and dictionaries, not function bodies. That is a different pitfall, and it is just as loud.

Axioma indexes from 1, not from 0. s[1] is the first character of a string; s[len(s)] and s[-1] are both the last. Slices are inclusive on both ends: s[2: n - 1] drops the first character and the last. That is the same convention as Julia (s[2:end-1]) and Lua (s:sub(2, #s-1)). Python (s[1:-1]) and JavaScript (s.slice(1, s.length - 1)) are 0-based and drop the end index. Write the Axioma bounds on paper once before you type them.

7.3 The pattern, once

Every function that processes an array follows the same template. It is the to-do-list sentence, compiled:

f: func(arr) [
  if len(arr) == 0 then
    <some base-case answer>
  else
    <combine first(arr) with f(rest(arr))>
]

Two branches: empty (the base case) and non-empty (the recursive step). The empty branch returns a value immediately — nothing left to recur on. The non-empty branch peels off the first element, recurs on the rest, and combines.

That is it. The rest of this chapter instantiates that template — for sum, count, last, membership, max, palindromes, early-stop scans, and a helper that walks by index. Each time, the only things that change are “what to return when empty” and “how to combine this piece with the recursive result.”

This is what How to Design Programs calls structural recursion: the recursion follows the shape of the data. The data is “either empty, or a first element plus a rest”; the function is “either return a base value, or combine first with the recursive result on rest.” You do not invent the decomposition. The data definition already did.

7.4 First worked example: sum_list

Problem. Given an array of numbers, return their sum.

1. Data. An array of numbers (which may be empty).

2. Signature.

# sum_list: Array -> Number

3. Examples.

# sum_list([])           = 0
# sum_list([42])         = 42
# sum_list([1, 2, 3])    = 6
# sum_list([10, -3, 5])  = 12

The empty example is not optional. It is the base case, written as a test.

4. Template. The empty/non-empty split:

sum_list: func(arr) [
  if len(arr) == 0 then
    ...
  else
    ... first(arr) ... sum_list(rest(arr)) ...
]

5. Body. Fill in the holes:

• Empty: the sum of no numbers is 0.
• Non-empty: first(arr) is one number, sum_list(rest(arr)) is the sum of the rest. Add them.

#language axioma/beginner
sum_list: func(arr) [
  if len(arr) == 0 then 0
  else first(arr) + sum_list(rest(arr))
]

println(sum_list([]))           # 0
println(sum_list([42]))         # 42
println(sum_list([1, 2, 3]))    # 6
println(sum_list([10, -3, 5]))  # 12

All four match. Move on with confidence.

How it actually runs

Trace sum_list([1, 2, 3]) by substituting, the way you substitute in algebra. Do not try to hold the whole call stack in your head as a movie. Replace one call at a time:

sum_list([1, 2, 3])
  = 1 + sum_list([2, 3])
  = 1 + (2 + sum_list([3]))
  = 1 + (2 + (3 + sum_list([])))
  = 1 + (2 + (3 + 0))
  = 1 + (2 + 3)
  = 1 + 5
  = 6

Each call peels one element. After three peels the array is empty — the base case fires — and the pending additions run on the way back. Those pending 1 +, 2 +, 3 + are real work waiting on the stack. We will come back to them in §7.11.

If a recursive function you wrote is “almost right,” this kind of trace is the fastest debugger you have. Pick the smallest example that fails. Substitute by hand until the substitution disagrees with what you meant. The bug is on that line.

7.5 Second worked example: count_list

Problem. Given an array, return the number of elements. (len already does this — we reimplement it so the pattern is the only thing in view.)

#language axioma/beginner
# count_list: Array -> Integer
# count_list([])          = 0
# count_list([42])        = 1
# count_list([1, 2, 3])   = 3

count_list: func(arr) [
  if len(arr) == 0 then 0
  else 1 + count_list(rest(arr))
]

println(count_list([]))         # 0
println(count_list([42]))       # 1
println(count_list([1, 2, 3]))  # 3

The body changed from first(arr) + recur to 1 + recur. We did not look at the element itself — we just counted it. The shape of the function is identical to sum_list.

That is the whole skill. Name the combining rule; the template does the rest.

7.6 Third worked example: last_element

Problem. Return the last element of an array. The empty case has no last element. Use none — Axioma’s absence value, the one you get from a total read that found nothing. (om is a different bottom, an undetermined value. They are not interchangeable. Empty-array “there isn’t one” is none.)

#language axioma/beginner
# last_element: Array -> Any-or-none
# last_element([])          = none
# last_element([42])        = 42
# last_element([1, 2, 3])   = 3

last_element: func(arr) [
  if len(arr) == 0 then none
  else if len(arr) == 1 then first(arr)
  else last_element(rest(arr))
]

println(last_element([]))          # none
println(last_element([42]))        # 42
println(last_element([1, 2, 3]))   # 3

This version has three branches:

• empty → none
• exactly one element → that element
• otherwise → recur on the rest

The two-case template grew a third case because the data has two flavors of non-empty — singleton and longer. That is a normal extension when the problem demands it. The recursive call still receives a strictly smaller array, so we still terminate.

(Axioma also has a built-in last(arr). The exercise is in seeing the pattern, not in replacing the primitive.)

7.7 Fourth worked example: has_value

Problem. Does the array contain a given value?

(contains is a reserved word — a builtin that tests membership on several collection types. We cannot bind that name, so the recursive version gets its own.)

#language axioma/beginner
# has_value: Array Any -> Boolean
# has_value([], 5)             = false
# has_value([1, 2, 3], 2)      = true
# has_value([1, 2, 3], 99)     = false
# has_value(["a", "b"], "b")   = true

has_value: func(arr, target) [
  if len(arr) == 0 then false
  else if first(arr) == target then true
  else has_value(rest(arr), target)
]

println(has_value([], 5))             # false
println(has_value([1, 2, 3], 2))      # true
println(has_value([1, 2, 3], 99))     # false
println(has_value(["a", "b"], "b"))   # true

Look at the structure:

• Empty → false (nothing here matches anything).
• First element matches → true. Stop. Do not look at the rest.
• Otherwise → recurse on the rest, return whatever that says.

That middle branch is early exit. Recursion is not obliged to visit every element. map and reduce (Chapter 10) always do. When the problem is “walk until you know the answer,” recursion — or a loop with break, later — is the honest shape. has_value([1, 2, 3], 1) never even looks at 2 or 3.

Boolean-returning functions on lists almost always have this shape: an empty-array default, a test on the front, and a recur-on-the-rest for everything else.

7.8 Fifth worked example: largest

Problem. Return the largest number in an array. Like last_element, the empty case has no sensible numeric answer — none.

#language axioma/beginner
# largest: Array -> Number-or-none
# largest([])              = none
# largest([7])             = 7
# largest([1, 99, 3])      = 99
# largest([-5, -10, -2])   = -2

largest: func(arr) [
  if len(arr) == 0 then none
  else if len(arr) == 1 then first(arr)
  else [
    rest_largest: largest(rest(arr))
    if first(arr) > rest_largest then first(arr) else rest_largest
  ]
]

println(largest([]))              # none
println(largest([7]))             # 7
println(largest([1, 99, 3]))      # 99
println(largest([-5, -10, -2]))   # -2

Three new tricks here:

1. Local binding inside a function body. rest_largest: largest(rest(arr)) names the recursive result so we can refer to it twice without calling largest twice (which would re-compute the whole tail). Chapter 12 will make this a habit; for now it is a peek at local definitions.

2. The block expression [ ... ] as an else branch. When an else arm has more than one thing in it (here: a local binding and an if-expression), wrap them in [ ... ]. Same block syntax as a function body — a sequence whose value is the last expression. Without the block, the parser does not know where the multi-line else is supposed to end.

3. The two-arm comparison. Once we have first(arr) and rest_largest, the answer is whichever is larger. A simple if. Chapter 5; now tucked into a list-recursion.

A combining rule you will meet constantly: max(this, recur). min, and, or, +, + on arrays — all the same skeleton.

7.9 Strings: a palindrome

Lists are not the only thing that shrinks. A string is either short enough to be obviously the same forwards and backwards, or it is a first character, a last character, and a strictly shorter string in the middle.

Problem. Is s a palindrome — the same backwards as forwards? civic is. cynic is not. radar is. A single letter is. The empty string is (vacuously: there is nothing to mismatch).

Walk it the way you actually check a word on paper:

• radar — first and last match (r/r). Look at ada.
• ada — first and last match (a/a). Look at d.
• d — one letter. Yes.

And the failing case:

• cynic — first and last match (c/c). Look at yni.
• yni — y and i differ. No. Stop. Do not look at n.

That is the three questions:

1. Stop when the string has length 0 or 1 — those are palindromes.
2. The smaller problem is the string with the first and last characters dropped.
3. Combine: if the ends differ, the answer is false; if they match, the answer is the answer for the middle.

#language axioma/beginner
# is_palindrome: String -> Boolean
# is_palindrome("")          = true
# is_palindrome("a")         = true
# is_palindrome("civic")     = true
# is_palindrome("cynic")     = false
# is_palindrome("radar")     = true
# is_palindrome("runner")    = false

is_palindrome: func(s) [
  n: length(s)
  if n <= 1 then true
  else if s[1] != s[n] then false
  else is_palindrome(s[2: n - 1])
]

println(is_palindrome(""))         # true
println(is_palindrome("a"))        # true
println(is_palindrome("civic"))    # true
println(is_palindrome("cynic"))    # false
println(is_palindrome("radar"))    # true
println(is_palindrome("runner"))   # false

Index arithmetic, slowly, because this is where a 0-based habit (Python, JavaScript, Java, C) disagrees with Axioma’s 1-based inclusive slices.

• Axioma strings are 1-indexed. s[1] is the first character; s[n] is the last. (s[-1] is also the last. Negative indices count from the end, the way a single xs[-1] already did in Chapter 6.)
• The slice s[2: n - 1] is inclusive on both ends. For civic (n is 5) that is s[2: 4], which is "ivi". Then "v". Then we stop. Julia writes the same window s[2:end-1]; Lua writes s:sub(2, #s-1).
• Python’s s[1:-1] and JavaScript’s s.slice(1, s.length - 1) land on the same characters — "ivi" — but the numbers are 0-based and the end is exclusive. Copy those numbers into Axioma and you drop the wrong characters. A slice that overshoots becomes "", empty is a palindrome, and "cynic" answers true: a wrong answer at exit 0.

rest does not work on strings. first("radar") happens to return "r", but rest("radar") is an error: rest wants an array, tuple, set, or list. On a string, drop the first character with s[2:] (or s[2..]), and drop both ends with s[2: n - 1] or the equivalent s[2..-2].

A logged trace

When the substitution-by-hand feels too quiet, print the argument as you go. This is the same function with a narrator:

#language axioma/beginner
is_palindrome_logged: func(s) [
  n: length(s)
  println("seeing if '" + s + "'")
  if n <= 1 then [
    println("length " + n + " — yes")
    true
  ] else if s[1] != s[n] then [
    println("mismatch " + s[1] + " vs " + s[n] + " — no")
    false
  ] else
    is_palindrome_logged(s[2: n - 1])
]

is_palindrome_logged("civic")
is_palindrome_logged("cynic")

seeing if 'civic'
seeing if 'ivi'
seeing if 'v'
length 1 — yes
true
seeing if 'cynic'
seeing if 'yni'
mismatch y vs i — no
false

Take the printlns out when you are done. They are a diagnostic, not part of the answer.

Same algorithm, no copying

Each slice builds a new string. For a 50,000-character palindrome that is a lot of copying for a question that only needed two characters per step. The fix is a helper that carries two indices and never allocates a middle:

#language axioma/beginner
is_palindrome2: func(s) [
  go: func(start, finish) [
    if start >= finish then true
    else if s[start] != s[finish] then false
    else go(start + 1, finish - 1)
  ]
  go(1, length(s))
]

println(is_palindrome2("civic"))      # true
println(is_palindrome2("cynic"))      # false
println(is_palindrome2("redivider"))  # true

The public function takes one argument. The inner go takes the moving bounds. Callers never see start and finish. That wrapper-plus-helper shape is how you keep a simple interface when the recursion needs extra state. Chapter 12 treats helpers as a design step; you just used one because the problem asked for it.

Notice that go is bound with : inside the body, so it can call itself. let go = func(start, finish) [ … go(…) … ] would not.

(There is also the one-liner s == reverse(s). Use it in production. We are not practicing reverse right now; we are practicing shrinking an input from both ends.)

7.10 Stop in the middle: sum_until_negative

map and reduce visit every element. Some problems should not. Sum the numbers in an array up to but not including the first negative. If there is no negative, sum all of them. If the first element is already negative, the sum is 0.

Two base cases: empty array, and “the front is negative.” The recursive case adds the front and continues.

#language axioma/beginner
# sum_until_negative: Array Number -> Number
# sum_until_negative([], 0)              = 0
# sum_until_negative([-1, 2, 3], 0)      = 0
# sum_until_negative([1, 2, 3], 0)       = 6
# sum_until_negative([1, 2, 3, -9, 10], 0) = 6

sum_until_negative: func(items, total) [
  if len(items) == 0 then total
  else if first(items) < 0 then total
  else sum_until_negative(rest(items), total + first(items))
]

println(sum_until_negative([], 0))                # 0
println(sum_until_negative([-1, 2, 3], 0))        # 0
println(sum_until_negative([1, 2, 3], 0))         # 6
println(sum_until_negative([1, 2, 3, -9, 10], 0)) # 6

The running total is an accumulator: the answer so far, carried forward, so that when we stop we already have it. The recursive call is the last thing the function does — there is no pending + waiting for the return. That is the shape Chapter 15 names and exploits. You do not need the name yet. You need the picture: work happens on the way down, and the base case returns the finished answer.

Why not reduce? Because reduce has no polite way to say “stop now, ignore the rest.” You can fake it with a flag inside the combining function, and then you have written a worse recursive function. When the algorithm is “walk until a condition,” write the walk.

7.11 Pending work, tail calls, and the depth guard

Look back at sum_list:

sum_list([1, 2, 3])
  = 1 + sum_list([2, 3])
  = 1 + (2 + sum_list([3]))
  = 1 + (2 + (3 + 0))

The + is pending during the recursive call. The interpreter has to remember “when that returns, add 1.” For three elements that is harmless. For three million it is three million pending additions.

The interpreter guards nested evaluation. This build reports a limit of 50,000 active Eval frames (recursion_limit() reports the number). Non-tail recursion of a long array trips a catchable error:

ERROR: recursion limit exceeded (max Eval depth 50000): possible
infinite recursion or excessively deep nesting

Use a small bounded example to study the result:

axioma> make_range: func(n) [ [i | i <- [1..n]] ]
axioma> sum_list(make_range(100))
5050

The maximum safe input also depends on the function and available resources; a source-level recursive call can use several Eval frames. Avoid treating the limit as a supported array size. Chapter 15 rewrites the same function so the recursive call is in tail position — nothing pending after it — and Axioma can reuse stack space for supported tail calls. The work and allocation costs of the body still matter.

A tiny pair makes the difference visible. Repeat a string n times.

Tail version — the recursive call is the answer:

#language axioma/beginner
repeat_str: func(s, acc, n) [
  if n == 0 then acc
  else repeat_str(s, acc + s, n - 1)
]
println(repeat_str("go", "", 3))   # gogogo

Trace: ("go", "", 3) → ("go", "go", 2) → ("go", "gogo", 1) → ("go", "gogogo", 0) → "gogogo". No pending concatenations. The accumulator is the result.

Non-tail version — concatenation waits for the recursive result:

#language axioma/beginner
repeat_str2: func(s, n) [
  if n == 0 then ""
  else s + repeat_str2(s, n - 1)
]
println(repeat_str2("go", 3))      # gogogo

Trace: to know "go" + repeat_str2("go", 2) we must first know repeat_str2("go", 2), which must first know repeat_str2("go", 1), which must first know repeat_str2("go", 0) = "", and only then do the concatenations wind back: "go", "gogo", "gogogo". Same answer. Pending work on every frame.

Most textbooks open recursion with factorial, which is the non-tail shape (n * fact(n - 1)). It matches one mathematical definition and it makes recursion feel like a magic trick you have to unwind. Palindromes and repeat_str finish at the bottom: once you hit the base case, you have the answer. That is the process you want in your hands first. Factorial’s winding-back is real, and you just saw it in sum_list and repeat_str2. It is not the only process, and it is not the one Axioma can run at unbounded depth.

For this chapter: do not worry about the ceiling. Coursework lists are small. Know that it exists, that tail-position self-recursion (and mutual tail-recursion) reuse a frame, and that Chapter 15 is where we start writing the tail form on purpose.

7.12 Other spellings you will see

The template with if len(arr) == 0 is the one to write until it is muscle memory. Axioma also lets the parameter pattern carry the empty/non-empty split:

#language axioma/beginner
func sum_list3([]) [0]
func sum_list3([h | t]) [h + sum_list3(t)]
println(sum_list3([1, 2, 3, 4]))   # 10

Two clauses, one name. The first clause is the base case. The second names the head h and the tail t without calling first and rest. It is the same function. Read it when you see it; write the if form until the recipe is automatic.

The same [h | t] syntax constructs on the way back out. Doubling every element:

#language axioma/beginner
double_each: func(arr) [
  if len(arr) == 0 then []
  else [2 * first(arr) | double_each(rest(arr))]
]
println(double_each([1, 2, 3]))   # [2, 4, 6]

[head | tail] on the right-hand side means “this element, then that array.” It is how you build an array of the same length as the input. push appends at the end, so push(double_each(rest(arr)), 2 * first(arr)) would reverse the result if you are not paying attention. Put the new head on the left.

Helpers that walk by index (1-based) are the other common spelling. Collect the positions of the short words:

#language axioma/beginner
keep_indices: func(arr, pred) [
  helper: func(position, acc) [
    if position > len(arr) then acc
    else if pred(arr[position]) then
      helper(position + 1, acc + [position])
    else
      helper(position + 1, acc)
  ]
  helper(1, [])
]
is_short: func(s) [length(s) < 6]
words: ["cow", "aardvark", "squirrel", "fish", "snake", "capybara"]
println(keep_indices(words, is_short))   # [1, 4, 5]

cow, fish, snake sit at positions 1, 4, and 5 — not 0, 3, 4. Anyone arriving from a 0-based language (Python, JavaScript, Java, C) will write helper(0, []) once. The error is index out of bounds: 0. Start at 1; stop when position > len(arr).

7.13 A pitfall catalog

These are the failures that show up in real code reviews. Each one is a wrong answer or a loud error, not a style preference.

A recursive function is wrong in exactly two ways: it does not stop, or it stops with the wrong combination. The trace in §7.4 distinguishes them. If the substitution never reaches a base case, it does not stop. If it reaches a base case and the values coming back are wrong, the combining rule is wrong.

7.14 When not to recurse

Recursion is the right tool when:

• the data is an arbitrary-size list, tree, or nest, and
• the decomposition is “this piece plus a smaller one of the same kind,” and
• you may need to stop before the end.

It is the wrong first tool when:

• You want to transform every element the same way. That is map (Chapter 10), or a comprehension {2 * x | x <- arr}.
• You want to keep some elements and drop others, looking at each once. That is filter.
• You want one running total over the whole collection, no early stop. That is reduce.
• You are counting with a local variable and a while. That still works (Chapter 16). Recursion is not a moral improvement on a loop. It is a better fit for recursive data.

Industry practice is blunt about this. Linear scans over arrays, in production systems, are loops or library HOFs. Recursion earns its keep on trees, nested documents, grammars, and “walk until” — the shapes where the data definition is already recursive. Chapter 8 is trees. That is where people who were unimpressed by sum_list suddenly need this chapter.

7.15 Reflection — the one skill you are acquiring

Look back at the bodies:

sum_list:             first(arr) + sum_list(rest(arr))
count_list:           1 + count_list(rest(arr))
last_element:         [base] / first(arr) / last_element(rest(arr))
has_value:            first(arr) == target / has_value(rest(arr), target)
largest:              max(first(arr), largest(rest(arr)))
is_palindrome:        ends match, then is_palindrome(middle)
sum_until_negative:   stop, or total + first and continue

What varies is the combining rule (and where you are allowed to stop). What stays the same is the shape: smallest case, smaller case, combine. If you can name those three, you can write the function.

The three questions again, because they are the whole chapter:

1. When do I stop?
2. What is the smaller problem?
3. How do I combine this piece with that answer?

Chapter 8 asks the same three questions of a binary tree. The data definition changes. The skill does not.

Exercises

Exercise 7.1 — count_zeros (the recursive version)

Rewrite Exercise 6.1 to handle arrays of any length using recursion. Signature: Array -> Integer.

• count_zeros([]) → 0
• count_zeros([0]) → 1
• count_zeros([1, 0, 2, 0, 0]) → 3
• count_zeros([1, 2, 3]) → 0

Exercise 7.2 — smallest

By analogy with largest. Empty array returns none; otherwise the minimum value.

• smallest([]) → none
• smallest([7]) → 7
• smallest([3, 1, 4, 1, 5, 9]) → 1

Exercise 7.3 — sum_of_squares

Sum the squares of the elements.

• sum_of_squares([]) → 0
• sum_of_squares([3]) → 9
• sum_of_squares([1, 2, 3]) → 14

Exercise 7.4 — count_above

How many elements are strictly greater than threshold?

• count_above([], 10) → 0
• count_above([5, 12, 8, 99], 10) → 2
• count_above([1, 2, 3], 100) → 0

Exercise 7.5 — double_each

Return a new array with every element doubled. (This produces a new array of the same length — the recursive result is an array, not a number.)

• double_each([]) → []
• double_each([1]) → [2]
• double_each([1, 2, 3]) → [2, 4, 6]

Hint: [2 * first(arr) | double_each(rest(arr))] — the cons form, which puts the new head on the front of the recursive result. It reads the same way [h | t] reads when you destructure, and because the whole thing is one bracket there is no singleton to spell and no block-vs-array question to worry about (contrast §6.6). Mind the order: the doubled head goes on the left. (push(...) appends at the end, so the push-based spelling needs the arguments the other way around: push will not preserve order if you build head-first.)

Exercise 7.6 (open) — reverse

Return the array in reverse order.

• reverse_arr([]) → []
• reverse_arr([42]) → [42]
• reverse_arr([1, 2, 3]) → [3, 2, 1]

Two design choices to make:

1. Where does first(arr) go in the recursive answer — at the front or at the end?
2. Which operation glues it on — +? push? the cons form?

Pick one, write down examples, then implement. (A linear-time version waits for Chapter 15. A correct quadratic version is a complete answer to this exercise.)

Exercise 7.7 — is_palindrome

Write is_palindrome(s) for strings, using the shrink-both- ends recursion from §7.9. Empty and single-character strings are palindromes. Do not call reverse.

• is_palindrome("") → true
• is_palindrome("a") → true
• is_palindrome("civic") → true
• is_palindrome("cynic") → false
• is_palindrome("redivider") → true
• is_palindrome("runner") → false

Then write is_palindrome2 that uses a nested helper with two indices and never slices. Both must agree on the examples above. (Do not name the helper check — that word is reserved. go is fine.)

Exercise 7.8 — take_while and drop_while

take_while(arr, pred) returns the longest prefix of arr whose elements all satisfy pred, and stops at the first failure — even if a later element would have passed. drop_while(arr, pred) returns whatever take_while did not take: the rest of the array starting at that first failure. If every element passes, take_while returns the whole array and drop_while returns [].

data: [2, 6, 42, 5, 7, 20, 3]
is_even: func(n) [n % 2 == 0]
# take_while(data, is_even)  → [2, 6, 42]
# drop_while(data, is_even)  → [5, 7, 20, 3]

20 is even and it is not in the take_while result. The walk stopped at 5.

Next chapter — the same three questions applied to a new data shape: binary trees, built from Concepts.

Solutions to selected exercises: Chapter 7 · Solutions in Appendix C. (Repo file: exercises/solutions/ch07_solutions.md.)

Chapter 8 · Trees via Concepts

What this chapter is. A list is a flat sequence: every element is followed by zero or one “next.” A tree is branching: every node can have several children. We’ll model trees in Axioma using Concepts — Axioma’s record/structure mechanism — and apply the same structural-recursion recipe from Chapter 7 to a new data shape.

8.1 Why a new shape?

A list of grades is a fine shape for “all the test scores in order.” But for a family tree, or a file system, or the arithmetic expression (1 + 2) * (3 - 4), a sequence isn’t enough — each node has multiple sub-structures. We need a shape where one node can hold both a left and a right.

We’ll build that shape now. The data type we’ll define here — binary tree, with a value plus a left and right child — is the running example. In Chapter 9 we’ll generalize.

8.2 Introducing Concepts

Axioma’s mechanism for “a thing with several named fields” is the Concept. Concepts are Axioma’s analog of:

In Axioma, the syntax is natural-language style:

concept Node           # declare Node as a kind of Concept
Node has value: 0          # Node has a field called 'value', default 0
Node has left: none        # ... and 'left', default none
Node has right: none       # ... and 'right', default none

Four lines, four sentences. concept Node declares the type; has clauses declare fields with default values. The defaults matter — if you don’t give a value when constructing, the field takes the default.

8.3 Making instances

To make an actual node, use the indefinite-article form a Node:

axioma> n5: a Node {value: 5}
axioma> n5.value
5
axioma> n5.left
none
axioma> n5.right
none

We provided only value; the other two defaulted to none. To make a node with children, pass them explicitly:

leaf4: a Node {value: 4}
leaf7: a Node {value: 7}
n5: a Node {value: 5, left: leaf4, right: leaf7}

That builds this little tree:

      5
     / \
    4   7

We can read fields with dot notation:

axioma> n5.value
5
axioma> n5.left.value
4
axioma> n5.right.value
7

(Chapter 1 of the Axioma manual covers Concepts in more depth. Here we use just enough for the tree shape.)

8.4 The tree shape, formally

A Tree is one of: - none — the empty tree - a Node instance with a value, a left (which is a Tree), and a right (which is a Tree)

That two-case definition is the data definition — and once again it has two cases. Empty/non-empty for lists in Chapter 7. Empty/ node for trees here. The recipe says: one branch in every function for each case.

8.5 Worked example: tree_size

Problem. Count how many nodes are in a tree.

1. Data. A Tree as defined above.

2. Signature.

# tree_size: Tree -> Integer

3. Examples.

# tree_size(none)                       = 0
# tree_size(a Node {value: 1})     = 1
# tree_size(  5
#            / \
#           4   7
#         )                              = 3

4. Template. Two cases (empty vs. Node) and two recursive calls in the non-empty branch — one for each child.

tree_size: func(t) [
  if t == none then
    ...
  else
    ... tree_size(t.left) ... tree_size(t.right) ...
]

5. Body.

• Empty: zero nodes.
• Node: this one node plus all the nodes in the left subtree plus all the nodes in the right subtree.

tree_size: func(t) [
  if t == none then 0
  else 1 + tree_size(t.left) + tree_size(t.right)
]

6. Tests.

leaf4: a Node {value: 4}
leaf7: a Node {value: 7}
n5: a Node {value: 5, left: leaf4, right: leaf7}

println(tree_size(none))    # 0
println(tree_size(leaf4))   # 1
println(tree_size(n5))      # 3

Notice the shape: same two-branch if, same “do something, then combine recursive results” — but now we have two recursive calls instead of one. Trees are structurally richer than lists, and the recursion mirrors that.

8.6 Worked example: tree_depth

Problem. Return the depth of the deepest leaf below the root. A leaf-only tree (one node) has depth 1. The empty tree has depth 0.

# tree_depth: Tree -> Integer

tree_depth: func(t) [
  if t == none then 0
  else [
    dl: tree_depth(t.left)
    dr: tree_depth(t.right)
    1 + (if dl > dr then dl else dr)
  ]
]

println(tree_depth(none))   # 0
println(tree_depth(leaf4))  # 1
println(tree_depth(n5))     # 2

We use a [ ... ] block in the else branch (per Chapter 7’s trick) to bind the two recursive results to names, then take the larger one and add 1 for this node.

8.7 Worked example: tree_contains

Problem. Does the tree contain a node with this value?

# tree_contains: Tree Any -> Boolean

tree_contains: func(t, target) [
  if t == none then false
  else if t.value == target then true
  else tree_contains(t.left, target) or tree_contains(t.right, target)
]

println(tree_contains(n5, 7))    # true
println(tree_contains(n5, 99))   # false
println(tree_contains(none, 1))  # false

The three branches: empty (false), match (true), neither (check both subtrees and or the results). Compare to the list contains in §7.5 — same shape, with an extra or because we now have two sub-problems instead of one.

8.8 Worked example: mirror

Problem. Produce a tree that’s a horizontal mirror image of the input — left becomes right, recursively, at every node.

# mirror: Tree -> Tree

mirror: func(t) [
  if t == none then none
  else a Node {value: t.value, left: mirror(t.right), right: mirror(t.left)}
]

The empty tree mirrors to itself (still empty). A non-empty node mirrors to a new node with the same value but with the left and right children swapped (and each recursively mirrored).

m: mirror(n5)
println(m.left.value)    # 7  (was on the right)
println(m.right.value)   # 4  (was on the left)

This is the first function we’ve written that constructs a new tree (as opposed to computing a number or boolean from a tree). The shape is the same — two-branch recursion — but the recursive combiner builds a new a Node instead of doing arithmetic.

8.9 The pattern

Just like for lists in Chapter 7, every tree-processing function follows the same template:

f: func(t) [
  if t == none then
    <base-case answer>
  else
    <combine t.value with f(t.left) and f(t.right)>
]

What changes from function to function:

• What to return for none — 0 for size/sum, false for contains, none for mirror, [] for traversal.
• How to combine t.value, f(t.left), and f(t.right) — add them, or them, build a new node, append the traversals.

That’s the whole pattern. Internalize it and you can write any tree-processing function in one sitting.

8.10 Reflection

We just transferred a habit — structural recursion — from one data shape (list) to another (tree). The skill generalizes: every recursive data type comes with a matching recursion template. Chapter 9 makes the generalization official: mutually recursive data shapes, where two (or more) Concepts refer to each other.

The Concept system is doing more than syntactic sugar here. By naming a record type (Node), we get a vocabulary for our data that the rest of the program can rely on. Compare with HtDP’s define-struct posn (x y) — Axioma’s Concept is the same idea with natural-language syntax and a few extra features (defaults, inheritance) we’ll meet in Chapter 18.

Exercises

You’ll need this preamble at the top of every solution:

#language axioma/beginner
concept Node
Node has value: 0
Node has left: none
Node has right: none

(And probably a small fixed tree to test against.)

Exercise 8.1 — tree_sum

Return the sum of all value fields in the tree.

• tree_sum(none) → 0

• tree_sum(a Node {value: 7}) → 7

• For the tree

        3
       / \
      1   5
         / \
        4   7

  tree_sum → 20.

Exercise 8.2 — count_leaves

A leaf is a non-none node whose left and right are both none. Count the leaves.

• count_leaves(none) → 0
• count_leaves(a Node {value: 7}) → 1
• count_leaves on the picture above → 3 (leaves are 1, 4, 7).

Exercise 8.3 — tree_max

Return the largest value in the tree, or none for an empty tree.

Hint: for the empty subtree case inside the recursion, you need to return a value that the comparison will lose to. One easy trick: a separate helper tree_max_helper(t, best) that carries a running maximum. Or have tree_max itself handle empty/leaf/ internal as three branches.

• tree_max(none) → none
• tree_max on the picture above → 7.

Exercise 8.4 — tree_min

By analogy with tree_max. Smallest value, or none for empty.

Exercise 8.5 — inorder

Return an array of values in inorder — left subtree, then this node, then right subtree.

Hint: cons this node onto the right subtree, then glue the left one in front — inorder(t.left) + [t.value | inorder(t.right)]. The cons form carries the singleton for you, so there is no trailing-comma spelling to remember. (The three-way concatenation inorder(t.left) + [t.value,] + inorder(t.right) also works; the trailing comma makes the Array intention explicit. A bare [t.value] also works mid-chain; the block reading matters at the start of a branch or function body (§6.6).)

• inorder(none) → []
• inorder on the picture above → [1, 3, 4, 5, 7].

Exercise 8.6 (open) — tree_height_balanced

Return true if for every node in the tree, the depths of the left and right subtrees differ by at most 1.

This is harder than it sounds. Spend time on the data definition and examples before writing code. Consider what “balanced” means for none, for a leaf, for a node whose subtrees are themselves balanced but of different depths.

Next chapter — what if Node referenced Tree and Tree referenced Node? Mutually recursive data shapes, and the mutually recursive functions that process them.

Solutions to selected exercises: Chapter 8 · Solutions in Appendix C. (Repo file: exercises/solutions/ch08_solutions.md.)

Chapter 9 · Mutual Recursion

What this chapter is. Sometimes two data shapes refer to each other. A Person belongs to a Household; a Household contains Persons. Or: an Expression is either a literal or an operator with sub-expressions. When the data shapes cross- reference, the functions that process them have to do the same — they become mutually recursive.

9.1 The data shape: two Concepts that refer to each other

Up to here every recursive data type referred only to itself — a tree’s children are trees, an array’s tail is an array. Now imagine modeling a small household:

A Person has a name and (sometimes) a household they belong to.

A Household has an address and an array of people.

The arrow goes both ways: Person → Household → Person. That’s mutual recursion at the data level.

In Axioma:

concept Person
Person has name: ""
Person has household: none

concept Household

Household has address: ""
Household has members: []

Now we can build a small instance:

h: a Household {address: "123 Main", members: [a Person {name: "Alice"}, a Person {name: "Bob"}]}
alice: a Person {name: "Alice", household: h}
bob: a Person {name: "Bob", household: h}

The household contains member records whose household slot remains none. The separate alice and bob records point to that household. These are finite views of the same people, not a cyclic object graph. Keeping the representation finite makes the stopping case explicit; Chapter 27 handles graphs using separate vertices, edges, and visited sets.

Now we can walk the data either direction:

axioma> alice.name
"Alice"
axioma> alice.household.address
"123 Main"
axioma> alice.household.members[1].name
"Alice"
axioma> alice.household.members[2].name
"Bob"

9.2 First worked example: counting household members

First, two cooperating functions:

# person_household_size: Person -> Integer
# household_size: Household -> Integer

person_household_size: func(p) [
  if p == none then 0
  else household_size(p.household)
]

household_size: func(h) [
  if h == none then 0
  else len(h.members)
]

println(person_household_size(alice))   # 2
println(person_household_size(bob))     # 2
println(household_size(h))              # 2

These functions follow one link, but are not mutually recursive: person_household_size calls household_size, which returns without calling back. Mutual recursion needs a cycle in the call graph, not a cycle in the data. The next example demonstrates that distinction.

A note on call-order. person_household_size calls household_size, but we defined person_household_size first. In Axioma that works because function bodies are looked up at call time, not at definition time. By the time we call person_household_size(alice), both functions exist.

9.3 Second worked example: arithmetic expressions

Time for a richer example. We’ll model arithmetic expressions like (1 + 2) * (3 - 4). The data definition is:

An Expression is one of: - a Literal number, or - an Operator application — a kind ("+", "-", "*", "/") plus a left Expression and a right Expression.

That’s not purely mutual recursion in the textbook sense (Operator points to Expression, but Literal doesn’t) — it’s variant recursion: one type with two flavors, and one flavor recurses. We’ll use two Concepts to model the two flavors.

concept Lit
Lit has value: 0

concept Op

Op has kind: "+"
Op has lhs: none
Op has rhs: none

To build (1 + 2) * (3 - 4):

e1: a Lit {value: 1}
e2: a Lit {value: 2}
plus: an Op {kind: "+", lhs: e1, rhs: e2}

e3: a Lit {value: 3}
e4: a Lit {value: 4}
minus: an Op {kind: "-", lhs: e3, rhs: e4}

expr: an Op {kind: "*", lhs: plus, rhs: minus}

Now the evaluator. The data has two flavors; the evaluator has two branches:

eval_expr: func(e) [
  if e is Lit then e.value
  else if e is Op then eval_op(e)
  else none
]

eval_op: func(e) [
  l: eval_expr(e.lhs)
  r: eval_expr(e.rhs)
  if e.kind == "+" then l + r
  else if e.kind == "-" then l - r
  else if e.kind == "*" then l * r
  else if e.kind == "/" then l / r
  else none
]

println(eval_expr(e1))      # 1
println(eval_expr(plus))    # 3
println(eval_expr(minus))   # -1
println(eval_expr(expr))    # -3

Two new ideas at work:

1. The is test. e is Lit returns true if e was built with a Lit. We dispatch on the kind of object, not on a field. (Note that is only tests — declaring the concept is concept Person, as in Chapter 9’s data definitions.)

2. Two functions that call each other. eval_expr dispatches an operator to eval_op; eval_op calls eval_expr on each child. This is mutual recursion. Every cycle moves to smaller sub-expressions, and a literal stops the recursion. The same evaluator could be written as a single recursive function, but splitting dispatch from operator evaluation exposes the call graph.

This is, in miniature, an interpreter — a program that takes data describing a computation and runs that computation. Chapter 22 builds it out into a full meta-circular evaluator for Axioma itself.

9.4 The shape

When data shapes A and B point at each other, the functions that process them point at each other too:

process_a: func(a) [
  ... process_b(a.field_of_type_B) ...
]
process_b: func(b) [
  ... process_a(b.field_of_type_A) ...
]

Each function gets one branch per shape of its argument, and the recursive calls hop between types as needed.

When data has variants (one type with several flavors), one function with one branch per variant does the job — or you split into one function per variant. Either is fine.

9.5 Reflection

We started Part II with arrays — the simplest arbitrary-size data shape. We ended with mutual recursion — the most general. The through-line is the design recipe unchanged:

1. Write down the data definition.
2. From the data definition, derive the function template — one branch per case.
3. Fill in the branches by combining the recursive results.

That recipe has now been applied to four different data shapes: fixed-size atoms (Part I), arrays (Chapter 7), trees (Chapter 8), and mutually-recursive concept graphs (this chapter). Every new data shape you ever meet — JSON, ASTs, file systems, scene graphs — you process the same way.

You’re done with Part II. The rest of the book is about abstraction (factoring out the parts of these patterns that don’t change so you can reuse them), stateful programming (when mutation is the right tool), and Axioma-specific extensions (Concepts vs. sum types, enums, multi-valued logic, logic programming, and the meta-circular evaluator).

Exercises

Exercise 9.1 — name_in_household

Given a Person, return an array of the names of all members of their household.

• For alice: ["Alice", "Bob"]
• For a person whose household is none: []

Exercise 9.2 — count_total_people

Given an array of Households, return the total number of people across all of them.

• count_total_people([]) → 0
• count_total_people([h1, h2]) → sum of len(h1.members) + len(h2.members)

Exercise 9.3 — expr_depth

Add an expr_depth(e) function that returns the depth of the expression tree. A Lit has depth 1; an Op has depth 1 + max(depth(lhs), depth(rhs)).

• expr_depth(a Lit {value: 7}) → 1
• expr_depth((1 + 2)) → 2
• expr_depth((1 + 2) * (3 - 4)) → 3

Exercise 9.4 — count_ops

Count the number of Op nodes in an expression (i.e., the number of binary operators).

• count_ops(a Lit {value: 7}) → 0
• count_ops((1 + 2)) → 1
• count_ops((1 + 2) * (3 - 4)) → 3

Exercise 9.5 — add_one_to_lits

Build a new expression in which every Lit has its value increased by 1, but the operator structure is unchanged.

• add_one_to_lits(a Lit {value: 7}) → a Lit {value: 8}
• add_one_to_lits((1 + 2)) → (2 + 3)

Hint: this is the “build a new tree” pattern from §8.8 applied to the two-variant Expression shape.

Exercise 9.6 (open) — extend the evaluator

Add support for a new operator of your choice — perhaps "%" (modulo), "^" (exponent), or "max" (the larger of two sub-results). What does the data definition gain? What changes in the evaluator?

Or — a harder twist — add a unary operator like "neg" (numeric negation) by introducing a third Concept UnaryOp and updating the evaluator to dispatch on three flavors instead of two.

End of Part II. Part III turns these patterns into reusable abstractions: map, filter, reduce, lambda functions, and local definitions.

Solutions to selected exercises: Chapter 9 · Solutions in Appendix C. (Repo file: exercises/solutions/ch09_solutions.md.)

Chapter 10 · Higher-Order Functions

What this chapter is. Part II ended with five recursive functions that all look the same. This chapter names what’s common, hands you three pre-written tools — map, filter, reduce — and shifts your job from “write the recursion” to “describe the transformation.” Broadcasting then extends a scalar rule to compatible collections, and fusion connects those rules without intermediate arrays.

10.1 The repetition you already noticed

At the end of Chapter 7 we listed the bodies of sum_list, count_list, largest, contains, and last_element side by side. They all had the same shape — peel off first(arr), recur on rest(arr), combine. Only the combining rule changed.

In Chapter 7 §7.8 I called that structural recursion. Now we’re going to take the next step: pull the recursion itself out into a reusable function, and pass in the combining rule as a parameter.

That parameter is another function. A function whose argument is a function is called a higher-order function — and writing them is the single biggest leap in your power as a programmer since you learned if.

10.2 First example — map

The pattern. “Take every element of an array, do something to it, return a new array of the results.”

We saw this in §7.5 exercise double_each: take [1, 2, 3], double each one, get [2, 4, 6]. We could also halve each one, or square each one, or convert each one to a string. The something changes; the for-every-element part doesn’t.

The for-every-element part has a name: map.

#language axioma/beginner
nums: [1, 2, 3, 4, 5]
double: func(x) [x * 2]
println(map(double, nums))    # [2, 4, 6, 8, 10]

Read that aloud: “map the function double over the array nums.” map is a function that takes two arguments — a function and an array — and returns a new array.

The function we pass in doesn’t have to be defined first; we can write it inline:

#language axioma/beginner
println(map(func(x) [x * x], [1, 2, 3, 4, 5]))
# [1, 4, 9, 16, 25]

Why this is worth learning. Before map, double_each was seven lines of recursion. After map, it’s one line. The recursion is still happening — map does it internally — but you don’t have to write it yourself.

10.3 Second example — filter

The pattern. “Keep the elements that satisfy a test; throw the rest away.”

Exercise 7.4 was count_above(arr, threshold) — count how many elements exceed a threshold. A close cousin: list the elements that exceed the threshold. The test changes (>10, even, prime, non-empty…); the keep-the-passing-ones part doesn’t.

The keep-the-passing-ones part has a name: filter.

#language axioma/beginner
nums: [3, 1, 4, 1, 5, 9, 2, 6]
is_big: func(x) [x > 4]
println(filter(is_big, nums))     # [5, 9, 6]
println(filter(func(x) [x % 2 == 0], nums))   # [4, 2, 6]

The function you pass to filter must return a Boolean — true to keep the element, false to drop it. By convention such a function is called a predicate, and predicate names usually read like a yes/no question: is_big, is_even, is_negative.

10.4 Third example — reduce

The pattern. “Walk through the array, combining elements with a running total.”

sum_list did this with +. largest did it with max. We could imagine product_list with *, concat_all with + on strings, all_true with and, and so on. The combining operation changes; the walk-and-accumulate part doesn’t.

The walk-and-accumulate part has a name: reduce.

#language axioma/beginner
nums: [1, 2, 3, 4, 5]
add: func(acc, x) [acc + x]
times: func(acc, x) [acc * x]
println(reduce(add, 0, nums))     # 15   (1+2+3+4+5)
println(reduce(times, 1, nums))   # 120  (1*2*3*4*5)

reduce takes three arguments: the combining function, a starting value (the accumulator — what the running total should be before any element is seen), and the array.

The combining function takes two arguments: the running total so far, and the next element. It returns the new running total.

Two common pitfalls:

• Wrong starting value. Starting reduce(add, 0, ...) gives the right sum because 0 is the identity for addition (adding 0 doesn’t change a number). For * the identity is 1, not 0. For string concatenation it’s "". For max it’s the smallest possible value (which is awkward — see below).
• Wrong combining direction. Some functions don’t matter (+, *, max). Others do — try reduce(func(a, b) [a - b], 0, [1, 2, 3]): you get -6, not -4 or 4, and which one you wanted depends on whether you’re folding from the left or the right.

reduce in Axioma folds from the left: it computes ((0 + 1) + 2) + 3.

When the direction matters, you can say it explicitly. Axioma has the Scheme-faithful folds foldl and foldr (with fold_left / fold_right spellings too):

#language axioma/beginner
foldl(func(acc, x) [acc - x], 0, [1, 2, 3])   # -6  — ((0-1)-2)-3, same as reduce
foldr(func(x, acc) [x - acc], 0, [1, 2, 3])   # 2   — 1-(2-(3-0))

foldl calls its function fn(acc, elem) (the accumulator first, like reduce); foldr calls fn(elem, acc) and works from the right end inward. Two more relatives in the same family: append_map(fn, xs) maps a collection-returning function and concatenates the results (Scheme’s append-map; also spelled flatmap / mapcat), and for_each(fn, xs) runs fn for its side effects and returns nothing.

10.5 Worked example — mean in three lines

Problem. Compute the average of an array of numbers.

1. Data. A non-empty array of numbers.

2. Signature.

# mean: Array -> Number

3. Examples.

# mean([4])               = 4
# mean([1, 2, 3])         = 2
# mean([10, 20, 30, 40])  = 25

4-5. Template / body. Sum the array, divide by length:

#language axioma/beginner
mean: func(arr) [
  reduce(func(a, b) [a + b], 0, arr) / len(arr)
]

6. Tests.

println(mean([4]))               # 4
println(mean([1, 2, 3]))         # 2
println(mean([10, 20, 30, 40]))  # 25

Three lines. Compare with the equivalent recursive version (probably ten lines, with a helper for sum). The recursion is hidden inside reduce; we just told it what to do with each element.

10.6 Combining HOFs — the pipeline shape

The real power emerges when you chain them. Here’s “average of the even numbers larger than 10”:

#language axioma/beginner
nums: [3, 11, 14, 17, 22, 8, 25, 30]
above_10: filter(func(x) [x > 10], nums)
evens: filter(func(x) [x % 2 == 0], above_10)
total: reduce(func(a, b) [a + b], 0, evens)
answer: total / len(evens)
println(answer)    # 22  (14 + 22 + 30 = 66, 66 / 3 = 22)

Each line is one transformation. The variables (above_10, evens, total) name the intermediate result — they’re not strictly necessary, but they document the steps.

In Chapter 12 we’ll learn how to make those intermediate names local to a single computation, so they don’t clutter the top level. For now, just appreciate that each step is a one-liner.

There is a second way to build a pipeline: instead of naming each intermediate result, name the transformation and glue the pieces together into a single reusable function. That is composition, and it gets its own treatment in §10.10.

10.7 Writing your own higher-order functions

map, filter, and reduce are not magic. They’re recursive functions you could have written yourself. Here is map in full — same structural-recursion template you saw in Chapter 7:

#language axioma/beginner
my_map: func(f, arr) [
  if len(arr) == 0 then []
  else [f(first(arr)) | my_map(f, rest(arr))]
]
println(my_map(func(x) [x * 2], [1, 2, 3]))   # [2, 4, 6]

The cons expression [f(first(arr)) | my_map(f, rest(arr))] places the transformed first value before the recursively transformed tail. An equivalent concatenation is [f(first(arr)),] + my_map(f, rest(arr)). The comma in that alternative distinguishes the one-element Array from a branch block (§6.6).

Two HtDP-classic HOFs not built into Axioma are any? and all?: “does any element satisfy this predicate?” and “do all elements satisfy it?” Defining them is a great exercise in HOF composition (and in fact you’ll do exactly that as Exercise 10.5 below):

#language axioma/beginner
any_of: func(pred, arr) [
  if len(arr) == 0 then false
  else if pred(first(arr)) then true
  else any_of(pred, rest(arr))
]
println(any_of(func(x) [x < 0], [3, 1, -1, 4]))   # true
println(any_of(func(x) [x < 0], [3, 1, 4]))       # false