Skip to content

Base

BaseInterpreter dataclass

BaseInterpreter(
    dialects: DialectGroup,
    *,
    fuel: int | None = None,
    debug: bool = False,
    max_depth: int = 128,
    max_python_recursion_depth: int = 8192
)

Bases: ABC, Generic[FrameType, ValueType]

A base class for interpreters.

This class defines the basic structure of an interpreter. It is designed to be subclassed to provide the actual implementation of the interpreter.

Required Overrides

When subclassing, if the subclass does not contain ABC, the subclass must define the following attributes:

  • keys: a list of strings that defines the order of dialects to select from.
  • void: the value to return when the interpreter evaluates nothing.

Frame class-attribute

Frame: type[FrameABC] = field(init=False)

The type of the frame to use for this interpreter.

debug class-attribute instance-attribute

debug: bool = field(default=False, kw_only=True)

Whether to enable debug mode.

dialects instance-attribute

dialects: DialectGroup

The dialects to interpret.

fuel class-attribute instance-attribute

fuel: int | None = field(default=None, kw_only=True)

The fuel limit for the interpreter.

keys class-attribute

keys: list[str]

The name of the interpreter to select from dialects by order.

max_depth class-attribute instance-attribute

max_depth: int = field(default=128, kw_only=True)

The maximum depth of the interpreter stack.

max_python_recursion_depth class-attribute instance-attribute

max_python_recursion_depth: int = field(
    default=8192, kw_only=True
)

The maximum recursion depth of the Python interpreter.

registry class-attribute instance-attribute

registry: InterpreterRegistry = field(
    init=False, compare=False
)

The interpreter registry.

state class-attribute instance-attribute

state: InterpreterState[FrameType] = field(
    init=False, compare=False
)

The interpreter state.

symbol_table class-attribute instance-attribute

symbol_table: dict[str, Statement] = field(
    init=False, compare=False
)

The symbol table.

void class-attribute instance-attribute

void: ValueType = field(init=False)

What to return when the interpreter evaluates nothing.

build_signature

build_signature(
    frame: FrameType, stmt: Statement
) -> Signature

build signature for querying the statement implementation.

Source code in src/kirin/interp/base.py
430
431
432
def build_signature(self, frame: FrameType, stmt: Statement) -> "Signature":
    """build signature for querying the statement implementation."""
    return Signature(stmt.__class__, tuple(arg.type for arg in stmt.args))

eval_recursion_limit

eval_recursion_limit(
    frame: FrameType,
) -> tuple[FrameType, ValueType]

Return the value of recursion exception, e.g in concrete interpreter, it will raise an exception if the limit is reached; in type inference, it will return a special value.

Source code in src/kirin/interp/base.py
423
424
425
426
427
428
def eval_recursion_limit(self, frame: FrameType) -> tuple[FrameType, ValueType]:
    """Return the value of recursion exception, e.g in concrete
    interpreter, it will raise an exception if the limit is reached;
    in type inference, it will return a special value.
    """
    raise InterpreterError("maximum recursion depth exceeded")

eval_stmt

eval_stmt(
    frame: FrameType, stmt: Statement
) -> StatementResult[ValueType]

Run a statement within the current frame. This is the entry point of running a statement. It will look up the statement implementation in the dialect registry, or optionally call a fallback implementation.

Parameters:

Name Type Description Default
frame FrameType

the current frame

required
stmt Statement

the statement to run

required

Returns:

Name Type Description
StatementResult StatementResult[ValueType]

the result of running the statement

Note

Overload this method for the following reasons: - to change the source tracking information - to take control of how to run a statement - to change the implementation lookup behavior that cannot acheive by overloading lookup_registry

Example
  • implement an interpreter that only handles MyStmt:
        class MyInterpreter(BaseInterpreter):
            ...
            def eval_stmt(self, frame: FrameType, stmt: Statement) -> StatementResult[ValueType]:
                if isinstance(stmt, MyStmt):
                    return self.run_my_stmt(frame, stmt)
                else:
                    return ()
    
