Reversible Programming is cool (Reversible Part 1)

+ +

+ Okay, a few days ago I learned about Reversible Programming. + I decided to write a little Rust DSL to implement some of the stuff I learned. + In this article I walk through the code for my implementation and talk about some of the stuff you could do with it. +

+ +

Math basis
Idea of the implementation
Foundations
First Combinators
Playing around
Under
Next Up

+ +

Math basis

+ So remember in math class when you learned to take the inverse of a function? + For example, say you have y = 3*x + 6. + You can take the inverse by solving for x. + In this case, the inverse of our function is x = y/3 - 2. + The idea behind reversible programming is that there's a specific way to write your code such that it can automatically compute the inverse. +

This has some wild implications:

Writing a parser automatically gives you a pretty-printer implementation
Database migrations are only half + as scary (writing your up + script automatically gives you your down + script)
Writing operations on an image (ex. Photoshop clone) gives you free undo and redo.

+ These are just a few of the crazy things you could theoretically + do with reversible programming. + But how does it actually work? +

+ +

Idea of the implementation

+ The idea behind this is that we can build small blocks of computation that we manually code the inverse logic for. + Then we use higher-level combinators to compose these small blocks together. + As long as the building-blocks are reversible and the combinators are implemented correctly, we'll have a fully reversible program. +

+ +

Foundations

As any Rust project starts, we'll define some shared behavior that our initial blocks of computation must implement.

trait Rev {
     type Input;
     type Output;
 
     fn forward(&self, i: Self::Input) -> Self::Output;
     fn reverse(&self, o: Self::Output) -> Self::Input;
 }

- -

- As a nice starter, let's write a block that would compute addition. - We can model this with a struct and an impl of the Rev trait. -

struct Addition<A> {
+
+			
+				As a nice starter, let's write a block that would compute addition.
+				We can model this with a struct and an impl of the Rev
+				trait.
+			
+			struct Addition<A> {
     amount: A
 }
 
@@ -82,38 +106,42 @@
     }
 }
 
-        
-            While the generics might look scary, this is just saying "the input and output can be any type that you can add and subtract with."
-            Honestly these are light work compared to what's coming up.
-        
-        Oh, and it will look nicer if we have an easy way to construct an Addition block:
-        fn plus<A>(amount: A) -> Addition<A> {
+			
+				While the generics might look scary, this is just saying "the input and output can be any type that you can add and subtract with."
+				Honestly these are light work compared to what's coming up.
+			
+			Oh, and it will look nicer if we have an easy way to construct an Addition
+				block:
+			fn plus<A>(amount: A) -> Addition<A> {
     Addition { amount }
 }
 
-        So let's see it in action!
-        fn main() {
+			So let's see it in action!
+			fn main() {
     let operation = plus(5);
 
     println!("{}", operation.forward(6));  // prints 11 (6 + 5 = 11)
     println!("{}", operation.reverse(11)); // prints 6 (11 - 5 = 6)
 }
 
-        Obviously nothing special so far. We're just using the inverse of addition, which is subtraction, just like our
-            trait impl said.
-        I've implemented a few more in the source code:
-        
-            neg() negates a number
-            times(x) multiplies a number by x
-            discrete(x: Vec<(A, B)>) creates a reversible block out of a set of discrete inputs and outputs.
-        
-
-        First Combinators
-        
-            The first combinator we'll implement is Pipe.
-            This takes in two Revs and and makes one that applies them in sequential order.
-        
-        struct Pipe<X, Y>(X, Y);
+			Obviously nothing special so far. We're just using the inverse of addition, which is subtraction, just like our
+				trait impl said.
+			I've implemented a few more in the source code:
+			
+				neg()
+				negates a number
+				times(x)
+				multiplies a number by x
+				discrete(x: Vec<(A, B)>)
+				creates a reversible block out of a set of discrete inputs and outputs.
+			
+
+			First Combinators
+			
+				The first combinator we'll implement is Pipe.
+				This takes in two Revs and and makes one that applies them in sequential order.
+			
+			struct Pipe<X, Y>(X, Y);
 impl<X, Y> Rev for Pipe<X, Y>
 where
     X: Iso,
@@ -131,11 +159,12 @@
     }
 }
 
