Compile and Run v3 (Capstone)

hard · compilers, bytecode, vm, capstone

Compile and Run v3 (Capstone)

Connect the full v3 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 BC2 text (Encode)
Decode back to bytecode (Decode)
Execute in the VM (Run on a new VM)

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
	TokenLBracket
	TokenRBracket
	TokenComma
	TokenSemicolon
	TokenColon
)

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
	Target  *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
	ExprArray
	ExprMap
	ExprIndex
)

type MapPair struct {
	Key   *Expr
	Value *Expr
}

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

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
	OpMakeClosure
	OpMakeArray
	OpMakeMap
	OpGetIndex
	OpSetIndex
)

type Instr struct {
	Op  OpCode
	Int int
	Str string
}

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

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

type ValueKind int

const (
	ValueNumber ValueKind = iota
	ValueString
	ValueBool
	ValueNil
	ValueArray
	ValueMap
	ValueClosure
)

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

type ObjKind int

const (
	ObjArray ObjKind = iota
	ObjMap
	ObjClosure
)

type Object struct {
	Kind    ObjKind
	Marked  bool
	Array   []Value
	Map     map[hashKey]Value
	Closure *Closure
}

type Closure struct {
	FuncID int
	Env    *Env
}

type hashKey struct {
	kind ValueKind
	num  int
	str  string
	b    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: TokenLBracket, Lexeme: "[", Line: startLine, Col: startCol})
			i++
			col++
		case ']':
			tokens = append(tokens, Token{Kind: TokenRBracket, 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++
		case ':':
			tokens = append(tokens, Token{Kind: TokenColon, 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.parseStmt()
		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) 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 TokenFn:
		return p.parseFnDecl()
	default:
		return p.parseAssignOrExpr()
	}
}

func (p *parser) parseFnDecl() (*Stmt, error) {
	if !p.match(TokenFn) {
		return nil, fmt.Errorf("expected fn")
	}
	nameTok := p.consume(TokenIdent, "expected function name")
	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, "expected parameter name")
		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) parseVarDecl() (*Stmt, error) {
	kindTok := p.advance()
	var kind VarKind
	switch kindTok.Kind {
	case TokenLet:
		kind = VarLet
	case TokenVar:
		kind = VarVar
	case TokenConst:
		kind = VarConst
	default:
		return nil, fmt.Errorf("expected variable declaration")
	}
	nameTok := p.consume(TokenIdent, "expected variable name")
	if nameTok == nil {
		return nil, fmt.Errorf("expected variable name")
	}
	var init *Expr
	if p.match(TokenAssign) {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		init = expr
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after variable declaration")
	}
	return &Stmt{Kind: StmtVar, VarKind: kind, Name: nameTok.Lexeme, Expr: init}, nil
}

func (p *parser) parseAssignOrExpr() (*Stmt, error) {
	left, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if p.match(TokenAssign) {
		if !isLValue(left) {
			return nil, fmt.Errorf("invalid assignment target")
		}
		right, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenSemicolon) {
			return nil, fmt.Errorf("expected ';' after assignment")
		}
		return &Stmt{Kind: StmtAssign, Target: left, Expr: right}, nil
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after expression")
	}
	return &Stmt{Kind: StmtExpr, Expr: left}, 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 if 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 while 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()
	if p.match(TokenSemicolon) {
		return &Stmt{Kind: StmtReturn}, nil
	}
	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) parseBlock() ([]*Stmt, error) {
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{'")
	}
	var body []*Stmt
	for p.peek().Kind != TokenRBrace && p.peek().Kind != TokenEOF {
		stmt, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		body = append(body, stmt)
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}'")
	}
	return body, nil
}

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

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

func (p *parser) parseComparison() (*Expr, error) {
	expr, err := p.parseTerm()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenLess:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "<", Left: expr, Right: right}
		case TokenLessEqual:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "<=", Left: expr, Right: right}
		case TokenGreater:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: ">", Left: expr, Right: right}
		case TokenGreaterEqual:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: ">=", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

