diff options
| author | Collin Williams <96917990+bluedragon1221@users.noreply.github.com> | 2026-09-19 21:13:32 -0500 |
|---|---|---|
| committer | Collin Williams <96917990+bluedragon1221@users.noreply.github.com> | 2026-09-19 21:13:32 -0500 |
| commit | b6f7b9dda8cd2e4b1c5b006ad5866d3ef7e62310 (patch) | |
| tree | cea3af7c287c28fcaf379ec3700f0aa76223e244 /reversible.html | |
| parent | ffd6abb1403d85b61c80fc8d23a3a04df8895c20 (diff) | |
inserting link:css via javascript was a bad idea
Diffstat (limited to 'reversible.html')
| -rw-r--r-- | reversible.html | 253 |
1 files changed, 141 insertions, 112 deletions
diff --git a/reversible.html b/reversible.html index 893b73a..a9b6477 100644 --- a/reversible.html +++ b/reversible.html @@ -1,66 +1,90 @@ <!DOCTYPE html> <html> + <head> + <meta charset="UTF-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <link rel="icon" href="static/Logo.svg" type="image/svg+xml"> + <link rel="stylesheet" href="article.css"> -<head> - <title>Reversible Programming is cool (Reversible Part 1)</title> - <meta property="article:published_time" content="2026-07-05"> - <script src="./article.js"></script> -</head> + <title>Reversible Programming is cool (Reversible Part 1)</title> + </head> -<body> - <article> - <header></header> + <body> + <article class="markdown-body"> + <header> + <div class="header-top"> + <a href="writing.html" class="header-logo-link"></a> + <div class="header-info"> + <h1>Reversible Programming is cool (Reversible Part 1)</h1> + <time datetime="2026-07-29">Published Jul 05, 2026</time> + </div> + </div> + <hr> + </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> + <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>Table of Contents</h2> + <ul> + <li><a href="#math">Math basis</a></li> + <li><a href="#idea">Idea of the implementation</a></li> + <li><a href="#foundations">Foundations</a></li> + <li><a href="#first">First Combinators</a></li> + <li><a href="#playground">Playing around</a></li> + <li><a href="#under">Under</a></li> + <li><a href="#next">Next Up</a></li> + </ul> - <h2 id="math">Math basis</h2> - <p> - So remember in math class when you learned to take the inverse of a function? - For example, say you have <code>y = 3*x + 6</code>. - You can take the inverse by solving for <code>x</code>. - In this case, the inverse of our function is <code>x = y/3 - 2</code>. - 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><fn>up</fn></code> script automatically gives you your <code><fn>down</fn></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="math">Math basis</h2> + <p> + So remember in math class when you learned to take the inverse of a function? + For example, say you have <code>y = 3*x + 6</code>. + You can take the inverse by solving for <code>x</code>. + In this case, the inverse of our function is <code>x = y/3 - 2</code>. + 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><fn>up</fn></code> + script automatically gives you your <code><fn>down</fn></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="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> { + <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><ty>Rev</ty></code> trait. - </p> - <pre><code><kw>struct</kw> <ty>Addition</ty><<ty>A</ty>> { + + <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><ty>Rev</ty></code> + trait. + </p> + <pre><code><kw>struct</kw> <ty>Addition</ty><<ty>A</ty>> { <prop>amount</prop>: <ty>A</ty> } @@ -82,38 +106,42 @@ } }</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." - <span class="comment">Honestly these are light work compared to what's coming up.</span> - </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>> { + <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." + <span class="comment">Honestly these are light work compared to what's coming up.</span> + </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>() { + <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><fn>neg</fn>()</code> negates a number</li> - <li><code><fn>times</fn>(x)</code> multiplies a number by x</li> - <li><code><fn>discrete</fn>(x: <ty>Vec</ty><(<ty>A</ty>, <ty>B</ty>)>)</code> creates a reversible block out of a set of discrete inputs and outputs.</li> - </ul> + <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><fn>neg</fn>()</code> + negates a number</li> + <li><code><fn>times</fn>(x)</code> + multiplies a number by x</li> + <li><code><fn>discrete</fn>(x: <ty>Vec</ty><(<ty>A</ty>, <ty>B</ty>)>)</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><ty>Pipe</ty></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>); + <h2 id="first">First Combinators</h2> + <p> + The first combinator we'll implement is <code><ty>Pipe</ty></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>, @@ -131,11 +159,12 @@ } }</code></pre> - <p> - Additionally, we'll implement <code><ty>Inverse</ty></code> (not to be confused with <code>.<fn>reverse</fn>()</code>). - This flips the forward and reverse methods. - </p> - <pre><code><kw>struct</kw> <ty>Inverse</ty><<ty>X</ty>>(<ty>X</ty>); + <p> + Additionally, we'll implement <code><ty>Inverse</ty></code> + (not to be confused with <code>.<fn>reverse</fn>()</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>; @@ -149,11 +178,11 @@ } }</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> { + <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>) } @@ -163,14 +192,14 @@ } } <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>() { + + <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> @@ -178,8 +207,8 @@ <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>() { + <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>)); @@ -192,13 +221,14 @@ <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><fn>under</fn></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>< + <h2 id="under">Under</h2> + <p> + <code><fn>under</fn></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> > @@ -209,11 +239,11 @@ <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>() { + <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>), @@ -228,15 +258,14 @@ <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> + <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> |
