interpreter module

exception src.interpreter.BreakException

Bases: Exception

class src.interpreter.Interpreter(ast)

Bases: object

COMPOUND_OPERATORS = {'minus_assign': ('execute_sub_assign', <function additive_safe>, <function Interpreter.<lambda>>), 'over_assign': ('execute_div_assign', <function division_safe>, <function c_truncated_div>), 'plus_assign': ('execute_add_assign', <function additive_safe>, <function Interpreter.<lambda>>), 'times_assign': ('execute_mul_assign', <function multiplicative_safe>, <function Interpreter.<lambda>>)}

class Interpreter

Bases: object

An interpreter for the Ulto programming language.

The Interpreter class is responsible for executing the abstract syntax tree (AST) of an Ulto program. It manages variable assignments, control flow (e.g., loops, conditionals), arithmetic operations, and reversible operations. The interpreter also handles memory management, profiling, and logging of execution details. Additionally, it interfaces with a C library for optimized arithmetic and compound assignment operations through foreign function interface (FFI) using ctypes.

ast

The abstract syntax tree representing the program.

Type:

list

symbol_table

A sorted dictionary used to store variable names and their associated values.

Type:

SortedDict

history

A list to keep track of execution history.

Type:

list

detailed_history

A list to store detailed execution history.

Type:

list

assignments

A counter for the number of assignments performed.

Type:

int

evaluations

A counter for the number of expressions evaluated.

Type:

int

reversals

A counter for the number of reversals executed.

Type:

int

current_step

The current step number in the execution.

Type:

int

memory_manager

An instance of the MemoryManager class for managing memory allocation.

Type:

MemoryManager

eager_vars

A set of variables identified for eager evaluation.

Type:

set

profiling_data

A dictionary to store profiling data for optimizing execution.

Type:

dict

profile_batch_size

The batch size for profiling updates.

Type:

int

profile_counter

A counter to manage profiling updates.

Type:

int

logstack

An instance of the LogStack class to manage reversible operations.

Type:

LogStack

lib

A C library loaded for performing arithmetic and compound assignments.

Type:

ctypes.CDLL

OPERATORS = {'and': ('execute_and', <function comparison_safe>, <function Interpreter.<lambda>>), 'eq': ('execute_eq', <function comparison_safe>, <function Interpreter.<lambda>>), 'gt': ('execute_gt', <function comparison_safe>, <function Interpreter.<lambda>>), 'gte': ('execute_gte', <function comparison_safe>, <function Interpreter.<lambda>>), 'int_div': ('execute_int_div', <function division_safe>, <function c_truncated_div>), 'lt': ('execute_lt', <function comparison_safe>, <function Interpreter.<lambda>>), 'lte': ('execute_lte', <function comparison_safe>, <function Interpreter.<lambda>>), 'minus': ('execute_sub', <function additive_safe>, <function Interpreter.<lambda>>), 'modulo': ('execute_modulo', <function division_safe>, <function c_remainder>), 'neq': ('execute_neq', <function comparison_safe>, <function Interpreter.<lambda>>), 'or': ('execute_or', <function comparison_safe>, <function Interpreter.<lambda>>), 'over': ('execute_div', <function division_safe>, <function c_truncated_div>), 'plus': ('execute_add', <function additive_safe>, <function Interpreter.<lambda>>), 'times': ('execute_mul', <function multiplicative_safe>, <function Interpreter.<lambda>>)}

accumulable_variables(node, body)

Returns the variables whose changes a loop can sum instead of listing.

Successive self-invertible updates to one variable compose: a thousand i += 1 steps undo as a single i -= 1000. So a variable a loop only ever adds to or subtracts from needs one recorded change for the entire run, however many times the loop goes round, even when the rest of the body is doing things that must still be recorded step by step.

A variable is disqualified when summing would lose something that is actually asked for:

• It is also assigned outright somewhere in the loop. An assignment replaces the value rather than shifting it, so the steps either side of it do not compose.

• It is the target of a rev x or revtrace x n anywhere in the program. Both walk a variable back one change at a time, which is exactly the history summing discards.

• The loop body contains any reversal at all, which would be asking to unwind iterations that are no longer recorded separately.

Args: node (tuple): The loop node. body (list): The statements of the loop body.

Returns: set: The variables eligible to be accumulated over the whole loop.

analyse_reversibility(statements)

Marks the statements that can be undone without storing a value.

x += e and x -= e are their own inverse as long as e does not read x, so undoing one is a matter of applying the opposite operation rather than restoring what was there before. That is worth detecting because the replaced value is often far larger than the operand, and because an inverted operation is what a reversible target would run without erasing anything. *= and /= are excluded: integer division truncates, so multiplying back does not reliably land on the original value.

Args: statements (list): The statements to analyse.

apply_operator(op, left, right)

Applies an operator to two operands.

Args: op (str): The operator. left (int): The left operand. right (int): The right operand.

Returns: The result of the operation.

begin_coalescing(node)

Starts accumulating a loop’s eligible variables, if it has any.

