<p>There's actually two questions here!</p>
<ol>
<li><p>The transformation you ask about is called <em>the tupling transformation</em>. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be turned into some extra arguments (as in the fibonacci function)</p>
<p>For references, see</p>
<ul>
<li><p>Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi, <a href="https://www.keisu.t.u-tokyo.ac.jp/data/1996/METR96-08.pdf" rel="nofollow noreferrer"><em>Cheap Tupling Transformation</em></a></p>
</li>
<li><p>Wei-Ngan Chin, Zhenjiang Hu, <a href="http://research.nii.ac.jp/%7Ehu/pub/saig02.ps" rel="nofollow noreferrer"><em>Towards a Modular Program Derivation via Fusion and Tupling</em></a></p>
</li>
</ul>
<p>This is one of my favourite program transformations, and I wish more people knew about it, and more compilers did it!</p>
</li>
<li><p>Your intuition that memoisation is enough to make reverse-mode AD work is a very good one. For a nice (IMO!) example of this, see my recent (POPL 2022) paper:</p>
<ul>
<li>Faustyna Krawiec, Simon Peyton-Jones, Neel Krishnaswami, Tom Ellis, Richard A. Eisenberg, and Andrew Fitzgibbon, <a href="https://www.cl.cam.ac.uk/%7Enk480/higher-order-ad.pdf" rel="nofollow noreferrer"><em>Provably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic Differentiation</em></a></li>
</ul>
<p>What we do is take a naive computation of reverse derivatives via repeated evaluation of forward-mode AD with dual numbers, and incrementally optimise it until we get an asymptotically efficient algorithm for reverse derivatives. One of the key steps is to maintain sharing, precisely to avoid exponential slowdowns from loss of sharing.</p>
</li>
</ol>

