Compile and Run (Capstone)

hard · compilers, bytecode, vm, capstone

Compile and Run (Capstone)

Connect the full compiler pipeline and execute the program.

Function signature

func CompileAndRun(src string) (Value, error)

Pipeline requirements

Your function must:

Lex source into tokens (Lex)
Parse tokens into a program AST (Parse)
Run semantic analysis (Analyze)
Compile to bytecode (Compile)
Encode to BC1 text (Encode)
Decode back to bytecode (Decode)
Execute in the VM (Run)

Return the final VM result.

Error handling

If lexing or parsing fails, return that error.
If semantic analysis returns errors, return the first error as error.
If decoding or execution fails, return that error.

Notes

The helper functions and types are provided in this file.
Keep the implementation readable.

package solution

import (
	"bufio"
	"fmt"
	"strconv"
	"strings"
)

type TokenKind int

const (
	TokenEOF TokenKind = iota
	TokenIdent
	TokenNumber
	TokenString
	TokenLet
	TokenVar
	TokenConst
	TokenFn
	TokenIf
	TokenElse
	TokenWhile
	TokenReturn
	TokenTrue
	TokenFalse
	TokenNil
	TokenPlus
	TokenMinus
	TokenStar
	TokenSlash
	TokenAssign
	TokenEqual
	TokenNotEqual
	TokenLess
	TokenLessEqual
	TokenGreater
	TokenGreaterEqual
	TokenBang
	TokenLParen
	TokenRParen
	TokenLBrace
	TokenRBrace
	TokenComma
	TokenSemicolon
)

type Token struct {
	Kind   TokenKind
	Lexeme string
	Line   int
	Col    int
}

type VarKind int

const (
	VarLet VarKind = iota
	VarVar
	VarConst
)

type StmtKind int

const (
	StmtVar StmtKind = iota
	StmtAssign
	StmtExpr
	StmtIf
	StmtWhile
	StmtReturn
	StmtBlock
	StmtFn
)

type Stmt struct {
	Kind    StmtKind
	VarKind VarKind
	Name    string
	Expr    *Expr
	Body    []*Stmt
	Else    []*Stmt
	Params  []string
}

type Program struct {
	Stmts []*Stmt
}

type ExprKind int

const (
	ExprNumber ExprKind = iota
	ExprString
	ExprBool
	ExprNil
	ExprIdent
	ExprUnary
	ExprBinary
	ExprCall
)

type Expr struct {
	Kind  ExprKind
	Value string
	Left  *Expr
	Right *Expr
	Args  []*Expr
}

type OpCode int

const (
	OpPushNum OpCode = iota
	OpPushStr
	OpPushBool
	OpPushNil
	OpLoad
	OpStore
	OpDefineVar
	OpDefineConst
	OpAdd
	OpSub
	OpMul
	OpDiv
	OpNeg
	OpNot
	OpEq
	OpNeq
	OpLt
	OpLte
	OpGt
	OpGte
	OpJump
	OpJumpIfFalse
	OpCall
	OpReturn
	OpEnterScope
	OpExitScope
	OpPop
)

type Instr struct {
	Op  OpCode
	Int int
	Str string
}

type Function struct {
	Name   string
	Params []string
	Code   []Instr
}

type Bytecode struct {
	Functions []Function
	Main      []Instr
}

type ValueKind int

const (
	ValueNumber ValueKind = iota
	ValueString
	ValueBool
	ValueNil
)

type Value struct {
	Kind ValueKind
	Num  int
	Str  string
	Bool bool
}

// CompileAndRun connects the whole pipeline and executes the program.
func CompileAndRun(src string) (Value, error) {
	// TODO: implement the full pipeline.
	return Value{}, fmt.Errorf("not implemented")
}

// Lex converts source text into tokens.
func Lex(src string) ([]Token, error) {
	var tokens []Token
	line := 1
	col := 1
	i := 0

for i < len(src) {
		ch := src[i]

switch ch {
		case ' ', '\t', '\r':
			i++
			col++
			continue
		case '\n':
			i++
			line++
			col = 1
			continue
		case '/':
			if i+1 < len(src) && src[i+1] == '/' {
				i += 2
				col += 2
				for i < len(src) && src[i] != '\n' {
					i++
					col++
				}
				continue
			}
		}

startLine := line
		startCol := col

if isAlpha(ch) || ch == '_' {
			start := i
			i++
			col++
			for i < len(src) && (isAlphaNum(src[i]) || src[i] == '_') {
				i++
				col++
			}
			lex := src[start:i]
			kind := identKind(lex)
			tokens = append(tokens, Token{Kind: kind, Lexeme: lex, Line: startLine, Col: startCol})
			continue
		}

if isDigit(ch) {
			start := i
			i++
			col++
			for i < len(src) && isDigit(src[i]) {
				i++
				col++
			}
			lex := src[start:i]
			tokens = append(tokens, Token{Kind: TokenNumber, Lexeme: lex, Line: startLine, Col: startCol})
			continue
		}

switch ch {
		case '"':
			lex, next, nextCol, err := readString(src, i, line, col)
			if err != nil {
				return nil, err
			}
			tokens = append(tokens, Token{Kind: TokenString, Lexeme: lex, Line: startLine, Col: startCol})
			i = next
			col = nextCol
		case '+':
			tokens = append(tokens, Token{Kind: TokenPlus, Lexeme: "+", Line: startLine, Col: startCol})
			i++
			col++
		case '-':
			tokens = append(tokens, Token{Kind: TokenMinus, Lexeme: "-", Line: startLine, Col: startCol})
			i++
			col++
		case '*':
			tokens = append(tokens, Token{Kind: TokenStar, Lexeme: "*", Line: startLine, Col: startCol})
			i++
			col++
		case '/':
			tokens = append(tokens, Token{Kind: TokenSlash, Lexeme: "/", Line: startLine, Col: startCol})
			i++
			col++
		case '=':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenEqual, Lexeme: "==", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenAssign, Lexeme: "=", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '!':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenNotEqual, Lexeme: "!=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenBang, Lexeme: "!", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '<':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenLessEqual, Lexeme: "<=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenLess, Lexeme: "<", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '>':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenGreaterEqual, Lexeme: ">=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenGreater, Lexeme: ">", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '(':
			tokens = append(tokens, Token{Kind: TokenLParen, Lexeme: "(", Line: startLine, Col: startCol})
			i++
			col++
		case ')':
			tokens = append(tokens, Token{Kind: TokenRParen, Lexeme: ")", Line: startLine, Col: startCol})
			i++
			col++
		case '{':
			tokens = append(tokens, Token{Kind: TokenLBrace, Lexeme: "{", Line: startLine, Col: startCol})
			i++
			col++
		case '}':
			tokens = append(tokens, Token{Kind: TokenRBrace, Lexeme: "}", Line: startLine, Col: startCol})
			i++
			col++
		case ',':
			tokens = append(tokens, Token{Kind: TokenComma, Lexeme: ",", Line: startLine, Col: startCol})
			i++
			col++
		case ';':
			tokens = append(tokens, Token{Kind: TokenSemicolon, Lexeme: ";", Line: startLine, Col: startCol})
			i++
			col++
		default:
			return nil, fmt.Errorf("line %d col %d: unexpected character %q", line, col, ch)
		}
	}

tokens = append(tokens, Token{Kind: TokenEOF, Lexeme: "", Line: line, Col: col})
	return tokens, nil
}

