The Expression Tree

Every symbolic object that SeQuant manipulates — a tensor, a scalar, a sum, a product, an entire many-body equation — is represented as a node in a tree of sequant::Expr objects. Understanding this small, shared vocabulary makes the rest of the library predictable: the same handful of node types recur everywhere, from the simple examples in Getting started to the equations produced by the coupled-cluster machinery.

Expr and ExprPtr

sequant::Expr is the abstract base of every expression node; concrete node types (described below) derive from it. Expressions are always managed through sequant::ExprPtr, a smart pointer (interchangeable with std::shared_ptr<Expr>) that adds the arithmetic operators (+, -, *) used to build up expressions programmatically. An ExprPtr is itself iterable over its immediate subexpressions, so an expression tree can be walked, matched, or rewritten generically without knowing the concrete type of every node.

Leaves: Tensor, Constant, Variable

sequant::Tensor is the most common leaf: a labeled tensor quantity with a bra and a ket index set (and, optionally, auxiliary indices), carrying its own permutational and particle symmetry. Registering the index spaces those indices belong to is covered separately.

Scalar quantities are represented by two different leaf types, depending on whether their value is known while building the expression:

  • sequant::Constant holds a fixed complex-rational number, e.g. the \(\frac{1}{2}\) prefactor of a commutator expansion.

  • sequant::Variable holds a named scalar, such as a perturbation strength \(\lambda\), whose value is not fixed by the expression itself.

  • sequant::Power represents base^exponent for a rational exponent, where the base is a Constant or a Variable.

  • sequant::TensorPower represents the element-wise base^exponent of a tensor leaf for a rational exponent. Build either kind of power with sequant::pow(), which refuses a compound tensor-valued base (name it as a ResultExpr and raise the resulting leaf). An odd integer exponent keeps the base’s permutational symmetry, an even one makes an antisymmetric base symmetric, and a non-integer exponent on an antisymmetric base is rejected. A TensorPower evaluates numerically on every backend; code export of one is supported by the text, Python and Julia TensorOperations generators (the ITF, Julia ITensor and Julia TensorKit generators refuse it; see Code Generation).