func (p *parser) parseTerm() (*Expr, error) {
	expr, err := p.parseFactor()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenPlus:
			p.advance()
			right, err := p.parseFactor()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "+", Left: expr, Right: right}
		case TokenMinus:
			p.advance()
			right, err := p.parseFactor()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "-", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

func (p *parser) parseFactor() (*Expr, error) {
	expr, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenStar:
			p.advance()
			right, err := p.parseUnary()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "*", Left: expr, Right: right}
		case TokenSlash:
			p.advance()
			right, err := p.parseUnary()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "/", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

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

func (p *parser) parsePostfix() (*Expr, error) {
	expr, err := p.parsePrimary()
	if err != nil {
		return nil, err
	}
	for {
		if p.match(TokenLParen) {
			args, err := p.parseArgs()
			if err != nil {
				return nil, err
			}
			if !p.match(TokenRParen) {
				return nil, fmt.Errorf("expected ')' after arguments")
			}
			expr = &Expr{Kind: ExprCall, Left: expr, Args: args}
			continue
		}
		if p.match(TokenLBracket) {
			idx, err := p.parseExpr()
			if err != nil {
				return nil, err
			}
			if !p.match(TokenRBracket) {
				return nil, fmt.Errorf("expected ']' after index")
			}
			expr = &Expr{Kind: ExprIndex, Left: expr, Right: idx}
			continue
		}
		break
	}
	return expr, nil
}

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) parsePrimary() (*Expr, error) {
	switch p.peek().Kind {
	case TokenNumber:
		return &Expr{Kind: ExprNumber, Value: p.advance().Lexeme}, nil
	case TokenString:
		return &Expr{Kind: ExprString, Value: p.advance().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:
		return &Expr{Kind: ExprIdent, Value: p.advance().Lexeme}, 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
	case TokenLBracket:
		return p.parseArray()
	case TokenLBrace:
		return p.parseMap()
	default:
		return nil, fmt.Errorf("unexpected token: %v", p.peek().Kind)
	}
}

func (p *parser) parseArray() (*Expr, error) {
	if !p.match(TokenLBracket) {
		return nil, fmt.Errorf("expected '['")
	}
	if p.match(TokenRBracket) {
		return &Expr{Kind: ExprArray}, nil
	}
	var elems []*Expr
	for {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		elems = append(elems, expr)
		if !p.match(TokenComma) {
			break
		}
	}
	if !p.match(TokenRBracket) {
		return nil, fmt.Errorf("expected ']' after array")
	}
	return &Expr{Kind: ExprArray, Elems: elems}, nil
}

func (p *parser) parseMap() (*Expr, error) {
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{'")
	}
	if p.match(TokenRBrace) {
		return &Expr{Kind: ExprMap}, nil
	}
	var pairs []MapPair
	for {
		key, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenColon) {
			return nil, fmt.Errorf("expected ':' after map key")
		}
		value, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		pairs = append(pairs, MapPair{Key: key, Value: value})
		if !p.match(TokenComma) {
			break
		}
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}' after map")
	}
	return &Expr{Kind: ExprMap, Pairs: pairs}, nil
}

func isLValue(expr *Expr) bool {
	if expr == nil {
		return false
	}
	switch expr.Kind {
	case ExprIdent, ExprIndex:
		return true
	default:
		return false
	}
}

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

func (p *parser) advance() Token {
	if p.pos < len(p.tokens) {
		p.pos++
		return p.tokens[p.pos-1]
	}
	return Token{Kind: TokenEOF}
}