Source code in src/kirin/interp/base.py
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
def eval_stmt(
    self, frame: FrameType, stmt: Statement
) -> StatementResult[ValueType]:
    """Run a statement within the current frame. This is the entry
    point of running a statement. It will look up the statement implementation
    in the dialect registry, or optionally call a fallback implementation.

    Args:
        frame: the current frame
        stmt: the statement to run

    Returns:
        StatementResult: the result of running the statement

    Note:
        Overload this method for the following reasons:
        - to change the source tracking information
        - to take control of how to run a statement
        - to change the implementation lookup behavior that cannot acheive
            by overloading [`lookup_registry`][kirin.interp.base.BaseInterpreter.lookup_registry]

    Example:
        * implement an interpreter that only handles MyStmt:
        ```python
            class MyInterpreter(BaseInterpreter):
                ...
                def eval_stmt(self, frame: FrameType, stmt: Statement) -> StatementResult[ValueType]:
                    if isinstance(stmt, MyStmt):
                        return self.run_my_stmt(frame, stmt)
                    else:
                        return ()
        ```

    """
    # TODO: update tracking information
    method = self.lookup_registry(frame, stmt)
    if method is not None:
        results = method(self, frame, stmt)
        if self.debug and not isinstance(results, (tuple, SpecialValue)):
            raise InterpreterError(
                f"method must return tuple or SpecialResult, got {results}"
            )
        return results
    elif stmt.dialect not in self.dialects:
        # NOTE: we should terminate the interpreter because this is a
        # deveoper error, not a user error.
        name = stmt.dialect.name if stmt.dialect else "None"
        raise ValueError(f"dialect {name} is not supported by {self.dialects}")

    return self.eval_stmt_fallback(frame, stmt)

eval_stmt_fallback

eval_stmt_fallback(
    frame: FrameType, stmt: Statement
) -> StatementResult[ValueType]

The fallback implementation of statements.

This is called when no implementation is found for the statement.

Parameters:

Name Type Description Default
frame FrameType

the current frame

required
stmt Statement

the statement to run

required

Returns:

Name Type Description
StatementResult StatementResult[ValueType]

the result of running the statement

Note

Overload this method to provide a fallback implementation for statements.

Source code in src/kirin/interp/base.py
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
def eval_stmt_fallback(
    self, frame: FrameType, stmt: Statement
) -> StatementResult[ValueType]:
    """The fallback implementation of statements.

    This is called when no implementation is found for the statement.

    Args:
        frame: the current frame
        stmt: the statement to run

    Returns:
        StatementResult: the result of running the statement

    Note:
        Overload this method to provide a fallback implementation for statements.
    """
    # NOTE: not using f-string here because 3.10 and 3.11 have
    #  parser bug that doesn't allow f-string in raise statement
    raise InterpreterError(
        "no implementation for stmt "
        + stmt.print_str(end="")
        + " from "
        + str(type(self))
    )

initialize

initialize() -> Self

Initialize the interpreter global states. This method is called right upon calling run to initialize the interpreter global states.

Default Implementation

This method provides default behavior but may be overridden by subclasses to customize or extend functionality.

Source code in src/kirin/interp/base.py
 99
100
101
102
103
104
105
106
107
108
109
110
def initialize(self) -> Self:
    """Initialize the interpreter global states. This method is called right upon
    calling [`run`][kirin.interp.base.BaseInterpreter.run] to initialize the
    interpreter global states.

    !!! note "Default Implementation"
        This method provides default behavior but may be overridden by subclasses
        to customize or extend functionality.
    """
    self.symbol_table: dict[str, Statement] = {}
    self.state: InterpreterState[FrameType] = InterpreterState()
    return self

initialize_frame abstractmethod

initialize_frame(
    code: Statement, *, has_parent_access: bool = False
) -> FrameType

Create a new frame for the given method.

Source code in src/kirin/interp/base.py
112
113
114
115
116
117
@abstractmethod
def initialize_frame(
    self, code: Statement, *, has_parent_access: bool = False
) -> FrameType:
    """Create a new frame for the given method."""
    ...

lookup_registry

lookup_registry(
    frame: FrameType, stmt: Statement
) -> Optional[StatementImpl[Self, FrameType]]

Lookup the statement implementation in the registry.

Parameters:

Name Type Description Default
frame FrameType

the current frame

required
stmt Statement

the statement to run

required

Returns:

Type Description
Optional[StatementImpl[Self, FrameType]]