func readString(src string, start int, line int, col int) (string, int, int, error) {
	var out []byte
	i := start + 1
	c := col + 1
	for i < len(src) {
		ch := src[i]
		if ch == '"' {
			return string(out), i + 1, c + 1, nil
		}
		if ch == '\n' {
			return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
		}
		if ch == '\\' {
			if i+1 >= len(src) {
				return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
			}
			i++
			c++
			esc := src[i]
			switch esc {
			case '"':
				out = append(out, '"')
			case '\\':
				out = append(out, '\\')
			case 'n':
				out = append(out, '\n')
			case 't':
				out = append(out, '\t')
			default:
				return "", 0, 0, fmt.Errorf("line %d col %d: invalid escape \\%c", line, col, esc)
			}
			i++
			c++
			continue
		}
		out = append(out, ch)
		i++
		c++
	}
	return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
}

func isAlpha(ch byte) bool {
	return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
}

func isDigit(ch byte) bool {
	return ch >= '0' && ch <= '9'
}

func isAlphaNum(ch byte) bool {
	return isAlpha(ch) || isDigit(ch)
}

func identKind(lex string) TokenKind {
	switch lex {
	case "let":
		return TokenLet
	case "var":
		return TokenVar
	case "const":
		return TokenConst
	case "fn":
		return TokenFn
	case "if":
		return TokenIf
	case "else":
		return TokenElse
	case "while":
		return TokenWhile
	case "return":
		return TokenReturn
	case "true":
		return TokenTrue
	case "false":
		return TokenFalse
	case "nil":
		return TokenNil
	default:
		return TokenIdent
	}
}

// Parse turns tokens into a program AST.
func Parse(tokens []Token) (*Program, error) {
	p := &parser{tokens: tokens}
	var stmts []*Stmt
	for p.peek().Kind != TokenEOF {
		stmt, err := p.parseDecl()
		if err != nil {
			return nil, err
		}
		stmts = append(stmts, stmt)
	}
	return &Program{Stmts: stmts}, nil
}

type parser struct {
	tokens []Token
	pos    int
}

func (p *parser) parseDecl() (*Stmt, error) {
	if p.match(TokenFn) {
		return p.parseFnDecl()
	}
	return p.parseStmt()
}

func (p *parser) parseFnDecl() (*Stmt, error) {
	nameTok := p.consume(TokenIdent)
	if nameTok == nil {
		return nil, fmt.Errorf("expected function name")
	}
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after function name")
	}
	params, err := p.parseParams()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after parameters")
	}
	body, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	return &Stmt{Kind: StmtFn, Name: nameTok.Lexeme, Params: params, Body: body}, nil
}

func (p *parser) parseParams() ([]string, error) {
	if p.peek().Kind == TokenRParen {
		return nil, nil
	}
	var params []string
	for {
		nameTok := p.consume(TokenIdent)
		if nameTok == nil {
			return nil, fmt.Errorf("expected parameter name")
		}
		params = append(params, nameTok.Lexeme)
		if !p.match(TokenComma) {
			break
		}
	}
	return params, nil
}

func (p *parser) parseStmt() (*Stmt, error) {
	switch p.peek().Kind {
	case TokenLet, TokenVar, TokenConst:
		return p.parseVarDecl()
	case TokenIf:
		return p.parseIf()
	case TokenWhile:
		return p.parseWhile()
	case TokenReturn:
		return p.parseReturn()
	case TokenLBrace:
		body, err := p.parseBlock()
		if err != nil {
			return nil, err
		}
		return &Stmt{Kind: StmtBlock, Body: body}, nil
	case TokenIdent:
		if p.peekNext().Kind == TokenAssign {
			return p.parseAssign()
		}
	}
	return p.parseExprStmt()
}

