path: root/awk/scheme/scheme/bin/vm.awk

#!/usr/bin/awk -f

# VM State Initialization
BEGIN {
    # Type tags
    T_NUMBER = "N"
    T_BOOLEAN = "B"
    T_SYMBOL = "S"
    T_PAIR = "P"
    T_FUNCTION = "F"
    T_NIL = "NIL"

    # VM registers
    stack_ptr = 0    # Stack pointer
    heap_ptr = 0     # Heap pointer
    pc = 0           # Program counter
    
    # Debug mode
    DEBUG = 0

    # Environment for variables
    env_size = 0
    
    # Function table (make it persistent)
    delete func_name
    delete func_pc
    delete func_code
    func_size = 0
    
    # Call stack
    call_stack_ptr = 0

    # State persistence
    STATE_FILE = "/tmp/scheme_vm.state"
    if (PERSIST) {
        debug("Loading state from: " STATE_FILE)
        if ((getline line < STATE_FILE) >= 0) {  # Check if file exists and is readable
            do {
                if (line ~ /^FUNC /) {
                    sub(/^FUNC /, "", line)
                    name = line
                    sub(/ .*$/, "", name)
                    code = line
                    sub(/^[^ ]+ /, "", code)
                    
                    debug("Loaded function: " name)
                    debug("Code: " code)
                    
                    func_name[func_size] = name
                    func_code[func_size] = code
                    func_size++
                }
            } while ((getline line < STATE_FILE) > 0)
            close(STATE_FILE)
        }
    }

    # Function environments
    delete func_env_names
    delete func_env_vals
    delete func_env_sizes

    # Global function storage
    delete FUNCTIONS  # Our own function storage array
}

# Debug output function
function debug(msg) {
    if (DEBUG) printf("[DEBUG] %s\n", msg) > "/dev/stderr"
}

# Value construction and access
function makeValue(type, val) {
    return type ":" val
}

function getType(val) {
    return substr(val, 1, index(val, ":") - 1)
}

function getValue(val) {
    return substr(val, index(val, ":") + 1)
}

# Type checking
function isNumber(val) { return getType(val) == T_NUMBER }
function isBoolean(val) { return getType(val) == T_BOOLEAN }
function isSymbol(val) { return getType(val) == T_SYMBOL }
function isPair(val) { return getType(val) == T_PAIR }
function isFunction(val) { return getType(val) == T_FUNCTION }
function isNil(val) { return getType(val) == T_NIL }

# Stack operations
function push(val) {
    stack[++stack_ptr] = val
    debug("Push: " val " (SP: " stack_ptr ")")
}

function pop() {
    if (stack_ptr < 1) error("Stack underflow")
    val = stack[stack_ptr--]
    debug("Pop: " val " (SP: " stack_ptr ")")
    return val
}

function peek() {
    if (stack_ptr < 1) error("Stack empty")
    return stack[stack_ptr]
}

# Heap operations
function allocate(val) {
    heap[++heap_ptr] = val
    refs[heap_ptr] = 1
    debug("Allocate: " val " at " heap_ptr)
    return heap_ptr
}

function getHeap(idx) {
    if (!(idx in heap)) {
        error("Invalid heap access: " idx)
        return ""
    }
    return heap[idx]
}

# Error handling
function error(msg) {
    print "Error at PC " pc ": " msg > "/dev/stderr"
    exit 1
}

# Arithmetic operations
function vm_add() {
    if (stack_ptr < 2) error("ADD requires two operands")
    val2 = pop()
    val1 = pop()
    if (!isNumber(val1) || !isNumber(val2)) 
        error("ADD requires numeric operands")
    result = getValue(val1) + getValue(val2)
    push(makeValue(T_NUMBER, result))
}

function vm_subtract() {
    if (stack_ptr < 2) error("SUB requires two operands")
    val2 = pop()
    val1 = pop()
    if (!isNumber(val1) || !isNumber(val2))
        error("SUB requires numeric operands")
    result = getValue(val1) - getValue(val2)
    push(makeValue(T_NUMBER, result))
}

