Type Checking — checker আসলে একটা ছোট evaluator

toylang/typecheck.py:

"""ToyLang semantic pass 2: type checking.
Needs: toylang/ast.py (lesson 5).
"""
from dataclasses import dataclass
from toylang.ast import (Program, LetStmt, Print, IfStmt,
                         WhileStmt, ExprStmt, NumLit, StrLit,
                         BoolLit, VarRef, BinOp, UnaryOp)


@dataclass
class TypeErr:
    msg: str
    line: int
    col: int
    end_col: int
    found: str | None = None

    def render(self):
        at = f"@{self.line}:{self.col}-{self.end_col}"
        extra = f" (found {self.found})" if self.found else ""
        return f"error[type]: {self.msg}{extra} {at}"


UNKNOWN = "?"          # poison pill after an error

# ---- operator signature table: op -> [(l, r, result)] ----------
SIGNATURES = {
    "plus":   [("int", "int", "int"),
               ("str", "str", "str")],
    "minus":  [("int", "int", "int")],
    "star":   [("int", "int", "int")],
    "slash":  [("int", "int", "int")],
    "eqeq":   [("T", "T", "bool")],        # T = same-type
    "bangeq": [("T", "T", "bool")],
    "lt":     [("int", "int", "bool")],
    "gt":     [("int", "int", "bool")],
    "lte":    [("int", "int", "bool")],
    "gte":    [("int", "int", "bool")],
    "andand": [("bool", "bool", "bool")],
    "oror":   [("bool", "bool", "bool")],
}
UNARY_SIG = {"neg": [("int", "int")],
             "not": [("bool", "bool")]}


def _span(n):
    return n.span.line, n.span.col, n.span.end_col


class TypeChecker:
    """A tiny evaluator: computes TYPES instead of values."""

    def __init__(self):
        self.scopes = [{}]
        self.errors = []

    # ---- environment ----------------------------------------------
    def _push(self): self.scopes.append({})

    def _pop(self): self.scopes.pop()

    def _bind(self, name, ty):
        self.scopes[-1][name] = ty

    def _lookup(self, name):
        for sc in reversed(self.scopes):
            if name in sc:
                return sc[name]
        return UNKNOWN          # resolver's job really; be lenient

    def _err(self, msg, node, found=None):
        l, c, e = _span(node)
        self.errors.append(TypeErr(msg, l, c, e, found))

    # ---- statements ---------------------------------------------------
    def check(self, prog: Program):
        for s in prog.stmts:
            self.stmt(s)

    def stmt(self, s):
        if isinstance(s, LetStmt):
            ty = self.expr(s.init)
            self._bind(s.name, ty)
        elif isinstance(s, Print):
            self.expr(s.arg)                 # any type, arity 1
        elif isinstance(s, ExprStmt):
            self.expr(s.expr)
        elif isinstance(s, IfStmt):
            self._need_bool(s.cond, "if condition")
            self._block(s.then)
            if s.else_ is not None:
                self._block(s.else_)
        elif isinstance(s, WhileStmt):
            self._need_bool(s.cond, "while condition")
            self._block(s.body)

    def _need_bool(self, e, where):
        """Checking mode: expected 'bool' flows down from context."""
        ty = self.expr(e)
        if ty != "bool" and ty != UNKNOWN:
            self._err(f"{where} must be bool", e, found=ty)

    def _block(self, stmts):
        self._push()
        for s in stmts:
            self.stmt(s)
        self._pop()

    # ---- expressions: the little evaluator --------------------------
    # (synth mode: type rises from children; positional checks like
    #  if-cond are the checking mode — hint flows down from context)
    def expr(self, e) -> str:
        if isinstance(e, NumLit):
            return "int"
        if isinstance(e, StrLit):
            return "str"
        if isinstance(e, BoolLit):
            return "bool"
        if isinstance(e, VarRef):
            return self._lookup(e.name)
        if isinstance(e, UnaryOp):
            got = self.expr(e.operand)
            for want, res in UNARY_SIG[e.op]:
                if got == want:
                    return res
            self._err(f"unary '{e.op}' not defined "
                      f"for {got}", e, found=got)
            return UNKNOWN
        if isinstance(e, BinOp):
            return self.bin(e)
        raise AssertionError(type(e))

    def bin(self, e: BinOp) -> str:
        lt = self.expr(e.left)
        rt = self.expr(e.right)
        if lt == UNKNOWN or rt == UNKNOWN:
            return UNKNOWN                   # cascade suppression

        # const-folding opportunity noticed HERE (free preview!)
        if (isinstance(e.left, NumLit)
                and isinstance(e.right, NumLit)):
            pass                             # IR lesson will use this

        for wl, wr, res in SIGNATURES[e.op]:
            ok_l = wl == "T" or lt == wl
            ok_r = wr == "T" or rt == wr
            if ok_l and ok_r and (
                    wl != "T" or lt == rt):  # same-type for T
                return res
        self._err(f"operator '{e.op}' not defined "
                  f"for {lt} and {rt}", e, found=f"{lt},{rt}")
        return UNKNOWN