func (p *parser) parseVarDecl() (*Stmt, error) {
	kindTok := p.advance()
	var kind VarKind
	switch kindTok.Kind {
	case TokenLet:
		kind = VarLet
	case TokenVar:
		kind = VarVar
	case TokenConst:
		kind = VarConst
	}
	nameTok := p.consume(TokenIdent)
	if nameTok == nil {
		return nil, fmt.Errorf("expected variable name")
	}
	var init *Expr
	if p.match(TokenAssign) {
		var err error
		init, err = p.parseExpr()
		if err != nil {
			return nil, err
		}
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after declaration")
	}
	return &Stmt{Kind: StmtVar, VarKind: kind, Name: nameTok.Lexeme, Expr: init}, nil
}

func (p *parser) parseAssign() (*Stmt, error) {
	nameTok := p.consume(TokenIdent)
	if nameTok == nil {
		return nil, fmt.Errorf("expected assignment target")
	}
	if !p.match(TokenAssign) {
		return nil, fmt.Errorf("expected '=' in assignment")
	}
	expr, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after assignment")
	}
	return &Stmt{Kind: StmtAssign, Name: nameTok.Lexeme, Expr: expr}, nil
}

func (p *parser) parseExprStmt() (*Stmt, error) {
	expr, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after expression")
	}
	return &Stmt{Kind: StmtExpr, Expr: expr}, nil
}

func (p *parser) parseBlock() ([]*Stmt, error) {
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{'")
	}
	var stmts []*Stmt
	for p.peek().Kind != TokenRBrace && p.peek().Kind != TokenEOF {
		stmt, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		stmts = append(stmts, stmt)
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}' after block")
	}
	return stmts, nil
}

func (p *parser) parseIf() (*Stmt, error) {
	p.advance()
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after if")
	}
	cond, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after condition")
	}
	thenBody, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	var elseBody []*Stmt
	if p.match(TokenElse) {
		elseBody, err = p.parseBlock()
		if err != nil {
			return nil, err
		}
	}
	return &Stmt{Kind: StmtIf, Expr: cond, Body: thenBody, Else: elseBody}, nil
}

func (p *parser) parseWhile() (*Stmt, error) {
	p.advance()
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after while")
	}
	cond, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after condition")
	}
	body, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	return &Stmt{Kind: StmtWhile, Expr: cond, Body: body}, nil
}

func (p *parser) parseReturn() (*Stmt, error) {
	p.advance()
	var expr *Expr
	if p.peek().Kind != TokenSemicolon {
		var err error
		expr, err = p.parseExpr()
		if err != nil {
			return nil, err
		}
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after return")
	}
	return &Stmt{Kind: StmtReturn, Expr: expr}, nil
}

func (p *parser) parseExpr() (*Expr, error) {
	return p.parseEquality()
}

