Foundationপ্রথম নীতি থেকে
LEVEL 5কঠিন~১৫ ঘণ্টাPython

Tiny Lisp Interpreter

Tiny Lisp Interpreter

কয়েকশো লাইনের Python-এ একটা কাজ করা Lisp dialect — s-expression reader, environment chain, closure, special forms, আর tail-call optimization সহ REPL। 'Function as value' আর lexical scope কাগজে-কলমে চালু প্রোগ্রামে কীভাবে বাস্তবায়িত হয় সেটাই এখানের শিক্ষা।

মাইলস্টোন

আগে যা পড়া দরকার

কেন এই প্রজেক্ট

Closures-and-environments লেসনে আমরা দেখেছি closure আসলে কী — একটা function তার জন্মের environment-এর reference সাথে নিয়ে ঘোরে। Evaluation-strategies লেসনে দেখেছি eager আর lazy eval-এর পার্থক্য। কিন্তু দুটোই ছিল অন্য কারো লেখা ভাষার বৈশিষ্ট্য। এই প্রজেক্টে সেই বৈশিষ্ট্যগুলো আপনিই বানাবেন — আর সবচেয়ে ছোট ভাষা দিয়ে, কারণ Lisp-এর syntax-ই তার AST: (a b c) মানেই একটা list node, parse tree আর source প্রায় একই জিনিস।

ফলে ভাষা-বাস্তবায়নের আসল সমস্যাগুলো — environment chain-এ variable lookup, closure-এ captured env, tail position চেনা — syntax-এর ঝামেলায় আটকে না থেকে সরাসরি দেখা যায়। পুরো interpreter ২০০–৪০০ লাইনে আঁটে, কিন্তু শেষ করলে Scheme-এর eval/apply cycle যে দুটো ফাংশন, সেটা আর গোপন জাদু থাকে না।

ধাপে ধাপে

১. Tokenizer + reader — টেক্সট থেকে AST

Lisp-এ token মাত্র কয়েক রকম: (, ), symbol, number। Paren-কে space-এ রূপান্তর করে split-ই যথেষ্ট:

def tokenize(src):
    return src.replace('(', ' ( ').replace(')', ' ) ').split()

def parse_all(src):
    tokens = tokenize(src)
    program = []
    while tokens:
        program.append(read_from(tokens))
    return program

def read_from(tokens):
    tok = tokens.pop(0)
    if tok == '(':
        expr = []
        while tokens[0] != ')':
            expr.append(read_from(tokens))
        tokens.pop(0)               # ')' খেয়ে ফেলুন
        return expr
    elif tok == ')':
        raise SyntaxError('অপ্রত্যাশিত )')
    else:
        return atom(tok)

def atom(tok):
    try:
        return int(tok)
    except ValueError:
        try:
            return float(tok)
        except ValueError:
            return Symbol(tok)

Representation খুব সরল: Symbol হলো str-এর subclass, number হলো int/float, list হলো Python list। মানে source-এর (define x 5) আসলে Python-এ ['define', 'x', 5] — code is data এখানে metaphor না, literal fact।

২. Environment — parent pointer সহ dict

class Symbol(str): pass

class Env(dict):
    def __init__(self, params=(), args=(), outer=None):
        self.update(zip(params, args))
        self.outer = outer

    def find(self, var):
        if var in self:
            return self
        if self.outer is None:
            raise NameError(f'{var} defined নয়')
        return self.outer.find(var)

Lookup চেইনটাই lexical scoping-এর পুরো বাস্তবায়ন: নিজের frame-এ না পেলে parent-এ, তারপর তার parent-এ। Global frame-এ পৌঁছালে সেখানে builtin (+, car, null?) বসানো থাকবে।

৩. evaluate — special form আর application

def evaluate(x, env):
    if isinstance(x, Symbol):
        return env.find(x)[x]
    if not isinstance(x, list):
        return x                     # number/string self-evaluate
    op = x[0]
    if op == 'quote':
        return x[1]
    if op == 'if':
        test, conseq, alt = x[1], x[2], x[3]
        return evaluate(conseq if evaluate(test, env) else alt, env)
    if op == 'define':
        _, name, expr = x
        env[name] = evaluate(expr, env)
        return None
    if op == 'set!':
        _, name, expr = x
        env.find(name)[name] = evaluate(expr, env)
        return None
    if op == 'lambda':
        return Procedure(x[1], x[2], env)
    proc = evaluate(op, env)
    args = [evaluate(a, env) for a in x[1:]]
    return proc.call(args)

লক্ষ্য করুন কোন branch-গুলো argument evaluate করে আর কোনগুলো করে না। (+ a b)-এর + যদি special form হতো না, তো a b আগে evaluate হয়। কিন্তু (if test conseq alt)-এ conseq আর alt দুটোই evaluate করলে side effect আর infinite loop-এ ভাষা ভেঙে যায়। Special form-এর সংজ্ঞাই — “argument না খেয়ে নিজের হাতে নেয়।”

৪. Closure — captured env

class Procedure:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env

    def call(self, args):
        if len(args) != len(self.params):
            raise TypeError(f'{len(self.params)} argument চাই, পেয়েছে {len(args)}')
        return evaluate(self.body, Env(self.params, args, self.env))

Closure-এর রহস্য এই Env(self.params, args, self.env) লাইনে: call-এর সময় নতুন frame তৈরি হয়, কিন্তু তার parent হলো call-site-এর env নয় — definition-site-এর env। Dynamic না, lexical। যাচাই করুন:

