Module v0

Version 0 (unstable).

Warning: This module is still under development and is expected to change. It is included in the library to allow for early experimentation, and for the core and model to converge incrementally.

This module defines representations of the hugr IR as plain data, designed to be as independent of implementation details as feasible. It can be used by the core compiler, alternative implementations or tooling that does not need the power/complexity of the full compiler. We provide the following in-memory representations:

• Table: Efficient intermediate data structure to facilitate conversions.
• AST: Abstract syntax tree that uses direct references rather than table indices.

The table and AST format are interconvertible and can be serialised to a binary and text format, respectively:

• Binary: Binary serialisation format optimised for performance and size.
• Text: Human readable s-expression based text format.

Logical Format

The hugr IR is a hierarchical graph data structure. Nodes represent both instructions that manipulate runtime values and symbols which represent named language objects. Instructions have input and output ports and runtime values flow between ports when they are connected by a link.

Nodes are organised into regions and do not have any explicit ordering between them; any schedule that respects the data dependencies between nodes is valid. Regions come in three different kinds. Module regions form the top level of a module and can only contain symbols. Dataflow regions describe how data flows from the region’s source ports to the region’s target ports. Controlflow regions are control flow graphs containing dataflow blocks, with control flow originating from the region’s source ports and ending in the region’s target ports.

Terms form a meta language that is used to describe types, parameters and metadata that are known statically. To allow types to be parameterized by values, types and values are treated uniformly as terms, enabling a restricted form of dependent typing. Terms are extensible declaratively via constructors. Constraints can be used to express more complex validation rules.

Remaining Mismatch with hugr-core

This data model was designed to encode as much of hugr-core as possible while also filling in conceptual gaps and providing a forward-compatible foundation for future development. However, there are still some mismatches with hugr-core that are not addressed by conversions in import/export:

• Some static types can not yet be represented in hugr-core although they should be.
• The model does not have types with a copy bound as hugr-core does, and instead uses a more general form of type constraints (#1556). Similarly, the model does not have bounded naturals. We perform a conversion for compatibility where possible, but this does not fully cover all potential cases of bounds.
• hugr-model allows to declare term constructors that serve as blueprints for constructing runtime values. This allows constants to have potentially multiple representations, which can be essential in case of very large constants that require efficient encodings. hugr-core is more restricted, requiring a canonical representation for constant values.
• hugr-model has support for passing closed regions as static parameters to operations, which allows for higher-order operations that require their function arguments to be statically known. We currently do not yet support converting this to hugr-core.
• In a model module, ports are connected when they share the same link. This differs from the type of port connectivity in the graph data structure used by hugr-core. However, hugr-core restricts connectivity so that in any group of connected ports there is at most one output port (for dataflow) or at most one input port (for control flow). In these cases, there is no mismatch.
• hugr-core only allows to define type aliases, but not aliases for other terms.
• hugr-model has no concept of order edges, encoding a strong preference that ordering requirements be encoded within the dataflow paradigm.
• Both hugr-model and hugr-core support metadata, but they use different encodings. hugr-core encodes metadata as JSON objects, while hugr-model uses terms. Using terms has the advantage that metadata can be validated with the same type checking mechanism as the rest of the model (#1553).
• hugr-model have a root region that corresponds to a root Module in hugr-core. hugr-core however can have nodes with different operations as their root (#1554).

Re-exports

pub use bumpalo;

Modules

ast

Abstract syntax tree representation of hugr modules.

binary

Binary format based on capnproto.

scope

Utilities for working with scoped symbols, variables and links.

table

Table representation of hugr modules.

Structs

LinkName

The name of a link.

SymbolName

The name of a symbol.

VarName

The name of a variable.

Enums

Literal

A static literal value.

RegionKind

The kind of a region.

ScopeClosure

Type to indicate whether scopes are open or closed.

Visibility

Describes how a function or symbol should be acted upon by a linker

Constants

COMPAT_CONST_JSON

Constructor for JSON encoded constants.

COMPAT_META_JSON

Constructor for JSON encoded metadata.

CORE_ADT

Runtime algebraic data types.

CORE_BYTES_TYPE

Type of bytes literals.

CORE_CALL

Operation to call a statically known function.

CORE_CALL_INDIRECT

Operation to call a functiion known at runtime.

CORE_CONST

The type for runtime constants.

CORE_CONSTRAINT

The type of constraints.

CORE_CONST_ADT

Constants for runtime algebraic data types.

CORE_CTRL

Type of control flow regions.

CORE_ENTRYPOINT

Metadata to tag a node or region as the entrypoint of a module.

CORE_FLOAT_TYPE

Type of float literals.

CORE_FN

Core function types.

CORE_LIST_TYPE

The type for lists of static data.

CORE_LOAD_CONST

Operation to load a constant value.

CORE_MAKE_ADT

Operation to create a value of an algebraic data type.

CORE_META

The type of metadata.

CORE_META_DESCRIPTION

Constructor for documentation metadata.

CORE_NAT_TYPE

Type of natural number literals.

CORE_NON_LINEAR

The constraint for non-linear runtime data.

CORE_STATIC

The type of static types.

CORE_STR_TYPE

Type of string literals.

CORE_TITLE

Metadata constructor for symbol titles.

CORE_TUPLE_TYPE

The type for tuples of static data.

CORE_TYPE

The type of runtime types.

ORDER_HINT_INPUT_KEY

Metadata constructor for order hint keys on input nodes.

ORDER_HINT_KEY

Metadata constructor for order hint keys.

ORDER_HINT_ORDER

Metadata constructor for order hints.

ORDER_HINT_OUTPUT_KEY

Metadata constructor for order hint keys on output nodes.