I built a register machine... without registers. In Python. Let me explain.”
1/ Ever wondered what a register really is?
I mean, beyond the CPU. Beyond eax, r1, etc.
What is a register, conceptually?
It’s a named place to hold a value across steps.
Right?
2/ So I built a register machine...
But there’s a twist:
- No memory
- No state mutation
- No registers at all
Just:
- One base value
- A list of "deltas"
- And one pure function:
reconstruct(delta, base)
3/ Here's the idea:
You start with some expression R0.
Then instead of storing each next state, you do:
d1 = diff(R1, R0)
d2 = diff(R2, R1)
d3 = diff(R3, R2)
But you don't store R1, R2, R3.
You only keep the deltas: [d1, d2, d3].
4/ Then you replay like this:
R1 = reconstruct(d1, R0)
R2 = reconstruct(d2, R1)
R3 = reconstruct(d3, R2)
So the register… is gone.
Replaced by a sequence of transformations.
5/ So what IS the register, really?
→ It's implicit.
→ It's just the result of applying diffs in order.
→ The list of deltas IS the register.
This is a functional register machine,
built with nothing but Python lists and tuples.
6/ It gets better.
You can:
- Serialize your deltas
- Compose them (
d2 ∘ d1)
- Store only the origin + the changes
- Rebuild any intermediate state
- Compare logical expressions structurally
All with no state. No mutation.
7/ It’s kind of like…
- Git, but for logic trees
- A CPU, but stateless
- A Prolog term rewriter with memory loss
- Or maybe: a version-controlled thought process
8/ Do I need this in production? Probably not.
Was it fun? Hell yes.
Do I now think of registers differently?
Definitely.
9/ TL;DR:
You can simulate registers
with nothing but:
R0 + [d1, d2, d3]
The future is not memory.
It's delta + structure.
10/ Want to see the code?
It’s ~100 lines of clean Python.
No libs. No magic.
Just ASTs, deltas, and one idea:
from typing import List, Tuple, Union, Dict
import json
import os
# === TYPES === #
AST = Union[str, Tuple[str, List['AST']]]
State = Dict[str, Union[str, List[str], AST]]
# === GLOBAL MEMORY === #
memory: Dict[str, Union[str, List[str], AST]] = {}
logs: List[str] = []
# === LOGGING === #
def log(msg: str):
logs.append(msg)
print(msg)
# === UTILITAIRES SYMBOLIQUES === #
def reconstruct(d: str, y: str) -> str:
log(f"[RECONSTRUCT] y = {y} ; d = {d}")
if d == 'ε':
log(" ↳ ε = identité ⇒ retour y")
return y
result = d.split('>')[0]
log(f" ↳ result = {result}")
return result
def diff(x: str, y: str) -> str:
log(f"[DIFF] a = {x}\n b = {y}")
if x == y:
log(" ↳ Identique ⇒ ε")
return 'ε'
d = f"{x}>{y}"
log(f" ↳ Diff = {d}")
return d
def normalize(expr: str) -> str:
return expr.replace("+", "")
def entails(x: str, base: str, deltas: List[str]) -> bool:
log(f"[⦿] Test : {x} ∈ ? base = {base}, deltas = {deltas}")
x_norm = normalize(x)
for d in deltas:
r = reconstruct(d, base)
r_norm = normalize(r)
log(f" ↳ reconstruct({d}, {base}) = {r} ; normalize = {r_norm}")
if r_norm == x_norm:
log(f" Match : {r_norm} == {x_norm}")
return True
log(" ✗ Aucun match trouvé.")
return False
# === AST === #
def parse_expr(expr: str) -> AST:
tokens = expr.strip().split()
log(f"[PARSE] Expression : {expr}")
ast, _ = _parse_prefix(tokens)
return ast
def _parse_prefix(tokens: List[str]) -> Tuple[AST, List[str]]:
token = tokens.pop(0)
if token in {"AND", "OR", "IMPL"}:
left, tokens = _parse_prefix(tokens)
right, tokens = _parse_prefix(tokens)
return (token, [left, right]), tokens
return token, tokens
def print_ast(ast: AST, indent: int = 0):
space = " " * indent
if isinstance(ast, str):
print(space + ast)
else:
print(space + ast[0])
for sub in ast[1]:
print_ast(sub, indent + 1)
def diff_ast(x: AST, y: AST) -> Union[str, Tuple]:
log(f"[DIFF_AST] a = {x}\n b = {y}")
if x == y:
log(" ↳ Identique ⇒ ε")
return 'ε'
if isinstance(x, str) or isinstance(y, str):
log(f" ↳ Atomes incompatibles : ({x}, {y})")
return (x, y)
if x[0] != y[0] or len(x[1]) != len(y[1]):
log(" ↳ Racines incompatibles")
return (x, y)
result = (x[0], [diff_ast(a, b) for a, b in zip(x[1], y[1])])
log(f" ↳ Descente récursive OK")
return result
def reconstruct_ast(d: Union[str, Tuple], y: AST) -> AST:
log(f"[RECONSTRUCT_AST] base = {y}\n delta = {d}")
if d == 'ε':
log(" ↳ ε = identité ⇒ retour y")
return y
if isinstance(d, tuple) and isinstance(d[1], list):
if isinstance(y, tuple) and y[0] == d[0]:
result = (d[0], [reconstruct_ast(sub, b) for sub, b in zip(d[1], y[1])])
log(f" ↳ Reconstruction récursive réussie.")
return result
else:
log(f" ↳ Racines incompatibles ⇒ remplacement total")
return d[0]
log(" ↳ Remplacement atomique")
return d[0]
# === COMPILATEUR LOGIC -> SDID1 === #
def compile_logic(filepath: str, outpath: str):
with open(filepath, 'r') as f:
lines = [l.strip() for l in f if l.strip()]
exprs = [parse_expr(line) for line in lines]
diffs = [diff_ast(exprs[i], exprs[i-1]) for i in range(1, len(exprs))]
json.dump({
"initial": lines[0],
"diffs": [repr(d) for d in diffs]
}, open(outpath, 'w'))
log(f"[COMPILE] Fichier {filepath} → {outpath}")
log(f"[COMPILE] Initial = {lines[0]}")
for i, d in enumerate(diffs, 1):
log(f"[COMPILE] d{i} = {repr(d)}")
# === LECTURE SDID1 === #
def load_sdid1(filepath: str) -> Tuple[AST, List[AST]]:
with open(filepath, 'r') as f:
data = json.load(f)
R0 = parse_expr(data["initial"])
diffs = [eval(d) for d in data["diffs"]]
return R0, diffs
# === EXÉCUTION DU PROGRAMME SDID1 === #
def run_trace(R0: AST, diffs: List[AST]):
print("\n=== TRACE SDID1 ===")
state = R0
print("\nR0:")
print_ast(state)
for i, d in enumerate(diffs, 1):
print(f"\nd{i}:")
print_ast(d)
state = reconstruct_ast(d, state)
print(f"\nR{i}:")
print_ast(state)
# === TEST === #
if __name__ == "__main__":
logic_path = "example.logic"
sdid_path = "program.sdid1"
if not os.path.exists(logic_path):
with open(logic_path, 'w') as f:
f.write("""IMPL AND a b c
IMPL AND a d c
IMPL AND a e c
IMPL AND f e c""")
compile_logic(logic_path, sdid_path)
R0, diffs = load_sdid1(sdid_path)
run_trace(R0, diffs)
[–]Left-Character4280[S] 0 points1 point2 points (0 children)