func (p *parser) match(kind TokenKind) bool {
	if p.peek().Kind == kind {
		p.pos++
		return true
	}
	return false
}

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

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) {
	if stmt.Target == nil {
		return
	}
	if stmt.Target.Kind == ExprIdent {
		name := stmt.Target.Value
		sym, ok := a.resolve(name)
		if !ok {
			a.errors = append(a.errors, "undefined name: "+name)
		} else if sym.kind != symVar {
			a.errors = append(a.errors, "cannot assign to const: "+name)
		}
	} else {
		a.analyzeExpr(stmt.Target)
	}
	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:
		if expr.Left != nil && expr.Left.Kind == ExprIdent {
			sym, ok := a.resolve(expr.Left.Value)
			if !ok {
				a.errors = append(a.errors, "undefined name: "+expr.Left.Value)
			} else if sym.kind == symFunc && sym.arity != len(expr.Args) {
				a.errors = append(a.errors, "arity mismatch: "+expr.Left.Value+" expects "+itoa(sym.arity))
			}
		} else {
			a.analyzeExpr(expr.Left)
		}
		for _, arg := range expr.Args {
			a.analyzeExpr(arg)
		}
	case ExprUnary:
		a.analyzeExpr(expr.Left)
	case ExprBinary:
		a.analyzeExpr(expr.Left)
		a.analyzeExpr(expr.Right)
	case ExprArray:
		for _, elem := range expr.Elems {
			a.analyzeExpr(elem)
		}
	case ExprMap:
		for _, pair := range expr.Pairs {
			a.analyzeExpr(pair.Key)
			a.analyzeExpr(pair.Value)
		}
	case ExprIndex:
		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:])
}

type funcState struct {
	functions []Function
	nextID    int
}

// Compile lowers a program AST into bytecode.
func Compile(prog *Program) Bytecode {
	state := &funcState{}
	c := &compiler{funcs: state}
	for _, stmt := range prog.Stmts {
		c.compileStmt(stmt)
	}
	return Bytecode{Functions: state.functions, Main: c.code}
}

type compiler struct {
	code  []Instr
	funcs *funcState
}

