Crush AST (CAST) Specification

Version note: This document describes the v0.3 base spec. The Rust struct implementation (crush-cast/src/lib.rs) is more complete: it adds TryCatch, Throw, LangBlock, StructDef, Break, Continue, DomMutate, DomEventListener, DomQuery, Spawn, Await, Lambda, Pipeline, Range, Match, and AI-native statement/expression nodes. Walkers in the repo declare cast_version values of "0.1" (Rust/Bash) or "0.2" (Python/JS).

Overview

CAST is the intermediate representation used by Crush to enable polyglot programming. Language walkers translate source code into CAST, and the Crush compiler translates CAST into CASM bytecode.

Design Principles

1. Language-Agnostic: CAST nodes should represent common programming constructs, not language-specific syntax
2. Explicit Control Flow: Control flow (if/while/for) is represented explicitly, not as jumps
3. Metadata Preservation: Each node includes meta for source language, line numbers, etc.
4. Type Hints: Optional type annotations for static analysis

Document Structure

Top-Level CAST Document

{
  "version": "0.3",
  "entry": "main",
  "lang": "python",
  "imports": {
    "native": ["os", "sys"],
    "crush": []
  },
  "functions": {
    "main": {
      "params": [],
      "body": [ /* Statement[] */ ],
      "return_type": null,
      "meta": {}
    }
  },
  "structs": {}
}

Statement Nodes

VarDecl - Variable Declaration

{
  "type": "VarDecl",
  "name": "x",
  "value": { /* Expr */ },
  "type_hint": "int",  // Optional
  "meta": { "lang": "python", "line": 5 }
}

Export - Export Variable

{
  "type": "Export",
  "name": "result",
  "value": { /* Expr */ },
  "meta": { "lang": "python" }
}

ExprStmt - Expression Statement

{
  "type": "ExprStmt",
  "expr": { /* Expr */ },
  "meta": { "lang": "python" }
}

If - Conditional Statement

{
  "type": "If",
  "condition": { /* Expr */ },
  "then_body": [ /* Statement[] */ ],
  "else_body": [ /* Statement[] */ ],  // Optional, can be null or []
  "meta": { "lang": "python", "line": 10 }
}

While - While Loop

{
  "type": "While",
  "condition": { /* Expr */ },
  "body": [ /* Statement[] */ ],
  "meta": { "lang": "python", "line": 15 }
}

For - For Loop

{
  "type": "For",
  "iterator": "item",
  "iterable": { /* Expr */ },
  "body": [ /* Statement[] */ ],
  "meta": { "lang": "python", "line": 20 }
}

Return - Function Return

{
  "type": "Return",
  "value": { /* Expr */ },  // Optional, null for void return
  "meta": { "lang": "python" }
}

StructDef - Struct/Class Definition

{
  "type": "StructDef",
  "name": "Point",
  "fields": [
    { "name": "x", "type_hint": "int" },
    { "name": "y", "type_hint": "int" }
  ],
  "methods": [
    {
      "name": "distance",
      "params": ["other"],
      "body": [ /* Statement[] */ ],
      "return_type": "float"
    }
  ],
  "meta": { "lang": "python" }
}

Expression Nodes

Literals

IntLiteral

{
  "type": "IntLiteral",
  "value": 42,
  "meta": { "lang": "python" }
}

StringLiteral

{
  "type": "StringLiteral",
  "value": "Hello, World!",
  "meta": { "lang": "python" }
}

BoolLiteral

{
  "type": "BoolLiteral",
  "value": true,
  "meta": { "lang": "python" }
}

NullLiteral

{
  "type": "NullLiteral",
  "meta": { "lang": "python" }
}

ArrayLiteral

{
  "type": "ArrayLiteral",
  "elements": [ /* Expr[] */ ],
  "meta": { "lang": "python" }
}

MapLiteral

{
  "type": "MapLiteral",
  "entries": [
    { "key": { /* Expr */ }, "value": { /* Expr */ } }
  ],
  "meta": { "lang": "python" }
}

Var - Variable Reference

{
  "type": "Var",
  "name": "x",
  "meta": { "lang": "python" }
}

BinaryOp - Binary Operation

{
  "type": "BinaryOp",
  "operator": "+",  // +, -, *, /, %, ==, !=, <, >, <=, >=, and, or
  "left": { /* Expr */ },
  "right": { /* Expr */ },
  "meta": { "lang": "python" }
}

UnaryOp - Unary Operation

{
  "type": "UnaryOp",
  "operator": "-",  // -, not, ~
  "operand": { /* Expr */ },
  "meta": { "lang": "python" }
}

Call - Function Call

{
  "type": "Call",
  "function": "add",
  "args": [ /* Expr[] */ ],
  "meta": { "lang": "python" }
}

CapabilityCall - Capability Invocation

{
  "type": "CapabilityCall",
  "name": "io.print",
  "args": [ /* Expr[] */ ],
  "meta": {
    "capability": true,
    "namespace": "io",
    "method": "print",
    "lang": "python"
  }
}

FieldAccess - Struct Field Access

{
  "type": "FieldAccess",
  "object": { /* Expr */ },
  "field": "x",
  "meta": { "lang": "python" }
}

Index - Array/Map Indexing

{
  "type": "Index",
  "object": { /* Expr */ },
  "index": { /* Expr */ },
  "meta": { "lang": "python" }
}

Metadata

All nodes should include a meta field with:

• lang: Source language (e.g., “python”, “rust”, “c”)
• line: Optional line number in source
• column: Optional column number in source
• Additional language-specific metadata as needed

Type Hints

Optional type_hint fields can be:

• Primitives: "int", "float", "str", "bool"
• Collections: "array", "map"
• Custom: "StructName"
• Generic: "Array<int>", "Map<str, int>"

Compilation Strategy

Control Flow → CASM

If Statement:

compile(condition)
jmp_if_not else_label
compile(then_body)
jmp end_label
else_label:
compile(else_body)
end_label:

While Loop:

loop_start:
compile(condition)
jmp_if_not loop_end
compile(body)
jmp loop_start
loop_end:

For Loop (requires iterator protocol):

compile(iterable)
store __iter
loop_start:
load __iter
cap_call iter.next 1
dup
jmp_if_not loop_end
store iterator
compile(body)
jmp loop_start
loop_end:
pop

Version History

• v0.3: Added control flow nodes (If, While, For), data structures (StructDef), and formal specification
• v0.2: Added CapabilityCall, Import, Export
• v0.1: Initial version with basic expressions and statements