Optional[StatementImpl]: the statement implementation if found, None otherwise.

Source code in src/kirin/interp/base.py
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
def lookup_registry(
    self, frame: FrameType, stmt: Statement
) -> Optional["StatementImpl[Self, FrameType]"]:
    """Lookup the statement implementation in the registry.

    Args:
        frame: the current frame
        stmt: the statement to run

    Returns:
        Optional[StatementImpl]: the statement implementation if found, None otherwise.
    """
    sig = self.build_signature(frame, stmt)
    if sig in self.registry.statements:
        return self.registry.statements[sig]
    elif (class_sig := Signature(stmt.__class__)) in self.registry.statements:
        return self.registry.statements[class_sig]
    return

new_frame

new_frame(
    code: Statement, *, has_parent_access: bool = False
) -> Generator[FrameType, Any, None]

Create a new frame for the given method and push it to the state.

Parameters:

Name Type Description Default
code Statement

the statement to run.

required

Other Parameters:

Name Type Description
has_parent_access bool

whether this frame has access to the parent frame entries. Defaults to False.

This is a context manager that creates a new frame, push and pop the frame automatically.

Source code in src/kirin/interp/base.py
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
@contextmanager
def new_frame(
    self, code: Statement, *, has_parent_access: bool = False
) -> Generator[FrameType, Any, None]:
    """Create a new frame for the given method and push it to the state.

    Args:
        code (Statement): the statement to run.

    Keyword Args:
        has_parent_access (bool): whether this frame has access to the
            parent frame entries. Defaults to False.

    This is a context manager that creates a new frame, push and pop
    the frame automatically.
    """
    frame = self.initialize_frame(code, has_parent_access=has_parent_access)
    self.state.push_frame(frame)
    try:
        yield frame
    finally:
        self.state.pop_frame()

permute_values staticmethod

permute_values(
    arg_names: Sequence[str],
    values: tuple[ValueType, ...],
    kwarg_names: tuple[str, ...],
) -> tuple[ValueType, ...]

Permute the arguments according to the method signature and the given keyword arguments, where the keyword argument names refer to the last n arguments in the values tuple.

Parameters:

Name Type Description Default
arg_names Sequence[str]

the argument names

required
values tuple[ValueType, ...]

the values tuple (should not contain method itself)

required
kwarg_names tuple[str, ...]

the keyword argument names

required
Source code in src/kirin/interp/base.py
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
@staticmethod
def permute_values(
    arg_names: Sequence[str],
    values: tuple[ValueType, ...],
    kwarg_names: tuple[str, ...],
) -> tuple[ValueType, ...]:
    """Permute the arguments according to the method signature and
    the given keyword arguments, where the keyword argument names
    refer to the last n arguments in the values tuple.

    Args:
        arg_names: the argument names
        values: the values tuple (should not contain method itself)
        kwarg_names: the keyword argument names
    """
    n_total = len(values)
    if kwarg_names:
        kwargs = dict(zip(kwarg_names, values[n_total - len(kwarg_names) :]))
    else:
        kwargs = None

    positionals = values[: n_total - len(kwarg_names)]
    args = BaseInterpreter.get_args(
        arg_names[len(positionals) + 1 :], positionals, kwargs
    )
    return args

run

run(
    mt: Method,
    args: tuple[ValueType, ...],
    kwargs: dict[str, ValueType] | None = None,
) -> ValueType

Run a method. This is the main entry point of the interpreter.

Parameters:

Name Type Description Default
mt Method

the method to run.

required
args tuple[ValueType]

the arguments to the method, does not include self.

required
kwargs dict[str, ValueType]

the keyword arguments to the method.

None

Returns:

Type Description
ValueType

Result[ValueType]: the result of the method.