function vm_multiply() {
    if (stack_ptr < 2) error("MUL requires two operands")
    val2 = pop()
    val1 = pop()
    if (!isNumber(val1) || !isNumber(val2))
        error("MUL requires numeric operands")
    result = getValue(val1) * getValue(val2)
    push(makeValue(T_NUMBER, result))
}

function vm_divide() {
    if (stack_ptr < 2) error("DIV requires two operands")
    val2 = pop()
    val1 = pop()
    if (!isNumber(val1) || !isNumber(val2))
        error("DIV requires numeric operands")
    if (getValue(val2) == 0)
        error("Division by zero")
    result = getValue(val1) / getValue(val2)
    push(makeValue(T_NUMBER, result))
}

# List operations
function vm_cons() {
    if (stack_ptr < 2) error("CONS requires two operands")
    val2 = pop()
    val1 = pop()
    pair_val = val1 "," val2
    pair_idx = allocate(pair_val)
    push(makeValue(T_PAIR, pair_idx))
}

function vm_car() {
    if (stack_ptr < 1) error("CAR requires one operand")
    val = pop()
    if (!isPair(val)) error("CAR requires pair operand")
    pair_idx = getValue(val)
    pair = getHeap(pair_idx)
    car_val = substr(pair, 1, index(pair, ",") - 1)
    push(car_val)
}

function vm_cdr() {
    if (stack_ptr < 1) error("CDR requires one operand")
    val = pop()
    if (!isPair(val)) error("CDR requires pair operand")
    pair_idx = getValue(val)
    pair = getHeap(pair_idx)
    cdr_val = substr(pair, index(pair, ",") + 1)
    push(cdr_val)
}

# Comparison operations
function vm_equal() {
    if (stack_ptr < 2) error("EQ requires two operands")
    val2 = pop()
    val1 = pop()
    result = (val1 == val2) ? "1" : "0"
    push(makeValue(T_BOOLEAN, result))
}

function vm_less_than() {
    if (stack_ptr < 2) error("LT requires two operands")
    val2 = pop()
    val1 = pop()
    if (!isNumber(val1) || !isNumber(val2))
        error("LT requires numeric operands")
    result = (getValue(val1) < getValue(val2)) ? "1" : "0"
    push(makeValue(T_BOOLEAN, result))
}

# Instruction execution
function execute(instr) {
    split(instr, parts, " ")
    op = parts[1]
    debug("Execute: " instr)
    
    if (op == "PUSH_CONST") {
        push(parts[2])
    }
    else if (op == "POP") {
        pop()
    }
    else if (op == "DUP") {
        val = peek()
        push(val)
    }
    else if (op == "SWAP") {
        if (stack_ptr < 2) error("SWAP requires two operands")
        val2 = pop()
        val1 = pop()
        push(val2)
        push(val1)
    }
    else if (op == "ADD") {
        vm_add()
    }
    else if (op == "SUB") {
        vm_subtract()
    }
    else if (op == "MUL") {
        vm_multiply()
    }
    else if (op == "DIV") {
        vm_divide()
    }
    else if (op == "CONS") {
        vm_cons()
    }
    else if (op == "CAR") {
        vm_car()
    }
    else if (op == "CDR") {
        vm_cdr()
    }
    else if (op == "EQ") {
        vm_equal()
    }
    else if (op == "LT") {
        vm_less_than()
    }
    else if (op == "PRINT") {
        if (stack_ptr < 1) error("PRINT requires one operand")
        print peek()
    }
    else if (op == "HALT") {
        if (stack_ptr > 0) {
            print peek()
        }
        exit(0)
    }
    else if (op == "STORE") {
        vm_store(parts[2])
    }
    else if (op == "POP_ENV") {
        vm_pop_env()
    }
    else if (op == "LOOKUP") {
        vm_lookup(parts[2])
    }
    else if (op == "LABEL") {
        vm_define_function(parts[2], pc)
    }
    else if (op == "CALL") {
        vm_call_function(parts[2])
    }
    else if (op == "RETURN") {
        vm_return()
    }
    else {
        error("Unknown instruction: " op)
    }
}