CC BY-SA 4.0
2022-01-15T23:26:11.653Z
2022-01-15T23:26:11.653Z
Neel Krishnaswami
<p>This is what I'm looking for. Take a recursive algorithm:</p>
<pre><code>def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)
</code></pre>
<p>and turn it into this:</p>
<pre><code>def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a
</code></pre>
<p>...in a way that's fully automated.</p>
<hr />
<p>My motivation is a hypothesis about <em>automatic differentiation</em>. The independent researcher Sandro Magi has had the <a href="https://higherlogics.blogspot.com/2020/05/dualcodual-numbers-for-forwardreverse.html" rel="noreferrer">following idea</a>:</p>
<ul>
<li><p>The <a href="https://en.wikipedia.org/wiki/Automatic_differentiation#Automatic_differentiation_using_dual_numbers" rel="noreferrer">dual numbers</a> can be used to express <em>forward mode automatic differentiation</em> in very little code. This fact is well known.</p>
</li>
<li><p>Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the <em>codual numbers</em>. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.</p>
</li>
<li><p>The <a href="https://higherlogics.blogspot.com/2020/05/dualcodual-numbers-for-forwardreverse.html" rel="noreferrer">codual numbers</a> naturally express something similar to <em>reverse-mode autodiff</em>, which is of major interest to applications.</p>
</li>
</ul>
<p>Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on <a href="https://higherlogics.blogspot.com/2020/05/easy-reverse-mode-automatic.html?showComment=1590876369081#c4027972603935304413" rel="noreferrer">some instances</a>. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation (as I've done <a href="https://github.com/wlad-svennik/memoized_coduals" rel="noreferrer">here</a>). The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.</p>
<p>Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of <em>top-down dynamic programming</em>, instead of the usually preferable <em>bottom-up dynamic programming</em>. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.</p>

CC BY-SA 4.0
2022-01-13T22:29:02.663Z
Such an automatic system seems to be unlikely to exist... Specific toy problems (like the above) can of course be handled. Automatic memoization (which is already enough to reduce the running time to polynomial) are supported by some languages like lisp and scheme. A nice description of this is in https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs . A more "standard" description how to do this transformation is in Jeff Erickson algorithms book. Maybe ask in compilation/programming-languages forum about this...
Sariel Har-Peled
CC BY-SA 4.0
2022-01-14T02:20:15.357Z
There are many posts on eliminating recursion, such as: https://softwareengineering.stackexchange.com/questions/347582/eliminating-recursion
naasking
CC BY-SA 4.0
2022-01-14T02:25:17.327Z
Related are compiler optimizations like "fusion" (https://stackoverflow.com/questions/38905369/what-is-fusion-in-haskell#38910170), and supercompilation (https://stackoverflow.com/questions/9067545/what-is-supercompilation), although those are pretty advanced compared to basic recursion elimination. I mention them because it's not always possible to eliminate recursion without adding allocation, but this can sometimes be done via fusion/supercompilation passes.
naasking
CC BY-SA 4.0
2022-01-14T08:33:02.190Z
@SarielHar-Peled I've already mentioned memoisation in my question. In Python, it's even easier than you said: https://docs.python.org/3/library/functools.html - This results in a "top-down" style of dynamic programming instead of a (loosely defined) "bottom-up" style. I think the tape-based approach to autodiff is an instance of bottom-up style, and so memoisation alone is not enough.
wlad
<reference-request><dynamic-programming><recursion>
Reference for automatically deriving dynamic programming algorithms from recursive algorithms?
wlad
# Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

(Asked by: username_0 on 2022-01-13)

This is what I'm looking for. Take a recursive algorithm:
def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

and turn it into this:
def fib(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b
  return a

...in a way that's fully automated.

My motivation is a hypothesis about automatic differentiation. The independent researcher Sandro Magi has had the following idea:

The dual numbers can be used to express forward mode automatic differentiation in very little code. This fact is well known.

Magi has shown that the dual numbers have a mathematically similar counterpart which he calls the codual numbers. On some level, there is no difference between the dual numbers and codual numbers; they are simply two different ways of representing the same mathematical object on a computer.

The codual numbers naturally express something similar to reverse-mode autodiff, which is of major interest to applications.


Unfortunately, Magi's simple algorithm exhibits exponential time behaviour on some instances. A good implementation of autodiff shouldn't behave that way. Simple experiments show that all known examples of exponential time behaviour can be solved using memoisation (as I've done here). The introduction of memoisation makes the time complexity of the resulting algorithm difficult to gauge.
Whenever exponential time behaviour gets fixed using memoisation, it indicates a connection to dynamic programming. In fact, this can be considered an instance of top-down dynamic programming, instead of the usually preferable bottom-up dynamic programming. I conjecture therefore that tape-based autodiff is the result of applying a transformation on Magi's codual numbers, turning it into an instance of bottom-up dynamic programming. This makes the time complexity legible.

**Tags:** reference-request, dynamic-programming, recursion
> **Comments:**
> **username_1**: Such an automatic system seems to be unlikely to exist... Specific toy problems (like the above) can of course be handled. Automatic memoization (which is already enough to reduce the running time to polynomial) are supported by some languages like lisp and scheme. A nice description of this is in https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs . A more "standard" description how to do this transformation is in Jeff Erickson algorithms book. Maybe ask in compilation/programming-languages forum about this...  
> **username_2**: There are many posts on eliminating recursion, such as: https://softwareengineering.stackexchange.com/questions/347582/eliminating-recursion  
> **username_2**: Related are compiler optimizations like "fusion" (https://stackoverflow.com/questions/38905369/what-is-fusion-in-haskell#38910170), and supercompilation (https://stackoverflow.com/questions/9067545/what-is-supercompilation), although those are pretty advanced compared to basic recursion elimination. I mention them because it's not always possible to eliminate recursion without adding allocation, but this can sometimes be done via fusion/supercompilation passes.  
> **username_0**: @SarielHar-Peled I've already mentioned memoisation in my question. In Python, it's even easier than you said: https://docs.python.org/3/library/functools.html - This results in a "top-down" style of dynamic programming instead of a (loosely defined) "bottom-up" style. I think the tape-based approach to autodiff is an instance of bottom-up style, and so memoisation alone is not enough.  

---

## 1 answers

### Answer by username_3 on 2022-01-15. Score: 4

There's actually two questions here!

1. The transformation you ask about is called *the tupling transformation*. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be turned into some extra arguments (as in the fibonacci function)

   For references, see

   * Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi, [*Cheap Tupling Transformation*](https://www.keisu.t.u-tokyo.ac.jp/data/1996/METR96-08.pdf)
   * Wei-Ngan Chin, Zhenjiang Hu, [*Towards a Modular Program Derivation via Fusion and Tupling*](http://research.nii.ac.jp/%7Ehu/pub/saig02.ps)

   This is one of my favourite program transformations, and I wish more people knew about it, and more compilers did it!
2. Your intuition that memoisation is enough to make reverse-mode AD work is a very good one. For a nice (IMO!) example of this, see my recent (POPL 2022) paper:

   * Faustyna Krawiec, Simon Peyton-Jones, Neel Krishnaswami, Tom Ellis, Richard A. Eisenberg, and Andrew Fitzgibbon, [*Provably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic Differentiation*](https://www.cl.cam.ac.uk/%7Enk480/higher-order-ad.pdf)

   What we do is take a naive computation of reverse derivatives via repeated evaluation of forward-mode AD with dual numbers, and incrementally optimise it until we get an asymptotically efficient algorithm for reverse derivatives. One of the key steps is to maintain sharing, precisely to avoid exponential slowdowns from loss of sharing.


---