tlis> (define (make-adder n) (lambda (x) (+ x n)))
tlis> (define add5 (make-adder 5))
tlis> (add5 3)
8

make-adder return করার পরেও তার frame-টা মরেনি — add5-এর closure ধরে রেখেছে। এই জীবিত-frame ধারণাটাই পরে GC-এর reachability-তে কাজে লাগবে।

৫. let / letrec — desugar, নতুন feature না

let নতুন machinery না — lambda-apply-এর sugar:

(let ((x 1) (y 2)) body)
≡  ((lambda (x y) body) 1 2)

Interpreter-এ এটা একটা ছোট transform ফাংশন, evaluate করার আগেই AST বদলে দেয়:

def desugar_let(expr):
    bindings, body = expr[1], expr[2]
    names  = [b[0] for b in bindings]
    vals   = [b[1] for b in bindings]
    return [['lambda', names, body]] + vals

letrec একই কৌশলে যায়, শুধু প্রতিটা name-কে আগে undefined দিয়ে pre-bind করে তারপর set! — নইলে mutually recursive definition-এর একটা চোখে দেখা bug হতো: lambda body-তে ঢোকার সময় sibling-এর binding এখনো না থাকা।

Checkpoint: mutual recursion চলবে —

tlis> (define (even? n) (if (= n 0) #t (odd? (- n 1))))
tlis> (define (odd? n)  (if (= n 0) #f (even? (- n 1))))
tlis> (even? 100001)
#t

(শেষ লাইনটা চলতে হলে পরের ধাপ দরকার — আপাতত 10001 দিয়ে টেস্ট করুন।)

৬. Tail call — trampoline বা TCO loop

উপরের evaluate প্রতিটা subexpression-এর জন্য Python recursion করে। Tail position-এর call (if-এর শেষ branch, body-র শেষ expr) Python stack-এ frame জমায় — ১০০০-এর বেশি গভীর হলে RecursionError। সমাধান দুটো:

TCO loop — evaluate-কে while True লুপে ঢুকিয়ে tail position replace করুন, recurse না করে:

def evaluate(x, env):
    while True:
        if isinstance(x, Symbol):
            return env.find(x)[x]
        if not isinstance(x, list):
            return x
        op = x[0]
        if op == 'if':
            test, conseq, alt = x[1], x[2], x[3]
            x = conseq if evaluate(test, env) else alt   # tail — continue
            continue
        if op == 'define':
            ...
        proc = evaluate(op, env)
        args = [evaluate(a, env) for a in x[1:]]
        if isinstance(proc, Procedure):
            x, env = proc.body, Env(proc.params, args, proc.env)  # tail call
            continue
        return proc.call(args)

Non-tail argument eval (args = [...]) তবু Python recursion করে — ঠিক আছে, সেটা expression-এর গভীরতা, recursion-এর দৈর্ঘ্য নয়। Fibonacci-র মতো branching recursion এতে বাঁচে না, কিন্তু loop-হিসেবে লেখা recursion (উপরের even?/odd?) এখন constant stack-এ চলে।

Trampoline — evaluator tail call-এ value না ফেরত দিয়ে একটা Thunk('call', proc, args) ফেরত দেয়, আর বাইরের ড্রাইভার লুপ value না পাওয়া পর্যন্ত bounce করে। Evaluation-strategies লেসনের delay/force-এরই আত্মীয় — পরে lazy evaluation যোগ করতে চাইলে এই পথ সহজ।

Checkpoint: (even? 1000001) এখন ঠিক উত্তর দেবে, Python stack এক বিটও না বাড়িয়ে।

৭. REPL + টেস্ট

def repl():
    env = global_env()
    while True:
        try:
            line = input('tlis> ')
        except EOFError:
            print()
            break
        try:
            val = evaluate(parse(line), env)
            if val is not None:
                print(lisp_str(val))
        except Exception as e:
            print(f'error: {e}')

Golden-output টেস্ট ফাইলে জোড়া দিয়ে রাখুন — input expression, তারপর expected print:

inputexpected
(define (fib n) (if (\< 2) n ...)) সহ fib—
(fib 10)55
(map (lambda (x) (* x x)) (list 1 2 3))(1 4 9)
(filter odd? (list 1 2 3 4 5))(1 3 5)

Higher-order case দুটো জরুরি — builtin Python ফাংশনকে argument হিসেবে user closure পাঠানো মানে দুই world-এর function calling convention এক জায়গায় মেলাতে হবে।

নিজেকে চ্যালেঞ্জ করুন

  1. cond, and, or — short-circuit semantics সহ special form
  2. String আর begin block — multiple-expression body
  3. Lazy evaluation — delay/force বা promise-based cons stream
  4. Error-এ source position — reader-এ line:col ট্র্যাক করে ভালো message
  5. Mark-sweep GC প্রজেক্টের collector-কে এই interpreter-এর object model-এ জোড়ার পরিকল্পনা করুন — root কারা?
  6. Bytecode VM প্রজেক্টের জন্য প্রস্তুতি — এই tree-walker eval-কে bytecode-এ compile করলে কোন ধাপগুলো বদলাবে?

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানেপরে
eval/apply cycleCompilers — Bytecode VM-এ একই লজিক, dispatch loop-এ
Environment chain ও closureType Checker প্রজেক্ট — type environment-এ একই shape
Special form বনাম functionMacro আর DSL design-এর ভিত্তি
TCO/trampolineCoroutine আর async runtime — একই continuation-ব্যবস্থাপনা