Evaluation Strategy — strict না lazy: expression কখন মূল্যায়িত হয়

লক্ষ্য: formal-semantics লেসনের evaluator-কে এতটুকু বদলানো যে সে গণনা পিছিয়ে রাখতে পারে — তিন strategy-র পার্থক্য log-এর লাইনে।

# lazy_eval.py — CBV vs call-by-name vs call-by-need
# চালান: python3 lazy_eval.py

# ── AST: tuple-based, formal-semantics লেসনের মতোই ──
def num(n):       return ('num', n)
def var(name):    return ('var', name)
def lam(p, body): return ('lam', p, body)          # λp.body
def app(f, a):    return ('app', f, a)             # f(a)
def add(a, b):    return ('add', a, b)

def show(e):
    t = e[0]
    if t == 'num': return str(e[1])
    if t == 'var': return e[1]
    if t == 'lam': return '(λ' + e[1] + '.' + show(e[2]) + ')'
    if t == 'add': return '(' + show(e[1]) + '+' + show(e[2]) + ')'
    return '(' + show(e[1]) + ' ' + show(e[2]) + ')'

# ── Strategy ১: call-by-value ──
def eval_cbv(e, env):
    tag = e[0]
    if tag == 'num':  return e[1]
    if tag == 'var':  return env[e[1]]
    if tag == 'add':  return eval_cbv(e[1], env) + eval_cbv(e[2], env)
    if tag == 'lam':  return ('closure', e, env)
    f = eval_cbv(e[1], env)
    arg = eval_cbv(e[2], env)          # ← argument আগে, ব্যবহৃত হোক বা না হোক
    _, (_, p, body), fenv = f
    call_env = dict(fenv); call_env[p] = arg
    return eval_cbv(body, call_env)

# ── Strategy ২: call-by-name (memoization ছাড়া) ──
def eval_name(e, env):
    tag = e[0]
    if tag == 'num':  return e[1]
    if tag == 'var':
        _, ex, en = env[e[1]]                  # binding = unforced expr
        print('    [name: re-eval] ' + show(ex))   # প্রতি ব্যবহারে পুনর্গণনা!
        return eval_name(ex, en)
    if tag == 'add':  return eval_name(e[1], env) + eval_name(e[2], env)
    if tag == 'lam':  return ('closure', e, env)
    f = eval_name(e[1], env)
    _, (_, p, body), fenv = f
    call_env = dict(fenv); call_env[p] = ('unforced', e[2], env)   # বর্ণনা ঢোকে
    return eval_name(body, call_env)

# ── Strategy ৩: call-by-need (thunk + memoization) ──
class Thunk:
    __slots__ = ('expr', 'env', 'cached', 'value')
    forced = 0                                 # মোট force গণনা
    def __init__(self, expr, env):
        self.expr, self.env = expr, env
        self.cached, self.value = False, None

def force(t):
    if not isinstance(t, Thunk): return t      # ইতিমধ্যে plain value
    if t.cached: return t.value                # দ্বিতীয়বার: ফ্রি
    Thunk.forced += 1
    print('    [need: force #' + str(Thunk.forced) + '] ' + show(t.expr))
    t.value = eval_need(t.expr, t.env)
    t.cached = True                            # ← memoization-এর মুহূর্ত
    return t.value

def eval_need(e, env):
    tag = e[0]
    if tag == 'num':  return e[1]
    if tag == 'var':  return force(env[e[1]])          # env slot-এ Thunk!
    if tag == 'add':
        return force(eval_need(e[1], env)) + force(eval_need(e[2], env))
    if tag == 'lam':  return ('closure', e, env)
    f = eval_need(e[1], env)
    _, (_, p, body), fenv = f
    call_env = dict(fenv); call_env[p] = Thunk(e[2], env)   # এখনো ঘুমাচ্ছে
    return eval_need(body, call_env)

# ── Demo: একই প্রোগ্রাম তিন বাস্তবতায় ──
if __name__ == '__main__':
    prog = app(lam('x', add(var('x'), var('x'))),
               app(lam('y', var('y')), num(21)))     # (λx.x+x)((λy.y)21)
    print('== CBV:');           print('  result:', eval_cbv(prog, {}))
    print('== call-by-name:');  print('  result:', eval_name(prog, {}))
    print('== call-by-need:');  print('  result:', eval_need(prog, {}))

    unused = app(lam('x', num(42)), app(lam('y', var('y')), num(999999)))
    print('== CBV (unused arg):', eval_cbv(unused, {}))
    print('== need (unused arg):', eval_need(unused, {}),
          '| total forces:', Thunk.forced)

প্রত্যাশিত output:

== CBV:
  result: 42
== call-by-name:
    [name: re-eval] ((λy.y) 21)
    [name: re-eval] 21
    [name: re-eval] ((λy.y) 21)
    [name: re-eval] 21
  result: 42
== call-by-need:
    [need: force #1] ((λy.y) 21)
    [need: force #2] 21
  result: 42
== CBV (unused arg): 42
== need (unused arg): 42 | total forces: 2

লাইন গুনুন: name ৪টা re-eval log লিখেছে (বাইরের expression দুই occurrence, ভেতরের y প্রতিবার) — work-এর duplication চোখের সামনে। Need মোট ২টা force (#1 বাইরের thunk, #2 তার ভেতরের y) — nested thunk-গুলোও memoize হয়; unused-argument কেসে force সংখ্যা একটিও বাড়েনি (total forces আগের ২-ই)। এই সংখ্যাগুলোই call-by-need-এর পুরো ঔচিত্য।

নিজে বাড়ান:

1. let x = expr in body form যোগ করুন — call-by-need-এ shared Thunk বসলে let ones = 1 : ones cyclic structure কীভাবে সম্ভব হয় দেখুন।
2. Force-count দিয়ে (λx. x + x + x) ARG-এ name বনাম need-এর evaluation অনুপাত মাপুন — occurrence বাড়ালে অনুপাত কীভাবে বাড়ে।
3. একটা seq(v) primitive যোগ করুন যা argument force করে — Haskell-এর foldl'-এর ভেতরে ঠিক এটাই ঘটে।