Abstract Syntax Tree (AST)
Relevant source files
The following files were used as context for generating this wiki page:
The Abstract Syntax Tree (AST) in the Jazz project serves as the primary intermediate representation of source code during the compilation process. It is divided into two distinct layers: the Surface AST, which represents the raw output of the parser, and the Core AST, which is a lowered, analyzer-facing representation used for semantic checks, type inference, and code generation.
The transition from text to executable involves a staged transformation where the AST is first constructed by the Lexer and Parser, then lowered into a form suitable for the Analyzer. This architecture ensures that the analyzer deals with a simplified, scope-aware representation while the parser maintains a contract with the surface syntax.
Sources: jazz-next/README.md:14-22, README.md:37-45
AST Architecture and Slices
The AST implementation is decoupled into specific functional slices within the jazz-next compiler path to separate parsing concerns from semantic analysis.
| Component | File Path | Purpose |
|---|---|---|
| Surface AST Contract | src/JazzNext/Compiler/Parser/AST.hs | Defines the shape of the tree immediately after parsing. |
| Core AST | src/JazzNext/Compiler/AST.hs | The analyzer-facing core used after lowering. |
| Lowering Boundary | src/JazzNext/Compiler/Parser/Lower.hs | Logic for converting Surface AST to Core AST. |
| Operator AST | docs/spec/syntax/operators.md | Defines the contract for fixity and operator sections. |
Sources: jazz-next/README.md:14-22, scripts/check-clarification-specs.sh:44-46
Data Flow and Transformation
The AST undergoes a structured transformation flow. Raw source text is tokenized and parsed into the Surface AST. This representation is then processed by the "Lowering" phase, which produces the Core AST. The Core AST is the input for the Analyzer, which performs binding/signature coherence checks and generates diagnostics.
The diagram shows the progression from source text to semantic analysis via the AST layers.
Sources: jazz-next/README.md:14-25, jazz-next/scripts/test-warning-config.sh:15-30
Surface vs. Core AST
Surface AST
The Surface AST maintains a close relationship with the user-facing syntax. It includes constructs for:
- Module Declarations: Brace-bodied module structures.
- Operator Sections: Specialized AST nodes for partial operator applications (e.g.,
(+10)). - Lambda Expressions: Surface-level representation of anonymous functions.
- If-Expressions: Representation of conditional control flow before desugaring.
Sources: README.md:43-45, jazz-next/scripts/test-warning-config.sh:19-35, scripts/check-clarification-specs.sh:40-42
Core AST
The Core AST is "analyzer-facing" and optimized for semantic validation. It facilitates:
- Scope-aware Analysis: Identifying rebinding issues (e.g., warning
W0001). - Binding Coherence: Ensuring signatures and bindings match.
- Purity Enforcement: Tracking
!marks for impure functions.
Sources: jazz-next/README.md:14-25, README.md:104-106
Integration with Backend (LLVM)
In legacy and reference implementations (jazz-hs), the AST is designed to eventually map to the LLVM AST. The project utilizes llvm-hs-pure for representing the LLVM IR.
LLVM AST Mapping
The conversion process involves mapping Jazz-specific AST nodes to LLVM Global Definitions and Basic Blocks.
The diagram represents the structural hierarchy of the target LLVM AST used for code generation.
Sources: jazz-hs/local-deps/llvm-hs-pretty/README.md:68-115, jazz-hs/local-deps/llvm-hs-pure/CHANGELOG.md:10-25
LLVM AST Features Used
- Metadata Nodes: The AST supports debug metadata (e.g.,
DILocation,DISubprogram) to facilitate debugging of the generated code. - Constants: Support for
AggregateZerofor initializing structs and arrays. - Attributes: Function and parameter attributes (e.g.,
NoFree,StrictFP).
Sources: jazz-hs/local-deps/llvm-hs-pure/CHANGELOG.md:86-90, jazz-hs/local-deps/llvm-hs/CHANGELOG.md:106-110
Implementation Status
The current implementation in jazz-next focuses on the "core expression subset."
| Feature | AST Support Level | Notes |
|---|---|---|
| Strong/Static Types | Verified | Core expression subset. |
| First-class Functions | Verified | Curried by default. |
| ADTs | Planned | End-to-end behavior not yet full. |
| Pattern Matching | Planned | Syntax stubs in parser. |
| Purity Marking | Partially Implemented | Direct ! call enforcement in binding bodies. |
Sources: README.md:17-30, jazz-next/scripts/test-warning-config.sh:22-26
Summary
The Jazz AST is the backbone of the compilation pipeline, transitioning from a syntax-heavy Surface AST to a semantics-oriented Core AST. This separation allows the compiler to handle complex syntax like operator sections and currying while providing the Analyzer with a clean interface for type inference and diagnostic generation. Future development aims to expand this tree to support full Algebraic Data Types (ADTs) and complete LLVM backend integration.