Last updated: 2026-11-21
PatLang Showcase: Bounds, Streams, Worlds and Parallel Sums
For new readers
Four more small programs, each pairing two of PatLang's paradigms to solve one problem: intervals with contracts, a coroutine with a notation of the program's own, isolated worlds with logic rules, and parallel code with exact fractions. Each sits beside the same program in Python. The first showcase page has four more pairs, and the Paradigms Guide explains each paradigm on its own.the guide unpacks each paradigm
As on the first page, the code shown is the file in the PatLang repository's showcase/ directory, and the output is what PatLang's test gates check it against, on the interpreter and as native builds for Windows and Linux. Each Python version runs in the same gates and prints the same lines, or a file of its own where the two differ by design.
Answers with guaranteed bounds
Interval arithmetic and design by contract. An interval is a number known only to lie between two bounds, and arithmetic on intervals gives an interval holding every possible result. With exact bounds, nothing is lost to rounding along the way. The program carries a measured rectangle's error through its area and perimeter, then squeezes the square root of 2 between bounds by bisection until they are under a millionth apart. A contract at every step checks that the root really is between them, and the float sqrt(2.0) lands inside the final interval.contracts catch bugs early see design by contract
# Answers with guaranteed bounds.
#
# Paradigms: interval arithmetic and design by contract.
#
# An interval is a number known only to lie between two bounds. Arithmetic on
# intervals gives an interval that contains every possible result, and with
# exact (rational) bounds nothing is lost to rounding on the way. Contracts
# then state what the bounds promise, and are checked on every call.
#
# Two uses: a measurement carried through a formula, with its error, and the
# square root of 2 squeezed between bounds until they are a millionth apart,
# with a contract at every step that the root really is between them.
#
# Given --page PATH, the program also draws the squeezing as a web page: each
# step's interval a bar in an SVG drawing, its exact bounds as the bar's
# title, narrowing on the float sqrt(2.0). SVG elements are nodes of the same
# tree as the rest of the page (lib/dom.patlang).
include "../self_hosting/lib/dom.patlang"
# ---- a measurement and its error ----
# A value measured to within plus or minus tol, as the interval it lies in.
make a function called measured takes value, tol returns iv
require tol >= 0
let iv = interval_make(value - tol, value + tol)
ensure (interval_lo(iv) <= value) and (value <= interval_hi(iv))
return iv
end
# The area of a rectangle and its perimeter, from measured sides.
make a function called area takes w, h returns a
let a = w * h
ensure interval_lo(a) <= interval_hi(a)
return a
end
print("== a measured rectangle ==")
let w = measured(2, 1 / 100)
let h = measured(3, 1 / 100)
print("width " + w + ", height " + h)
let a = area(w, h)
print("area lies in " + a)
print("so the area is " + interval_lo(a) + " at least and " + interval_hi(a) + " at most")
print("perimeter lies in " + (w * 2 + h * 2))
# ---- the square root of 2, squeezed ----
# One bisection step on [lo, hi]: keeps the half where x*x - 2 changes sign.
# The contract is the claim being made: the root is in the new interval,
# which is checked exactly, by squaring the bounds.
make a function called narrow takes iv returns half
require (interval_lo(iv) * interval_lo(iv) <= 2) and (interval_hi(iv) * interval_hi(iv) >= 2)
let lo = interval_lo(iv)
let hi = interval_hi(iv)
let mid = (lo + hi) / 2
let half = interval_make(mid, hi)
if mid * mid > 2 then
let half = interval_make(lo, mid)
end
ensure (interval_lo(half) * interval_lo(half) <= 2) and (interval_hi(half) * interval_hi(half) >= 2)
return half
end
make a function called width takes iv returns w
return interval_hi(iv) - interval_lo(iv)
end
# The page: [1, 2] drawn 400 wide, a bar 10 high for each interval in turn,
# and a line where the float sqrt(2.0) is.
make a function called squeeze_page takes seen, f returns page
let page = dom_page("Squeezing the square root of 2")
let body = dom_body(page)
dom_set_text(dom_append(body, dom_element("h1")), "Squeezing the square root of 2")
let height = "" + (vec_len(seen) * 10)
let svg = dom_append(body, dom_element("svg"))
dom_set_attr(svg, "width", "400")
dom_set_attr(svg, "height", height)
let k = 0
while k < vec_len(seen) do
let iv = vec_get(seen, k)
let bar = dom_append(svg, dom_element("rect"))
dom_set_attr(bar, "x", to_fixed((interval_lo(iv) - 1) * 400, 3))
dom_set_attr(bar, "y", "" + (k * 10))
dom_set_attr(bar, "width", to_fixed(width(iv) * 400, 3))
dom_set_attr(bar, "height", "8")
dom_set_attr(bar, "fill", "#60a5fa")
dom_set_text(dom_append(bar, dom_element("title")), "" + iv)
let k = k + 1
end
let x = to_fixed((f - 1) * 400, 3)
let line = dom_append(svg, dom_element("line"))
dom_set_attr(line, "x1", x)
dom_set_attr(line, "y1", "0")
dom_set_attr(line, "x2", x)
dom_set_attr(line, "y2", height)
dom_set_attr(line, "stroke", "#dc2626")
let last = vec_get(seen, vec_len(seen) - 1)
dom_set_text(dom_append(body, dom_element("p")), "after " + (vec_len(seen) - 1) + " steps the root lies in " + last)
return page
end
print("== the square root of 2 ==")
let root = interval_make(1, 2)
let seen = vec_new()
vec_push(seen, root)
let steps = 0
while width(root) > 1 / 1000000 do
let root = narrow(root)
vec_push(seen, root)
let steps = steps + 1
end
print("after " + steps + " steps the root lies in " + root)
print("width " + width(root) + ", under a millionth: " + (width(root) < 1 / 1000000))
let f = sqrt(2.0)
print("the float sqrt(2.0) = " + f + " lies inside: " + ((interval_lo(root) <= f) and (f <= interval_hi(root))))
# Interval arithmetic itself confirms the bracket: x*x - 2 evaluated over the
# whole interval contains zero.
let g = root * root - 2
print("x*x - 2 over the interval lies in " + g + ", which contains zero: " + ((interval_lo(g) <= 0) and (0 <= interval_hi(g))))
let args = argv()
if (list_len(args) == 2) and (args[0] == "--page") then
write_file(args[1], dom_document_html(squeeze_page(seen, f)))
end
Output:
== a measured rectangle == width [199/100,201/100], height [299/100,301/100] area lies in [59501/10000,60501/10000] so the area is 59501/10000 at least and 60501/10000 at most perimeter lies in [249/25,251/25] == the square root of 2 == after 20 steps the root lies in [741455/524288,1482911/1048576] width 1/1048576, under a millionth: true the float sqrt(2.0) = 1.4142135623730951 lies inside: true x*x - 2 over the interval lies in [-296863/274877906944,1778369/1099511627776], which contains zero: true
Given --page PATH, the program draws the bisection: one bar for each interval in turn, narrowing on a line at sqrt(2.0), with each bar's exact bounds as its tooltip. The SVG elements are nodes in the same document tree as the heading and the closing sentence, built with lib/dom.patlang.
The page it writes:
Python's standard library has no interval type, so its version writes a small class over fractions.Fraction with addition, subtraction, multiplication and printing. Outside the standard library, mpmath offers interval arithmetic on its own arbitrary-precision floats, rounded outwards. The contracts turn into assert statements, which python -O removes.
The Python version
"""The guaranteed bounds of showcase/p5_guaranteed_bounds.patlang, in Python.
Python's standard library has no interval type, so the sketch writes the
small one it needs over fractions.Fraction, with + - * and printing. (mpmath has interval arithmetic, outside the standard library, with
float bounds rounded outwards; exact bounds are what this program wants.)
PatLang has intervals built in, with exact bounds when the numbers are exact.
The contracts become asserts, which python -O removes.
Prints the same lines as the PatLang program.
"""
from fractions import Fraction
from math import sqrt
class Interval:
def __init__(self, lo, hi):
assert lo <= hi
self.lo, self.hi = lo, hi
@staticmethod
def of(x):
return x if isinstance(x, Interval) else Interval(x, x)
def __add__(self, other):
o = Interval.of(other)
return Interval(self.lo + o.lo, self.hi + o.hi)
def __sub__(self, other):
o = Interval.of(other)
return Interval(self.lo - o.hi, self.hi - o.lo)
def __mul__(self, other):
o = Interval.of(other)
ends = [self.lo * o.lo, self.lo * o.hi, self.hi * o.lo, self.hi * o.hi]
return Interval(min(ends), max(ends))
def __str__(self):
return f"[{self.lo},{self.hi}]"
def b(x):
"""A bool as PatLang prints one."""
return "true" if x else "false"
def measured(value, tol):
assert tol >= 0
iv = Interval(value - tol, value + tol)
assert iv.lo <= value <= iv.hi
return iv
def area(w, h):
a = w * h
assert a.lo <= a.hi
return a
print("== a measured rectangle ==")
w = measured(Fraction(2), Fraction(1, 100))
h = measured(Fraction(3), Fraction(1, 100))
print(f"width {w}, height {h}")
a = area(w, h)
print(f"area lies in {a}")
print(f"so the area is {a.lo} at least and {a.hi} at most")
print(f"perimeter lies in {w * 2 + h * 2}")
def narrow(iv):
assert iv.lo * iv.lo <= 2 and iv.hi * iv.hi >= 2
mid = (iv.lo + iv.hi) / 2
half = Interval(iv.lo, mid) if mid * mid > 2 else Interval(mid, iv.hi)
assert half.lo * half.lo <= 2 and half.hi * half.hi >= 2
return half
def width(iv):
return iv.hi - iv.lo
print("== the square root of 2 ==")
root = Interval(Fraction(1), Fraction(2))
steps = 0
while width(root) > Fraction(1, 1000000):
root = narrow(root)
steps += 1
print(f"after {steps} steps the root lies in {root}")
print(f"width {width(root)}, under a millionth: {b(width(root) < Fraction(1, 1000000))}")
f = sqrt(2.0)
print(f"the float sqrt(2.0) = {f!r} lies inside: {b(root.lo <= f <= root.hi)}")
g = root * root - 2
print(f"x*x - 2 over the interval lies in {g}, which contains zero: {b(g.lo <= 0 <= g.hi)}")
A calculator whose lexer is a coroutine
Syntax definitions and fibres. The calculator's operators are declared in a little notation of their own: each line gives a symbol, its precedence and the function that applies it. A syntax definition at the top of the file expands those lines, before the program runs, into calls that record each operator as a fact. The lexer is a fibre that walks the input and yields one token whenever the parser asks for one, so it never builds a list of tokens, and neither side is a state machine. Precedence climbing over the operator facts does the parsing, so a new operator is one more line in the block.
# A calculator whose lexer is a coroutine.
#
# Paradigms: syntax definitions and fibres.
#
# The calculator's operators are declared in a small language of their own,
# defined by a syntax definition: each line names a symbol, its precedence and
# the function that applies it. The definition expands, before the program
# runs, into ordinary calls that record each operator as a fact.
#
# The lexer is a fibre. It walks the input and yields one token at a time; the
# parser asks for the next token when it wants one, so neither is written as
# a state machine or a callback, and the lexer never builds a list of tokens.
# The parser is precedence climbing over the operator facts, so adding an
# operator is one line in the operators block.
syntax OperatorTable {
trigger: Keyword("operators");
tokens {
Symbol(sym) = regex("[-+*/%^]", sym);
Level(n) = regex("[0-9]+", n);
Fn(name) = regex("[a-z_]+", name);
Arrow = "=>";
}
rule OperatorLine {
let sym = expect Symbol;
let level = expect Level;
expect Arrow;
let name = expect Fn;
return rule_add("operator", [sym, to_num(level), name], []);
}
}
make a function called op_add takes a, b returns r
return a + b
end
make a function called op_sub takes a, b returns r
return a - b
end
make a function called op_mul takes a, b returns r
return a * b
end
make a function called op_div takes a, b returns r
require b != 0
return a / b
end
operators {
+ 1 => op_add
- 1 => op_sub
* 2 => op_mul
/ 2 => op_div
}
# ---- the lexer: a fibre yielding one token at a time ----
make a function called is_digit takes c returns yes
return (c >= 48) and (c <= 57)
end
# Yields ["num", n], ["op", symbol], ["(", ""], [")", ""], and ["end", ""]
# for ever after the input runs out.
make a function called lex takes text returns last
let bytes = bytes_from_str(text)
let i = 0
let n = bytes_len(bytes)
while i < n do
let c = bytes[i]
if is_digit(c) then
let v = 0
while (i < n) and is_digit(bytes[i]) do
let v = v * 10 + (bytes[i] - 48)
let i = i + 1
end
fiber_yield(["num", v])
elif c == 32 then
let i = i + 1
elif (c == 40) or (c == 41) then
fiber_yield([chr(c), ""])
let i = i + 1
else
fiber_yield(["op", chr(c)])
let i = i + 1
end
end
while true do
fiber_yield(["end", ""])
end
return 0
end
# ---- the parser: pulls tokens, keeping one token of look-ahead ----
class Parser {
field lexer = 0
field ahead = 0
make a function called peek takes self returns tok
return self.ahead
end
make a function called take takes self returns tok
let tok = self.ahead
self.ahead = fiber_resume(self.lexer, 0)
return tok
end
}
# [level, function] for an operator symbol, or [0, ""] for none.
make a function called operator takes sym returns entry
let sols = solve("operator", [sym, logic_var("Level"), logic_var("Fn")])
if list_len(sols) == 0 then
return [0, ""]
end
return [sols[0][1], sols[0][2]]
end
make a function called primary takes p returns v
let tok = p.take()
if tok[0] == "num" then
return tok[1]
end
if tok[0] == "(" then
let v = expression(p, 1)
let close = p.take()
assert close[0] == ")"
return v
end
if (tok[0] == "op") and (tok[1] == "-") then
return 0 - primary(p)
end
assert false
return 0
end
# Precedence climbing: operators of at least min_level, left associative.
make a function called expression takes p, min_level returns v
let v = primary(p)
while true do
let tok = p.peek()
if tok[0] != "op" then
return v
end
let entry = operator(tok[1])
if entry[0] < min_level then
return v
end
p.take()
let rhs = expression(p, entry[0] + 1)
let v = apply(entry[1], v, rhs)
end
return v
end
make a function called calculate takes text returns v
let p = new("Parser")
p.lexer = fiber_new("lex")
# the first resume passes the text in and gives the first token
p.ahead = fiber_resume(p.lexer, text)
let v = expression(p, 1)
let last = p.peek()
assert last[0] == "end"
return v
end
print("== the operators, as facts ==")
print("" + list_len(solve("operator", [logic_var("S"), logic_var("L"), logic_var("F")])) + " operators declared")
print("== calculations ==")
let inputs = ["1 + 2 * 3", "(1 + 2) * 3", "10 / 4", "2 * (3 + 4) - 5 / 10", "-3 * -(2 + 1)", "1 / 3 + 1 / 6"]
let i = 0
while i < list_len(inputs) do
print(inputs[i] + " = " + calculate(inputs[i]))
let i = i + 1
end
Output:
== the operators, as facts == 4 operators declared == calculations == 1 + 2 * 3 = 7 (1 + 2) * 3 = 9 10 / 4 = 5/2 2 * (3 + 4) - 5 / 10 = 27/2 -3 * -(2 + 1) = 9 1 / 3 + 1 / 6 = 1/2
Python does this one well. A generator is already a coroutine lexer, with next() pulling one token at a time, and a dict literal holds the operator table as briefly as the PatLang notation does. What remains is the arithmetic: Python's / gives a float, so its parser turns each number into a Fraction to keep 10 / 4 as 5/2.fractions avoid floating-point precision loss
The Python version
"""The calculator of showcase/p6_coroutine_lexer.patlang, in Python.
Python does this one well. A generator is a coroutine lexer, and next() pulls
one token at a time; an operator table is a dict literal. The PatLang program
writes its table in a notation of its own (a syntax definition) and keeps it
as facts it queries; in Python a dict is as short and needs nothing defined.
The difference that remains is the numbers: Python's / gives a float, so the
parser converts each number to a Fraction to keep 10 / 4 as 5/2.
Prints the same lines as the PatLang program.
"""
from fractions import Fraction
import operator
# symbol: (level, function)
OPERATORS = {
"+": (1, operator.add),
"-": (1, operator.sub),
"*": (2, operator.mul),
"/": (2, operator.truediv),
}
def lex(text):
i, n = 0, len(text)
while i < n:
c = text[i]
if c.isdigit():
v = 0
while i < n and text[i].isdigit():
v = v * 10 + int(text[i])
i += 1
yield ("num", Fraction(v))
elif c == " ":
i += 1
elif c in "()":
yield (c, "")
i += 1
else:
yield ("op", c)
i += 1
while True:
yield ("end", "")
class Parser:
def __init__(self, text):
self.lexer = lex(text)
self.ahead = next(self.lexer)
def peek(self):
return self.ahead
def take(self):
tok, self.ahead = self.ahead, next(self.lexer)
return tok
def primary(p):
tok = p.take()
if tok[0] == "num":
return tok[1]
if tok[0] == "(":
v = expression(p, 1)
assert p.take()[0] == ")"
return v
if tok == ("op", "-"):
return -primary(p)
raise SyntaxError(tok)
def expression(p, min_level):
v = primary(p)
while True:
tok = p.peek()
if tok[0] != "op" or OPERATORS[tok[1]][0] < min_level:
return v
level, f = OPERATORS[tok[1]]
p.take()
v = f(v, expression(p, level + 1))
def calculate(text):
p = Parser(text)
v = expression(p, 1)
assert p.peek()[0] == "end"
return v
def show(x):
"""A value as PatLang prints it: a whole fraction as an int."""
return str(x.numerator) if x.denominator == 1 else str(x)
print("== the operators, as facts ==")
print(f"{len(OPERATORS)} operators declared")
print("== calculations ==")
for text in ["1 + 2 * 3", "(1 + 2) * 3", "10 / 4", "2 * (3 + 4) - 5 / 10", "-3 * -(2 + 1)", "1 / 3 + 1 / 6"]:
print(f"{text} = {show(calculate(text))}")
What if we changed the rules?
Worlds and logic programming. A course catalogue is a handful of facts (which course needs which first) and two rules that work out everything a student must have taken before each course. Proposed changes are tried one at a time, each in a world of its own. A world has its own facts, files and output, and nothing done inside it reaches the program. One proposal is fine; one would make a course its own prerequisite and is refused; one fails its check outright, which stops only its world. Afterwards the program's own catalogue is exactly as it began, with nothing to undo.
# What if we changed the rules?
#
# Paradigms: worlds and logic programming.
#
# A course catalogue is a set of facts and rules: which course needs which
# first, and from those, what a student must have taken before each course.
# Proposed changes to the catalogue are tried one at a time, each in a world
# of its own: a world has its own facts, its own files and its own output, and
# nothing done inside it reaches the program. Each world loads the catalogue,
# applies one change and checks what must stay true. A change that breaks the
# catalogue is reported and thrown away with its world; one whose check fails
# outright stops only its world. The program's own catalogue is never touched,
# so there is nothing to undo.
# The catalogue, in whichever store is current: the program's, or a world's.
make a function called load_catalogue returns done
rule needs(algorithms, programming).
rule needs(databases, programming).
rule needs(compilers, algorithms).
rule needs(compilers, theory).
rule needs(theory, discrete_maths).
rule before(A, B) :- needs(A, B).
rule before(A, C) :- needs(A, B), before(B, C).
return true
end
make a function called has takes items, x returns yes
let i = 0
while i < list_len(items) do
if items[i] == x then
return true
end
let i = i + 1
end
return false
end
# The courses a course needs, directly or not, each once.
make a function called all_before takes course returns courses
let sols = solve("before", [course, logic_var("X")])
let courses = []
let i = 0
while i < list_len(sols) do
if not has(courses, sols[i][1]) then
let courses = list_push(courses, sols[i][1])
end
let i = i + 1
end
return courses
end
# A course that needs itself through a chain of needs, or "" for none. A
# walk over the needs facts, not the recursive before rule, which would never
# finish on a cycle.
make a function called course_in_cycle returns course
let edges = solve("needs", [logic_var("A"), logic_var("B")])
let i = 0
while i < list_len(edges) do
let start = edges[i][0]
let seen = []
let todo = [start]
let pos = 0
while pos < list_len(todo) do
let at = todo[pos]
let pos = pos + 1
let k = 0
while k < list_len(edges) do
if edges[k][0] == at then
if edges[k][1] == start then
return start
end
if not has(seen, edges[k][1]) then
let seen = list_push(seen, edges[k][1])
let todo = list_push(todo, edges[k][1])
end
end
let k = k + 1
end
end
let i = i + 1
end
return ""
end
# A proposal: its name and the facts it adds, as [name, [[course, prereq], ...]].
# In its world: the catalogue, the change, then the checks. A cycle is a
# problem reported; a course needing more than four others breaks the
# faculty's rule, an assert, and stops the world.
make a function called try_change takes proposal returns verdict
let w = world_new()
let result = world_call(w, || do
load_catalogue()
let added = proposal[1]
let i = 0
while i < list_len(added) do
rule_add("needs", added[i], [])
let i = i + 1
end
let looped = course_in_cycle()
if looped != "" then
return ["a course needs itself: " + looped]
end
assert list_len(all_before("compilers")) <= 4
return []
end)
world_free(w)
let verdict = [proposal[0], result]
return verdict
end
# A world's call gives ["done", what the code returned], here its list of
# problems, or ["stopped", the code it stopped with].
make a function called report takes verdict returns ok
let result = verdict[1]
if result[0] == "stopped" then
print(verdict[0] + ": stopped inside its world (code " + result[1] + "), the program carries on")
return false
end
let problems = result[1]
if list_len(problems) == 0 then
print(verdict[0] + ": fine")
return true
end
print(verdict[0] + ": refused, " + str_join(problems, "; "))
return false
end
load_catalogue()
print("== the catalogue ==")
print("compilers needs, directly or not: " + all_before("compilers"))
print("== proposals, each in its own world ==")
let proposals = [
["databases needs algorithms", [["databases", "algorithms"]]],
["programming needs compilers", [["programming", "compilers"]]],
["discrete_maths needs databases", [["discrete_maths", "databases"]]]
]
let i = 0
while i < list_len(proposals) do
report(try_change(proposals[i]))
let i = i + 1
end
print("== the program's catalogue afterwards ==")
print("does programming need compilers here? " + (list_len(solve("needs", ["programming", "compilers"])) > 0))
print("compilers needs, directly or not: " + all_before("compilers"))
Output:
== the catalogue == compilers needs, directly or not: [algorithms, theory, programming, discrete_maths] == proposals, each in its own world == databases needs algorithms: fine programming needs compilers: refused, a course needs itself: algorithms discrete_maths needs databases: stopped inside its world (code 3), the program carries on == the program's catalogue afterwards == does programming need compilers here? false compilers needs, directly or not: [algorithms, theory, programming, discrete_maths]
In Python the facts become a list of pairs and the rules a transitive closure written as a function. Each proposal works on a copy of the list, and a broken check is an exception caught around the attempt. That isolates the data and the failure. A world goes further, taking any files written and anything printed with it, and Python gets that degree of isolation only from a separate process. Where the PatLang output says a world stopped with code 3, the Python output names the exception instead.process isolation is heavy; worlds are lighter
The Python version
"""The what-if catalogue of showcase/p7_what_if.patlang, in Python.
The facts are a list of (course, prerequisite) pairs, and "before" is a
transitive closure written as a function. Each proposal is tried on a copy of
the list, and a broken rule is an exception caught around the try. That
isolates the data and the failure. A PatLang world isolates more: its facts,
its files and its output, so code that writes a file or prints inside a world
leaves nothing behind. Python gets that only from a separate process.
Where the PatLang program says its world stopped with code 3, this one names
the exception; its expected output is showcase/compare/expected/p7_what_if.txt.
"""
import copy
CATALOGUE = [
("algorithms", "programming"),
("databases", "programming"),
("compilers", "algorithms"),
("compilers", "theory"),
("theory", "discrete_maths"),
]
def all_before(needs, course):
"""What course needs, directly or not, each once, in the order found."""
found = []
todo = [course]
while todo:
at = todo.pop(0)
for a, b in needs:
if a == at and b not in found:
found.append(b)
todo.append(b)
return found
def course_in_cycle(needs):
for start, _ in needs:
seen, todo = [], [start]
while todo:
at = todo.pop(0)
for a, b in needs:
if a == at:
if b == start:
return start
if b not in seen:
seen.append(b)
todo.append(b)
return ""
def try_change(needs, added):
trial = copy.deepcopy(needs) + added
looped = course_in_cycle(trial)
if looped:
return ["a course needs itself: " + looped]
assert len(all_before(trial, "compilers")) <= 4
return []
print("== the catalogue ==")
print("compilers needs, directly or not: [" + ", ".join(all_before(CATALOGUE, "compilers")) + "]")
print("== proposals, each in its own world ==")
proposals = [
("databases needs algorithms", [("databases", "algorithms")]),
("programming needs compilers", [("programming", "compilers")]),
("discrete_maths needs databases", [("discrete_maths", "databases")]),
]
for name, added in proposals:
try:
problems = try_change(CATALOGUE, added)
except AssertionError:
print(f"{name}: stopped inside its try (AssertionError), the program carries on")
continue
print(f"{name}: fine" if not problems else f"{name}: refused, " + "; ".join(problems))
print("== the program's catalogue afterwards ==")
print("does programming need compilers here? " + ("true" if ("programming", "compilers") in CATALOGUE else "false"))
print("compilers needs, directly or not: [" + ", ".join(all_before(CATALOGUE, "compilers")) + "]")
Exact sums, in parallel, with the same answer every time
Parallel functional code and exact numbers. The harmonic number H(3000) = 1 + 1/2 + ... + 1/3000 is a fraction whose numerator runs to 1,303 digits. The program splits the sum into ranges, sums each on its own thread through parallel_map, and adds the parts. Fraction addition is exact and associative, so one part, two, four or eight all give the same fraction to the last digit. The same splits done in floats disagree in their final places, because float addition is not associative.floats trade precision for speed
# Exact sums, in parallel, with the same answer every time.
#
# Paradigms: parallel functional code and exact numbers.
#
# The harmonic number H(n) = 1 + 1/2 + ... + 1/n is a fraction whose
# numerator and denominator grow to hundreds of digits. The sum is split into
# ranges, each range summed on its own thread by parallel_map, and the parts
# added. Fraction addition is exact and associative, so the result is the
# same to the last digit however the work is split: one part, two, four or
# eight. Floating-point sums split the same ways can differ in the last
# places, because float addition is not associative; that is shown at the end.
# The sum of 1/k for k from range[0] up to range[1] - 1, exactly.
make a function called partial_sum takes range returns s
let s = 0
let k = range[0]
while k < range[1] do
let s = s + 1 / k
let k = k + 1
end
return s
end
# The same in floats.
make a function called partial_sum_float takes range returns s
let s = 0.0
let k = range[0]
while k < range[1] do
let s = s + 1.0 / k
let k = k + 1
end
return s
end
# 1..n split into parts ranges of (nearly) equal length.
make a function called split takes n, parts returns ranges
let ranges = []
let p = 0
while p < parts do
let lo = 1 + floor(n * p / parts)
let hi = 1 + floor(n * (p + 1) / parts)
let ranges = list_push(ranges, [lo, hi])
let p = p + 1
end
return ranges
end
make a function called total takes items returns s
let s = items[0]
let i = 1
while i < list_len(items) do
let s = s + items[i]
let i = i + 1
end
return s
end
# The number of digits in a fraction's numerator: the text before its "/".
make a function called numerator_digits takes q returns d
let text = "" + q
let i = 0
while i < text.length do
if text[i] == "/" then
return i
end
let i = i + 1
end
return text.length
end
let n = 3000
print("== H(" + n + ") exactly ==")
let answers = []
let parts = [1, 2, 4, 8]
let i = 0
while i < list_len(parts) do
let h = total(parallel_map(split(n, parts[i]), "partial_sum"))
let answers = list_push(answers, h)
print("split into " + parts[i] + ": a fraction whose numerator has " + numerator_digits(h) + " digits")
let i = i + 1
end
let same = true
let j = 1
while j < list_len(answers) do
if answers[j] != answers[0] then
let same = false
end
let j = j + 1
end
print("all four splits give the same fraction: " + same)
print("H(" + n + ") is about " + (answers[0] * 1.0))
print("== the same sums in floats ==")
let floats = []
let k = 0
while k < list_len(parts) do
let f = total(parallel_map(split(n, parts[k]), "partial_sum_float"))
let floats = list_push(floats, f)
print("split into " + parts[k] + ": " + f)
let k = k + 1
end
let fsame = true
let m = 1
while m < list_len(floats) do
if floats[m] != floats[0] then
let fsame = false
end
let m = m + 1
end
print("all four float splits agree: " + fsame)
Output:
== H(3000) exactly == split into 1: a fraction whose numerator has 1303 digits split into 2: a fraction whose numerator has 1303 digits split into 4: a fraction whose numerator has 1303 digits split into 8: a fraction whose numerator has 1303 digits all four splits give the same fraction: true H(3000) is about 8.583749889959186 == the same sums in floats == split into 1: 8.583749889959169 split into 2: 8.583749889959186 split into 4: 8.58374988995919 split into 8: 8.583749889959183 all four float splits agree: false
Python has exact fractions and arbitrary-size integers, and its Fraction addition reduces by the gcd of the denominators first, the same method PatLang uses (Knuth's The Art of Computer Programming, volume 2, section 4.5.1). The difference lies in the parallelism. In the standard build of CPython only one thread runs Python code at a time, so the sketch uses a process pool and sends each range out and each partial sum back, pickled. PatLang's threads share the program's memory.
Python is also faster here. On the same machine, best of three runs, the Python version took 0.31 s, against 2.59 s for the PatLang native build and 2.90 s interpreted. Python's big integers are written in C, and PatLang's are written in PatLang, so the gap is in the integer arithmetic underneath.
The Python version
"""The exact parallel sums of showcase/p8_exact_in_parallel.patlang, in Python.
Python has exact fractions (fractions.Fraction) and arbitrary-size integers,
and its Fraction addition is the same algorithm as PatLang's (it reduces by
the gcd of the denominators first). The difference is the parallelism: a
thread does not run Python code in parallel while another holds the
interpreter lock, so the sketch uses a process pool, which sends each range
to another process and each partial sum back, pickled. PatLang's parallel_map
runs the ranges on threads that share the program's memory.
Prints the same lines as the PatLang program.
"""
from fractions import Fraction
from multiprocessing import Pool
def partial_sum(rng):
lo, hi = rng
s = Fraction(0)
for k in range(lo, hi):
s += Fraction(1, k)
return s
def partial_sum_float(rng):
lo, hi = rng
s = 0.0
for k in range(lo, hi):
s += 1.0 / k
return s
def split(n, parts):
return [(1 + n * p // parts, 1 + n * (p + 1) // parts) for p in range(parts)]
def total(items):
s = items[0]
for x in items[1:]:
s += x
return s
def b(x):
return "true" if x else "false"
if __name__ == "__main__":
n = 3000
parts = [1, 2, 4, 8]
with Pool(8) as pool:
print(f"== H({n}) exactly ==")
answers = []
for p in parts:
h = total(pool.map(partial_sum, split(n, p)))
answers.append(h)
print(f"split into {p}: a fraction whose numerator has {len(str(h.numerator))} digits")
print(f"all four splits give the same fraction: {b(all(a == answers[0] for a in answers))}")
print(f"H({n}) is about {float(answers[0])!r}")
print("== the same sums in floats ==")
floats = []
for p in parts:
f = total(pool.map(partial_sum_float, split(n, p)))
floats.append(f)
print(f"split into {p}: {f!r}")
print(f"all four float splits agree: {b(all(f == floats[0] for f in floats))}")
Graduate Attributes
Modelled on this page
- Critical Thinker: Performance timings are compared directly to highlight implementation trade-offs rather than claiming superiority.
- Digitally Fluent: Code is presented alongside its output to demonstrate how digital tools handle precision and isolation.
- Subject Specialist: Technical distinctions between coroutines, generators and processes are explained through concrete implementation details.
University of Reading Graduate Attributes framework.