func (c *compiler) compileFunction(stmt *Stmt) int {
	id := c.funcs.nextID
	c.funcs.nextID++
	fc := &compiler{funcs: c.funcs}
	for _, s := range stmt.Body {
		fc.compileStmt(s)
	}
	fc.ensureReturn()
	c.funcs.functions = append(c.funcs.functions, Function{ID: id, Name: stmt.Name, Params: stmt.Params, Code: fc.code})
	return id
}

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:
		if stmt.Target != nil && stmt.Target.Kind == ExprIdent {
			c.compileExpr(stmt.Expr)
			c.emit(Instr{Op: OpStore, Str: stmt.Target.Value})
			return
		}
		if stmt.Target != nil && stmt.Target.Kind == ExprIndex {
			c.compileExpr(stmt.Target.Left)
			c.compileExpr(stmt.Target.Right)
			c.compileExpr(stmt.Expr)
			c.emit(Instr{Op: OpSetIndex})
			return
		}
	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:
		id := c.compileFunction(stmt)
		c.emit(Instr{Op: OpMakeClosure, Int: id})
		c.emit(Instr{Op: OpDefineConst, Str: stmt.Name})
	}
}

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:
		c.compileExpr(expr.Left)
		for _, arg := range expr.Args {
			c.compileExpr(arg)
		}
		c.emit(Instr{Op: OpCall, Int: len(expr.Args)})
	case ExprArray:
		for _, elem := range expr.Elems {
			c.compileExpr(elem)
		}
		c.emit(Instr{Op: OpMakeArray, Int: len(expr.Elems)})
	case ExprMap:
		for _, pair := range expr.Pairs {
			c.compileExpr(pair.Key)
			c.compileExpr(pair.Value)
		}
		c.emit(Instr{Op: OpMakeMap, Int: len(expr.Pairs)})
	case ExprIndex:
		c.compileExpr(expr.Left)
		c.compileExpr(expr.Right)
		c.emit(Instr{Op: OpGetIndex})
	}
}

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 BC2 text format.
func Encode(bc Bytecode) string {
	var b strings.Builder
	writeLine(&b, "BC2")
	for _, fn := range bc.Functions {
		line := "FUNC " + strconv.Itoa(fn.ID) + " " + 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 BC2 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] != "BC2" {
		return Bytecode{}, fmt.Errorf("missing BC2 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) >= 3 && toks[0] == "FUNC" {
			id, err := strconv.Atoi(toks[1])
			if err != nil {
				return Bytecode{}, err
			}
			fn := Function{ID: id, Name: toks[2], Params: append([]string(nil), toks[3:]...)}
			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 " + strconv.Itoa(ins.Int)
	case OpReturn:
		return "RETURN"
	case OpEnterScope:
		return "ENTER_SCOPE"
	case OpExitScope:
		return "EXIT_SCOPE"
	case OpPop:
		return "POP"
	case OpMakeClosure:
		return "MAKE_CLOSURE " + strconv.Itoa(ins.Int)
	case OpMakeArray:
		return "MAKE_ARRAY " + strconv.Itoa(ins.Int)
	case OpMakeMap:
		return "MAKE_MAP " + strconv.Itoa(ins.Int)
	case OpGetIndex:
		return "GET_INDEX"
	case OpSetIndex:
		return "SET_INDEX"
	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":
		return parseIntInstr(toks, OpCall)
	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
	case "MAKE_CLOSURE":
		return parseIntInstr(toks, OpMakeClosure)
	case "MAKE_ARRAY":
		return parseIntInstr(toks, OpMakeArray)
	case "MAKE_MAP":
		return parseIntInstr(toks, OpMakeMap)
	case "GET_INDEX":
		return Instr{Op: OpGetIndex}, nil
	case "SET_INDEX":
		return Instr{Op: OpSetIndex}, 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")
}

type binding struct {
	val    Value
	isConst bool
}

type Env struct {
	vars   map[string]*binding
	parent *Env
}

type frame struct {
	code []Instr
	ip   int
	env  *Env
}

type Heap struct {
	objects []*Object
}

func (h *Heap) alloc(obj *Object) *Object {
	h.objects = append(h.objects, obj)
	return obj
}

func (h *Heap) sweep() {
	live := h.objects[:0]
	for _, obj := range h.objects {
		if obj.Marked {
			obj.Marked = false
			live = append(live, obj)
		}
	}
	h.objects = live
}

func (h *Heap) count() int {
	return len(h.objects)
}

type VM struct {
	stack  []Value
	frames []frame
	funcs  map[int]Function
	heap   *Heap
	global *Env
}

func NewVM() *VM {
	return &VM{heap: &Heap{}}
}

func (vm *VM) Run(bc Bytecode) (Value, error) {
	vm.stack = nil
	vm.frames = nil
	vm.funcs = map[int]Function{}
	vm.heap = &Heap{}
	for _, fn := range bc.Functions {
		vm.funcs[fn.ID] = fn
	}
	vm.global = &Env{vars: map[string]*binding{}}
	vm.pushFrame(bc.Main, vm.global)

for len(vm.frames) > 0 {
		fr := vm.currentFrame()
		if fr.ip >= len(fr.code) {
			if len(vm.frames) == 1 {
				if len(vm.stack) > 0 {
					return vm.stack[len(vm.stack)-1], nil
				}
				return Value{Kind: ValueNil}, nil
			}
			vm.popFrame()
			vm.push(Value{Kind: ValueNil})
			continue
		}

instr := fr.code[fr.ip]
		fr.ip++

switch instr.Op {
		case OpPushNum:
			vm.push(Value{Kind: ValueNumber, Num: instr.Int})
		case OpPushStr:
			vm.push(Value{Kind: ValueString, Str: instr.Str})
		case OpPushBool:
			vm.push(Value{Kind: ValueBool, Bool: instr.Int != 0})
		case OpPushNil:
			vm.push(Value{Kind: ValueNil})
		case OpLoad:
			b, ok := fr.env.lookup(instr.Str)
			if !ok {
				return Value{}, fmt.Errorf("undefined name: %s", instr.Str)
			}
			vm.push(b.val)
		case OpStore:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if err := fr.env.assign(instr.Str, v); err != nil {
				return Value{}, err
			}
		case OpDefineVar:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			fr.env.define(instr.Str, v, false)
		case OpDefineConst:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			fr.env.define(instr.Str, v, true)
		case OpAdd:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind == ValueNumber && b.Kind == ValueNumber {
				vm.push(Value{Kind: ValueNumber, Num: a.Num + b.Num})
				break
			}
			if a.Kind == ValueString && b.Kind == ValueString {
				vm.push(Value{Kind: ValueString, Str: a.Str + b.Str})
				break
			}
			return Value{}, fmt.Errorf("type error: add")
		case OpSub:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: sub")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num - b.Num})
		case OpMul:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: mul")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num * b.Num})
		case OpDiv:
			b, a, err := vm.pop2()
			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")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num / b.Num})
		case OpNeg:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if v.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: neg")
			}
			vm.push(Value{Kind: ValueNumber, Num: -v.Num})
		case OpNot:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: !isTruthy(v)})
		case OpEq:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: valueEqual(a, b)})
		case OpNeq:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: !valueEqual(a, b)})
		case OpLt:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lt")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num < b.Num})
		case OpLte:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lte")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num <= b.Num})
		case OpGt:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gt")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num > b.Num})
		case OpGte:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gte")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num >= b.Num})
		case OpJump:
			fr.ip = instr.Int
		case OpJumpIfFalse:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if !isTruthy(v) {
				fr.ip = instr.Int
			}
		case OpCall:
			args, err := vm.popArgs(instr.Int)
			if err != nil {
				return Value{}, err
			}
			callee, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if callee.Kind != ValueClosure || callee.Obj == nil || callee.Obj.Closure == nil {
				return Value{}, fmt.Errorf("call of non-function")
			}
			closure := callee.Obj.Closure
			fn, ok := vm.funcs[closure.FuncID]
			if !ok {
				return Value{}, fmt.Errorf("unknown function id %d", closure.FuncID)
			}
			if len(args) != len(fn.Params) {
				return Value{}, fmt.Errorf("arity mismatch")
			}
			callEnv := &Env{vars: map[string]*binding{}, parent: closure.Env}
			for i, name := range fn.Params {
				callEnv.define(name, args[i], false)
			}
			vm.pushFrame(fn.Code, callEnv)
		case OpReturn:
			ret, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			vm.popFrame()
			if len(vm.frames) == 0 {
				return ret, nil
			}
			vm.push(ret)
		case OpEnterScope:
			fr.env = &Env{vars: map[string]*binding{}, parent: fr.env}
		case OpExitScope:
			if fr.env.parent != nil {
				fr.env = fr.env.parent
			}
		case OpPop:
			if _, err := vm.pop(); err != nil {
				return Value{}, err
			}
		case OpMakeClosure:
			obj := vm.heap.alloc(&Object{Kind: ObjClosure, Closure: &Closure{FuncID: instr.Int, Env: fr.env}})
			vm.push(Value{Kind: ValueClosure, Obj: obj})
		case OpMakeArray:
			arr, err := vm.popList(instr.Int)
			if err != nil {
				return Value{}, err
			}
			obj := vm.heap.alloc(&Object{Kind: ObjArray, Array: arr})
			vm.push(Value{Kind: ValueArray, Obj: obj})
		case OpMakeMap:
			m := map[hashKey]Value{}
			for i := 0; i < instr.Int; i++ {
				val, err := vm.pop()
				if err != nil {
					return Value{}, err
				}
				keyVal, err := vm.pop()
				if err != nil {
					return Value{}, err
				}
				key, ok := toKey(keyVal)
				if !ok {
					return Value{}, fmt.Errorf("invalid map key")
				}
				m[key] = val
			}
			obj := vm.heap.alloc(&Object{Kind: ObjMap, Map: m})
			vm.push(Value{Kind: ValueMap, Obj: obj})
		case OpGetIndex:
			idx, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			target, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			v, err := vm.getIndex(target, idx)
			if err != nil {
				return Value{}, err
			}
			vm.push(v)
		case OpSetIndex:
			val, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			idx, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			target, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if err := vm.setIndex(target, idx, val); err != nil {
				return Value{}, err
			}
		default:
			return Value{}, fmt.Errorf("unknown opcode")
		}
	}
	return Value{Kind: ValueNil}, nil
}