An inner loop inside an already accumulating one does not start its own run. Its updates join the outer total, which is both correct and better compression, since the outer analysis already covered the inner body.

Args: node (tuple): The loop node about to run.

Returns: bool: True if accumulation was started by this call.

bind_loop_variable(var_name, value)

Binds a loop variable for one iteration, recording the state it replaced.

The binding is recorded like any other assignment. Without it the loop variable would be the one piece of state a reversed loop could not put back, since nothing else says what it held before the loop began.

In a compressed loop only the first binding is recorded. Restoring a value is absolute, so the state from before the first iteration is the only one reversal needs, and recording the rest would put back the per-iteration cost the compression exists to remove.

Args: var_name (str): The loop variable. value (any): The value for this iteration.

collect_named_reversals(ast)

Collects every variable reversed or traced by name in the program.

These need their history kept one change at a time, so they are never accumulated, wherever in the program the reversal appears relative to the loop that changes them.

Args: ast (list): The abstract syntax tree.

collect_profiling_data(ast)

Collects profiling data from the AST.

Args: ast (list): The abstract syntax tree.

describe_state(var_name, index)

Returns the value a variable held index changes ago, without reversing.

A self-invertible change records the operand rather than the value it replaced, so its earlier state is not stored anywhere and has to be worked out by inverting. That has to be done from the present backwards through every intervening change, which is why this walks rather than reading a single entry.

Args: var_name (str): The variable to trace back. index (int): How many changes back to look.

Returns: The value held at that point, or None if it is out of range.

detect_eager_vars()

Detects eager variables based on the profiling data.

end_coalescing(node)

Records the net change of an accumulated loop, one event per variable.

Only the loop that started the run closes it, so an inner loop finishing does not flush the totals its parent is still gathering.

Args: node (tuple): The loop node that has finished.

error(message)

Raises an error with the given message.

Args: message (str): The error message.

evaluate_expression(expr)

Evaluates an expression.

Args: expr (any): The expression to be evaluated.

Returns: The evaluated result.

execute(capture=False)

Executes the AST.

Parameters:

capture (bool) – When true, the program’s output is collected instead of being written to stdout. A host embedding the interpreter, such as the web front end, needs the text back rather than printed, and under a WSGI server there may be no usable stdout to print to.

Returns: str: The program’s output. Empty unless capture was requested.

execute_assignment(node)

Executes an assignment node.

Args: node (tuple): The assignment node.

execute_block(statements)

Executes a block of statements, remembering where each one began.

The mark taken before a statement runs is what a later bare rev unwinds back to, so reversing a statement reverses everything it did, however many branches or iterations that turned out to involve. Marks are kept per block, so a rev inside a loop body reverses a statement of that body rather than reaching outside it.

Args: statements (list): The statements to execute.

execute_compound_assign(node, op)

Executes a compound assignment (+=, -=, *=, /=) on a variable.

The arithmetic goes to the matching C entry point whenever the operands are small enough for the result to stay inside a 32-bit int, and is done in Python otherwise.

Parameters:

• node (tuple) – The compound assignment node, as (_, var_name, value).

• op (str) – The compound operator, used to select the C entry point.

Raises:

KeyError – If var_name is not found in the symbol table.

execute_for(node)

Executes a for loop node.

Args: node (tuple): The for loop node.

execute_if(node)

Executes an if node.

Args: node (tuple): The if node.

execute_minus_assign(node)

Executes a minus assignment operation (-=) on a variable.

Parameters:

node (tuple) – The assignment node, as (_, var_name, value).

execute_node(node)

Executes a single node in the AST.

Args: node (tuple): The node to be executed.

execute_over_assign(node)

Executes a division assignment operation (/=) on a variable.

Parameters:

node (tuple) – The assignment node, as (_, var_name, value).

execute_plus_assign(node)

Executes a plus assignment operation (+=) on a variable.

Parameters:

node (tuple) – The assignment node, as (_, var_name, value).

execute_print(node)

Executes a print node.

Args: node (tuple): The print node.

execute_reverse(node)

Executes a reverse node.

Args: node (tuple): The reverse node.

execute_revtrace(node)

Executes a revtrace node.

Args: node (tuple): The revtrace node.

execute_times_assign(node)

Executes a times assignment operation (*=) on a variable.

Parameters:

node (tuple) – The assignment node, as (_, var_name, value).

execute_while(node)

Executes a while node.

Args: node (tuple): The while node.

get_memory_usage()

Gets the current memory usage.

Returns: float: The memory usage in megabytes.

locate_operations_library()

Finds the compiled arithmetic library built for the machine in use.

Builds are shipped for more than one architecture, so the right one is chosen from the running machine rather than assumed. The build filed under this machine’s architecture is preferred over the loose copy beside this file, because that loose copy can only ever be right for one architecture. It is still used as a fallback, since an installed package may ship nothing else.

Returns: str: The path of the library to load.

Raises: FileNotFoundError: If no build matches this machine.