Source code in src/kirin/interp/base.py
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
def run(
    self,
    mt: Method,
    args: tuple[ValueType, ...],
    kwargs: dict[str, ValueType] | None = None,
) -> ValueType:
    """Run a method. This is the main entry point of the interpreter.

    Args:
        mt (Method): the method to run.
        args (tuple[ValueType]): the arguments to the method, does not include self.
        kwargs (dict[str, ValueType], optional): the keyword arguments to the method.

    Returns:
        Result[ValueType]: the result of the method.
    """
    if self._eval_lock:
        raise InterpreterError(
            "recursive eval is not allowed, use run_method instead"
        )

    self._eval_lock = True
    self.initialize()
    current_recursion_limit = sys.getrecursionlimit()
    sys.setrecursionlimit(self.max_python_recursion_depth)
    args = self.get_args(mt.arg_names[len(args) + 1 :], args, kwargs)
    try:
        _, results = self.run_method(mt, args)
    except Exception as e:
        # NOTE: insert the interpreter state into the exception
        # so we can print the stack trace
        setattr(e, KIRIN_INTERP_STATE, self.state)
        raise e
    finally:
        self._eval_lock = False
        sys.setrecursionlimit(current_recursion_limit)
    return results

run_block

run_block(
    frame: FrameType, block: Block
) -> SpecialValue[ValueType]

Run a block within the current frame.

Parameters:

Name Type Description Default
frame FrameType

the current frame.

required
block Block

the block to run.

required

Returns:

Name Type Description
SpecialValue SpecialValue[ValueType]

the result of running the block terminator.

Source code in src/kirin/interp/base.py
255
256
257
258
259
260
261
262
263
264
265
266
@deprecated("use run_succ instead")
def run_block(self, frame: FrameType, block: Block) -> SpecialValue[ValueType]:
    """Run a block within the current frame.

    Args:
        frame: the current frame.
        block: the block to run.

    Returns:
        SpecialValue: the result of running the block terminator.
    """
    ...

run_callable

run_callable(
    code: Statement, args: tuple[ValueType, ...]
) -> tuple[FrameType, ValueType]

Run a callable statement.

Parameters:

Name Type Description Default
code Statement

the statement to run.

required
args tuple[ValueType, ...]

the arguments to the statement, includes self if the corresponding callable region contains a self argument.

required

Returns:

Name Type Description
ValueType tuple[FrameType, ValueType]

the result of the statement.

Source code in src/kirin/interp/base.py
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
def run_callable(
    self, code: Statement, args: tuple[ValueType, ...]
) -> tuple[FrameType, ValueType]:
    """Run a callable statement.

    Args:
        code (Statement): the statement to run.
        args (tuple[ValueType, ...]): the arguments to the statement,
            includes self if the corresponding callable region contains a self argument.

    Returns:
        ValueType: the result of the statement.
    """
    if self.state.depth >= self.max_depth:
        return self.eval_recursion_limit(self.state.current_frame)

    interface = code.get_trait(traits.CallableStmtInterface)
    if interface is None:
        raise InterpreterError(f"statement {code.name} is not callable")

    frame = self.initialize_frame(code)
    self.state.push_frame(frame)
    body = interface.get_callable_region(code)
    if not body.blocks:
        return self.state.pop_frame(), self.void
    results = self.run_callable_region(frame, code, body, args)
    return self.state.pop_frame(), results

run_callable_region

run_callable_region(
    frame: FrameType,
    code: Statement,
    region: Region,
    args: tuple[ValueType, ...],
) -> ValueType

A hook defines how to run the callable region given the interpreter context. Frame should be pushed before calling this method and popped after calling this method.

A callable region is a region that can be called as a function. Unlike a general region (or the MLIR convention), it always return a value to be compatible with the Python convention.

Source code in src/kirin/interp/base.py
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
def run_callable_region(
    self,
    frame: FrameType,
    code: Statement,
    region: Region,
    args: tuple[ValueType, ...],
) -> ValueType:
    """A hook defines how to run the callable region given
    the interpreter context. Frame should be pushed before calling
    this method and popped after calling this method.

    A callable region is a region that can be called as a function.
    Unlike a general region (or the MLIR convention), it always return a value
    to be compatible with the Python convention.
    """
    results = self.run_ssacfg_region(frame, region, args)
    if isinstance(results, ReturnValue):
        return results.value
    elif not results:  # empty result or None
        return self.void
    raise InterpreterError(
        f"callable region {code.name} does not return `ReturnValue`, got {results}"
    )

run_method abstractmethod

run_method(
    method: Method, args: tuple[ValueType, ...]
) -> tuple[FrameType, ValueType]

How to run a method.