func (p *parser) parseEquality() (*Expr, error) {
	left, err := p.parseComparison()
	if err != nil {
		return nil, err
	}
	for p.match(TokenEqual, TokenNotEqual) {
		op := p.previous().Lexeme
		right, err := p.parseComparison()
		if err != nil {
			return nil, err
		}
		left = &Expr{Kind: ExprBinary, Value: op, Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseComparison() (*Expr, error) {
	left, err := p.parseTerm()
	if err != nil {
		return nil, err
	}
	for p.match(TokenLess, TokenLessEqual, TokenGreater, TokenGreaterEqual) {
		op := p.previous().Lexeme
		right, err := p.parseTerm()
		if err != nil {
			return nil, err
		}
		left = &Expr{Kind: ExprBinary, Value: op, Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseTerm() (*Expr, error) {
	left, err := p.parseFactor()
	if err != nil {
		return nil, err
	}
	for p.match(TokenPlus, TokenMinus) {
		op := p.previous().Lexeme
		right, err := p.parseFactor()
		if err != nil {
			return nil, err
		}
		left = &Expr{Kind: ExprBinary, Value: op, Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseFactor() (*Expr, error) {
	left, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
	for p.match(TokenStar, TokenSlash) {
		op := p.previous().Lexeme
		right, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		left = &Expr{Kind: ExprBinary, Value: op, Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseUnary() (*Expr, error) {
	if p.match(TokenBang, TokenMinus) {
		op := p.previous().Lexeme
		right, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &Expr{Kind: ExprUnary, Value: op, Left: right}, nil
	}
	return p.parsePrimary()
}

func (p *parser) parsePrimary() (*Expr, error) {
	tok := p.peek()
	switch tok.Kind {
	case TokenNumber:
		p.advance()
		return &Expr{Kind: ExprNumber, Value: tok.Lexeme}, nil
	case TokenString:
		p.advance()
		return &Expr{Kind: ExprString, Value: tok.Lexeme}, nil
	case TokenTrue:
		p.advance()
		return &Expr{Kind: ExprBool, Value: "true"}, nil
	case TokenFalse:
		p.advance()
		return &Expr{Kind: ExprBool, Value: "false"}, nil
	case TokenNil:
		p.advance()
		return &Expr{Kind: ExprNil}, nil
	case TokenIdent:
		p.advance()
		name := tok.Lexeme
		if p.match(TokenLParen) {
			args, err := p.parseArgs()
			if err != nil {
				return nil, err
			}
			if !p.match(TokenRParen) {
				return nil, fmt.Errorf("expected ')' after call")
			}
			return &Expr{Kind: ExprCall, Value: name, Args: args}, nil
		}
		return &Expr{Kind: ExprIdent, Value: name}, nil
	case TokenLParen:
		p.advance()
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenRParen) {
			return nil, fmt.Errorf("expected ')' after expression")
		}
		return expr, nil
	default:
		return nil, fmt.Errorf("unexpected token %q", tok.Lexeme)
	}
}

func (p *parser) parseArgs() ([]*Expr, error) {
	if p.peek().Kind == TokenRParen {
		return nil, nil
	}
	var args []*Expr
	for {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		args = append(args, expr)
		if !p.match(TokenComma) {
			break
		}
	}
	return args, nil
}

func (p *parser) match(kinds ...TokenKind) bool {
	for _, kind := range kinds {
		if p.peek().Kind == kind {
			p.advance()
			return true
		}
	}
	return false
}

func (p *parser) consume(kind TokenKind) *Token {
	if p.peek().Kind == kind {
		tok := p.advance()
		return &tok
	}
	return nil
}

func (p *parser) advance() Token {
	if p.pos < len(p.tokens) {
		p.pos++
	}
	return p.previous()
}

func (p *parser) previous() Token {
	if p.pos == 0 {
		return Token{Kind: TokenEOF}
	}
	return p.tokens[p.pos-1]
}

func (p *parser) peek() Token {
	if p.pos >= len(p.tokens) {
		return Token{Kind: TokenEOF}
	}
	return p.tokens[p.pos]
}

func (p *parser) peekNext() Token {
	if p.pos+1 >= len(p.tokens) {
		return Token{Kind: TokenEOF}
	}
	return p.tokens[p.pos+1]
}

type symbolKind int

const (
	symVar symbolKind = iota
	symConst
	symFunc
)

type symbol struct {
	kind  symbolKind
	arity int
}

// Analyze checks semantic rules and returns error messages.
func Analyze(prog *Program) []string {
	a := &analyzer{
		scopes: []map[string]symbol{{}},
	}
	for _, stmt := range prog.Stmts {
		a.analyzeStmt(stmt)
	}
	return a.errors
}

type analyzer struct {
	scopes     []map[string]symbol
	inFunction int
	errors     []string
}

func (a *analyzer) analyzeStmt(stmt *Stmt) {
	if stmt == nil {
		return
	}
	switch stmt.Kind {
	case StmtVar:
		a.analyzeVarDecl(stmt)
	case StmtAssign:
		a.analyzeAssign(stmt)
	case StmtExpr:
		a.analyzeExpr(stmt.Expr)
	case StmtIf:
		a.analyzeExpr(stmt.Expr)
		a.analyzeBlock(stmt.Body)
		if len(stmt.Else) > 0 {
			a.analyzeBlock(stmt.Else)
		}
	case StmtWhile:
		a.analyzeExpr(stmt.Expr)
		a.analyzeBlock(stmt.Body)
	case StmtReturn:
		if a.inFunction == 0 {
			a.errors = append(a.errors, "return outside function")
		}
		a.analyzeExpr(stmt.Expr)
	case StmtBlock:
		a.analyzeBlock(stmt.Body)
	case StmtFn:
		a.analyzeFn(stmt)
	}
}

func (a *analyzer) analyzeVarDecl(stmt *Stmt) {
	name := stmt.Name
	if a.inCurrentScope(name) {
		a.errors = append(a.errors, "redeclare in same scope: "+name)
		return
	}
	if stmt.VarKind == VarConst && stmt.Expr == nil {
		a.errors = append(a.errors, "const requires initializer: "+name)
	}
	a.analyzeExpr(stmt.Expr)

kind := symVar
	if stmt.VarKind == VarConst {
		kind = symConst
	}
	a.scopes[len(a.scopes)-1][name] = symbol{kind: kind}
}

func (a *analyzer) analyzeAssign(stmt *Stmt) {
	sym, ok := a.resolve(stmt.Name)
	if !ok {
		a.errors = append(a.errors, "undefined name: "+stmt.Name)
	} else if sym.kind == symConst {
		a.errors = append(a.errors, "cannot assign to const: "+stmt.Name)
	}
	a.analyzeExpr(stmt.Expr)
}

func (a *analyzer) analyzeFn(stmt *Stmt) {
	name := stmt.Name
	if a.inCurrentScope(name) {
		a.errors = append(a.errors, "redeclare in same scope: "+name)
		return
	}
	a.scopes[len(a.scopes)-1][name] = symbol{kind: symFunc, arity: len(stmt.Params)}

a.pushScope()
	for _, param := range stmt.Params {
		if a.inCurrentScope(param) {
			a.errors = append(a.errors, "redeclare in same scope: "+param)
			continue
		}
		a.scopes[len(a.scopes)-1][param] = symbol{kind: symVar}
	}
	a.inFunction++
	for _, s := range stmt.Body {
		a.analyzeStmt(s)
	}
	a.inFunction--
	a.popScope()
}

func (a *analyzer) analyzeBlock(stmts []*Stmt) {
	a.pushScope()
	for _, s := range stmts {
		a.analyzeStmt(s)
	}
	a.popScope()
}

func (a *analyzer) analyzeExpr(expr *Expr) {
	if expr == nil {
		return
	}
	switch expr.Kind {
	case ExprIdent:
		if _, ok := a.resolve(expr.Value); !ok {
			a.errors = append(a.errors, "undefined name: "+expr.Value)
		}
	case ExprCall:
		sym, ok := a.resolve(expr.Value)
		if !ok {
			a.errors = append(a.errors, "undefined name: "+expr.Value)
		} else if sym.kind != symFunc {
			a.errors = append(a.errors, "call of non-function: "+expr.Value)
		} else if sym.arity != len(expr.Args) {
			a.errors = append(a.errors, "arity mismatch: "+expr.Value+" expects "+itoa(sym.arity))
		}
		for _, arg := range expr.Args {
			a.analyzeExpr(arg)
		}
	case ExprUnary:
		a.analyzeExpr(expr.Left)
	case ExprBinary:
		a.analyzeExpr(expr.Left)
		a.analyzeExpr(expr.Right)
	default:
		for _, arg := range expr.Args {
			a.analyzeExpr(arg)
		}
	}
}

func (a *analyzer) resolve(name string) (symbol, bool) {
	for i := len(a.scopes) - 1; i >= 0; i-- {
		if sym, ok := a.scopes[i][name]; ok {
			return sym, true
		}
	}
	return symbol{}, false
}

func (a *analyzer) inCurrentScope(name string) bool {
	_, ok := a.scopes[len(a.scopes)-1][name]
	return ok
}

func (a *analyzer) pushScope() {
	a.scopes = append(a.scopes, map[string]symbol{})
}

func (a *analyzer) popScope() {
	if len(a.scopes) > 1 {
		a.scopes = a.scopes[:len(a.scopes)-1]
	}
}

func itoa(n int) string {
	if n == 0 {
		return "0"
	}
	var out [20]byte
	i := len(out)
	for n > 0 {
		i--
		out[i] = byte('0' + n%10)
		n /= 10
	}
	return string(out[i:])
}

// Compile lowers a program AST into bytecode.
func Compile(prog *Program) Bytecode {
	c := &compiler{}
	for _, stmt := range prog.Stmts {
		if stmt.Kind == StmtFn {
			c.functions = append(c.functions, c.compileFunction(stmt))
			continue
		}
		c.compileStmt(stmt)
	}
	return Bytecode{Functions: c.functions, Main: c.code}
}

type compiler struct {
	code      []Instr
	functions []Function
}

func (c *compiler) compileFunction(stmt *Stmt) Function {
	fc := &compiler{}
	for _, s := range stmt.Body {
		fc.compileStmt(s)
	}
	fc.ensureReturn()
	return Function{Name: stmt.Name, Params: stmt.Params, Code: fc.code}
}

func (c *compiler) ensureReturn() {
	if len(c.code) == 0 || c.code[len(c.code)-1].Op != OpReturn {
		c.emit(Instr{Op: OpPushNil})
		c.emit(Instr{Op: OpReturn})
	}
}

func (c *compiler) compileStmt(stmt *Stmt) {
	switch stmt.Kind {
	case StmtVar:
		if stmt.Expr != nil {
			c.compileExpr(stmt.Expr)
		} else {
			c.emit(Instr{Op: OpPushNil})
		}
		if stmt.VarKind == VarConst {
			c.emit(Instr{Op: OpDefineConst, Str: stmt.Name})
		} else {
			c.emit(Instr{Op: OpDefineVar, Str: stmt.Name})
		}
	case StmtAssign:
		c.compileExpr(stmt.Expr)
		c.emit(Instr{Op: OpStore, Str: stmt.Name})
	case StmtExpr:
		c.compileExpr(stmt.Expr)
		c.emit(Instr{Op: OpPop})
	case StmtIf:
		c.compileExpr(stmt.Expr)
		jumpIf := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
		c.compileBlock(stmt.Body)
		jumpEnd := c.emit(Instr{Op: OpJump, Int: -1})
		c.patch(jumpIf, len(c.code))
		if len(stmt.Else) > 0 {
			c.compileBlock(stmt.Else)
		}
		c.patch(jumpEnd, len(c.code))
	case StmtWhile:
		start := len(c.code)
		c.compileExpr(stmt.Expr)
		jumpIf := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
		c.compileBlock(stmt.Body)
		c.emit(Instr{Op: OpJump, Int: start})
		c.patch(jumpIf, len(c.code))
	case StmtReturn:
		if stmt.Expr != nil {
			c.compileExpr(stmt.Expr)
		} else {
			c.emit(Instr{Op: OpPushNil})
		}
		c.emit(Instr{Op: OpReturn})
	case StmtBlock:
		c.compileBlock(stmt.Body)
	case StmtFn:
		// Functions are compiled at top level only.
	}
}

func (c *compiler) compileBlock(stmts []*Stmt) {
	c.emit(Instr{Op: OpEnterScope})
	for _, s := range stmts {
		c.compileStmt(s)
	}
	c.emit(Instr{Op: OpExitScope})
}

func (c *compiler) compileExpr(expr *Expr) {
	switch expr.Kind {
	case ExprNumber:
		v, _ := strconv.Atoi(expr.Value)
		c.emit(Instr{Op: OpPushNum, Int: v})
	case ExprString:
		c.emit(Instr{Op: OpPushStr, Str: expr.Value})
	case ExprBool:
		if expr.Value == "true" {
			c.emit(Instr{Op: OpPushBool, Int: 1})
		} else {
			c.emit(Instr{Op: OpPushBool, Int: 0})
		}
	case ExprNil:
		c.emit(Instr{Op: OpPushNil})
	case ExprIdent:
		c.emit(Instr{Op: OpLoad, Str: expr.Value})
	case ExprUnary:
		c.compileExpr(expr.Left)
		switch expr.Value {
		case "-":
			c.emit(Instr{Op: OpNeg})
		case "!":
			c.emit(Instr{Op: OpNot})
		}
	case ExprBinary:
		c.compileExpr(expr.Left)
		c.compileExpr(expr.Right)
		switch expr.Value {
		case "+":
			c.emit(Instr{Op: OpAdd})
		case "-":
			c.emit(Instr{Op: OpSub})
		case "*":
			c.emit(Instr{Op: OpMul})
		case "/":
			c.emit(Instr{Op: OpDiv})
		case "==":
			c.emit(Instr{Op: OpEq})
		case "!=":
			c.emit(Instr{Op: OpNeq})
		case "<":
			c.emit(Instr{Op: OpLt})
		case "<=":
			c.emit(Instr{Op: OpLte})
		case ">":
			c.emit(Instr{Op: OpGt})
		case ">=":
			c.emit(Instr{Op: OpGte})
		}
	case ExprCall:
		for _, arg := range expr.Args {
			c.compileExpr(arg)
		}
		c.emit(Instr{Op: OpCall, Str: expr.Value, Int: len(expr.Args)})
	}
}

func (c *compiler) emit(instr Instr) int {
	c.code = append(c.code, instr)
	return len(c.code) - 1
}

func (c *compiler) patch(pos int, target int) {
	c.code[pos].Int = target
}

// Encode converts bytecode into a BC1 text format.
func Encode(bc Bytecode) string {
	var b strings.Builder
	writeLine(&b, "BC1")
	for _, fn := range bc.Functions {
		line := "FUNC " + fn.Name
		for _, p := range fn.Params {
			line += " " + p
		}
		writeLine(&b, line)
		for _, ins := range fn.Code {
			writeLine(&b, encodeInstr(ins))
		}
		writeLine(&b, "END")
	}
	writeLine(&b, "MAIN")
	for _, ins := range bc.Main {
		writeLine(&b, encodeInstr(ins))
	}
	writeLine(&b, "END")
	return b.String()
}

// Decode parses BC1 text into bytecode.
func Decode(src string) (Bytecode, error) {
	scanner := bufio.NewScanner(strings.NewReader(src))
	var lines []string
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if line == "" || strings.HasPrefix(line, "#") {
			continue
		}
		lines = append(lines, line)
	}
	if err := scanner.Err(); err != nil {
		return Bytecode{}, err
	}
	if len(lines) == 0 || lines[0] != "BC1" {
		return Bytecode{}, fmt.Errorf("missing BC1 header")
	}

var bc Bytecode
	i := 1
	for i < len(lines) {
		line := lines[i]
		if line == "MAIN" {
			code, next, err := parseSection(lines, i+1)
			if err != nil {
				return Bytecode{}, err
			}
			bc.Main = code
			i = next
			continue
		}
		toks, err := splitTokens(line)
		if err != nil {
			return Bytecode{}, err
		}
		if len(toks) >= 2 && toks[0] == "FUNC" {
			fn := Function{Name: toks[1], Params: append([]string(nil), toks[2:]...)}
			code, next, err := parseSection(lines, i+1)
			if err != nil {
				return Bytecode{}, err
			}
			fn.Code = code
			bc.Functions = append(bc.Functions, fn)
			i = next
			continue
		}
		return Bytecode{}, fmt.Errorf("unexpected line: %s", line)
	}
	return bc, nil
}

func parseSection(lines []string, start int) ([]Instr, int, error) {
	var code []Instr
	for i := start; i < len(lines); i++ {
		line := lines[i]
		if line == "END" {
			return code, i + 1, nil
		}
		toks, err := splitTokens(line)
		if err != nil {
			return nil, 0, err
		}
		ins, err := parseInstr(toks)
		if err != nil {
			return nil, 0, err
		}
		code = append(code, ins)
	}
	return nil, 0, fmt.Errorf("missing END")
}

func encodeInstr(ins Instr) string {
	switch ins.Op {
	case OpPushNum:
		return "PUSH_NUM " + strconv.Itoa(ins.Int)
	case OpPushStr:
		return "PUSH_STR \"" + escapeString(ins.Str) + "\""
	case OpPushBool:
		return "PUSH_BOOL " + strconv.Itoa(ins.Int)
	case OpPushNil:
		return "PUSH_NIL"
	case OpLoad:
		return "LOAD " + ins.Str
	case OpStore:
		return "STORE " + ins.Str
	case OpDefineVar:
		return "DEFINE_VAR " + ins.Str
	case OpDefineConst:
		return "DEFINE_CONST " + ins.Str
	case OpAdd:
		return "ADD"
	case OpSub:
		return "SUB"
	case OpMul:
		return "MUL"
	case OpDiv:
		return "DIV"
	case OpNeg:
		return "NEG"
	case OpNot:
		return "NOT"
	case OpEq:
		return "EQ"
	case OpNeq:
		return "NEQ"
	case OpLt:
		return "LT"
	case OpLte:
		return "LTE"
	case OpGt:
		return "GT"
	case OpGte:
		return "GTE"
	case OpJump:
		return "JUMP " + strconv.Itoa(ins.Int)
	case OpJumpIfFalse:
		return "JUMP_IF_FALSE " + strconv.Itoa(ins.Int)
	case OpCall:
		return "CALL " + ins.Str + " " + strconv.Itoa(ins.Int)
	case OpReturn:
		return "RETURN"
	case OpEnterScope:
		return "ENTER_SCOPE"
	case OpExitScope:
		return "EXIT_SCOPE"
	case OpPop:
		return "POP"
	default:
		return ""
	}
}

func parseInstr(toks []string) (Instr, error) {
	if len(toks) == 0 {
		return Instr{}, fmt.Errorf("empty instruction")
	}
	op := toks[0]
	switch op {
	case "PUSH_NUM":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_NUM expects 1 arg")
		}
		v, err := strconv.Atoi(toks[1])
		if err != nil {
			return Instr{}, err
		}
		return Instr{Op: OpPushNum, Int: v}, nil
	case "PUSH_STR":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_STR expects 1 arg")
		}
		return Instr{Op: OpPushStr, Str: toks[1]}, nil
	case "PUSH_BOOL":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_BOOL expects 1 arg")
		}
		v, err := strconv.Atoi(toks[1])
		if err != nil {
			return Instr{}, err
		}
		return Instr{Op: OpPushBool, Int: v}, nil
	case "PUSH_NIL":
		return Instr{Op: OpPushNil}, nil
	case "LOAD":
		return parseNameInstr(toks, OpLoad)
	case "STORE":
		return parseNameInstr(toks, OpStore)
	case "DEFINE_VAR":
		return parseNameInstr(toks, OpDefineVar)
	case "DEFINE_CONST":
		return parseNameInstr(toks, OpDefineConst)
	case "ADD":
		return Instr{Op: OpAdd}, nil
	case "SUB":
		return Instr{Op: OpSub}, nil
	case "MUL":
		return Instr{Op: OpMul}, nil
	case "DIV":
		return Instr{Op: OpDiv}, nil
	case "NEG":
		return Instr{Op: OpNeg}, nil
	case "NOT":
		return Instr{Op: OpNot}, nil
	case "EQ":
		return Instr{Op: OpEq}, nil
	case "NEQ":
		return Instr{Op: OpNeq}, nil
	case "LT":
		return Instr{Op: OpLt}, nil
	case "LTE":
		return Instr{Op: OpLte}, nil
	case "GT":
		return Instr{Op: OpGt}, nil
	case "GTE":
		return Instr{Op: OpGte}, nil
	case "JUMP":
		return parseIntInstr(toks, OpJump)
	case "JUMP_IF_FALSE":
		return parseIntInstr(toks, OpJumpIfFalse)
	case "CALL":
		if len(toks) != 3 {
			return Instr{}, fmt.Errorf("CALL expects 2 args")
		}
		arity, err := strconv.Atoi(toks[2])
		if err != nil {
			return Instr{}, err
		}
		return Instr{Op: OpCall, Str: toks[1], Int: arity}, nil
	case "RETURN":
		return Instr{Op: OpReturn}, nil
	case "ENTER_SCOPE":
		return Instr{Op: OpEnterScope}, nil
	case "EXIT_SCOPE":
		return Instr{Op: OpExitScope}, nil
	case "POP":
		return Instr{Op: OpPop}, nil
	default:
		return Instr{}, fmt.Errorf("unknown opcode: %s", op)
	}
}

func parseNameInstr(toks []string, op OpCode) (Instr, error) {
	if len(toks) != 2 {
		return Instr{}, fmt.Errorf("name opcode expects 1 arg")
	}
	return Instr{Op: op, Str: toks[1]}, nil
}

func parseIntInstr(toks []string, op OpCode) (Instr, error) {
	if len(toks) != 2 {
		return Instr{}, fmt.Errorf("int opcode expects 1 arg")
	}
	v, err := strconv.Atoi(toks[1])
	if err != nil {
		return Instr{}, err
	}
	return Instr{Op: op, Int: v}, nil
}

func splitTokens(line string) ([]string, error) {
	var toks []string
	i := 0
	for i < len(line) {
		for i < len(line) && line[i] == ' ' {
			i++
		}
		if i >= len(line) {
			break
		}
		if line[i] == '"' {
			i++
			var out []byte
			closed := false
			for i < len(line) {
				ch := line[i]
				if ch == '"' {
					i++
					closed = true
					break
				}
				if ch == '\\' {
					if i+1 >= len(line) {
						return nil, fmt.Errorf("invalid escape")
					}
					i++
					esc := line[i]
					switch esc {
					case '"':
						out = append(out, '"')
					case '\\':
						out = append(out, '\\')
					case 'n':
						out = append(out, '\n')
					case 't':
						out = append(out, '\t')
					default:
						return nil, fmt.Errorf("invalid escape")
					}
					i++
					continue
				}
				out = append(out, ch)
				i++
			}
			if !closed {
				return nil, fmt.Errorf("unterminated string")
			}
			toks = append(toks, string(out))
			continue
		}
		start := i
		for i < len(line) && line[i] != ' ' {
			i++
		}
		toks = append(toks, line[start:i])
	}
	return toks, nil
}

func escapeString(s string) string {
	var b strings.Builder
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case '\\':
			b.WriteString("\\\\")
		case '"':
			b.WriteString("\\\"")
		case '\n':
			b.WriteString("\\n")
		case '\t':
			b.WriteString("\\t")
		default:
			b.WriteByte(s[i])
		}
	}
	return b.String()
}

func writeLine(b *strings.Builder, line string) {
	b.WriteString(line)
	b.WriteString("\n")
}

// Run executes bytecode and returns the final value.
func Run(bc Bytecode) (Value, error) {
	funcs := map[string]Function{}
	for _, fn := range bc.Functions {
		funcs[fn.Name] = fn
	}

global := &env{scopes: []map[string]binding{{}}}
	return execute(bc.Main, global, funcs)
}

type binding struct {
	val     Value
	isConst bool
}

type env struct {
	scopes []map[string]binding
	parent *env
}

func execute(code []Instr, envState *env, funcs map[string]Function) (Value, error) {
	stack := []Value{}
	ip := 0

pop := func() (Value, error) {
		if len(stack) == 0 {
			return Value{}, fmt.Errorf("stack underflow")
		}
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		return v, nil
	}

push := func(v Value) {
		stack = append(stack, v)
	}

for ip < len(code) {
		instr := code[ip]
		switch instr.Op {
		case OpPushNum:
			push(Value{Kind: ValueNumber, Num: instr.Int})
		case OpPushStr:
			push(Value{Kind: ValueString, Str: instr.Str})
		case OpPushBool:
			push(Value{Kind: ValueBool, Bool: instr.Int != 0})
		case OpPushNil:
			push(Value{Kind: ValueNil})
		case OpLoad:
			b, ok := envState.lookup(instr.Str)
			if !ok {
				return Value{}, fmt.Errorf("undefined name: %s", instr.Str)
			}
			push(b.val)
		case OpStore:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			if err := envState.assign(instr.Str, v); err != nil {
				return Value{}, err
			}
		case OpDefineVar:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			envState.define(instr.Str, v, false)
		case OpDefineConst:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			envState.define(instr.Str, v, true)
		case OpAdd:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind == ValueNumber && b.Kind == ValueNumber {
				push(Value{Kind: ValueNumber, Num: a.Num + b.Num})
				break
			}
			if a.Kind == ValueString && b.Kind == ValueString {
				push(Value{Kind: ValueString, Str: a.Str + b.Str})
				break
			}
			return Value{}, fmt.Errorf("type error: add")
		case OpSub:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: sub")
			}
			push(Value{Kind: ValueNumber, Num: a.Num - b.Num})
		case OpMul:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: mul")
			}
			push(Value{Kind: ValueNumber, Num: a.Num * b.Num})
		case OpDiv:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: div")
			}
			if b.Num == 0 {
				return Value{}, fmt.Errorf("division by zero")
			}
			push(Value{Kind: ValueNumber, Num: a.Num / b.Num})
		case OpNeg:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			if v.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: neg")
			}
			push(Value{Kind: ValueNumber, Num: -v.Num})
		case OpNot:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			push(Value{Kind: ValueBool, Bool: !isTruthy(v)})
		case OpEq:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			push(Value{Kind: ValueBool, Bool: equalValue(a, b)})
		case OpNeq:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			push(Value{Kind: ValueBool, Bool: !equalValue(a, b)})
		case OpLt:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lt")
			}
			push(Value{Kind: ValueBool, Bool: a.Num < b.Num})
		case OpLte:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lte")
			}
			push(Value{Kind: ValueBool, Bool: a.Num <= b.Num})
		case OpGt:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gt")
			}
			push(Value{Kind: ValueBool, Bool: a.Num > b.Num})
		case OpGte:
			b, a, err := pop2(&stack)
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gte")
			}
			push(Value{Kind: ValueBool, Bool: a.Num >= b.Num})
		case OpJump:
			ip = instr.Int
			continue
		case OpJumpIfFalse:
			v, err := pop()
			if err != nil {
				return Value{}, err
			}
			if !isTruthy(v) {
				ip = instr.Int
				continue
			}
		case OpCall:
			fn, ok := funcs[instr.Str]
			if !ok {
				return Value{}, fmt.Errorf("undefined function: %s", instr.Str)
			}
			if instr.Int != len(fn.Params) {
				return Value{}, fmt.Errorf("arity mismatch: %s", instr.Str)
			}
			args, err := popN(&stack, instr.Int)
			if err != nil {
				return Value{}, err
			}
			callEnv := &env{scopes: []map[string]binding{{}}, parent: envState.root()}
			for i, param := range fn.Params {
				callEnv.define(param, args[i], false)
			}
			res, err := execute(fn.Code, callEnv, funcs)
			if err != nil {
				return Value{}, err
			}
			push(res)
		case OpReturn:
			if len(stack) == 0 {
				return Value{Kind: ValueNil}, nil
			}
			v := stack[len(stack)-1]
			return v, nil
		case OpEnterScope:
			envState.push()
		case OpExitScope:
			envState.pop()
		case OpPop:
			_, err := pop()
			if err != nil {
				return Value{}, err
			}
		}
		ip++
	}

