Source-linked AI summary
The Reversible Intermediate Language L4, its Type System, and its Bidirectional Small-Step Semantics
Torben Ægidius Mogensen
TL;DR
RSSA’s fixed instruction set and lack of types limit its generality and safety. L4 defines a typed reversible intermediate language with bidirectional execution rules that permit direction changes; it allows variable liveness across blocks, with more complicated validity checking.
Problem
RSSA has a fixed instruction set and is untyped, limiting its generality and the safety and specificity of static typing.
Source: §1 · p. 1Method
L4 combines a linear type system with integrated forward and backward small-step execution rules that allow execution direction to switch.
Source: §12 · p. 15Results
L4 allows variable liveness across block boundaries when each variable has one creation and elimination point and read-only uses occur between them.
Source: §12 · p. 15Takeaways & Limitations
L4 is intended as a compiler intermediate form, where its acknowledged difficulty of reading and coding is not a major issue.
Source: §9 · p. 9L4 programs are neither easy to read nor easy to code, a difficulty the authors consider less important for an intermediate form.
Source: §9 · p. 9
Abstract
from arXiv · showhide
L4 is a generic, reversible, linearly-typed, low-level language intended as an intermediate language for compiling reversible programming languages to reversible machines. L4 is intended to replace and generalise RSSA, a reversible SSA form. Inspiration is drawn from other low-level reversible languages such as HSSA. In this paper, we define L4 first informally, and then give a formal type system and a bidirectional small-step semantics for L4: The rules have direction indicators to determine forwards or backwards execution, and the direction can be changed during execution.
1 Introduction
L4 draws on RSSA and HSSA while adding static typing and generalizing conditional entries and exits. Its types describe reversible use, elimination, and creation of values.
1 Introduction
- RSSA’s fixed instruction set and lack of types limit its generality and safety, while HSSA generalizes its instructions and makes variable creation, elimination, and use explicit.L4’s notation is inspired by both languages, with additional typing and generalized conditional entries and exits.Source: §1 · p. 1
2 Types
- L4 uses simple and function types, with simple types including unsigned integers and potentially Booleans, fixed-width numbers, and memories.A program may have multiple memories.Source: §2 · pp. 1–2
- A function type s→t⇀ ↽u specifies values used but not eliminated, values eliminated, and values created, and applies to predefined and program-defined functions.The notation is taken from Agni.Source: §2 · p. 2
- Values are linear in both execution directions: they may be read but not modified between creation and elimination, but not before or after.Read-only parameters are compared to borrowed values in Rust.Source: §2 · p. 2
3 Constants, Variables, and Arguments
Constants and variables carry explicit types, and arguments are lists of typed constants or variables whose type is the list of their element types.
3 Constants, Variables, and Arguments
- Constants and variables are explicitly typed, and an argument list’s type is the list of its elements’ types.Examples include 0:b, 42:u64, x:u64, and c:b.Source: §3 · p. 2
4 Instructions
Instructions use typed arguments to specify which values are used, eliminated, and created. Calls and uncalls are mutually inverse, while constant outputs assert an expected value.
4 Instructions
- A predefined-operation instruction uses arguments of type s, eliminates type t, and creates type u according to the operation’s function type.Its notation orders value flow left to right.Source: §4 · p. 3
- A call executes a defined function and its mutually inverse uncall executes it backwards, exchanging inputs and outputs.The two forms are mutually inverse.Source: §4 · p. 3
- A constant output asserts that the expected output equals the specified constant.Source: §4 · p. 3
5 Blocks, Entries and Exits
Blocks comprise an entry, instructions, and an exit; their generalized entries and exits support conditional, unconditional, and multi-way control flow.
5 Blocks, Entries and Exits
- A block consists of an entry, a possibly empty sequence of instructions, and an exit.Source: §5 · p. 3
- An entry lists labels and arguments; its first argument is a control integer selecting the incoming label, and remaining arguments are passed into the block.A single-label entry commonly uses constant 0 as its control argument, representing an unconditional entry.Source: §5 · p. 3
- An exit lists arguments and labels; its first argument is a control integer selecting the jump destination, and remaining arguments are passed to that label.A single-label exit represents an unconditional jump.Source: §5 · p. 3
- Generalized entries and exits support conditional and unconditional control flow and multi-way jumps, reducing the number of syntactic forms and semantic rules.The multi-way jumps act like jump tables.Source: §5 · p. 3
- Begin denotes a function’s entry point, End its unique exit point, and a jump to ERROR causes a run-time error.Because of reversibility, ERROR labels can also occur in entries.Source: §5 · p. 3
6 Function Definitions
L4 function definitions specify a function’s type, its read-only variables, and the blocks that define its behavior. The Begin and End label arguments determine the eliminated and created types, while block order is immaterial.
6 Function Definitions
- A function definition gives the function a type of the form s→t⇀↽u.The type specifies used, eliminated, and created values or variables.Source: §6 · p. 4
- The definition lists read-only variables used in the function and the blocks that define it.Source: §6 · p. 4
- Begin-label arguments determine the eliminated types, End-label arguments determine the created types, and block order does not matter.Source: §6 · p. 4
7 Inverting Code
L4 inversion exchanges eliminated and created types while preserving read-only uses. It also reverses the structure of instructions, entries, exits, blocks, and function definitions.
7 Inverting Code
- An operation is invertible when it has an inverse with the same used types and its eliminated and created types exchanged.The inverse of < and swap8 is itself; + and - are inverses, and memadd32 has inverse memsub32.Source: §7 · p. 4
- Inverting a call changes it to an uncall, and vice versa; entries and exits also exchange roles.Entry and exit labels Begin and End exchange, while other labels remain unchanged.Source: §7 · p. 4
- A block’s inversion reverses its instruction order and inverts its entry, instructions, and exit.Source: §7 · p. 4
- A function definition is inverted by replacing its name with its inverse and inverting each block.Source: §7 · p. 4
8 Syntax
L4 syntax is presented as a grammar, with additional static rules governing names, labels, and variable use. These rules give variables unique creation and elimination points while permitting read-only use between them.
8 Syntax
- The grammar for L4 is shown in Fig. 1.Source: §8 · p. 4, Figure 1 · p. 5
- Function names are unique, and labels and variables are local to their function definition.Source: §8 · p. 4
- Variables in an instruction or call must occur in disjoint used, eliminated, and created argument lists.Read-only function arguments are neither creation nor elimination contexts and must be preserved unchanged.Source: §8 · p. 6
- Each label occurs in one entry and one exit, except for Begin, End, and ERROR; jumping to ERROR causes a runtime error.Source: §8 · p. 6
- Every variable has a unique creation point and a unique elimination point, with read-only use allowed between them.A variable used in an elimination context cannot be used in another elimination context; variables can be read but not modified between creation and elimination.Source: §8 · p. 6
9 Examples
The examples show L4 implementations of Fibonacci-pair, power, and map functions, including loops, read-only parameters, function calls, and three-way control. The paper notes that L4 is difficult to read and code, but is intended as a compiler intermediate form.
9 Examples
- The Fibonacci-pair example uses a loop instead of the recursive Haskell-style definition.The Haskell-style version recurs from the pair (a, b) to (b, a+b), with n decreasing until zero.Source: §9 · p. 6, Figure 2
- The power-function example illustrates read-only parameters and requires x > 1 for reversibility.When Recur is entered with x <= 1, the assertion that y < 2 is false and fails.Source: §9 · p. 6, Figure 3
- The map example combines function calls with three-way control.Its L4 code includes calls to ff with distinct constants in separate branches.Source: §9 · pp. 6, 8, Figure 4
- The examples are difficult to read and code, a cost the authors consider less important for compiler intermediate use.Source: §9 · p. 9
10 A Type System for L4
L4’s type system checks instructions, blocks, and functions against type and label mappings while tracking how environments change. Its bidirectional rules support checking the same argument relation forwards or backwards.
10 A Type System for L4
- The type system uses mappings for predefined operators, function types, and labels, with each label tied to an in-scope variable environment and argument types.Begin and End label arguments correspond to a function’s parameters and results.Source: §10 · p. 9
- Argument helper rules check variables and constants against types while reversibly removing variables from or adding them to environments.Read-only parameters are excluded from the environment in which removed variables are checked.Source: §10 · p. 9
- Instructions transform one environment into another and may use bindings shared by both, predefined operators, and defined functions.The instruction judgment is reversible between its two environments.Source: §10 · p. 9
- Entry and exit rules assign environments around control-flow boundaries, with exits symmetric to entries and labels in a shared entry or exit using the same environment.Begin and End environments contain only the function’s read-only parameters.Source: §10 · p. 9
- A block is checked by chaining its entry, instruction list, and exit, while a function is correct only when its parameters and results match its type and all blocks satisfy their label bindings.The label mapping must include correct bindings for Begin and End.Source: §10 · p. 9
- The label mapping need not be explicit in the rules; it can be built minimally from Begin using a work-set algorithm or inferred with logic variables and unification.The paper also notes that function mappings can be constructed from declarations and Begin and End blocks.Source: §10 · p. 10
11 A Bidirectional Small-Step Semantics for L4
L4’s small-step semantics represents execution with an environment, program point, direction, function, and call stack. Its rules handle forward and backward execution, including jumps, function calls, and stopping conditions.
11 A Bidirectional Small-Step Semantics for L4
- An execution state tracks live variable values, the current function and program point, execution direction, and a call stack that saves prior execution context.The program point records the most recently entered block, executed and unexecuted instructions, and the block exit.Source: §11 · p. 10
- The mappings used during execution remain fixed, and forward and backward rules coexist so execution can handle uncall.The mappings cover predefined operations, function read-only arguments, and blocks associated with entry and exit labels.Source: §11 · p. 10
- The argument relation can add or remove variables and values from an environment; a constant assertion can fail when a value does not match the constant.Programs are assumed syntactically correct and well typed, and overloading is assumed resolved.Source: §11 · p. 10
- Execution starts at the first function’s Begin state and stops at End, with the reverse run starting at the stop state and continuing back to start.Reaching End forward or Begin backward with an empty call stack stops execution.Source: §11 · pp. 14–15
- A forward jump selects a destination label using its control value, transfers control and parameters to the destination block, and can fail for an out-of-range value or an ERROR label.Backward jumps are symmetric; jumps to Begin or End are handled by other rules.Source: §11 · p. 14
- Calls save the current program point on the stack and begin the called function; uncall reverses execution direction, while return direction depends on whether control returns from call or uncall.The paper reports testing the semantic rules in Prolog with test programs run both forwards and backwards.Source: §11 · p. 15
12 Contributions and Related Work
L4 formalizes a reversible, linear intermediate language with a type system and bidirectional execution semantics. Its cross-block variable liveness permits shorter parameter lists and easier function inlining, while making validity checking more complicated.
12 Contributions and Related Work
- L4 is reversible and linear, and unlike RSSA and HSSA it is strongly typed and has formal type-system and execution-semantics definitions.RSSA is untyped, while HSSA generalized RSSA with a flexible instruction set and an irreversible input-discarding instruction.Source: §12 · p. 15
- L4 permits variable liveness across block boundaries when each variable has one creation and elimination point and read-only uses lie between them.Compared with HSSA’s same-block creation and elimination requirement, this shortens parameter lists and makes function inlining easier, but complicates validity checking.Source: §12 · p. 15
- L4 integrates forward and backward rules and can switch direction during execution; unlike Janus’s approach, it reverses direction at uncall rather than requiring inverted called-function code [5].Its direction-bit control is similar to BobISA and PISA.Source: §12 · p. 15
- The authors implemented a parser, type-checker, and interpreter in Standard ML, plus a partial evaluator and a translator from a subset of L4 to BobISA.Separating primitive types and operations into a module allows L4 to be instantiated to different instruction sets.Source: §12 · p. 16