Evaluation and Scripts in Rust

# Evaluation and Scripts in Rust

## CS 631 Systems Foundations

---

## ParseNode Enum

```rust
pub enum ParseNode {
    IntLit(u32),
    Ident(String),
    UnaryOp {
        op: UnaryOp,
        operand: Box<ParseNode>,
    },
    BinaryOp {
        op: BinaryOp,
        left: Box<ParseNode>,
        right: Box<ParseNode>,
    },
    Assign {
        name: String,
        expr: Box<ParseNode>,
    },
    Print {
        expr: Box<ParseNode>,
        base: Box<ParseNode>,
        width: Box<ParseNode>,
    },
}
```

---

## Why Box?

`Box<ParseNode>` allocates on heap:

```rust
let node = ParseNode::BinaryOp {
    op: BinaryOp::Add,
    left: Box::new(ParseNode::IntLit(2)),
    right: Box::new(ParseNode::IntLit(3)),
};
```

**Reasons**:

- Recursive types need indirection
- Prevents infinite size at compile time
- Enables tree structures

---

## HashMap-Based Environment

```rust
use std::collections::HashMap;

pub type Environment = HashMap<String, u32>;
```

<div class="info-box">
Idiomatic Rust: use built-in HashMap for O(1) lookup.
</div>

```rust
let mut env = HashMap::new();
env.insert("x".to_string(), 10);
env.insert("y".to_string(), 20);
```

---

## HashMap Operations

| Operation | Method |
|-----------|--------|
| Insert/Update | `insert(key, value)` |
| Lookup | `get(key)` → `Option<&u32>` |
| Check | `contains_key(key)` |
| Remove | `remove(key)` |

Automatic upsert with `insert()`.

---

## Option Type

```rust
enum Option<T> {
    Some(T),
    None,
}
```

Represents value that might not exist.

**Lookup returns Option**:

```rust
match env.get(name) {
    Some(&value) => value,
    None => panic!("undefined variable: {}", name),
}
```

---

## Variable Lookup

```rust
fn lookup_var(env: &Environment, name: &str) -> u32 {
    env.get(name)
       .copied()
       .unwrap_or_else(|| {
           eprintln!("Error: undefined variable '{}'", name);
           std::process::exit(1)
       })
}
```

- `.copied()` converts `Option<&u32>` → `Option<u32>`
- `.unwrap_or_else()` provides error handling

---

## Expression Evaluation

```rust
pub fn eval_expression(node: &ParseNode,
                       env: &mut Environment) -> u32 {
    match node {
        ParseNode::IntLit(val) => *val,
        ParseNode::Ident(name) => lookup_var(env, name),

ParseNode::UnaryOp { op, operand } => {
            eval_unary(*op, operand, env)
        }

ParseNode::BinaryOp { op, left, right } => {
            eval_binary(*op, left, right, env)
        }

_ => panic!("Invalid expression node"),
    }
}
```

---

## Pattern Matching

<div class="highlight-box">
Pattern matching on enums is <strong>exhaustive</strong> — compiler ensures all cases handled.
</div>

```rust
match node {
    ParseNode::IntLit(val) => *val,
    ParseNode::Ident(name) => lookup_var(env, name),
    // Compiler error if any variant missing
}
```

---

## Unary Evaluation

```rust
fn eval_unary(op: UnaryOp, operand: &ParseNode,
              env: &mut Environment) -> u32 {
    let val = eval_expression(operand, env);

match op {
        UnaryOp::Neg => (-(val as i32)) as u32,
        UnaryOp::Not => !val,
    }
}
```

**Type casting for negation**:

1. Cast `u32` → `i32`
2. Apply unary `-`
3. Cast back to `u32`

---

## Binary Evaluation

```rust
fn eval_binary(op: BinaryOp, left: &ParseNode,
               right: &ParseNode,
               env: &mut Environment) -> u32 {
    let left_val = eval_expression(left, env);
    let right_val = eval_expression(right, env);

match op {
        BinaryOp::Add => left_val.wrapping_add(right_val),
        BinaryOp::Sub => left_val.wrapping_sub(right_val),
        BinaryOp::Mul => left_val.wrapping_mul(right_val),
        BinaryOp::Div => left_val / right_val,
        BinaryOp::Shr => left_val >> right_val,
        BinaryOp::Shl => left_val << right_val,
        /* ... */
    }
}
```

---

## Wrapping Arithmetic

