Abstract Syntax Tree
The abstract syntax tree is the core data structure of the backend.
It represents the generated C code on a level of abstraction fit for pystencils.
The range of syntax and structure represented by the AST is from the kernel function (upper limit) to just above the arithmetic-logical expressions (lower limit). Above that, code generation is the business of whatever framework pystencils is embedded in. Below, we use `pymbolic`.
## Class Hierarchy and Syntax Modelling
The base class of the AST nodes shall be `PsAstNode`. Its primary tasks are:
- Manage the branching structure
- Manage custom metadata
There shall be a dedicated class for each required syntactic structure, including:
- *Loops:* We model increment-type loops by `PsLoop`
- *Expressions:* Expressions are modelled using pymbolic. Each pymbolic expression in the AST is wrapped in the `PsExpression` leaf node or its subclasses.
## Typing in Expressions
In a well-formed AST, all pymbolic expressions must be fully typed; they may contain no bare `Variable`s and no bare constants, but only their typed variants `PsTypedVariable` and `PsTypedConstants` (see pycodegen/pystencils#77).
## Correspondence to frontend data structures and metadata
The AST is made up of a fixed set of backend data structures, and shall contain no frontend (e.g. SymPy-related) data structures in its primary structure. However, mappings to front-end structures might be managed within the AST metadata.
A metadata dict shall exist on each AST node for any frontend to store arbitrary data in. The backend shall not access that metadata.
## Visitors
As most algorithms on the AST will follow the visitor pattern, a type-based visitor dispatcher is provided to simplify the implementation of recursive visitor-type algorithms.
task