if len(stack) == 0 {
		return Value{Kind: ValueNil}, nil
	}
	return stack[len(stack)-1], nil
}

func pop2(stack *[]Value) (Value, Value, error) {
	if len(*stack) < 2 {
		return Value{}, Value{}, fmt.Errorf("stack underflow")
	}
	s := *stack
	b := s[len(s)-1]
	a := s[len(s)-2]
	*stack = s[:len(s)-2]
	return b, a, nil
}

func popN(stack *[]Value, n int) ([]Value, error) {
	if len(*stack) < n {
		return nil, fmt.Errorf("stack underflow")
	}
	s := *stack
	start := len(s) - n
	out := append([]Value(nil), s[start:]...)
	*stack = s[:start]
	return out, nil
}

func equalValue(a, b Value) bool {
	if a.Kind != b.Kind {
		return false
	}
	switch a.Kind {
	case ValueNumber:
		return a.Num == b.Num
	case ValueString:
		return a.Str == b.Str
	case ValueBool:
		return a.Bool == b.Bool
	case ValueNil:
		return true
	default:
		return false
	}
}

func isTruthy(v Value) bool {
	if v.Kind == ValueNil {
		return false
	}
	if v.Kind == ValueBool {
		return v.Bool
	}
	return true
}

func (e *env) push() {
	e.scopes = append(e.scopes, map[string]binding{})
}

func (e *env) pop() {
	if len(e.scopes) > 1 {
		e.scopes = e.scopes[:len(e.scopes)-1]
	}
}

func (e *env) define(name string, val Value, isConst bool) {
	e.scopes[len(e.scopes)-1][name] = binding{val: val, isConst: isConst}
}

func (e *env) lookup(name string) (binding, bool) {
	for i := len(e.scopes) - 1; i >= 0; i-- {
		if b, ok := e.scopes[i][name]; ok {
			return b, true
		}
	}
	if e.parent != nil {
		return e.parent.lookup(name)
	}
	return binding{}, false
}

func (e *env) assign(name string, val Value) error {
	for i := len(e.scopes) - 1; i >= 0; i-- {
		if b, ok := e.scopes[i][name]; ok {
			if b.isConst {
				return fmt.Errorf("cannot assign to const: %s", name)
			}
			e.scopes[i][name] = binding{val: val, isConst: b.isConst}
			return nil
		}
	}
	if e.parent != nil {
		return e.parent.assign(name, val)
	}
	return fmt.Errorf("undefined name: %s", name)
}

func (e *env) root() *env {
	cur := e
	for cur.parent != nil {
		cur = cur.parent
	}
	return cur
}