Ridgun

The language itself: a compiler that compiles itself, the stable project tool, the specification and the book

04-pattern-matching-and-guards.md208 lines · 10.2 KBRaw

1	# Chapter 04: Goodbye `if/else`, Goodbye `while` (Pattern Matching, Guards, and TCO)
2
3	When you tell someone that Ridgun has no `if`, no `else`, no `switch`, no `for`, and no `while` keyword, they usually look at you as if you just said you're going to build a house without a hammer or nails:
4
5	> "No `if` and no `while`? Then how on earth do I make a decision or loop over a million items?"
6
7	It turns out that `if/else` and `while` are fairly blunt tools inherited from how hardware jumps (`GOTO`) worked in the 1950s. In Ridgun we replace them with three pieces that fit together like a glove:
8	1. *Pattern Matching* (when deciding based on the shape or exact value of data).
9	2. Boolean guards `\|` (when deciding based on a condition or range).
10	3. Tail recursion with TCO (which the compiler turns into a blazing-fast native `loop` under the hood).
11
12	Let's see them in action.
13
14	---
15
16	## 4.1. Pattern Matching: When the Argument Already Gives You the Answer
17
18	We saw a preview of this in the previous chapter. Instead of taking a generic variable `x` and opening five `if (x == ...)` branches inside the function body, in Ridgun you put the cases right at the front door of the function:
19
20	```ridgun
21	http status Int => String
22	http status 200 = "OK: Everything went smoothly"
23	http status 301 = "Moved permanently"
24	http status 404 = "Not found (did you check under the couch?)"
25	http status 500 = "Server is on fire"
26	http status n = "Unknown status code: {n}"
27	```
28
29	Ridgun tests the rows from top to bottom:
30	- If `404` comes in, it jumps straight to the third row.
31	- If `418` comes in, none of the first four rows match, so it falls through to the last row (`n`), which catches any integer and names it `n` so you can format it.
32	- And what if in the last case you don't even care what number it was? Put an underscore `_` (wildcard) and forget about it: `http status _ = "Other status code"`.
33
34	---
35
36	## 4.2. Boolean Guards (`\|`): Your Scalpel for Ranges, Conditional Bindings, and Decision Trees
37
38	"Okay, pattern matching is great when I'm looking for `200` or `404`. But what if I want to check whether `score >= 5` or `age > 18 and age < 65`? I'm not going to write 47 rows for every number between 18 and 65!"
39
40	Of course not! That is what guards (`\|`) are for.
41
42	When the result depends on an inequality or a logical combination, right after the `=` of the function (or of any local variable) you open a ladder of vertical bars `\|`:
43
44	```ridgun
45	grade Int => String
46	grade score =
47	\| score < 0 = "Impossible score (negative points?)"
48	\| score < 5 = "Fail"
49	\| score < 7 = "Pass"
50	\| score < 9 = "Merit"
51	\| score <= 10 = "Distinction"
52	\| otherwise = "Off the scale"
53	```
54
55	Look closely at how it works:
56	- The `=` sign on the header line (`grade score =`) aligns underneath `=>` just like in any other function.
57	- Below it, you read top to bottom just like a rate card: each `\| condition = result` line is checked in order. The moment one evaluates to `True`, it returns that result and we're done.
58	- At the end you place `\| otherwise = ...`, which means "in any other case" (your safety net so no path ever falls through without a return value).
59
60	### Clear Lowercase Boolean Logic (`and`, `or`, `xor`, `not`)
61	Have you ever noticed how many languages use `\|` for bits, `\|\|` for booleans, `!` for negation... so when you read a complex condition it looks like a cat walked across your keyboard (`if (!a && (b \|\| c))`)?
62
63	In Ridgun, since `\|` is already the sacred symbol for guards and algebraic data types, and `\|\|` is the parallelism operator, boolean operators are written as clear lowercase words:
64
65	- `and`: both sides must hold, using short-circuit evaluation (`age >= 18 and has_license`: if the left side is `False`, the right side is not evaluated).
66	- `or`: at least one side holds, using short-circuit evaluation (`day == "saturday" or day == "sunday"`: if the left side is `True`, the right side is not evaluated).
67	- `xor`: one or the other holds, but not both at once.
68	- `not`: flips the boolean (`not (is empty text)`).
69	- `<`, `>`, `<=`, `>=`: compare both numbers (`Int`, `Float`) and `String` values in lexicographical UTF-8 order (`"alpha" < "beta"`).
70
71	Look how clean the classic leap-year check becomes:
72
73	```ridgun
74	is leap year Int => Bool
75	is leap year y =
76	\| (y % 400) == 0 = True
77	\| (y % 4) == 0 and (y % 100) != 0 = True
78	\| otherwise = False
79	```
80
81	Zero cryptic symbols. Someone who has never seen Ridgun can read it and understand it on the first try.
82
83	### Conditional Local Variables (`x =` + `\|`)
84	Because every `=` in Ridgun follows the same universal rule, you can also use `\|` to assign a local variable without having to extract a separate helper function:
85
86	```ridgun
87	ticket price Int Bool => Int
88	ticket price base is_large_family =
89	discount =
90	\| is_large_family = 20
91	\| base > 100 = 10
92	\| otherwise = 0
93	base - (base * discount / 100)
94	```
95
96	### Nested Decision Trees and the Compact Terminator `\|.`
97	"What if inside a `\| cond =` or `\| otherwise =` branch I want to open another sub-tree of `\|` guards 3 or 4 levels deep, and then return to an outer level?"
98
99	You can nest `\|` inside `\|` as many levels deep as you want. And when a nested `\|` block finishes while more branches of a parent level (or more sequential statements in the block) continue below it, you place `\|.` at the end of its last line (`\| otherwise = value \|.`) to indicate with zero ambiguity that the sub-tree is closed and you are stepping back to the parent level:
100
101	```ridgun
102	route request Int Int Bool Bool Int Int => Int
103	route request method role signed is_admin size_kb limited =
104	\| method == 0 =
105	\| size_kb == 0 = 204
106	\| otherwise = 200 \|.
107	\| method == 1 =
108	\| not signed = 401
109	\| otherwise =
110	-- Level 2: signed POST request
111	\| limited > 0 =
112	-- Level 3: rate-limit check
113	\| is_admin =
114	-- Level 4: administrator override
115	\| size_kb > 10000 = 413
116	\| otherwise = 202 \|.
117	\| otherwise = 429 \|.
118	\| size_kb > 1000 =
119	-- Level 3: back from Level 4 thanks to `\|.`
120	\| role >= 2 and is_admin = 201
121	\| otherwise = 413 \|.
122	\| otherwise = 201 \|.
123	\| otherwise = 405
124	```
125
126	Notice how clean that is:
127	- In a flat 1-level guard tree (or at the very end of the entire function) you never need to write `\|.` (that would be unnecessary noise).
128	- You only write `\|.` when closing a nested branch that is followed below by a branch at an outer level.
129
130	### Multi-Line Blocks Inside a Guard (`\| cond =` + indented block)
131	Just as you can open a multi-line indented block after the `=` of a normal function, after the `=` of any `\| cond =` or `\| otherwise =` guard you can also add a newline and open a sequential block:
132
133	```ridgun
134	adjust window Int Int => Int
135	adjust window idx limit =
136	\| idx >= limit =
137	cap = limit - 1
138	scaled = cap * 2
139	scaled + 10
140	\| otherwise =
141	next = idx + 1
142	next * 2
143	```
144
145	Each guard branch gets its own clean local scope, and its last line is the value returned by that branch.
146
147	---
148
149	## 4.3. "No `while`? Won't the Stack Blow Up If I Scan a Large File?"
150
151	Let's address the elephant in the room.
152
153	If you come from Python, Java, or JavaScript, you were taught from day one that "recursion looks pretty on a university whiteboard, but in the real world it blows the call stack (`StackOverflowError`) after 1,000 iterations; use a `while` loop".
154
155	That is true in languages that do not optimize tail calls. But in a systems functional language like Ridgun, tail recursion IS a `while` loop dressed up as a pure function.
156
157	### What Is the Difference Between Normal Recursion and Tail Recursion?
158	Look at these two functions that count down from `n` to `0` while summing the numbers:
159
160	```ridgun
161	-- Version A: NORMAL recursion (leaves pending work for the return trip)
162	sum slow Int => Int
163	sum slow 0 = 0
164	sum slow n = n + (sum slow (n - 1))
165
166	-- Version B: TAIL recursion (keeps a running total in `acc`)
167	sum fast loop Int Int => Int
168	sum fast loop 0 acc = acc
169	sum fast loop n acc = sum fast loop (n - 1) (acc + n)
170	```
171
172	- In Version A, before it can compute `n + ...`, the function has to wait for `sum slow (n - 1)` to finish. That forces the CPU to push `n` onto the call stack at every step.
173	- In Version B, the call to `sum fast loop` is the very last thing that happens on the line. Nothing is left waiting after it. You pass the updated running total right into `acc + n`.
174
175	### `ridgunc`'s Magic Trick (TCO: Tail-Call Optimization)
176	When `ridgunc` compiles `sum fast loop`, it sees that the function calls itself in tail position and says:
177
178	> "Why would I allocate a new stack frame when the current one is finished? I'll just overwrite `n` with `n - 1`, overwrite `acc` with `acc + n`, and jump back to the top with a native `loop { ... continue; }`."
179
180	The result:
181	1. You can call `sum fast loop 100_000_000 0` (one hundred million iterations) and it will consume exactly 0 extra bytes of stack.
182	2. It runs at the exact same speed as a hand-written `while` loop in Rust or C, without you having to declare a single mutable variable in your Ridgun code.
183
184	---
185
186	## 4.4. The Master Pattern You Will Use in Every Ridgun Program
187
188	Whenever you would think in another language "I'll write a `while` loop with an index `i` and an accumulator", in Ridgun you write a pair of functions like this (the clean public function and its tail-recursive `_loop` helper):
189
190	```ridgun
191	find char loop String Int Int Int => Int
192	find char loop text pos end target =
193	\| pos >= end = -1
194	\| (str char at text pos) == target = pos
195	\| otherwise = find char loop text (pos + 1) end target
196
197	find char String Int => Int
198	find char text target = find char loop text 0 (str len text) target
199	```
200
201	Look at the three guards in `find char loop`:
202	1. Did I reach the end (`pos >= end`)? Return `-1` (end of loop).
203	2. Did I find the character at `pos`? Return `pos` (end of loop).
204	3. Not this one? Advance to the next index (`pos + 1`) with a tail call (which the compiler turns into `continue;`).
205
206	Clean, immune to clobbered-state bugs, and fast as lightning.
207
208	In Chapter 05 we will get our hands on data collections: lists, tuples, functions that accept an arbitrary number of arguments (`...`), and J/APL-style sequence masks.