| Operation | Behavior |
|-----------|----------|
| `+`, `-`, `*` | Panics on overflow (debug) |
| `.wrapping_add()` | Wraps (two's complement) |
| `.checked_add()` | Returns `Option<u32>` |
| `.saturating_add()` | Clamps to min/max |

**For NTLang**: Use wrapping arithmetic.

```rust
let a: u32 = 0xFFFFFFFF;
let b: u32 = 2;
let c = a.wrapping_add(b);  // 1
```

---

## Arithmetic Shift Right

```rust
BinaryOp::Asr => {
    ((left_val as i32) >> right_val) as u32
}
```

Cast to `i32` to preserve sign bit during shift.

---

## Statement Evaluation

```rust
pub fn eval_statement(node: &ParseNode,
                      env: &mut Environment) {
    match node {
        ParseNode::Assign { name, expr } => {
            let value = eval_expression(expr, env);
            env.insert(name.clone(), value);
        }

ParseNode::Print { expr, base, width } => {
            let value = eval_expression(expr, env);
            let base_val = eval_expression(base, env);
            let width_val = eval_expression(width, env);
            print_formatted(value, base_val, width_val);
        }

_ => panic!("Invalid statement"),
    }
}
```

---

## Assignment

```rust
ParseNode::Assign { name, expr } => {
    let value = eval_expression(expr, env);
    env.insert(name.clone(), value);
}
```

`HashMap::insert` automatically performs upsert.

**String cloning**:

```rust
name.clone()  // Creates new String owned by HashMap
```

---

## Mutable References

```rust
fn eval_expression(node: &ParseNode,
                   env: &mut Environment) -> u32
```

`&mut Environment` means:

- Mutable reference
- Only one at a time
- Can modify HashMap

<div class="info-box">
Rust enforces <strong>single mutable reference</strong> rule at compile time.
</div>

---

## Ownership Rules

```rust
let mut env = HashMap::new();

eval_statement(&stmt1, &mut env);
eval_statement(&stmt2, &mut env);
```

Multiple sequential mutable borrows OK.

**Not allowed**:

```rust
let ref1 = &mut env;
let ref2 = &mut env;  // Error!
```

---

## Print Formatting

```rust
fn print_formatted(value: u32, base: u32, width: u32) {
    let masked = apply_width_mask(value, width);

match base {
        10 => {
            let signed = sign_extend(masked, width);
            println!("{}", signed);
        }
        16 => {
            let hex = format_hex(masked, width);
            println!("0x{}", hex);
        }
        2 => {
            let bin = format_binary(masked, width);
            println!("0b{}", bin);
        }
        _ => panic!("invalid base"),
    }
}
```

---

## Width Masking

```rust
fn apply_width_mask(value: u32, width: u32) -> u32 {
    if width == 32 {
        value
    } else {
        let mask = (1u32 << width) - 1;
        value & mask
    }
}
```

---

## Sign Extension

```rust
fn sign_extend(value: u32, width: u32) -> i32 {
    let masked = apply_width_mask(value, width);
    let sign_bit = 1u32 << (width - 1);

if masked & sign_bit != 0 {
        let extension = !((1u32 << width) - 1);
        (masked | extension) as i32
    } else {
        masked as i32
    }
}
```

---

## Program Evaluation

```rust
pub fn eval_program(statements: &[ParseNode]) {
    let mut env = HashMap::new();

for stmt in statements {
        eval_statement(stmt, &mut env);
    }
}
```

Simple iteration over statement slice.

---

## Error Handling: Panic

For unrecoverable errors:

```rust
if right_val == 0 {
    panic!("division by zero");
}

if ![2, 10, 16].contains(&base) {
    panic!("base must be 2, 10, or 16");
}
```

---

## Error Handling: eprintln + exit

```rust
if !env.contains_key(name) {
    eprintln!("Error: undefined variable '{}'", name);
    std::process::exit(1);
}
```

- `eprintln!` writes to stderr
- `std::process::exit(1)` terminates

---

## Automatic Memory Management

```rust
{
    let node = ParseNode::IntLit(42);
    // Use node...
}  // Automatically dropped and freed
```

`Box<ParseNode>` freed when out of scope.

**No manual free needed** — ownership system handles it.

---

## Clone vs Reference

| Pattern | Ownership | Cost |
|---------|-----------|------|
| `name.clone()` | New String | Allocation |
| `&name` | Borrow | Free |

For HashMap insert: must clone or move.

```rust
env.insert(name.clone(), value);
```

---

## Pattern Matching Advantages

**Exhaustiveness**:

```rust
match node {
    ParseNode::IntLit(val) => *val,
    ParseNode::Ident(name) => lookup(name),
    // Compiler error if missing case
}
```

**Destructuring**:

```rust
ParseNode::BinaryOp { op, left, right } => {
    // Direct access to fields
}
```

---

## Module Structure

```text
project01/rust/src/
├── main.rs          # Entry point
├── scan.rs          # Scanner
├── parse.rs         # Parser, AST
├── eval.rs          # Evaluator
└── convert.rs       # Base conversion
```

**main.rs**:

```rust
mod scan;
mod parse;
mod eval;

use eval::eval_program;
```

---

## Integration

```rust
fn main() {
    let args: Vec<String> = std::env::args().collect();

let source = std::fs::read_to_string(&args[1])
        .expect("failed to read file");

let tokens = scan(&source);
    let statements = parse_program(&tokens);

eval_program(&statements);
}
```

---

## Summary

1. **Enum-based AST** with pattern matching
2. **HashMap environment** for O(1) lookup
3. **Pattern matching** — exhaustive, type-safe
4. **Option type** for nullable values
5. **Mutable references** with `&mut`
6. **Wrapping arithmetic** for overflow
7. **Box** for recursive structures
8. **Ownership** — automatic memory management
9. **Error handling** — panic or Result