func (vm *VM) currentFrame() *frame {
	return &vm.frames[len(vm.frames)-1]
}

func (vm *VM) pushFrame(code []Instr, env *Env) {
	vm.frames = append(vm.frames, frame{code: code, env: env})
}

func (vm *VM) popFrame() {
	if len(vm.frames) > 0 {
		vm.frames = vm.frames[:len(vm.frames)-1]
	}
}

func (vm *VM) push(v Value) {
	vm.stack = append(vm.stack, v)
}

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

func (vm *VM) pop2() (Value, Value, error) {
	b, err := vm.pop()
	if err != nil {
		return Value{}, Value{}, err
	}
	a, err := vm.pop()
	if err != nil {
		return Value{}, Value{}, err
	}
	return b, a, nil
}

func (vm *VM) popArgs(n int) ([]Value, error) {
	if n == 0 {
		return nil, nil
	}
	args := make([]Value, n)
	for i := n - 1; i >= 0; i-- {
		v, err := vm.pop()
		if err != nil {
			return nil, err
		}
		args[i] = v
	}
	return args, nil
}

func (vm *VM) popList(n int) ([]Value, error) {
	if n == 0 {
		return nil, nil
	}
	out := make([]Value, n)
	for i := n - 1; i >= 0; i-- {
		v, err := vm.pop()
		if err != nil {
			return nil, err
		}
		out[i] = v
	}
	return out, nil
}

