Combine scopes, type inference and type rules into a checker for statements.
What to build
A program that type-checks a small block-structured program and lists every line with an error.
Requirements
- Statements:
let NAME = EXPRdeclares NAME with the type of EXPR (inferred);set NAME = EXPRassigns;if EXPRandwhile EXPRstart a block that ends atend;print EXPR. Expressions are trees in prefix form with the rules and messages of the previous exercise. - For each line, report only its first error as
line K: MESSAGE: an expression error;NAME is already declaredfor aletof a name in the same scope;NAME is not declaredfor asetof an unknown name;cannot assign T to NAME of type U;condition is T, not bool. Aletwith an error declares nothing. If there are no errors, printno type errors.
Input
Line 1: n. Then n lines; blocks are balanced.
Output
One line per error, or no type errors.
Constraints
n ≤ 60.
Example
Input:
5
let n = 10
let big = (< 100 n)
set n = (+ n 1)
set big = n
print (+ "n = " n)
Output:
line 4: cannot assign int to big of type bool
line 5: + cannot take str and int
Why it works
The symbol table supplies each variable's type, inference fills it in at the let, and the expression rules check everything else, line by line.
Examples
Example 1 · Input
5 let n = 10 let big = (< 100 n) set n = (+ n 1) set big = n print (+ "n = " n)
Expected output
line 4: cannot assign int to big of type bool line 5: + cannot take str and int
Example 2 · Input
4 let i = 0 while (< i 3) set i = (+ i 1) end
Expected output
no type errors
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a stack of scopes mapping names to types; `if` and `while` push a scope, `end` pops it.
Hint 2
For each line, check its expression first; stop at the first error on that line and move on to the next line.
Solution
Show one correct solution (try it yourself first)
import re
RULES = {
("+", "int", "int"): "int",
("-", "int", "int"): "int",
("*", "int", "int"): "int",
("+", "str", "str"): "str",
("<", "int", "int"): "bool",
("and", "bool", "bool"): "bool",
("or", "bool", "bool"): "bool",
("not", "bool"): "bool",
}
scopes = [{}]
class TypeCheckError(Exception):
pass
def lookup(name):
for scope in reversed(scopes):
if name in scope:
return scope[name]
return None
def read(text):
tokens = re.findall(r'\(|\)|"[^"]*"|[^\s()]+', text)
def node():
token = tokens.pop(0)
if token != "(":
return token
items = []
while tokens[0] != ")":
items.append(node())
tokens.pop(0)
return items
return node()
def check(node):
if isinstance(node, str):
if node.isdigit():
return "int"
if node.startswith('"'):
return "str"
if node in ("true", "false"):
return "bool"
found = lookup(node)
if found is None:
raise TypeCheckError(f"{node} is not declared")
return found
op, *args = node
types = [check(arg) for arg in args]
if op == "if":
if types[0] != "bool":
raise TypeCheckError(f"if needs a bool condition, not {types[0]}")
if types[1] != types[2]:
raise TypeCheckError(f"if branches differ: {types[1]} and {types[2]}")
return types[1]
if op == "==" and types[0] == types[1]:
return "bool"
key = (op, *types)
if key not in RULES:
raise TypeCheckError(f"{op} cannot take {' and '.join(types)}")
return RULES[key]
errors = []
for k in range(1, int(input()) + 1):
line = input().strip()
try:
if line == "end":
scopes.pop()
continue
m = re.fullmatch(r"(let|set) (\w+) = (.+)", line)
if m:
kind, name, expr = m.groups()
t = check(read(expr))
if kind == "let":
if name in scopes[-1]:
raise TypeCheckError(f"{name} is already declared")
scopes[-1][name] = t
else:
target = lookup(name)
if target is None:
raise TypeCheckError(f"{name} is not declared")
if target != t:
raise TypeCheckError(f"cannot assign {t} to {name} of type {target}")
continue
kind, expr = line.split(" ", 1)
if kind in ("if", "while"):
scopes.append({})
t = check(read(expr))
if t != "bool":
raise TypeCheckError(f"condition is {t}, not bool")
else:
check(read(expr))
except TypeCheckError as error:
errors.append(f"line {k}: {error}")
print("\n".join(errors) if errors else "no type errors")