log_execution_details(start_time, end_time)

Logs the execution details to a file.

Args: start_time (float): The start time of the execution. end_time (float): The end time of the execution.

mark_accumulable(node, body)

Works out which of a loop’s variables can be recorded once for the run.

Args: node (tuple): The loop node. body (list): The statements of the loop body.

print_computation_cost()

Prints the computation cost of the execution.

profile_assignment(node)

Profiles an assignment node.

Args: node (tuple): The assignment node.

profile_if(node)

Profiles an if node.

Args: node (tuple): The if node.

profile_node(node)

Profiles a single node in the AST. For now, handling conditionals, assignments, reversals and prints.

Args: node (tuple): The node to be profiled.

profile_print(node)

Profiles a print node.

Args: node (tuple): The print node.

profile_reverse(node)

Profiles a reverse node.

Args: node (tuple): The reverse node.

profile_revtrace(node)

Profiles a revtrace node.

Args: node (tuple): The revtrace node.

profile_while(node)

Profiles a while node.

Args: node (tuple): The while node.

prune_logstack()

python_fallback(fallback, left, right)

Applies the Python equivalent of an operation the C path cannot take.

Args: fallback (callable): The Python implementation of the operation. left (any): The left operand. right (any): The right operand.

Returns: The result of the operation.

record_change(var_name, event)

Records a state change on the trace and indexes it by variable.

Args: var_name (str): The variable the change applies to. event (tuple): The event describing how to undo the change.

Returns: int: The position of the event in the trace.

references(expr, var_name)

Reports whether an expression reads a given variable.

Args: expr (any): The expression to inspect. var_name (str): The variable to look for.

Returns: bool: True if the variable may be read by the expression.

reverse_statement()

Reverses the statement most recently completed in the enclosing block.

This is the block form of rev, written without a variable name. Where rev x steps one variable back, this steps one whole statement back: an if reverses whichever branch actually ran, and a loop reverses every iteration it actually performed. Repeating it walks back through the block a statement at a time, which is the backward reading of the program the forward one just executed.

Statements that changed nothing are stepped over rather than counted. A print has no state to restore, and output already written cannot be unwritten, so stopping on one would make rev look like it had done nothing. The same applies to a statement whose changes have each already been reversed by name.

reverse_to(mark)

Unwinds every outstanding change recorded after a mark, newest first.

This is what makes a branch or a loop reverse deterministically. The trace already says which statements ran, so the condition never has to be re-tested to work out which way the if went, and the iteration count never has to be recovered. Both are consequences of what was recorded rather than something re-derived from state the body may have destroyed.

Args: mark (int): The trace position to unwind back to.

Returns: int: The number of changes undone.

run_for(node)

Runs the iterations of a for loop.

Args: node (tuple): The for loop node.

substitute(expr)

Replaces the variables in an expression with what they are bound to now.

Laziness is meant to defer the work of computing a value, not to change which value gets computed. An expression that still names its variables when it is finally evaluated reads whatever they hold at that later moment, so t = p + q followed by p = q would compute t from the new p. Capturing the bindings at the point of assignment keeps a lazy result identical to the eager one.

Nothing is forced here. A binding that is itself unevaluated is carried into the expression as it stands, so the deferral survives. It also ends the self reference in i = i + 1, which used to describe a value in terms of itself: the captured binding is the old one, not the one being created.

Args: expr (any): The expression to capture bindings for.

Returns: The expression with its variables replaced by their current bindings.

undo_event(event)

Undoes a single recorded state change.

Args: event (tuple): The event to undo.

update_profiling_data(expr)

Updates the profiling data with the given expression.

Args: expr (any): The expression to be profiled.

walk_statements(statements)

Yields every statement in a block, including those nested inside it.

Args: statements (list): The statements to walk.

Yields: tuple: Each statement, outermost first.

src.interpreter.additive_safe(left, right)

Reports whether an addition or subtraction can be delegated to C safely.

src.interpreter.c_remainder(left, right)

Returns a remainder taking the sign of the dividend, matching C’s %.

src.interpreter.c_truncated_div(left, right)

Divides two integers truncating toward zero, matching C’s / on ints.

Python’s // floors instead, so the two disagree on negative operands. The C behaviour is the one Ulto programs already observe, so the Python path reproduces it rather than letting results shift with operand magnitude.

src.interpreter.comparison_safe(left, right)

Reports whether a comparison or logical operation can be delegated to C.

Comparisons cannot overflow, so only the operand range matters.

src.interpreter.division_safe(left, right)

Reports whether a division, integer division or modulo can be delegated to C.

A zero divisor is excluded because the library exits the process on it, and INT32_MIN / -1 is excluded because its result does not fit in a C int.

src.interpreter.in_c_range(value)

Reports whether a value can cross the FFI boundary as a C int without loss.

Args: value (any): The value to be checked.

Returns: bool: True if the value is an integer inside the 32-bit signed range.

src.interpreter.multiplicative_safe(left, right)

Reports whether a multiplication can be delegated to C safely.