# Program loading
{
    # Store each line as an instruction
    program[NR-1] = $0
}

# Program execution
END {
    # Execute program
    while (pc < length(program)) {
        execute(program[pc++])
    }
    
    # Print final result if any and we haven't HALTed
    if (stack_ptr > 0) {
        print peek()
    }

    # Save state if persistence is enabled
    if (PERSIST) {
        debug("Saving state to: " STATE_FILE)
        for (i = 0; i < func_size; i++) {
            debug("Saving function: " func_name[i])
            print "FUNC " func_name[i] " " func_code[i] > STATE_FILE
        }
        close(STATE_FILE)
    }
}

# Add new VM operations
function vm_store(name) {
    debug("Storing " peek() " as " name " at env_size: " env_size)
    # Store in current environment frame
    env_name[env_size] = name
    env_val[env_size] = peek()
    env_size++
    debug("Environment after store:")
    dump_env()
}

function vm_pop_env() {
    if (env_size <= 0) error("Environment underflow")
    debug("Popping environment at size: " env_size)
    debug("Removing: " env_name[env_size-1] " = " env_val[env_size-1])
    env_size--
}

function vm_lookup(name,    i) {
    debug("Looking up " name " in environment of size: " env_size)
    dump_env()
    for (i = env_size - 1; i >= 0; i--) {
        if (env_name[i] == name) {
            debug("Found " name " = " env_val[i] " at position " i)
            push(env_val[i])
            return
        }
    }
    error("Undefined variable: " name)
}

function vm_define_function(name, start_pc) {
    debug("Defining function: " name " at " start_pc)
    
    # Build function code
    code = ""
    i = start_pc
    while (i < length(program) && program[i] != "RETURN") {
        if (code != "") code = code "\n"
        code = code program[i]
        i++
    }
    code = code "\nRETURN"
    
    # Store in our function array
    debug("Storing function: " name " = " code)
    FUNCTIONS[name] = code
    
    pc = i + 1
}

function vm_call_function(name,    code_lines, j, saved_pc, saved_env_size, arg, param_name) {
    debug("Calling function: " name)
    
    if (!(name in FUNCTIONS)) {
        error("Undefined function: " name)
    }
    
    # Get argument from stack before modifying program
    arg = pop()
    debug("Function argument: " arg)
    
    saved_pc = pc
    saved_env_size = env_size
    
    # Split function code into lines
    split(FUNCTIONS[name], code_lines, "\n")
    
    # Extract parameter name from first STORE instruction
    if (code_lines[1] ~ /^STORE /) {
        param_name = substr(code_lines[1], 7)  # Skip "STORE "
        debug("Found parameter name: " param_name)
    } else {
        error("Function missing parameter definition")
    }
    
    # Create new environment frame with correct parameter name
    debug("Creating new environment frame at size: " env_size)
    env_name[env_size] = param_name
    env_val[env_size] = arg
    env_size++
    
    # Add function code to program
    for (j in code_lines) {
        program[length(program)] = code_lines[j]
    }
    
    # Jump to function code
    pc = length(program) - length(code_lines)
    call_stack[++call_stack_ptr] = saved_pc
    env_stack[call_stack_ptr] = saved_env_size
    
    debug("Function found, jumping to PC: " pc " with env_size: " saved_env_size)
    dump_env()
}

function vm_return() {
    if (call_stack_ptr > 0) {
        # Save return value
        ret_val = pop()
        
        # Restore environment
        while (env_size > env_stack[call_stack_ptr]) {
            debug("Popping environment at size: " env_size)
            vm_pop_env()
        }
        
        # Restore program counter
        pc = call_stack[call_stack_ptr--]
        
        # Push return value back
        push(ret_val)
        
        debug("Returned with value: " ret_val " and env_size: " env_size)
    }
}

# New helper function to dump environment state
function dump_env(    i) {
    debug("Environment dump:")
    for (i = 0; i < env_size; i++) {
        debug("  " i ": " env_name[i] " = " env_val[i])
    }
}