func (vm *VM) getIndex(target Value, idx Value) (Value, error) {
	switch target.Kind {
	case ValueArray:
		if idx.Kind != ValueNumber {
			return Value{}, fmt.Errorf("index must be number")
		}
		arr := target.Obj.Array
		if idx.Num < 0 || idx.Num >= len(arr) {
			return Value{}, fmt.Errorf("index out of range")
		}
		return arr[idx.Num], nil
	case ValueMap:
		key, ok := toKey(idx)
		if !ok {
			return Value{}, fmt.Errorf("invalid map key")
		}
		val, ok := target.Obj.Map[key]
		if !ok {
			return Value{Kind: ValueNil}, nil
		}
		return val, nil
	default:
		return Value{}, fmt.Errorf("indexing non-collection")
	}
}

func (vm *VM) setIndex(target Value, idx Value, val Value) error {
	switch target.Kind {
	case ValueArray:
		if idx.Kind != ValueNumber {
			return fmt.Errorf("index must be number")
		}
		arr := target.Obj.Array
		if idx.Num < 0 || idx.Num >= len(arr) {
			return fmt.Errorf("index out of range")
		}
		arr[idx.Num] = val
		target.Obj.Array = arr
		return nil
	case ValueMap:
		key, ok := toKey(idx)
		if !ok {
			return fmt.Errorf("invalid map key")
		}
		target.Obj.Map[key] = val
		return nil
	default:
		return fmt.Errorf("indexing non-collection")
	}
}

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

func valueEqual(a Value, 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
	case ValueArray, ValueMap, ValueClosure:
		return a.Obj == b.Obj
	default:
		return false
	}
}

func toKey(v Value) (hashKey, bool) {
	switch v.Kind {
	case ValueNumber:
		return hashKey{kind: v.Kind, num: v.Num}, true
	case ValueString:
		return hashKey{kind: v.Kind, str: v.Str}, true
	case ValueBool:
		return hashKey{kind: v.Kind, b: v.Bool}, true
	case ValueNil:
		return hashKey{kind: v.Kind}, true
	default:
		return hashKey{}, false
	}
}

func (e *Env) define(name string, v Value, isConst bool) {
	if e.vars == nil {
		e.vars = map[string]*binding{}
	}
	e.vars[name] = &binding{val: v, isConst: isConst}
}

func (e *Env) lookup(name string) (*binding, bool) {
	for cur := e; cur != nil; cur = cur.parent {
		if b, ok := cur.vars[name]; ok {
			return b, true
		}
	}
	return nil, false
}

func (e *Env) assign(name string, v Value) error {
	for cur := e; cur != nil; cur = cur.parent {
		if b, ok := cur.vars[name]; ok {
			if b.isConst {
				return fmt.Errorf("cannot assign to const: %s", name)
			}
			b.val = v
			return nil
		}
	}
	return fmt.Errorf("undefined name: %s", name)
}