Evaluation and Scripts

# Evaluation and Scripts

## CS 631 Systems Foundations

---

## From Parsing to Evaluation

The compilation pipeline:

```text
Source → Scanner → Tokens → Parser → AST → Evaluator → Result
```

We've built the scanner and parser. Now we focus on:

**Evaluator**: Traverses the AST and computes results

<div class="info-box">
An Abstract Syntax Tree (AST) represents the hierarchical structure of a program.
</div>

---

## What is an AST?

Expression: `2 + 3 * 4`

```text
AST:
        +
       / \
      2   *
         / \
        3   4
```

The tree encodes operator precedence:

- `*` is deeper → evaluated first
- `+` is at the root → evaluated last

---

## Tree Traversal: Post-Order

To evaluate: visit children before parent

```text
        +
       / \
      2   *
         / \
        3   4
```

**Evaluation order**: `2`, `3`, `4`, `*`, `+`

1. Evaluate `2` → 2
2. Evaluate `3` → 3
3. Evaluate `4` → 4
4. Evaluate `3 * 4` → 12
5. Evaluate `2 + 12` → 14

---

## Recursive Evaluation Algorithm

```text
function evaluate(node):
    if node is a literal:
        return node.value

if node is unary operation:
        operand = evaluate(node.child)
        return apply_op(node.operator, operand)

if node is binary operation:
        left = evaluate(node.left)
        right = evaluate(node.right)
        return apply_op(node.operator, left, right)
```

<div class="highlight-box">
This is called <strong>post-order traversal</strong> — process children before parent.
</div>

---

## Example: Evaluating `(2 + 3) * 4`

```text
AST:
        *
       / \
      +   4
     / \
    2   3
```

**Trace**:

| Call | Returns |
|------|---------|
| `eval(2)` | 2 |
| `eval(3)` | 3 |
| `eval(+)` | 5 |
| `eval(4)` | 4 |
| `eval(*)` | 20 |

---

## Expression Mode vs Script Mode

**Expression Mode** (`-e` flag):

```bash
$ ./project01 -e "2 + 3"
5
```

Evaluates a single expression.

**Script Mode** (file):

```bash
$ ./project01 script.ntl
```

Executes a sequence of statements.

---

## Grammar Extension

**Expression grammar** (Section 1):

```text
program ::= expression EOT
```

**Script grammar** (Section 2):

```text
program    ::= (statement '\n')* EOT
statement  ::= assignment | print_statement
assignment ::= ident '=' expression
print_statement ::= 'print' '(' expr ',' expr ',' expr ')'
```

Key changes: statements, assignments, print, identifiers

---

## Extending the Grammar

**Operands** now include identifiers:

**New tokens**:

- `ident` — variable names
- `=` — assignment
- `,` — comma
- `\n` — newline (statement separator)
- `#` — comments

---

## Variables and the Environment

An **environment** maps variable names to values:

```text
Environment = { "x": 10, "y": 20, "z": 30 }
```

| Operation | Description |
|-----------|-------------|
| Lookup | Get value of a variable |
| Insert | Add new variable |
| Update | Change existing variable |
| Upsert | Insert or update |

<div class="info-box">
NTLang uses <strong>upsert</strong> semantics — assignment creates or updates.
</div>

---

## Scope

NTLang has a **single global scope**:

```text
x = 10
y = x + 5
x = 20        # Updates existing x
print(x, 10, 32)
print(y, 10, 32)
```

Output:

```text
20
15
```

No local scopes, functions, or blocks.

---

## Environment Example

Script:

```text
x = 2 + 3
y = x * 4
print(y, 10, 32)
```

**Execution trace**:

| Statement | Environment | Action |
|-----------|-------------|--------|
| (start) | `{}` | Empty |
| `x = 2 + 3` | `{"x": 5}` | Bind x to 5 |
| `y = x * 4` | `{"x": 5, "y": 20}` | Lookup x, bind y to 20 |
| `print(...)` | `{"x": 5, "y": 20}` | Lookup y, print 20 |

---

## Assignment Statement

```text
ident = expression
```

**Evaluation**:

1. Evaluate the expression
2. Bind the variable name to the value

**Example**:

```text
a = 3
b = 4
c = 5
q = (a * 7 * 7) + (b * 7) + c
```

After execution:

```text
{"a": 3, "b": 4, "c": 5, "q": 180}
```

---

## Print Statement

```text
print(expression, base, width)
```

**Evaluation**:

1. Evaluate `expression` → value
2. Evaluate `base` → 2, 10, or 16
3. Evaluate `width` → 4, 8, 16, or 32
4. Format and print

**Example**:

```text
x = 15
print(x, 10, 32)    # 15
print(x, 16, 8)     # 0x0F
print(x, 2, 4)      # 0b1111
```

---

## Print Formatting

| Base | Format | Example Output |
|------|--------|----------------|
| 10 | Signed decimal | `15` or `-5` |
| 16 | Hex with prefix | `0x0F` (width 8) |
| 2 | Binary with prefix | `0b1111` (width 4) |

For base 10: values are **signed** (two's complement)

For base 16 and 2: width determines number of digits

---

## Expression Evaluation with Variables

```text
function evaluate_expression(expr, env):
    if expr is literal:
        return expr.value

if expr is identifier:
        if expr.name not in env:
            error("undefined variable")
        return env[expr.name]

if expr is binary operation:
        left = evaluate(expr.left, env)
        right = evaluate(expr.right, env)
        return apply_op(left, right)
```

<div class="highlight-box">
Identifiers require <strong>lookup</strong> in the environment.
</div>

---

## Statement Evaluation

```text
function evaluate_statement(stmt, env):
    if stmt is assignment:
        value = evaluate_expression(stmt.expr, env)
        env[stmt.ident] = value

if stmt is print:
        value = evaluate_expression(stmt.expr, env)
        base = evaluate_expression(stmt.base, env)
        width = evaluate_expression(stmt.width, env)
        print_formatted(value, base, width)
```

Environment is passed to all evaluation functions.

---

## Program Evaluation

```text
function evaluate_program(statements, env):
    for each statement in statements:
        evaluate_statement(statement, env)
```

Simple loop through the statement list.

Environment persists across statements.

---

## Script Example: Basic Assignment

**p1.ntl**:

```text
x = 1 + 2
print(x, 10, 32)
print(x, 2, 32)
print(x, 16, 32)
```

**Output**:

```text
3
0b00000000000000000000000000000011
0x00000003
```

---

## Script Example: Quadratic

**p2.ntl**:

```text
# Quadratic equation
x = 7
a = 3
b = 4
c = 5
q = (a * x * x) + (b * x) + c
print(q, 10, 32)
```

**Output**: `180`

Computes: 3×7² + 4×7 + 5 = 147 + 28 + 5 = 180

---

## Script Example: Two's Complement

**p3.ntl**:

```text
x = 241
y = (~x) + 1
print(x, 10, 32)
print(y, 10, 32)
```

**Output**:

```text
241
-241
```

`(~x) + 1` is the two's complement negation.

---

## Error Handling

**Undefined variable**:

```text
print(x, 10, 32)    # x not defined
```

Should report error and exit.

**Invalid base/width**:

```text
print(5, 11, 32)    # base must be 2, 10, or 16
print(5, 10, 7)     # width must be 4, 8, 16, or 32
```

---

## Implementation: Data Structures

| Component | Data Structure |
|-----------|----------------|
| Environment | Hash map or array |
| AST | Tree of nodes |
| Values | 32-bit unsigned integers |

**Hash map** (Rust): O(1) lookup, dynamic

**Array** (C): O(n) lookup, simpler, sufficient for small programs

---

## Implementation: Passing Environment

Environment must thread through all evaluation:

```text
evaluate_expression(expr, env)
evaluate_statement(stmt, env)
evaluate_program(stmts, env)
```

- **C**: Pass pointer to environment struct
- **Rust**: Pass mutable reference `&mut HashMap<String, u32>`

---

## Summary

1. **Post-order traversal** — evaluate children before parent

2. **Grammar extension** — from single expression to statement list

3. **Environment** — maps variable names to values

4. **Assignment** — evaluate expression, bind to variable

5. **Print** — format value with specified base/width

6. **Identifiers** — require lookup in environment

7. **Scope** — single global scope in NTLang

8. **Threading** — environment passed through all evaluations