General theory, before any specifics. New acronyms: SSOT.
-
TDD (test-driven development): Red, green, refactor: write a failing test (red), write just enough code to pass (green), then clean up with the tests as a safety net (refactor). This code's dialect: every demo reseeds, prints, then asserts — no crash means pass — and the harness never dies mid-suite. run traps a failing demo and prints its stack dump, so --all can count failures and keep going:
function run(funs,w, ok,msg)
srand(the.seed)
if funs[w] then
ok, msg = xpcall(funs[w], debug.traceback)
if not ok then print(msg) end
return ok end end
The eg table is the whole test framework: demos are just entries, so adding a test is one assignment, no registration ceremony:
eg = {} -- the demo table
eg["--col"] = function( n) -- green: watch, then lock in
n = adds{1,2,3,4,5}
print(show{mu=n:mid(), sd=n:div()})
assert(n:mid() == 3) end
eg["--ent"] = function( s)
s = adds({"a","a","b"}, Sym())
assert(abs(s:div() - 0.918) < 0.01) end
eg["--broke"] = function() -- red: prints a stack dump;
assert(2 + 2 == 5) end -- --all counts it, moves on
But beware: test suites are code, with their own maintenance bill — suites of 30 to 50 percent of total code size are not uncommon. So be choosy. A test with zero assertions tests nothing: keep the assert. Mere line coverage can mislead — touching a line is not checking its meaning; prefer a few detailed checks on the code's semantics over many shallow ones. And keep long-running tests out of the suite: slow suites do not get run, and an unrun suite protects nothing.
-
Python slices: x[lo:hi] is items lo to hi-1; blanks mean "from the start" or "to the end"; negatives count from the end:
x = [a, b, c, d, e]
0 1 2 3 4 <- index
-5 -4 -3 -2 -1 <- negative index
x[:2] = [a, b] x[2:] = [c, d, e]
x[-2:] = [d, e] x[1:3] = [b, c]
x[:] = a copy of x
In 101.py: s[:1]=="-" (first char), s[1:] (the rest), a[2:] (strip a leading "--").
-
Python f-strings: f"..." runs the braced parts as code; after a colon comes a format spec, which may itself be computed:
| write | get |
|---|
| f"{x:.0f}" | x, zero decimals |
| f"{x:.{the.round}f}" | x, the.round decimals |
| f":{k} {say(v)}" | any expression allowed |
That second row is why --round=4 changes every number 101.py prints: one policy value, one printing mechanism.
-
Python doc strings: A string as the first statement of a file (or def) is stored, not executed: __doc__. 101.py's doc string is its usage message (-h just prints it) AND its settings table — settings(__doc__) regx-scrapes the defaults out of the help text. One string: help, defaults, documentation. That is SSOT and mechanism-policy in thirteen lines of Python.
-
Python environ: os.environ is a dict of the shell's variables. Lets one default live outside the code, per machine:
MOOT = (os.environ.get("MOOT") or
os.path.expanduser("~/gits/moot"))
Set MOOT in your shell and 101.py finds your data; set nothing and a sane default fires.
-
Python argv: sys.argv is the command line, split on spaces: argv[0] the script name, the rest yours. 101.py walks it twice — first pass updates settings from --key=val, second runs any named tests:
for a in sys.argv[1:]:
if a[:2]=="--" and "=" in a:
k,v = a[2:].split("=",1)
if k in vars(the): setattr(the, k, thing(v))
for a in sys.argv[1:]:
if (n := "test_"+a) in funs:
random.seed(the.seed); funs[n]()
Note that last line; see RNG, next.
-
RNG (random number generator): Computers do not roll dice. An RNG is a deterministic formula that looks random; from the same seed, the same stream, forever. This course uses the Park-Miller minimal standard (one multiply, one modulo):
Seed = (16807 * Seed) % 2147483647
The point of need: RESET the seed before every run. Then every experiment replays exactly — same seed, same "random" numbers, same result — on your machine, your grader's, and in Lua or Python alike (ports are graded by diff-ing the two streams). 101.py does this before every test:
random.seed(the.seed); funs[n]() # reset, then run
Forget the reset and your "bug" changes every run. Reset, and science becomes repeatable.
-
Python reflection (self-registering tests): How does a new demo join the command line? In Lua, by hand: eg["--tree"] = function() ... end. Python can do the registration itself, since globals() is just a dict of every top-level name:
def test_tree():
"recursive contrast splits; leaves show row counts"
show(tree(Tbl(csv(the.file))))
eg = {"-" + k[5:]: f for k, f in globals().items()
if k.startswith("test_")}
def run(f): # reseed, call f, catch crashes
seed(the.seed)
try: f()
except Exception: traceback.print_exc()
if __name__ == "__main__":
for j, s in enumerate(sys.argv):
if f := eg.get("-" + s.lstrip("-")): run(f)
elif (k := s.lstrip("-")) in the:
the[k] = atom(sys.argv[j + 1])
Four tricks, top to bottom. Self-registration: the dict comprehension scans globals(), keeps every name starting test_, strips the prefix (k[5:]) and maps the flag -tree to the function itself. Write def test_x and -x exists; delete it and the flag is gone. Mechanism-policy again: the policy is a naming convention, the mechanism two lines. And the docstring rides along as the flag's help text (f.__doc__). run() = reseed, then shield: reseed first, so every demo replays exactly (see RNG, above). Then try/except: a crashing demo prints its full stack (traceback) and the loop moves on, so one failure cannot hide the others. The main guard: dispatch fires only when this file is the script the user ran; importing it defines everything and runs nothing (Lua's go(eg) plays the same role). One pass over argv: the walrus := names a value inside the test. lstrip("-") accepts -tree or --tree. A flag naming a test runs it; a flag naming a settings key takes the NEXT argument (sys.argv[j + 1]), coerces it with atom, and updates the. Order matters: python x.py -seed 42 -tree resets the seed before the test fires.
-
regx (regular expressions): Little languages for matching text. Just enough for 101.py and the Lua at its side (Lua patterns use "%" where Python uses "\", and "-" where Python uses "*?"):
| means | python | lua |
|---|
| word char (letter/digit) | \w | %w |
| whitespace / non-space | \s and \S | %s and %S |
| letter / lowercase | [a-zA-Z] | %a and %l |
| any chars, lazy | .*? | .- |
| start / end of string | ^ and $ | ^ and $ |
| one char from a set | [^=\n] | [+-] |
| capture a group | ( ) | ( ) |
| all matches | re.findall | s:gmatch |
| find / replace | re.search, re.sub | s:find, s:gsub |
| a literal dot | \. | %. |
The two worked examples, one per language — 101.py scraping its --key ... = default pairs from its doc string, ezr picking a column's kind off its first letter:
pat = r"--(\w+)\s+[^=\n]*=\s*(\S+)" # 101.py
return (name:find"^%l" and Sym or Num)(name,at) -- ezr.lua
-
Gaussian (mean, second moment): The bell curve:
* *
* *
* *
* *
* *
* *
* * * *
--------+-----------+-----------+----
mu-sd mu mu+sd
(68% of the data falls
within mu +/- 1*sd)
Summarized by two moments: the first moment μ (the mean, mu) and, from the second moment, the spread (m2 = sum of squared deviations, so sd = √(m2/(n-1))). Two tricks make these course-critical: both update incrementally, one value at a time (welford, week 1); and two summaries subtract without resampling. From ezr-eg1's --without demo: pour {10,20,30} into a summary of {1,2,3,4,5}, subtract a summary of {10,20,30}, and mu and sd of {1..5} come back exactly. Learn, unlearn, in O(1) — no stored data (see stream, week 1).
-
pdf (probability density function): The bell curve, or any curve like it: the relative likelihood of each value. For a normal with mean μ and deviation σ, the likelihood of x falls off as the square of its distance from the mean:
- f(x) = 1/(σ√(2π)) · e-(x-μ)²/(2σ²)
This code never evaluates a pdf directly — only areas under it matter, and those come from the cdf.
-
cdf (cumulative distribution function): The fraction of a population at or below a value: the area under the pdf up to x. Monotone, 0..1 — which makes it a natural normalizer: norm maps any cell to "what fraction of this column sits below you?". The normal cdf has no closed form, so ezr uses a logistic approximation (good to about ±1%), with the z-score clamped to ±3:
- cdf(z) ≈ 1 / (1 + e-1.702z)
function NUM.norm(i,v, z)
if v == "?" then return v end
z = (v - i.mu) / (i:div() + TINY)
return 1 / (1 + exp(-1.702 * max(-3, min(3, z)))) end
A bonus, for later: discretization rides on this for free. To turn any number into a small bin id, take floor(the.bins · num:norm(23)) — since norm is the cdf, equal-width slices of 0..1 give (roughly) equal-frequency bins of the data.
-
noir: Nominal, Ordinal, Interval, Ratio (Stevens 1946): the four scales of measurement. This code collapses them to two: symbols you can only count (nominal) and numbers you can subtract (interval and up). One header letter decides which:
-- Column kind from the first letter: lowercase makes a SYM,
-- uppercase a NUM.
function Col(name,at)
return (name:find"^%l" and Sym or Num)(name,at) end
-
Num: The summary of a numeric column: count n, mean mu, and m2 (the sum of squared deviations from the mean, from which the standard deviation falls out). Nothing else is stored — not the data, just three numbers. A trailing "-" in the name means "goal: minimize".
function Num(name,at)
name = name or ""
return new(NUM, {at=at or 1, name=name, n=0, mu=0, m2=0,
heaven = name:find"-$" and 0 or 1}) end
That last line, in Python, uses the True/False-is-1/0 trick (bools ARE ints, so arithmetic on a test needs no if):
heaven = 1 - (name[-1] == "-") # True==1, False==0
-
Sym: The summary of a symbolic column: count n and a table of counts has. Again, no data kept — just the histogram.
function Sym(name,at)
return new(SYM, {at=at or 1, name=name or "", n=0, has={}}) end
-
columnProtocol: Num and Sym answer the same eight questions — one polymorphic protocol, two implementations. Everything downstream (tables, distance, trees, cuts) talks to the protocol, never to the type:
| question | Num answers | Sym answers |
|---|
| add | welford update of mu, m2 | bump a count in has |
| sub | welford, run backwards | drop a count |
| mid | mean | mode |
| div | standard deviation | entropy |
| norm | cdf position, 0..1 | identity |
| dist | gap of normed values | 0 if same else 1 |
| holds | x ≤ v | x == v |
| reset | zero mu, m2 | empty has |
Two samples, both sides of add. Note the shared conventions: "?" (missing) is ignored on the way in, and inc=-1 runs the summary backwards (see stream):
function NUM.add(i,v,inc, d)
if v == "?" then return v end
inc = inc or 1
i.n = i.n + inc
d = v - i.mu
i.mu = i.mu + inc * d / i.n
i.m2 = i.m2 + inc * d * (v - i.mu); return v end
function SYM.add(i,v,inc)
if v == "?" then return v end
inc = inc or 1
i.n = i.n + inc
i.has[v] = inc + (i.has[v] or 0)
if i.has[v] <= 0 then i.has[v] = nil end
return v end
-
welford: Welford's 1962 one-pass update: mean and variance from a stream, no stored data, no catastrophic cancellation. After each value v:
- n' = n+1
- d = v - μ
- μ' = μ + d/n'
- m2' = m2 + d(v - μ')
then sd = √(m2/(n-1)). The NUM.add code above is exactly these four lines. Run with inc=-1 the algebra inverts, which is what makes summaries subtractable.
-
stream: A summary you can update — and un-update — one datum at a time, in constant memory. The inc argument (+1 or -1) means adding is O(1) and so is deleting, so any add-and-forget sweep over n items runs in linear time. Remember that: it matters later. Trees will score EVERY possible split of a sorted column in one linear pass — adding each row to the summary on one side of the cut while forgetting it from the other — where naive rebuilding would cost O(n²). It is also why (a+b)-b == a is a testable law (--without, --sub in ezr-eg1).
function NUM.reset(i) i.n, i.mu, i.m2 = 0, 0, 0 end
function SYM.reset(i) i.n, i.has = 0, {} end
-
mid (mode, mean): The most frequent symbol: a Sym's answer to mid ("what is typical here?"). The mean is the same question asked of numbers — both are one value standing in for the whole column. That is why mid is one protocol slot, not two functions with different names:
function SYM.mid(i, hi,out)
hi = -1
for k, n in pairs(i.has) do
if n > hi then hi, out = n, k end end
return out end
function NUM.mid(i) return i.mu end
-
diversity (entropy, standard deviation): Shannon 1948: the spread of a symbol column, in bits — the mean surprise of drawing from counts pk = nk/n:
All-same symbols: 0 bits. Uniform over k symbols: log2 k bits. Variance (or sd) is the same question asked of numbers — "how far is this column from settled?" — which is why div ("diversity") is one protocol slot with two spellings:
function SYM.div(i)
return sum(i.has, function(n, p)
p = n / i.n
return -p * log(p) / log(2) end) end
function NUM.div(i)
return i.n < 2 and 0 or sqrt(max(i.m2,0) / (i.n-1)) end
The two analogies are one design rule: every protocol slot names a question; each type answers in its own dialect. Central tendency: mean, mode. Diversity: sd, entropy. Trees built on div therefore handle numeric and symbolic goals with the same code.
New acronyms: none. New terms: Tbl, minkowski, distx, heaven, disty.
-
Tbl: Rows, plus the column summaries those rows built. Row 1 of any source is the header, and the header alone decides each column's kind (noir) and role: a trailing "!" is the class, "+" or "-" a goal (a y column), "X" is ignored, the rest are the x (independent) columns.
function Tbl(src)
src = iter(src)
return adds(src, new(TBL, {rows={}, mid=nil,
cols=Cols(src())})) end
function Cols(names, all,x,y,klass)
all, x, y = {}, {}, {}
for at, s in ipairs(names) do
all[at] = Col(s, at)
if s:find"!$" then klass = all[at]
elseif s:find"[+-]$" then y[#y+1] = all[at]
elseif s:sub(-1) ~= "X" then x[#x+1] = all[at] end end
return new(COLS, {names=names,all=all,x=x,y=y,klass=klass}) end
-
minkowski: Minkowski's p-norm, folding many per-column gaps gc (each 0..1) into one 0..1 number:
p=1 is the Manhattan distance (all gaps count equally), p=2 Euclidean; as p grows, the largest single gap dominates. the.p defaults to 2.
function minkowski(cols,f, d,n)
d, n = 0, TINY
for _, c in ipairs(cols) do n, d = n+1, d + f(c) ^ the.p end
return (d / n) ^ (1 / the.p) end
Note the design: minkowski never touches the data. It takes a function f and calls f(c) per column, on demand — a higher-order, lazy style. Each caller passes its own little lambda (distx measures row gaps, disty measures gaps to heaven), and no intermediate list of gaps is ever built. The Python analog is a generator expression, computing each term only as it is summed:
d = (sum(f(c)**p for c in cols) / len(cols)) ** (1/p)
-
distx: The gap between two rows, over the x columns only: each column measures its own 0..1 gap (dist in the columnProtocol), and minkowski folds them. An unknown "?" assumes the worst: symbols that might differ, do; a missing number is pushed to whichever end is further away. That rule has a name — the Aha heuristic, from the instance-based learning literature: when ignorance is total, assume maximum distance.
function SYM.dist(i,a,b)
if a == "?" and b == "?" then return 1 end
return a ~= b and 1 or 0 end
function NUM.dist(i,a,b)
if a == "?" and b == "?" then return 1 end
a, b = i:norm(a), i:norm(b)
if a == "?" then a = b > 0.5 and 0 or 1 end
if b == "?" then b = a > 0.5 and 0 or 1 end
return abs(a - b) end
function TBL.distx(i,row1,row2)
return minkowski(i.cols.x, function(c)
return c:dist(row1[c.at], row2[c.at]) end) end
-
heaven: The best value a goal column can hope for, in normalized 0..1 space: 0 for a minimize goal (trailing "-"), 1 for a maximize goal (trailing "+"). Decided in one line, at column birth:
heaven = name:find"-$" and 0 or 1
-
disty: The gap from a row's goals to heaven: each y column measures |norm(v) - heaven|, and minkowski folds them. 0 = best possible row, 1 = worst. No model, no weights, no training — sort rows by disty and the best float to the top (--disty in ezr-eg2). disty is an aggregation function, the zooming rival to frontier-chasing (see the Pareto zoom effect, above). Later weeks make disty the thing that costs money: it reads the goal columns, and goals are labels.
Why do labels cost? Because x and y columns have different economics. The x columns are cheap observables; the y columns are verdicts. Look at a used car: its color, cylinders and weight are free at a glance, but its honest miles-per-gallon needs a long test drive. Or: which degree you enrolled in is an x, known today; whether it was the right degree is a y that may take decades to label. In practice we are rich in x and poor in y — which is why whole later weeks (active learning) are about spending as few y's as possible.
function TBL.disty(i,row)
if i.model and row[i.cols.y[1].at] == "?" then
i:label(row) end
return minkowski(i.cols.y, function(y)
return abs(y:norm(row[y.at]) - y.heaven) end) end
