Project P056
Mini spreadsheet
Cells A1 to F9 holding numbers, labels and formulas - + - * / with parentheses, cell references, SUM, MIN, MAX and AVG over ranges - kept as exact fractions. Every change recalculates the sheet in dependency order (Kahn's algorithm), and formulas caught in a cycle are found and marked instead of looping.
3 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
A small spreadsheet: columns A to F, rows 1 to 9. A cell holds a number, a label, or a formula that starts with =. Formulas use + - * / and parentheses, cells like B3, and SUM, MIN, MAX and AVG over cells and ranges like D2:D4. Every change works the whole sheet out again, in an order where each formula comes after the formulas it reads. A formula caught in a cycle is found and marked instead of looping forever.
main.eml- the menu, reading cells and contents, the value and formula views, and the samplesheet.eml- formulas: the tokens, a parser that also works the value out, and the recalculation orderfrac.eml- exact fractions, from P007 by way of P038 and P044
How each part works:
- Values are exact fractions, so 1.2 * 10 is exactly 12 and a third is a third. The value view shows two decimal places and marks a rounded value with ~.
- A formula is read by recursive descent: an expression is terms joined by + and -, a term is factors joined by * and /, and a factor is a number, a cell, a function, a minus sign before a factor, or an expression in parentheses. That is why =2+3*4 is 14. A formula that does not parse is refused with the reason, and nothing changes.
- An empty cell counts as 0 in arithmetic. Arithmetic on a label gives #TEXT, and dividing by zero gives #DIV/0; an error passes on to every formula that reads it. SUM, MIN, MAX and AVG skip empty cells and labels. AVG of nothing is #DIV/0, and MIN or MAX of nothing is 0.
- The order is Kahn's algorithm, as in the corpus case
topological-sort. A formula is ready when every formula it reads is done; doing it may make others ready. Formulas never made ready are in a cycle, or read something that is, and they show #CYCLE until the cycle is broken. The order view lists both.
What is checked: menu choices 1 to 7; cells from A1 to F9 (either case); contents up to 60 characters; formulas that parse - numbers, cells A1 to F9, + - * / ( ), and SUM, MIN, MAX, AVG with cells and ranges separated by commas. An empty answer cancels.
Sessions: sessions/basic.in loads a small order: three items, their totals, a subtotal, tax at 8%, the total and the average. - The views show values, formulas and the order they were worked out: D2, D3, D4, D6, D9, D7, D8. - B3 changes to 1.25, and seven formulas are worked out again. - B7 becomes =D8/100. D7 reads B7 and D8 reads D7, so the three make a cycle; the rest still work. - B7 becomes 0.1, which breaks the cycle: tax 3.7 and total 40.7.
sessions/bad-input.in gives: - menu choices 0 and x; - cells G1 and A0, and an empty cell; - empty contents; - the broken formulas =1+ and =SUM(B1; - =A1+1 in A1, a cycle of one; - =B1/C1 on empty cells; - a label, and a formula that multiplies it; - a SUM over the label, that formula and an empty cell; - 61 characters; - AVG of an empty column; - A1 emptied, then the values, the formulas and the order.
Built on the verified corpus case topological-sort (Kahn's algorithm, which finds the cycle in what it leaves over).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Mini spreadsheet ==
Cells A1 to F9 hold numbers, labels, or formulas such as =B2*C2 or =SUM(D2:D4).
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 0
Pick a number from 1 to 7.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> x
Pick a number from 1 to 7.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> G1
Type a cell from A1 to F9, like B3.
cell> A0
Type a cell from A1 to F9, like B3.
cell>
Cancelled.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A1
content of A1 (a number, a label, or =formula)>
Cancelled - use 2) to empty a cell.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A1
content of A1 (a number, a label, or =formula)> =1+
Not a formula: it has something missing where a number, a cell or ( should be. Nothing was changed.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A1
content of A1 (a number, a label, or =formula)> =SUM(B1
Not a formula: it has SUM( with no , between two cells or no ) at the end. Nothing was changed.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A1
content of A1 (a number, a label, or =formula)> =A1+1
A1 = #CYCLE; 0 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A2
content of A2 (a number, a label, or =formula)> =B1/C1
A2 = #DIV/0; 1 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A3
content of A3 (a number, a label, or =formula)> label
A3 = label; 1 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A4
content of A4 (a number, a label, or =formula)> =A3*2
A4 = #TEXT; 2 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A5
content of A5 (a number, a label, or =formula)> =SUM(A3:A4, B9)
A5 = #TEXT; 3 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A6
content of A6 (a number, a label, or =formula)> =1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
Keep a cell to 60 characters.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> A6
content of A6 (a number, a label, or =formula)> =AVG(B1:B9)
A6 = #DIV/0; 4 formula cell(s) worked out again.
1 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 2
cell to empty> A1
A1 is empty now; 4 formula cell(s) worked out again.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 3
A B C D E F
1
2 #DIV/0
3 label
4 #TEXT
5 #TEXT
6 #DIV/0
7
8
9
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 4
A B C D E F
1
2 =B1/C1
3 label
4 =A3*2
5 =SUM(A3:A~
6 =AVG(B1:B~
7
8
9
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 5
Worked out in this order: A2, A4, A6, A5.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 7
Bye.
What was typed (42 lines)
0
x
1
G1
A0
1
A1
1
A1
=1+
1
A1
=SUM(B1
1
A1
=A1+1
1
A2
=B1/C1
1
A3
label
1
A4
=A3*2
1
A5
=SUM(A3:A4, B9)
1
A6
=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
1
A6
=AVG(B1:B9)
2
A1
3
4
5
7
basic
interpreter: byte-equal== Mini spreadsheet ==
Cells A1 to F9 hold numbers, labels, or formulas such as =B2*C2 or =SUM(D2:D4).
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 6
A small order: three items, their totals, tax at 8% and an average.
A B C D E F
1 Item Price Qty Total
2 Paper 4.5 3 13.5
3 Pens 1.2 10 12
4 Folders 2.75 4 11
5
6 Subtotal 36.5
7 Tax rate 0.08 2.92
8 Total 39.42
9 Average ~12.17
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 4
A B C D E F
1 Item Price Qty Total
2 Paper 4.5 3 =B2*C2
3 Pens 1.2 10 =B3*C3
4 Folders 2.75 4 =B4*C4
5
6 Subtotal =SUM(D2:D~
7 Tax rate 0.08 =D6*B7
8 Total =D6+D7
9 Average =AVG(D2:D~
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 5
Worked out in this order: D2, D3, D4, D6, D9, D7, D8.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> B3
content of B3 (a number, a label, or =formula)> 1.25
B3 = 1.25; 7 formula cell(s) worked out again.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> B7
content of B7 (a number, a label, or =formula)> =D8/100
B7 = #CYCLE; 5 formula cell(s) worked out again.
3 formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 5
Worked out in this order: D2, D3, D4, D6, D9.
In a cycle, or reading one: B7, D7, D8.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 3
A B C D E F
1 Item Price Qty Total
2 Paper 4.5 3 13.5
3 Pens 1.25 10 12.5
4 Folders 2.75 4 11
5
6 Subtotal 37
7 Tax rate #CYCLE #CYCLE
8 Total #CYCLE
9 Average ~12.33
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 1
cell> B7
content of B7 (a number, a label, or =formula)> 0.1
B7 = 0.1; 7 formula cell(s) worked out again.
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 3
A B C D E F
1 Item Price Qty Total
2 Paper 4.5 3 13.5
3 Pens 1.25 10 12.5
4 Folders 2.75 4 11
5
6 Subtotal 37
7 Tax rate 0.1 3.7
8 Total 40.7
9 Average ~12.33
1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit
choice> 7
Bye.
What was typed (16 lines)
6
4
5
1
B3
1.25
1
B7
=D8/100
5
3
1
B7
0.1
3
7
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P056 mini spreadsheet: six columns and nine rows of numbers, labels and
# formulas. Formulas use + - * / ( ), cells like B3 and SUM, MIN, MAX, AVG
# over ranges like A1:A5; every change recalculates the sheet in an order
# where each formula comes after the formulas it reads, and a cycle is
# found and named instead of looping forever.
import frac
import sheet
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def shown(v):
# A value in at most 10 characters: numbers to two decimal places with
# ~ in front when rounded, labels cut to fit, errors as they are.
if v[0] == "e":
return v[1]
if v[0] == "t":
if len(v[1]) > 10:
return v[1][0:9] + "~"
return v[1]
frac.decimal(v[1], 2) => s
if len(s) > 6 and s[0:6] == "about ":
"~" + s[6:len(s)] => s
if len(s) > 10:
return "#WIDE"
return s
def grid(cells, vals, formulas):
" " => head
for c in [0:5]:
" " + "ABCDEF"[c] => h
head + h[len(h) - 10:len(h)] + " " => head
trim_right(head) ^0
for r in [0:8]:
" " + str(r + 1) + " " => line
for c in [0:5]:
r * 6 + c => k
if formulas:
cells[k] => s
if len(s) > 10:
s[0:9] + "~" => s
else:
shown(vals[k]) => s
if formulas or vals[k][0] == "t":
while len(s) < 10:
s + " " => s
else:
while len(s) < 10:
" " + s => s
line + s + " " => line
trim_right(line) ^0
def trim_right(s):
len(s) => j
while j > 0 and s[j - 1] == " ":
j - 1 => j
return s[0:j]
def ask_cell(prompt):
while True:
trim(input(prompt)) => answer
if answer == "":
return -1
sheet.cell_index(answer) => k
if k >= 0:
return k
"Type a cell from A1 to F9, like B3." ^0
def set_cell(state):
ask_cell("cell> ") => k
if k == -1:
"Cancelled." ^0
return
trim(input("content of " + sheet.cell_name(k) + " (a number, a label, or =formula)> ")) => text
if text == "":
"Cancelled - use 2) to empty a cell." ^0
return
if len(text) > 60:
"Keep a cell to 60 characters." ^0
return
if text[0] == "=":
sheet.checked(text[1:len(text)]) => c
if c[0] != "":
("Not a formula: " + c[0] + ". Nothing was changed.") ^0
return
text => state[0][k]
update(state, k)
def update(state, k):
sheet.recalculated(state[0]) => res
res[0] => state[1]
res[1] => state[2]
sheet.cell_name(k) + " = " + shown(state[1][k]) => what
if state[0][k] == "":
sheet.cell_name(k) + " is empty now" => what
(what + "; " + str(len(state[2])) + " formula cell(s) worked out again.") ^0
0 => stuck
for j in [0:53]:
if state[0][j] != "" and state[0][j][0] == "=" and state[1][j][0] == "e" and state[1][j][1] == "#CYCLE":
stuck + 1 => stuck
if stuck > 0:
(str(stuck) + " formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.") ^0
def clear_cell(state):
ask_cell("cell to empty> ") => k
if k == -1:
"Cancelled." ^0
return
"" => state[0][k]
update(state, k)
def order(state):
if len(state[2]) == 0:
"No formula has been worked out yet." ^0
else:
"" => s
for k in state[2]:
if s != "":
s + ", " => s
s + sheet.cell_name(k) => s
("Worked out in this order: " + s + ".") ^0
"" => stuck
for j in [0:53]:
if state[0][j] != "" and state[0][j][0] == "=" and state[1][j][1] == "#CYCLE":
if stuck != "":
stuck + ", " => stuck
stuck + sheet.cell_name(j) => stuck
if stuck != "":
("In a cycle, or reading one: " + stuck + ".") ^0
def sample(state):
[""] * 54 => cells
[["A1", "Item"], ["B1", "Price"], ["C1", "Qty"], ["D1", "Total"],
["A2", "Paper"], ["B2", "4.5"], ["C2", "3"], ["D2", "=B2*C2"],
["A3", "Pens"], ["B3", "1.2"], ["C3", "10"], ["D3", "=B3*C3"],
["A4", "Folders"], ["B4", "2.75"], ["C4", "4"], ["D4", "=B4*C4"],
["A6", "Subtotal"], ["D6", "=SUM(D2:D4)"],
["A7", "Tax rate"], ["B7", "0.08"], ["D7", "=D6*B7"],
["A8", "Total"], ["D8", "=D6+D7"],
["A9", "Average"], ["D9", "=AVG(D2:D4)"]] => entries
for e in entries:
e[1] => cells[sheet.cell_index(e[0])]
cells => state[0]
sheet.recalculated(cells) => res
res[0] => state[1]
res[1] => state[2]
"A small order: three items, their totals, tax at 8% and an average." ^0
"== Mini spreadsheet ==" ^0
"Cells A1 to F9 hold numbers, labels, or formulas such as =B2*C2 or =SUM(D2:D4)." ^0
# [cell texts, cell values, the order formulas were worked out]
[[""] * 54, [], []] => state
sheet.recalculated(state[0]) => first
first[0] => state[1]
True => running
while running:
"" ^0
"1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
set_cell(state)
elif choice == "2":
clear_cell(state)
elif choice == "3":
grid(state[0], state[1], False)
elif choice == "4":
grid(state[0], state[1], True)
elif choice == "5":
order(state)
elif choice == "6":
sample(state)
grid(state[0], state[1], False)
elif choice == "7":
False => running
else:
"Pick a number from 1 to 7." ^0
"Bye." ^0
Python projection (main.py)
import frac
import sheet
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def shown(v):
if v[0] == "e":
return v[1]
if v[0] == "t":
if len(v[1]) > 10:
return v[1][0:9] + "~"
return v[1]
s = frac.decimal(v[1], 2)
if len(s) > 6 and s[0:6] == "about ":
s = "~" + s[6:len(s)]
if len(s) > 10:
return "#WIDE"
return s
def grid(cells, vals, formulas):
head = " "
for c in range(0, 6):
h = " " + "ABCDEF"[c]
head = head + h[len(h) - 10:len(h)] + " "
print(trim_right(head))
for r in range(0, 9):
line = " " + str(r + 1) + " "
for c in range(0, 6):
k = r * 6 + c
if formulas:
s = cells[k]
if len(s) > 10:
s = s[0:9] + "~"
else:
s = shown(vals[k])
if formulas or vals[k][0] == "t":
while len(s) < 10:
s = s + " "
else:
while len(s) < 10:
s = " " + s
line = line + s + " "
print(trim_right(line))
def trim_right(s):
j = len(s)
while j > 0 and s[j - 1] == " ":
j = j - 1
return s[0:j]
def ask_cell(prompt):
while True:
answer = trim(input(prompt))
if answer == "":
return -1
k = sheet.cell_index(answer)
if k >= 0:
return k
print("Type a cell from A1 to F9, like B3.")
def set_cell(state):
k = ask_cell("cell> ")
if k == -1:
print("Cancelled.")
return
text = trim(input("content of " + sheet.cell_name(k) + " (a number, a label, or =formula)> "))
if text == "":
print("Cancelled - use 2) to empty a cell.")
return
if len(text) > 60:
print("Keep a cell to 60 characters.")
return
if text[0] == "=":
c = sheet.checked(text[1:len(text)])
if c[0] != "":
print("Not a formula: " + c[0] + ". Nothing was changed.")
return
state[0][k] = text
update(state, k)
def update(state, k):
res = sheet.recalculated(state[0])
state[1] = res[0]
state[2] = res[1]
what = sheet.cell_name(k) + " = " + shown(state[1][k])
if state[0][k] == "":
what = sheet.cell_name(k) + " is empty now"
print(what + "; " + str(len(state[2])) + " formula cell(s) worked out again.")
stuck = 0
for j in range(0, 54):
if state[0][j] != "" and state[0][j][0] == "=" and state[1][j][0] == "e" and state[1][j][1] == "#CYCLE":
stuck = stuck + 1
if stuck > 0:
print(str(stuck) + " formula cell(s) are in a cycle, or read one - they show #CYCLE until it is broken.")
def clear_cell(state):
k = ask_cell("cell to empty> ")
if k == -1:
print("Cancelled.")
return
state[0][k] = ""
update(state, k)
def order(state):
if len(state[2]) == 0:
print("No formula has been worked out yet.")
else:
s = ""
for k in state[2]:
if s != "":
s = s + ", "
s = s + sheet.cell_name(k)
print("Worked out in this order: " + s + ".")
stuck = ""
for j in range(0, 54):
if state[0][j] != "" and state[0][j][0] == "=" and state[1][j][1] == "#CYCLE":
if stuck != "":
stuck = stuck + ", "
stuck = stuck + sheet.cell_name(j)
if stuck != "":
print("In a cycle, or reading one: " + stuck + ".")
def sample(state):
cells = [""] * 54
entries = [["A1", "Item"], ["B1", "Price"], ["C1", "Qty"], ["D1", "Total"], ["A2", "Paper"], ["B2", "4.5"], ["C2", "3"], ["D2", "=B2*C2"], ["A3", "Pens"], ["B3", "1.2"], ["C3", "10"], ["D3", "=B3*C3"], ["A4", "Folders"], ["B4", "2.75"], ["C4", "4"], ["D4", "=B4*C4"], ["A6", "Subtotal"], ["D6", "=SUM(D2:D4)"], ["A7", "Tax rate"], ["B7", "0.08"], ["D7", "=D6*B7"], ["A8", "Total"], ["D8", "=D6+D7"], ["A9", "Average"], ["D9", "=AVG(D2:D4)"]]
for e in entries:
cells[sheet.cell_index(e[0])] = e[1]
state[0] = cells
res = sheet.recalculated(cells)
state[1] = res[0]
state[2] = res[1]
print("A small order: three items, their totals, tax at 8% and an average.")
print("== Mini spreadsheet ==")
print("Cells A1 to F9 hold numbers, labels, or formulas such as =B2*C2 or =SUM(D2:D4).")
state = [[""] * 54, [], []]
first = sheet.recalculated(state[0])
state[1] = first[0]
running = True
while running:
print("")
print("1) set a cell 2) empty a cell 3) values 4) formulas 5) order 6) sample 7) quit")
choice = trim(input("choice> "))
if choice == "1":
set_cell(state)
elif choice == "2":
clear_cell(state)
elif choice == "3":
grid(state[0], state[1], False)
elif choice == "4":
grid(state[0], state[1], True)
elif choice == "5":
order(state)
elif choice == "6":
sample(state)
grid(state[0], state[1], False)
elif choice == "7":
running = False
else:
print("Pick a number from 1 to 7.")
print("Bye.")
sheet.eml
eml# P056 mini spreadsheet - formulas and recalculation. The sheet has columns
# A to F and rows 1 to 9; cell k (0 to 53) is column k % 6, row k / 6.
# A cell holds text as typed: "" (empty), a number, a formula starting
# with "=", or any other text (a label). A value is ["n", fraction],
# ["t", text] or ["e", error].
import frac
def cell_name(k):
return "ABCDEF"[k % 6] + str(int(k / 6) + 1)
def cell_index(s):
# "B3" or "b3" as 0 to 53, or -1.
if len(s) != 2:
return -1
-1 => col
for c in [0:5]:
if s[0] == "ABCDEF"[c] or s[0] == "abcdef"[c]:
c => col
if col == -1 or not (s[1] >= "1" and s[1] <= "9"):
return -1
return (int(s[1]) - 1) * 6 + col
def tokens(f):
# The formula text after "=" as tokens: ["num", fraction], ["cell", k],
# ["fn", name], ["op", "+"] and so on; or [["bad", why]].
[] => out
0 => i
while i < len(f):
f[i] => c
if c == " ":
i + 1 => i
elif c == "+" or c == "-" or c == "*" or c == "/" or c == "(" or c == ")" or c == ":" or c == ",":
out + [["op", c]] => out
i + 1 => i
elif c >= "0" and c <= "9" or c == ".":
i => j
while j < len(f) and (f[j] >= "0" and f[j] <= "9" or f[j] == "."):
j + 1 => j
frac.parse(f[i:j]) => x
if len(x) == 0:
return [["bad", "the number " + f[i:j]]]
out + [["num", x]] => out
j => i
elif (c >= "A" and c <= "Z") or (c >= "a" and c <= "z"):
i => j
while j < len(f) and ((f[j] >= "A" and f[j] <= "Z") or (f[j] >= "a" and f[j] <= "z") or (f[j] >= "0" and f[j] <= "9")):
j + 1 => j
f[i:j] => w
cell_index(w) => k
if k >= 0:
out + [["cell", k]] => out
else:
"" => up
for ch in w:
ch => u
for q in [0:25]:
if ch == "abcdefghijklmnopqrstuvwxyz"[q]:
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[q] => u
up + u => up
if up == "SUM" or up == "MIN" or up == "MAX" or up == "AVG":
out + [["fn", up]] => out
else:
return [["bad", w + ", which is not a cell from A1 to F9 or one of SUM, MIN, MAX, AVG"]]
j => i
else:
return [["bad", "the character " + c]]
return out
# The parser walks the tokens with a position kept in p[0]. Each step
# returns a value, given the values of all cells so far (vals); parsing
# alone (vals = []) only checks the shape and collects the cells read.
def peek(ts, p):
if p[0] < len(ts):
return ts[p[0]]
return ["end", ""]
def is_op(t, c):
return t[0] == "op" and t[1] == c
def arith(a, b, op):
if a[0] == "e":
return a
if b[0] == "e":
return b
if a[0] == "t" or b[0] == "t":
return ["e", "#TEXT"]
if op == "+":
return ["n", frac.plus(a[1], b[1])]
if op == "-":
return ["n", frac.minus(a[1], b[1])]
if op == "*":
return ["n", frac.times(a[1], b[1])]
if frac.is_zero(b[1]):
return ["e", "#DIV/0"]
return ["n", frac.over(a[1], b[1])]
def read_cell(k, vals, refs):
# refs is [the list of cells read so far], kept in a one-item list so
# every call adds to the same one.
refs[0] + [k] => refs[0]
if len(vals) == 0:
return ["n", [0, 1]]
vals[k] => v
if v[0] == "t" and v[1] == "":
return ["n", [0, 1]]
return v
def expr(ts, p, vals, refs):
term(ts, p, vals, refs) => v
while is_op(peek(ts, p), "+") or is_op(peek(ts, p), "-"):
peek(ts, p)[1] => op
p[0] + 1 => p[0]
arith(v, term(ts, p, vals, refs), op) => v
return v
def term(ts, p, vals, refs):
factor(ts, p, vals, refs) => v
while is_op(peek(ts, p), "*") or is_op(peek(ts, p), "/"):
peek(ts, p)[1] => op
p[0] + 1 => p[0]
arith(v, factor(ts, p, vals, refs), op) => v
return v
def factor(ts, p, vals, refs):
peek(ts, p) => t
if is_op(t, "-"):
p[0] + 1 => p[0]
return arith(["n", [0, 1]], factor(ts, p, vals, refs), "-")
if t[0] == "num":
p[0] + 1 => p[0]
return ["n", t[1]]
if t[0] == "cell":
p[0] + 1 => p[0]
return read_cell(t[1], vals, refs)
if is_op(t, "("):
p[0] + 1 => p[0]
expr(ts, p, vals, refs) => v
if not is_op(peek(ts, p), ")"):
["bad", "a ( without its )"] => p[1]
else:
p[0] + 1 => p[0]
return v
if t[0] == "fn":
p[0] + 1 => p[0]
return function(t[1], ts, p, vals, refs)
["bad", "something missing where a number, a cell or ( should be"] => p[1]
return ["e", "#BAD"]
def function(fname, ts, p, vals, refs):
# SUM, MIN, MAX or AVG of cells and ranges: (A1:A5) or (A1, B2, C1:C3).
if not is_op(peek(ts, p), "("):
["bad", fname + " without ( after it"] => p[1]
return ["e", "#BAD"]
p[0] + 1 => p[0]
[] => cells
while True:
peek(ts, p) => a
if a[0] != "cell":
["bad", fname + "( with something other than cells and ranges in it, where " + fname + "(A1:A5) would do"] => p[1]
return ["e", "#BAD"]
p[0] + 1 => p[0]
if is_op(peek(ts, p), ":"):
p[0] + 1 => p[0]
peek(ts, p) => b
if b[0] != "cell":
["bad", "a range with no cell after its :"] => p[1]
return ["e", "#BAD"]
p[0] + 1 => p[0]
a[1] % 6 => c1
b[1] % 6 => c2
int(a[1] / 6) => r1
int(b[1] / 6) => r2
if c2 < c1:
c1 => t
c2 => c1
t => c2
if r2 < r1:
r1 => t
r2 => r1
t => r2
for r in [r1:r2]:
for c in [c1:c2]:
cells + [r * 6 + c] => cells
else:
cells + [a[1]] => cells
if is_op(peek(ts, p), ","):
p[0] + 1 => p[0]
elif is_op(peek(ts, p), ")"):
p[0] + 1 => p[0]
break
else:
["bad", fname + "( with no , between two cells or no ) at the end"] => p[1]
return ["e", "#BAD"]
# Empty cells and labels are left out, as spreadsheets do; an error in
# any cell makes the whole result that error.
[] => nums
for k in cells:
read_cell(k, vals, refs) => v
if v[0] == "e":
return v
if v[0] == "n" and not (len(vals) > 0 and vals[k][0] == "t"):
nums + [v[1]] => nums
if len(vals) == 0:
return ["n", [0, 1]]
if fname == "SUM" or fname == "AVG":
[0, 1] => s
for x in nums:
frac.plus(s, x) => s
if fname == "SUM":
return ["n", s]
if len(nums) == 0:
return ["e", "#DIV/0"]
return ["n", frac.over(s, [len(nums), 1])]
if len(nums) == 0:
return ["n", [0, 1]]
nums[0] => best
for x in nums:
if fname == "MIN" and frac.less(x, best):
x => best
if fname == "MAX" and frac.less(best, x):
x => best
return ["n", best]
def checked(text):
# Parses a formula ("=" already taken off): [problem or "", the cells it
# reads, the tokens].
tokens(text) => ts
if len(ts) > 0 and ts[0][0] == "bad":
return ["it has " + ts[0][1], [], []]
if len(ts) == 0:
return ["it is empty", [], []]
[0, ""] => p
[[]] => refs
expr(ts, p, [], refs)
if p[1] != "":
return ["it has " + p[1][1], [], []]
if p[0] < len(ts):
return ["something is left over after the formula ends", [], []]
return ["", refs[0], ts]
def value_of(ts, vals):
[0, ""] => p
[[]] => refs
return expr(ts, p, vals, refs)
def recalculated(cells):
# Every cell's value, and the formula cells in the order they were
# worked out. The order is Kahn's algorithm, as in the corpus case
# topological-sort: a formula is ready once every formula it reads is
# done; formulas never ready are caught in a cycle, or read one that is.
[] => vals
[] => formulas
for k in [0:53]:
cells[k] => s
if s == "":
vals + [["t", ""]] => vals
elif s[0] == "=":
vals + [["e", "#CYCLE"]] => vals
formulas + [k] => formulas
else:
frac.parse(s) => x
if len(x) > 0:
vals + [["n", x]] => vals
else:
vals + [["t", s]] => vals
# reads[k]: the formula cells formula k reads, once each
{} => reads
{} => waiting
for k in formulas:
checked(cells[k][1:len(cells[k])]) => c
[] => mine
for r in c[1]:
if cells[r] != "" and cells[r][0] == "=":
False => seen
for m in mine:
if m == r:
True => seen
if not seen:
mine + [r] => mine
mine => reads[k]
len(mine) => waiting[k]
[] => ready
for k in formulas:
if waiting[k] == 0:
ready + [k] => ready
[] => order
0 => head
while head < len(ready):
ready[head] => k
head + 1 => head
order + [k] => order
tokens(cells[k][1:len(cells[k])]) => ts
value_of(ts, vals) => vals[k]
for j in formulas:
for r in reads[j]:
if r == k:
waiting[j] - 1 => waiting[j]
if waiting[j] == 0:
ready + [j] => ready
return [vals, order]
Python projection (sheet.py)
import frac
def cell_name(k):
return "ABCDEF"[k % 6] + str(int(k / 6) + 1)
def cell_index(s):
if len(s) != 2:
return -1
col = -1
for c in range(0, 6):
if s[0] == "ABCDEF"[c] or s[0] == "abcdef"[c]:
col = c
if col == -1 or not (s[1] >= "1" and s[1] <= "9"):
return -1
return (int(s[1]) - 1) * 6 + col
def tokens(f):
out = []
i = 0
while i < len(f):
c = f[i]
if c == " ":
i = i + 1
elif c == "+" or c == "-" or c == "*" or c == "/" or c == "(" or c == ")" or c == ":" or c == ",":
out = out + [["op", c]]
i = i + 1
elif c >= "0" and c <= "9" or c == ".":
j = i
while j < len(f) and (f[j] >= "0" and f[j] <= "9" or f[j] == "."):
j = j + 1
x = frac.parse(f[i:j])
if len(x) == 0:
return [["bad", "the number " + f[i:j]]]
out = out + [["num", x]]
i = j
elif c >= "A" and c <= "Z" or c >= "a" and c <= "z":
j = i
while j < len(f) and (f[j] >= "A" and f[j] <= "Z" or f[j] >= "a" and f[j] <= "z" or f[j] >= "0" and f[j] <= "9"):
j = j + 1
w = f[i:j]
k = cell_index(w)
if k >= 0:
out = out + [["cell", k]]
else:
up = ""
for ch in w:
u = ch
for q in range(0, 26):
if ch == "abcdefghijklmnopqrstuvwxyz"[q]:
u = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[q]
up = up + u
if up == "SUM" or up == "MIN" or up == "MAX" or up == "AVG":
out = out + [["fn", up]]
else:
return [["bad", w + ", which is not a cell from A1 to F9 or one of SUM, MIN, MAX, AVG"]]
i = j
else:
return [["bad", "the character " + c]]
return out
def peek(ts, p):
if p[0] < len(ts):
return ts[p[0]]
return ["end", ""]
def is_op(t, c):
return t[0] == "op" and t[1] == c
def arith(a, b, op):
if a[0] == "e":
return a
if b[0] == "e":
return b
if a[0] == "t" or b[0] == "t":
return ["e", "#TEXT"]
if op == "+":
return ["n", frac.plus(a[1], b[1])]
if op == "-":
return ["n", frac.minus(a[1], b[1])]
if op == "*":
return ["n", frac.times(a[1], b[1])]
if frac.is_zero(b[1]):
return ["e", "#DIV/0"]
return ["n", frac.over(a[1], b[1])]
def read_cell(k, vals, refs):
refs[0] = refs[0] + [k]
if len(vals) == 0:
return ["n", [0, 1]]
v = vals[k]
if v[0] == "t" and v[1] == "":
return ["n", [0, 1]]
return v
def expr(ts, p, vals, refs):
v = term(ts, p, vals, refs)
while is_op(peek(ts, p), "+") or is_op(peek(ts, p), "-"):
op = peek(ts, p)[1]
p[0] = p[0] + 1
v = arith(v, term(ts, p, vals, refs), op)
return v
def term(ts, p, vals, refs):
v = factor(ts, p, vals, refs)
while is_op(peek(ts, p), "*") or is_op(peek(ts, p), "/"):
op = peek(ts, p)[1]
p[0] = p[0] + 1
v = arith(v, factor(ts, p, vals, refs), op)
return v
def factor(ts, p, vals, refs):
t = peek(ts, p)
if is_op(t, "-"):
p[0] = p[0] + 1
return arith(["n", [0, 1]], factor(ts, p, vals, refs), "-")
if t[0] == "num":
p[0] = p[0] + 1
return ["n", t[1]]
if t[0] == "cell":
p[0] = p[0] + 1
return read_cell(t[1], vals, refs)
if is_op(t, "("):
p[0] = p[0] + 1
v = expr(ts, p, vals, refs)
if not is_op(peek(ts, p), ")"):
p[1] = ["bad", "a ( without its )"]
else:
p[0] = p[0] + 1
return v
if t[0] == "fn":
p[0] = p[0] + 1
return function(t[1], ts, p, vals, refs)
p[1] = ["bad", "something missing where a number, a cell or ( should be"]
return ["e", "#BAD"]
def function(fname, ts, p, vals, refs):
if not is_op(peek(ts, p), "("):
p[1] = ["bad", fname + " without ( after it"]
return ["e", "#BAD"]
p[0] = p[0] + 1
cells = []
while True:
a = peek(ts, p)
if a[0] != "cell":
p[1] = ["bad", fname + "( with something other than cells and ranges in it, where " + fname + "(A1:A5) would do"]
return ["e", "#BAD"]
p[0] = p[0] + 1
if is_op(peek(ts, p), ":"):
p[0] = p[0] + 1
b = peek(ts, p)
if b[0] != "cell":
p[1] = ["bad", "a range with no cell after its :"]
return ["e", "#BAD"]
p[0] = p[0] + 1
c1 = a[1] % 6
c2 = b[1] % 6
r1 = int(a[1] / 6)
r2 = int(b[1] / 6)
if c2 < c1:
t = c1
c1 = c2
c2 = t
if r2 < r1:
t = r1
r1 = r2
r2 = t
for r in range(r1, r2+1):
for c in range(c1, c2+1):
cells = cells + [r * 6 + c]
else:
cells = cells + [a[1]]
if is_op(peek(ts, p), ","):
p[0] = p[0] + 1
elif is_op(peek(ts, p), ")"):
p[0] = p[0] + 1
break
else:
p[1] = ["bad", fname + "( with no , between two cells or no ) at the end"]
return ["e", "#BAD"]
nums = []
for k in cells:
v = read_cell(k, vals, refs)
if v[0] == "e":
return v
if v[0] == "n" and not (len(vals) > 0 and vals[k][0] == "t"):
nums = nums + [v[1]]
if len(vals) == 0:
return ["n", [0, 1]]
if fname == "SUM" or fname == "AVG":
s = [0, 1]
for x in nums:
s = frac.plus(s, x)
if fname == "SUM":
return ["n", s]
if len(nums) == 0:
return ["e", "#DIV/0"]
return ["n", frac.over(s, [len(nums), 1])]
if len(nums) == 0:
return ["n", [0, 1]]
best = nums[0]
for x in nums:
if fname == "MIN" and frac.less(x, best):
best = x
if fname == "MAX" and frac.less(best, x):
best = x
return ["n", best]
def checked(text):
ts = tokens(text)
if len(ts) > 0 and ts[0][0] == "bad":
return ["it has " + ts[0][1], [], []]
if len(ts) == 0:
return ["it is empty", [], []]
p = [0, ""]
refs = [[]]
expr(ts, p, [], refs)
if p[1] != "":
return ["it has " + p[1][1], [], []]
if p[0] < len(ts):
return ["something is left over after the formula ends", [], []]
return ["", refs[0], ts]
def value_of(ts, vals):
p = [0, ""]
refs = [[]]
return expr(ts, p, vals, refs)
def recalculated(cells):
vals = []
formulas = []
for k in range(0, 54):
s = cells[k]
if s == "":
vals = vals + [["t", ""]]
elif s[0] == "=":
vals = vals + [["e", "#CYCLE"]]
formulas = formulas + [k]
else:
x = frac.parse(s)
if len(x) > 0:
vals = vals + [["n", x]]
else:
vals = vals + [["t", s]]
reads = {}
waiting = {}
for k in formulas:
c = checked(cells[k][1:len(cells[k])])
mine = []
for r in c[1]:
if cells[r] != "" and cells[r][0] == "=":
seen = False
for m in mine:
if m == r:
seen = True
if not seen:
mine = mine + [r]
reads[k] = mine
waiting[k] = len(mine)
ready = []
for k in formulas:
if waiting[k] == 0:
ready = ready + [k]
order = []
head = 0
while head < len(ready):
k = ready[head]
head = head + 1
order = order + [k]
ts = tokens(cells[k][1:len(cells[k])])
vals[k] = value_of(ts, vals)
for j in formulas:
for r in reads[j]:
if r == k:
waiting[j] = waiting[j] - 1
if waiting[j] == 0:
ready = ready + [j]
return [vals, order]
frac.eml
eml# P056 mini spreadsheet - exact fractions, from P007 (calculator) by way of
# P038 and P044.
# A number is a list [n, d]: n / d in lowest terms with d > 0. Integers have
# no size limit, but EML has no //, and a / b goes through a float that cannot
# hold a large quotient exactly, so whole-number division is written out.
def quotient(a, b):
# a // b for whole numbers a >= 0 and b > 0, exact at any size. Long
# division by doubling: take away the largest b * 2^k that still fits.
0 => q
while a >= b:
b => m
1 => k
while m + m <= a:
m + m => m
k + k => k
a - m => a
q + k => q
return q
def gcd(a, b):
while b != 0:
a % b => r
b => a
r => b
return a
def make(n, d):
# n / d in lowest terms with a positive denominator (d != 0).
if d < 0:
0 - n => n
0 - d => d
abs(n) => a
gcd(a, d) => g
if n < 0:
return [0 - quotient(a, g), quotient(d, g)]
return [quotient(a, g), quotient(d, g)]
def plus(x, y):
return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])
def minus(x, y):
return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])
def times(x, y):
return make(x[0] * y[0], x[1] * y[1])
def over(x, y):
# x / y; the caller has checked that y is not zero.
return make(x[0] * y[1], x[1] * y[0])
def is_zero(x):
return x[0] == 0
def digits_value(s):
# The value of a string of 1 to 9 digits, otherwise -1.
if s == "" or len(s) > 9:
return -1
0 => n
for c in s:
if not (c in "0123456789"):
return -1
n * 10 + int(c) => n
return n
def parse(s):
# "3", "-2", "3/4", "-0.25" as a fraction; [] if it is not a number.
1 => sign
if len(s) > 0 and s[0] == "-":
-1 => sign
s[1:len(s)] => s
0 => k
while k < len(s) and s[k] != "/" and s[k] != ".":
k + 1 => k
if k == len(s):
digits_value(s) => n
if n < 0:
return []
return make(sign * n, 1)
digits_value(s[0:k]) => whole
s[k + 1:len(s)] => rest
digits_value(rest) => part
if whole < 0 or part < 0:
return []
if s[k] == "/":
if part == 0:
return []
return make(sign * whole, part)
# a decimal point: 0.25 is 25 / 100
1 => scale
for c in rest:
scale * 10 => scale
return make(sign * (whole * scale + part), scale)
def less(x, y):
return x[0] * y[1] < y[0] * x[1]
def decimal(x, places):
# x to the given number of decimal places, halves rounded away from zero,
# with "about " in front when the value does not end there exactly.
"" => sign
abs(x[0]) => n
if x[0] < 0:
"-" => sign
1 => scale
for k in [1:places]:
scale * 10 => scale
quotient(2 * n * scale + x[1], 2 * x[1]) => t
"" => about
if (n * scale) % x[1] != 0:
"about " => about
str(quotient(t, scale)) => whole
str(t % scale) => part
while len(part) < places:
"0" + part => part
# drop trailing zeros of an exact value
if about == "":
while len(part) > 0 and part[len(part) - 1] == "0":
part[0:len(part) - 1] => part
if t == 0:
"" => sign
if part == "":
return about + sign + whole
return about + sign + whole + "." + part
def text(x):
# "3", "-3", "3/4", "-3/4".
if x[1] == 1:
return str(x[0])
return str(x[0]) + "/" + str(x[1])
Python projection (frac.py)
def quotient(a, b):
q = 0
while a >= b:
m = b
k = 1
while m + m <= a:
m = m + m
k = k + k
a = a - m
q = q + k
return q
def gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
def make(n, d):
if d < 0:
n = 0 - n
d = 0 - d
a = abs(n)
g = gcd(a, d)
if n < 0:
return [0 - quotient(a, g), quotient(d, g)]
return [quotient(a, g), quotient(d, g)]
def plus(x, y):
return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])
def minus(x, y):
return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])
def times(x, y):
return make(x[0] * y[0], x[1] * y[1])
def over(x, y):
return make(x[0] * y[1], x[1] * y[0])
def is_zero(x):
return x[0] == 0
def digits_value(s):
if s == "" or len(s) > 9:
return -1
n = 0
for c in s:
if not c in "0123456789":
return -1
n = n * 10 + int(c)
return n
def parse(s):
sign = 1
if len(s) > 0 and s[0] == "-":
sign = -1
s = s[1:len(s)]
k = 0
while k < len(s) and s[k] != "/" and s[k] != ".":
k = k + 1
if k == len(s):
n = digits_value(s)
if n < 0:
return []
return make(sign * n, 1)
whole = digits_value(s[0:k])
rest = s[k + 1:len(s)]
part = digits_value(rest)
if whole < 0 or part < 0:
return []
if s[k] == "/":
if part == 0:
return []
return make(sign * whole, part)
scale = 1
for c in rest:
scale = scale * 10
return make(sign * (whole * scale + part), scale)
def less(x, y):
return x[0] * y[1] < y[0] * x[1]
def decimal(x, places):
sign = ""
n = abs(x[0])
if x[0] < 0:
sign = "-"
scale = 1
for k in range(1, places+1):
scale = scale * 10
t = quotient(2 * n * scale + x[1], 2 * x[1])
about = ""
if n * scale % x[1] != 0:
about = "about "
whole = str(quotient(t, scale))
part = str(t % scale)
while len(part) < places:
part = "0" + part
if about == "":
while len(part) > 0 and part[len(part) - 1] == "0":
part = part[0:len(part) - 1]
if t == 0:
sign = ""
if part == "":
return about + sign + whole
return about + sign + whole + "." + part
def text(x):
if x[1] == 1:
return str(x[0])
return str(x[0]) + "/" + str(x[1])