// Tensor is a leaf Expr: a labeled tensor with a bra and a ket index set
auto f = ex<Tensor>(L"f", bra{L"i_1"}, ket{L"a_1"});
auto g = ex<Tensor>(L"g", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"});

// ExprPtr arithmetic builds Product and Sum nodes; both are associative and
// flatten automatically, so nesting them never grows the tree depth
auto product = f * g;      // a Product of 2 factors
auto sum = f * g + g + f;  // a Sum of 3 summands, not a Sum of a Sum and f

SEQUANT_ASSERT(product.is<Product>());
SEQUANT_ASSERT(product.as<Product>().factors().size() == 2);
SEQUANT_ASSERT(sum.is<Sum>());
SEQUANT_ASSERT(sum.as<Sum>().summands().size() == 3);

std::wcout << sum << std::endl;

// TensorPower is the element-wise rational power of a tensor leaf; pow()
// builds it, e.g. the inverse of a symmetric denominator tensor
auto D = ex<Tensor>(L"D", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"},
                    TensorSymmetries{.perm = Symmetry::Symm,
                                     .braket = BraKetSymmetry::Symm,
                                     .column = ColumnSymmetry::Symm});
auto D_inv = pow(D, rational{-1});

SEQUANT_ASSERT(D_inv.is<TensorPower>());
SEQUANT_ASSERT(D_inv.as<AbstractTensor>()._symmetry() == Symmetry::Symm);

// an even power of an antisymmetric tensor is symmetric
auto t = ex<Tensor>(L"t", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"},
                    Symmetry::Antisymm);
SEQUANT_ASSERT(pow(t, rational{2})->as<AbstractTensor>()._symmetry() ==
               Symmetry::Symm);

std::wcout << std::format(L"{}", D_inv) << std::endl;

Composition: Product and Sum

sequant::Product (a scalar times zero or more factors) and sequant::Sum (zero or more summands) combine other expressions. Both are associative and flatten automatically: multiplying a Product into another Product, or adding a Sum into another Sum, does not create a deeper tree — the factors/summands are merged into the same node. A bare Constant factor is likewise folded straight into a Product’s scalar prefactor rather than kept as a separate factor. This is why the ordinary +/* operators on ExprPtr are usually all that is needed to build up even large equations: the tree stays as flat as possible without any manual bookkeeping.

// scalar leaves: Constant (a compile-time rational/complex number),
// Variable (a named runtime scalar), and Power (base^exponent, with base
// being a Constant or a Variable)
auto half = ex<Constant>(rational(1, 2));
auto lambda = ex<Variable>(L"\\lambda");
auto lambda_sq = ex<Power>(lambda, 2);

SEQUANT_ASSERT(lambda_sq.as<Power>().base() == lambda);
SEQUANT_ASSERT(lambda_sq.as<Power>().exponent() == 2);

auto scaled = half * g;  // Constant and Tensor combine into one Product
std::wcout << std::format(L"{}", scaled) << std::endl;

Note

Two expressions that are mathematically equal are not necessarily represented by identical trees until they have been put into canonical form; see Canonicalization.

ResultExpr: naming an equation

An sequant::Expr on its own has no notion of “what it is equal to” — it is only ever the right-hand side of an implicit equation. sequant::ResultExpr closes that gap by pairing an expression with an explicit left-hand side, either a sequant::Tensor (for a tensorial result such as a residual \(R^{a_1}_{i_1}\)) or a sequant::Variable (for a scalar result such as an energy). This is the representation handed to optimize() and to the code generators, since both need to know the external index pairing and symmetry of the result, not just the expression that computes it.

// ResultExpr pairs an expression with an explicit left-hand side, e.g.
// "R^{a_1}_{i_1} = f^{a_1}_{i_1}"; this is the object handed to optimize()
// and to the code generators in SeQuant/core/export
auto result = ResultExpr(Tensor(L"R", bra{L"i_1"}, ket{L"a_1"}), f);

SEQUANT_ASSERT(result.produces_tensor());
std::wcout << std::format(L"{}", result.expression()) << std::endl;

A tensorial expression that a later equation needs as a factor, a Hadamard (element-wise) product such as \(\ell^{a_1 a_2}_{i_1 i_2} = M^{a_1 a_2}_{i_1 i_2} / D^{a_1 a_2}_{i_1 i_2}\) in a perturbative correction, is composed through heads: it becomes its own ResultExpr, whose head declares the external indices and symmetries once, and the later equation uses that head as a leaf via ResultExpr::result_as_tensor() rather than respelling it. This is also how a compound expression is raised to a power: name it, then apply sequant::pow() to the leaf.

// Compose through ResultExpr heads: each stage is its own equation whose
// head declares the external indices and symmetries once, and later stages
// reuse the head via result_as_tensor() instead of respelling it
const TensorSymmetries antisymm{.perm = Symmetry::Antisymm};
auto M = ex<Tensor>(L"M", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"}, antisymm);
auto L = ex<Tensor>(L"L", bra{L"a_1", L"a_2"}, ket{L"i_1", L"i_2"}, antisymm);

// ℓ = M ⊙ D^{-1}: a Hadamard (element-wise) product, legal because the
// head names its externals; the head declares ℓ's antisymmetry
auto ell = ResultExpr(
    Tensor(L"ℓ", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"}, antisymm),
    M * pow(D, rational{-1}));

// E = L · ℓ: an ordinary contraction of the leaf ℓ, taken from the head
auto E = ResultExpr(Variable(L"E"), L * ex<Tensor>(ell.result_as_tensor()));

SEQUANT_ASSERT(!E.produces_tensor());
std::wcout << std::format(L"{}", ell.expression()) << std::endl;
std::wcout << std::format(L"{}", E.expression()) << std::endl;

Under a head, the summands of a sequant::Sum need not carry the same external indices: a summand may omit some of the head’s indices, meaning that it is constant along those modes and is broadcast over them, as in the orbital-energy denominator D{i_1,i_2;a_1,a_2} = ε{;a_1} + ε{;a_2} - ε{i_1;} - ε{i_2;}. is_valid() accepts such a ResultExpr if every summand’s external indices are a subset of the head’s and together the summands supply all of them; a bare Sum, which has no head to name the missing modes, must still be uniformly indexed. Aux modes cannot be broadcast over: a summand must carry every aux index of the head. sequant::binarize() of a ResultExpr wraps each short summand in a unary sequant::EvalOp::Broadcast node, which expands it over the head modes it lacks; sequant::optimize() optimizes the summands like any others and leaves the broadcast to binarize. Evaluating such a tree requires BackendArrayOps on the cache (CacheManager::set_array_ops), the same backend hooks batched evaluation uses (see Evaluation Trace Analysis), because the extents and tilings of the added modes come from the backend’s per-space tilings; as in batched evaluation, the leaf tilings must agree with those array ops on every mode, which the broadcast itself does not diagnose. Code export spells the Broadcast nodes per backend (see Code Generation).

// under a head, a summand may omit head indices and is then constant along
// those modes, e.g. the orbital-energy denominator
// D{i_1,i_2;a_1,a_2} = ε{;a_1} + ε{;a_2} - ε{i_1;} - ε{i_2;}
auto denominator =
    ResultExpr(Tensor(L"D", bra{L"i_1", L"i_2"}, ket{L"a_1", L"a_2"}),
               ex<Tensor>(L"ε", bra{}, ket{L"a_1"}) +
                   ex<Tensor>(L"ε", bra{}, ket{L"a_2"}) -
                   ex<Tensor>(L"ε", bra{L"i_1"}, ket{}) -
                   ex<Tensor>(L"ε", bra{L"i_2"}, ket{}));
SEQUANT_ASSERT(is_valid(denominator));

// binarize() expands each summand over the head indices it lacks with a
// Broadcast node: here the root sums four of them
[[maybe_unused]] auto const tree = binarize(denominator);
SEQUANT_ASSERT(tree->is_sum() && tree.right()->is_broadcast());

std::wcout << std::format(L"{}", denominator.expression()) << std::endl;

Systems of equations

Equations composed through heads, such as D, ℓ and a consumer of ℓ, can be binarized together: sequant::binarize() of a std::span<const ResultExpr> returns an sequant::InlinedSystem with one evaluation tree per equation, in input order, a consumed flag for each equation whose head another equation used, and roots(), the trees of the equations no other equation used. Each leaf that names a head is replaced by that head’s equation, binarized as it would be on its own (so a broadcast sum gets its Broadcast nodes and nested definitions are inlined in turn); the equations may be given in any order.

A sequant::Tensor leaf names a head if its label, its bra, ket and aux ranks and the index space and number of proto indices of every slot agree with the head’s. A leaf that agrees only with bra and ket swapped, as sequant::canonicalize() may spell it, names a bra-ket symmetric head too; for a conjugate-symmetric head it throws (define the conjugate as its own equation), and for a head without bra-ket symmetry it is a different tensor. A head that matches the leaf as written takes precedence over one that matches it swapped. A leaf with the same label but a different shape remains an ordinary leaf, served by the leaf evaluator. A leaf that names a head must declare the head’s symmetries, otherwise binarization throws; spelling the use through ResultExpr::result_as_tensor() guarantees that. A sequant::Variable leaf names a scalar head by its label; a conjugated use, or a use as the base of a scalar power, throws, so define the conjugate or the power as its own equation. Two equations with the same label and shape (for a bra-ket symmetric head, also with bra and ket swapped), and a definition that reaches its own head, are errors as well; the API reference lists every exception.

An inlined equation enters its consumer as one factor with the layout and symmetries of the authored head: the consumer contracts with ℓ as declared, not with the factors of its right-hand side, so the head, rather than the factors that define it, is what the consumer’s legality (for instance the context’s strict bra-ket rule) is checked against. Repeated uses of a head yield subtrees with equal hashes and are recognized as the same intermediate like any repeated subexpression. Batched evaluation (see Batched (Memory-Bounded) Evaluation) slices through an inlined equation like through any other subtree, so a batch loop opened in the consumer also bounds the intermediates of the definition: a denominator built from orbital energies need not be materialized whole. Code export does not use the system overload; export each ResultExpr in order (see Code Generation), and a later equation reads an earlier head like any other tensor.

// binarize() of a system inlines each definition into its uses: a leaf
// names a head if label, ranks and index spaces agree (a leaf that names a
// head with other symmetries throws); D's head is D, the base of the power
// in ℓ, defined as the broadcast sum above
auto D_def = ResultExpr(D->as<Tensor>(), denominator.expression());

// R{i_2;i_3} = L{a_1,a_2;i_1,i_3} · ℓ{i_1,i_2;a_1,a_2}, ℓ taken from its head
auto R = ResultExpr(
    Tensor(L"R", bra{L"i_2"}, ket{L"i_3"}),
    ex<Tensor>(L"L", bra{L"a_1", L"a_2"}, ket{L"i_1", L"i_3"}, antisymm) *
        ex<Tensor>(ell.result_as_tensor()));

// one tree per equation, in input order; D and ℓ are inlined, R is a root
[[maybe_unused]] auto sys = binarize(std::vector{D_def, ell, R});
SEQUANT_ASSERT((sys.consumed == container::svector<bool>{true, true, false}));
SEQUANT_ASSERT(sys.roots().size() == 1);

The examples print expressions with << and std::format, which SeQuant/core/io/format.hpp provides and which default to SeQuant’s text serialization format. Once built, an expression tree can be rendered to LaTeX or round-tripped through that format; see I/O for both and for the format specifiers that select between them.