This is defined by subclasses to describe what's the corresponding value of a method during the interpretation. Usually, this method just calls run_callable.

Parameters:

Name Type Description Default
method Method

the method to run.

required
args tuple[ValueType, ...]

the arguments to the method, does not include self.

required

Returns:

Name Type Description
ValueType tuple[FrameType, ValueType]

the result of the method.

Source code in src/kirin/interp/base.py
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
@abstractmethod
def run_method(
    self, method: Method, args: tuple[ValueType, ...]
) -> tuple[FrameType, ValueType]:
    """How to run a method.

    This is defined by subclasses to describe what's the corresponding
    value of a method during the interpretation. Usually, this method
    just calls [`run_callable`][kirin.interp.base.BaseInterpreter.run_callable].

    Args:
        method (Method): the method to run.
        args (tuple[ValueType, ...]): the arguments to the method, does not include self.

    Returns:
        ValueType: the result of the method.
    """
    ...

run_ssacfg_region abstractmethod

run_ssacfg_region(
    frame: FrameType,
    region: Region,
    args: tuple[ValueType, ...],
) -> tuple[ValueType, ...] | None | ReturnValue[ValueType]

This implements how to run a region with MLIR SSA CFG convention.

Parameters:

Name Type Description Default
frame FrameType

the current frame.

required
region Region

the region to run.

required
args tuple[ValueType, ...]

the arguments to the region.

required

Returns:

Type Description
tuple[ValueType, ...] | None | ReturnValue[ValueType]

tuple[ValueType, ...] | SpecialValue[ValueType]: the result of running the region.

when region returns tuple[ValueType, ...], it means the region terminates normally with YieldValue. When region returns ReturnValue, it means the region terminates and needs to pop the frame. Region cannot return Successor because reference to external region is not allowed.

Source code in src/kirin/interp/base.py
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
@abstractmethod
def run_ssacfg_region(
    self, frame: FrameType, region: Region, args: tuple[ValueType, ...]
) -> tuple[ValueType, ...] | None | ReturnValue[ValueType]:
    """This implements how to run a region with MLIR SSA CFG convention.

    Args:
        frame: the current frame.
        region: the region to run.
        args: the arguments to the region.

    Returns:
        tuple[ValueType, ...] | SpecialValue[ValueType]: the result of running the region.

    when region returns `tuple[ValueType, ...]`, it means the region terminates normally
    with `YieldValue`. When region returns `ReturnValue`, it means the region terminates
    and needs to pop the frame. Region cannot return `Successor` because reference to
    external region is not allowed.
    """
    ...

run_stmt

run_stmt(
    stmt: Statement, args: tuple[ValueType, ...]
) -> StatementResult[ValueType]

execute a statement with arguments in a new frame.

Parameters:

Name Type Description Default
stmt Statement

the statement to run.

required
args tuple[ValueType, ...]

the arguments to the statement.

required

Returns:

Type Description
StatementResult[ValueType]

StatementResult[ValueType]: the result of the statement.

Source code in src/kirin/interp/base.py
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
def run_stmt(
    self, stmt: Statement, args: tuple[ValueType, ...]
) -> StatementResult[ValueType]:
    """execute a statement with arguments in a new frame.

    Args:
        stmt (Statement): the statement to run.
        args (tuple[ValueType, ...]): the arguments to the statement.

    Returns:
        StatementResult[ValueType]: the result of the statement.
    """
    with self.new_frame(stmt) as frame:
        frame.set_values(stmt.args, args)
        results = self.eval_stmt(frame, stmt)
        return results

run_succ

run_succ(
    frame: FrameType, succ: Successor
) -> SpecialValue[ValueType]

Run a successor within the current frame. Args: frame: the current frame. succ: the successor to run.

Returns:

Name Type Description
SpecialValue SpecialValue[ValueType]

the result of running the successor.

Source code in src/kirin/interp/base.py
268
269
270
271
272
273
274
275
276
277
def run_succ(self, frame: FrameType, succ: Successor) -> SpecialValue[ValueType]:
    """Run a successor within the current frame.
    Args:
        frame: the current frame.
        succ: the successor to run.

    Returns:
        SpecialValue: the result of running the successor.
    """
    ...

InterpreterMeta

Bases: ABCMeta

A metaclass for interpreters.