1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
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>
|