-        
-            Additionally, we'll implement Inverse (not to be confused with .reverse()).
-            This flips the forward and reverse methods.
-        
-        struct Inverse<X>(X);
+			
+				Additionally, we'll implement Inverse
+				(not to be confused with .reverse()).
+				This flips the forward and reverse methods.
+			
+			struct Inverse<X>(X);
 impl<X: Iso> Rev for Inverse<X> {
     type Input = X::Output;
     type Output = X::Input;
@@ -149,11 +178,11 @@
     }
 }
 
-        
-            And finally, it will look nicer if we can use a chaining syntax to apply these combinators.
-            We'll do that using an extension trait:
-        
-        trait RevExt: Rev + Sized {
+			
+				And finally, it will look nicer if we can use a chaining syntax to apply these combinators.
+				We'll do that using an extension trait:
+			
+			trait RevExt: Rev + Sized {
     fn then<N: Rev<Input = Self::Output>>(self, other: N) -> Pipe<Self, N> {
         Pipe(self, other)
     }
@@ -163,14 +192,14 @@
     }
 }
 impl<T: Rev> RevExt for T {}
-        
-        Playing around
-        
-            So, what can we do with these combinators?
-            Quite a lot, actually!
-            Our math example from the beginning is trivial now:
-        
-        fn main() {
+
+			Playing around
+			
+				So, what can we do with these combinators?
+				Quite a lot, actually!
+				Our math example from the beginning is trivial now:
+			
+			fn main() {
     let y = times(3).then(plus(6));
     let x = y.inverse(); // We don't have to know how this gets computed!
 
@@ -178,8 +207,8 @@
     println!("{}", x.forward(30)); // prints 8
 }
 
-        Here's a little celsius to farenheit calculator that only encodes the transformation one way:
-        fn main() {
+			Here's a little celsius to farenheit calculator that only encodes the transformation one way:
+			fn main() {
     // F = (C * 1.8) + 32
     let celsius_to_fahrenheit = times(1.8).then(add(32.0));
 
@@ -192,13 +221,14 @@
     println!("{}", fahrenheit_to_celsius.forward(32.0));  // prints 0.0
 }
 
-        Under
-        
-            under is a higher order combinator, which means it's implemented in terms of other combinators.
-            Under basically says "do a thing, do another thing, then undo the first thing.
-            With this foundation built up, we can implement it quite easily:
-        
-    fn under<Op, Val>(op: Op, val: Val) -> impl Rev<
+			Under
+			
+				under
+				is a higher order combinator, which means it's implemented in terms of other combinators.
+				Under basically says "do a thing, do another thing, then undo the first thing.
+				With this foundation built up, we can implement it quite easily:
+			
+			fn under<Op, Val>(op: Op, val: Val) -> impl Rev<
     Input = Op::Input,
     Output = Op::Input
 >
@@ -209,11 +239,11 @@
     op.clone().then(val).then(op.inverse())
 }
 
-        
-            We can use this to encode "setup operations."
-            For example, this code takes in a number string, and returns a number string, but does an operation on integers in-between.
-        
-        fn main() {
+			
+				We can use this to encode "setup operations."
+				For example, this code takes in a number string, and returns a number string, but does an operation on integers in-between.
+			
+			fn main() {
     let num_as_str = discrete(vec![
         ("one", 1),
         ("two", 2),
@@ -228,15 +258,14 @@
     println!("{}", operation.forward("three")); // prints "six"
     println!("{}", operation.reverse("five")); // prints "two"
 }
-        
-        Next Up
-        
-            Well, that's all I've got for today.
-            Next time, we'll look at data-structures, like sum and product types, and maybe some other stuff.
-            The source code for this project so far is available here.
-            Stay tuned!
-        
-

Math basis

Idea of the implementation

Foundations

Table of Contents

Math basis

Idea of the implementation

Foundations

First Combinators

First Combinators

Playing around

Playing around

Under

Under

Next Up

Next Up