def run_checker(src_ast: Program):
    c = TypeChecker()
    c.check(src_ast)
    return c.errors

Test harness — ছয়টা failing program:

def _test():
    from toylang.ast import (Span, NumLit, StrLit, BoolLit,
                             VarRef, BinOp, UnaryOp, LetStmt,
                             Print, IfStmt, WhileStmt)

    def num(v, l=1, c=1):
        return NumLit(Span(l, c, c + len(str(v))), v)

    def var(n, l=1, c=1):
        return VarRef(Span(l, c, c + len(n)), n)

    # explicit-span BinOp helper (spans rough is fine for tests)
    def B(op, l_, r_, ln=1, c=1):
        return BinOp(Span(ln, c, c + 3), op, l_, r_)

    def errs(prog):
        es = run_checker(prog)
        return [e.msg for e in es]

    # 1. if-condition is int, not bool
    p = Program((IfStmt(Span(1, 1, 12),
                        B("plus", num(1), num(2)), (), None),))
    assert any("must be bool" in m for m in errs(p))

    # 2. arithmetic on bool
    p = Program((ExprStmt(Span(1, 1, 14),
                          B("plus", BoolLit(Span(1, 1, 5), True),
                            BoolLit(Span(1, 9, 13), False))),))
    assert any("'+' not defined for bool and bool" in m
               for m in errs(p))

    # 3. == across different types
    p = Program((ExprStmt(Span(1, 1, 10),
                          B("eqeq", num(1),
                            BoolLit(Span(1, 6, 9), True))),))
    assert any("'==' not defined for int and bool" in m
               for m in errs(p))

    # 4. mixed + (str, int)
    p = Program((LetStmt(Span(1, 1, 20), "greet",
                         StrLit(Span(1, 12, 18), "hi")),
                 ExprStmt(Span(2, 1, 22),
                          B("plus", var("greet"), num(5)))),)
    assert any("'+' not defined for str and int" in m
               for m in errs(p))

    # 5. while-condition is str
    p = Program((WhileStmt(Span(1, 1, 16),
                           StrLit(Span(1, 8, 10), "x"), ()),))
    assert any("while condition must be bool" in m
               for m in errs(p))

    # 6. unary ! on int
    p = Program((ExprStmt(Span(1, 1, 5),
                          UnaryOp(Span(1, 1, 4), "not",
                                  num(42))),))
    assert any("unary 'not' not defined for int" in m
               for m in errs(p))

    print("all 6 type-error tests passed")

if __name__ == "__main__":
    _test()

Expected:

$ python3 toylang/typecheck.py
all 6 type-error tests passed

Sample rendered diagnostic (demo main দিয়ে):

error[type]: operator '+' not defined for str and int (found str,int) @2:3-2:6

নিজে বাড়ান:

1. Widening ladder step যোগ করুন: float type + int→float implicit — শুধু signature table আর compatible() change হবে? Verify: logic untouched claim।
2. Const-fold actually implement করুন: expr() returns (ty, maybe_value) tuple — IR lesson-এর জন্য ready হোন।
3. !=-এ structural rule ভাঙুন deliberately (T-constraint বাদ) — কোন new program এখন fail করে সেটা observe করুন।