RRust, reversible DSL for Rust

RRust is a reversible subset of Rust inside of Rust, this means you can use it to write a algorithm and then it can run forwards as usually, but it can also run in the reverse direction undoing everything it just did.

Example

use rrust::{rfn, rif};

rfn!(Fib, (x1: &mut i32, x2: &mut i32, n: &mut i32), {
    rif!(
        *n == 0,
        {
            *x1 += 1;
            *x2 += 1;
        },
        {
            *n -= 1;
            Fib::forward(x1, x2, n);
            *x1 += *x2;
            std::mem::swap(x1, x2);
        },
        *x1 == *x2
    );
});

let mut x1 = 0;
let mut x2 = 0;
let mut n = 10;

Fib::forward(&mut x1, &mut x2, &mut n);

assert_eq!(x1, 89);
assert_eq!(x2, 144);
assert_eq!(n, 0);

Fib::backwards(&mut x1, &mut x2, &mut n);

assert_eq!(x1, 0);
assert_eq!(x2, 0);
assert_eq!(n, 10);

Limitations

To keep the code reversible it is necessary to put some limitations on what is possible to do.

Mutating operations

The only operations in this DSL that can cause a mutation are +=, -= and ^= all other mutating operations are disallowed as they cannot be reversed.

Though it is possible to use other operations together with mutating operations for example in a += e. Here a must be a identifier or a dereference of a identifier, but e can be any expression that does not cause a mutation.

Operator	Reverse
`+=`	`-=`
`-=`	`+=`
`^=`	`^=`

Aliasing

Mutable aliasing is not allowed and will cause a runtime error if attempted. This is because a operation with aliasing can cause loss of information and thus making it irreversible. For example a -= a will always cause a to be nullified and thus causing a loss of information.

Function and method calls

At the given time no non-reversible Rust functions or methods are allowed to be called inside of reversible code, this is a something that can be changed since non-mutating functions and methods could be allowed here.

Bibliography

The language as it is now is mostly based upon the Janus formalized in the following paper:

Tetsuo Yokoyama and Robert Glück. 2007. A reversible programming language and its invertible self-interpreter. DOI

Comments

Add a way to make custom reversible functions

At the moment functions that have a inverse counterpart are hardcoded, for example forward gets turned into backwards, if it was possible to implement a trait in some way to generalize it would make it easier to extend RRust.
enhancement

opened by Erk- 0
Add support for rotate
When rotate_left is used the inverse should be rotate_right and the same the other way around.

For example

a.rotate_left(b); // ↓ a.rotate_right(b);

This is likely not enough since rotate is not a mutating operation so a way would be to make our own function along the lines of:

fn rotate_left(i: &mut u32, n: u32) { *i = *i.rotate_left(n); }

And then swap that between left and right in the reverse macro.
enhancement good first issue
opened by Erk- 0
Add a "@" construct to RRust

The language Hermes has a construct s1 @ s2 which expands into s1; s2; I[s1]; where I means the inverse of s1. This is a common pattern in the examples of algorithms in the HERMES paper: https://doi.org/10.1016/j.scico.2021.102746

opened by Erk- 0