diff options
Diffstat (limited to 'reversible.html')
| -rw-r--r-- | reversible.html | 242 |
1 files changed, 242 insertions, 0 deletions
diff --git a/reversible.html b/reversible.html new file mode 100644 index 0000000..378045f --- /dev/null +++ b/reversible.html @@ -0,0 +1,242 @@ +<!DOCTYPE html> +<html> + +<head> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + + <title>Reversible Programming Blew my Mind (Reversible Part 1)</title> + <meta property="article:published_time" content="2026-07-05"> + <link rel="stylesheet" href="prose.css"> + <script src="./article.js"></script> +</head> + +<body> + <article> + <header></header> + + <p> + Okay, a few days ago I learned about <a href="https://en.wikipedia.org/wiki/Reversible_programming_language">Reversible Programming</a>. + 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. + </p> + + <div id="toc"></div> + + <h2 id="math">Math basis</h2> + <p>So remember in math class when you learned to take the inverse of a function?</p> + <p>For example, say you have <code>y = 3*x + 6</code>.</p> + <p>You can take the inverse by solving for x. In this case, the inverse of our function is <code>x = y/3 - 2</code>.</p> + <p>The idea behind reversible programming is that there's a specific way to write your code such that it can <strong>automatically compute the inverse</strong>.</p> + <p>This has some wild implications:</p> + <ul> + <li>Writing a parser automatically gives you a pretty-printer implementation</li> + <li>Database migrations are only <em>half</em> as scary (writing your <code>up</code> script automatically gives you your <code>down</code> script)</li> + <li>Writing operations on an image (ex. Photoshop clone) gives you free undo and redo.</li> + </ul> + <p> + These are just a few of the crazy things you could <em>theoretically</em> do with Reversible Programming. + But how does it actually work? + </p> + + <h2 id="idea">Idea of the implementation</h2> + <p> + 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. + </p> + + <h2 id="foundations">Foundations</h2> + <p>As any Rust project starts, we'll define some shared behavior that our initial blocks of computation must implement.</p> + <pre><code><kw>trait</kw> <ty>Rev</ty> { + <kw>type</kw> <ty>Input</ty>; + <kw>type</kw> <ty>Output</ty>; + + <kw>fn</kw> <fn>forward</fn>(&<kw>self</kw>, <id>i</id>: <kw>Self</kw>::<ty>Input</ty>) -> <kw>Self</kw>::<ty>Output</ty>; + <kw>fn</kw> <fn>reverse</fn>(&<kw>self</kw>, <id>o</id>: <kw>Self</kw>::<ty>Output</ty>) -> <kw>Self</kw>::<ty>Input</ty>; +}</code></pre> + + <p> + 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 <code>Rev</code> trait. + </p> + <pre><code><kw>struct</kw> <ty>Addition</ty><<ty>A</ty>> { + <prop>amount</prop>: <ty>A</ty> +} + +<kw>impl</kw><<ty>A</ty>> <ty>Rev</ty> <kw>for</kw> <ty>Addition</ty><<ty>A</ty>> +<kw>where</kw> + <ty>A</ty>: <mod>std</mod>::<mod>ops</mod>::<ty>Add</ty><<ty>Output</ty> = <ty>A</ty>> + + <mod>std</mod>::<mod>ops</mod>::<ty>Sub</ty><<ty>Output</ty> = <ty>A</ty>> + + <ty>Copy</ty> +{ + <kw>type</kw> <ty>Input</ty> = <ty>A</ty>; + <kw>type</kw> <ty>Output</ty> = <ty>A</ty>; + + <kw>fn</kw> <fn>forward</fn>(&self, <id>a</id>: <ty>A</ty>) -> <ty>A</ty> { + <id>a</id> + <id>self</id>.<prop>amount</prop> + } + + <kw>fn</kw> <fn>reverse</fn>(&self, <id>b</id>: <ty>A</ty>) -> <ty>A</ty> { + <id>b</id> - <id>self</id>.<prop>amount</prop> + } +}</code></pre> + + <p> + 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. + </p> + <p>Oh, and it will look nicer if we have an easy way to construct an <code>Addition</code> block:</p> + <pre><code><kw>fn</kw> <fn>plus</fn><<ty>A</ty>>(<id>amount</id>: <ty>A</ty>) -> <ty>Addition</ty><<ty>A</ty>> { + <ty>Addition</ty> { <prop>amount</prop> } +}</code></pre> + + <p>So let's see it in action!</p> + <pre><code class="language-rust"><kw>fn</kw> <fn>main</fn>() { + <kw>let</kw> <id>operation</id> = <fn>plus</fn>(<num>5</num>); + + <mac>println!</mac>(<str>"{}"</str>, <id>operation</id>.<fn>forward</fn>(<num>6</num>)); <com>// prints 11 (6 + 5 = 11)</com> + <mac>println!</mac>(<str>"{}"</str>, <id>operation</id>.<fn>reverse</fn>(<num>11</num>)); <com>// prints 6 (11 - 5 = 6)</com> +}</code></pre> + + <p>Obviously nothing special so far. We're just using the inverse of addition, which is subtraction, just like our + trait impl said.</p> + <p>I've implemented a few more in the <a href="./reversible.rs#:~:text=%2F%2F%20more%20blocks">source code</a>:</p> + <ul> + <li><code>neg()</code> negates a number</li> + <li><code>times(x)</code> multiplies a number by x</li> + <li><code>discrete(x: Vec<(A, B)>)</code> creates a reversible block out of a set of discrete inputs and outputs.</li> + </ul> + + <h2 id="first">First Combinators</h2> + <p> + The first combinator we'll implement is <code>Pipe</code>. + This takes in two <code>Rev</code>s and and makes one that applies them in sequential order. + </p> + <pre><code><kw>struct</kw> <ty>Pipe</ty><<ty>X</ty>, <ty>Y</ty>>(<ty>X</ty>, <ty>Y</ty>); +<kw>impl</kw><<ty>X</ty>, <ty>Y</ty>> <ty>Rev</ty> <kw>for</kw> <ty>Pipe</ty><<ty>X</ty>, <ty>Y</ty>> +<kw>where</kw> + <ty>X</ty>: <ty>Iso</ty>, + <ty>Y</ty>: <ty>Iso</ty><<ty>Input</ty> = <ty>X</ty>::<ty>Output</ty>> +{ + <kw>type</kw> <ty>Input</ty> = <ty>X</ty>::<ty>Input</ty>; + <kw>type</kw> <ty>Output</ty> = <ty>Y</ty>::<ty>Output</ty>; + + <kw>fn</kw> <fn>forward</fn>(&<kw>self</kw>, <id>a</id>: <kw>Self</kw>::<ty>Input</ty>) -> <kw>Self</kw>::<ty>Output</ty> { + <kw>self</kw>.<num>1</num>.<fn>forward</fn>(<kw>self</kw>.<num>0</num>.<fn>forward</fn>(<id>a</id>)) + } + + <kw>fn</kw> <fn>reverse</fn>(&<kw>self</kw>, <id>c</id>: <kw>Self</kw>::<ty>Output</ty>) -> <kw>Self</kw>::<ty>Input</ty> { + <kw>self</kw>.<num>0</num>.<fn>reverse</fn>(<kw>self</kw>.<num>1</num>.<fn>reverse</fn>(<id>c</id>)) + } +}</code></pre> + + <p> + Additionally, we'll implement <code>Inverse</code> (not to be confused with <code>.reverse()</code>). + This flips the forward and reverse methods. + </p> + <pre><code><kw>struct</kw> <ty>Inverse</ty><<ty>X</ty>>(<ty>X</ty>); +<kw>impl</kw><<ty>X</ty>: <ty>Iso</ty>> <ty>Rev</ty> <kw>for</kw> <ty>Inverse</ty><<ty>X</ty>> { + <kw>type</kw> <ty>Input</ty> = <ty>X</ty>::<ty>Output</ty>; + <kw>type</kw> <ty>Output</ty> = <ty>X</ty>::<ty>Input</ty>; + + <kw>fn</kw> <fn>forward</fn>(&<kw>self</kw>, <id>a</id>: <kw>Self</kw>::<ty>Input</ty>) -> <kw>Self</kw>::<ty>Output</ty> { + <kw>self</kw>.<num>0</num>.<fn>reverse</fn>(<id>a</id>) + } + + <kw>fn</kw> <fn>reverse</fn>(&<kw>self</kw>, <id>b</id>: <kw>Self</kw>::<ty>Output</ty>) -> <kw>Self</kw>::<ty>Input</ty> { + <kw>self</kw>.<num>0</num>.<fn>forward</fn>(<id>b</id>) + } +}</code></pre> + + <p> + 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: + </p> + <pre><code><kw>trait</kw> <ty>RevExt</ty>: <ty>Rev</ty> + <ty>Sized</ty> { + <kw>fn</kw> <fn>then</fn><<ty>N</ty>: <ty>Rev</ty><<ty>Input</ty> = <kw>Self</kw>::<ty>Output</ty>>>(<kw>self</kw>, <id>other</id>: <ty>N</ty>) -> <ty>Pipe</ty><<kw>Self</kw>, <ty>N</ty>> { + <ty>Pipe</ty>(<kw>self</kw>, <id>other</id>) + } + + <kw>fn</kw> <fn>inverse</fn>(<kw>self</kw>) -> <ty>Inverse</ty><<kw>Self</kw>> { + <ty>Inverse</ty>(<kw>self</kw>) + } +} +<kw>impl</kw><<ty>T</ty>: <ty>Rev</ty>> <ty>RevExt</ty> <kw>for</kw> <ty>T</ty> {}</code></pre> + + <h2 id="playground">Playing around</h2> + <p> + So, what can we do with these combinators? + Quite a lot, actually! + Our math example from the beginning is trivial now: + </p> + <pre><code><kw>fn</kw> <fn>main</fn>() { + <kw>let</kw> <id>y</id> = <fn>times</fn>(<num>3</num>).<fn>then</fn>(<fn>plus</fn>(<num>6</num>)); + <kw>let</kw> <id>x</id> = <id>y</id>.<fn>inverse</fn>(); <com>// We don't have to know how this gets computed!</com> + + <mac>println!</mac>(<str>"{}"</str>, <id>y</id>.<fn>forward</fn>(<num>8</num>)); <com>// prints 30</com> + <mac>println!</mac>(<str>"{}"</str>, <id>x</id>.<fn>forward</fn>(<num>30</num>)); <com>// prints 8</com> +}</code></pre> + + <p>Here's a little celsius to farenheit calculator that only encodes the transformation one way:</p> + <pre><code><kw>fn</kw> <fn>main</fn>() { + <com>// F = (C * 1.8) + 32</com> + <kw>let</kw> <id>celsius_to_fahrenheit</id> = <fn>times</fn>(<num>1.8</num>).<fn>then</fn>(<fn>add</fn>(<num>32.0</num>)); + + <mac>println!</mac>(<str>"{}"</str>, <id>celsius_to_fahrenheit</id>.<fn>forward</fn>(<num>0.0</num>)); <com>// prints 32.0</com> + <mac>println!</mac>(<str>"{}"</str>, <id>celsius_to_fahrenheit</id>.<fn>forward</fn>(<num>100.0</num>)); <com>// prints 212.0</com> + + <mac>println!</mac>(<str>"{}"</str>, <id>celsius_to_fahrenheit</id>.<fn>reverse</fn>(<num>212.0</num>)); <com>// prints 100.0</com> + + <kw>let</kw> <id>fahrenheit_to_celsius</id> = <id>celsius_to_fahrenheit</id>.<fn>inverse</fn>(); + <mac>println!</mac>(<str>"{}"</str>, <id>fahrenheit_to_celsius</id>.<fn>forward</fn>(<num>32.0</num>)); <com>// prints 0.0</com> +}</code></pre> + + <h2 id="under">Under</h2> + <p> + <code>under</code> 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: + </p> + <pre><code><kw>fn</kw> <fn>under</fn><<ty>Op</ty>, <ty>Val</ty>>(<id>op</id>: <ty>Op</ty>, <id>val</id>: <ty>Val</ty>) -> <kw>impl</kw> <ty>Rev</ty>< + <ty>Input</ty> = <ty>Op</ty>::<ty>Input</ty>, + <ty>Output</ty> = <ty>Op</ty>::<ty>Input</ty> +> +<kw>where</kw> + <ty>Op</ty>: <ty>Rev</ty> + <ty>Clone</ty>, + <ty>Val</ty>: <ty>Rev</ty><<ty>Input</ty> = <ty>Op</ty>::<ty>Output</ty>, <ty>Output</ty> = <ty>Op</ty>::<ty>Output</ty>> +{ + <id>op</id>.<fn>clone</fn>().<fn>then</fn>(<id>val</id>).<fn>then</fn>(<id>op</id>.<fn>inverse</fn>()) +}</code></pre> + + <p> + 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. + </p> + <pre><code><kw>fn</kw> <fn>main</fn>() { + <kw>let</kw> <id>num_as_str</id> = <fn>discrete</fn>(<mac>vec!</mac>[ + (<str>"one"</str>, <num>1</num>), + (<str>"two"</str>, <num>2</num>), + (<str>"three"</str>, <num>3</num>), + (<str>"four"</str>, <num>4</num>), + (<str>"five"</str>, <num>5</num>), + (<str>"six"</str>, <num>6</num>) + ]); + + <kw>let</kw> <id>operation</id> = <fn>under</fn>(<id>num_as_str</id>, <fn>add</fn>(<num>3</num>)); + + <mac>println!</mac>(<str>"{}"</str>, <id>operation</id>.<fn>forward</fn>(<str>"three"</str>)); <com>// prints "six"</com> + <mac>println!</mac>(<str>"{}"</str>, <id>operation</id>.<fn>reverse</fn>(<str>"five"</str>)); <com>// prints "two"</com> +}</code></pre> + + <h2 id="next">Next Up</h2> + <p> + 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 <a href="./reversible.rs">here</a>. + Stay tuned! + </p> + </article> +</body> + +</html>
\ No newline at end of file |