5 ms·

I wrote the paper that this article is describing [1], and can answer questions. The paper is probably more approachable than you think. Basically I rewrite co

I wrote the paper that this article is describing [1], and can answer questions. The paper is probably more approachable than you think. Basically I rewrite code like `let intermediate_value = recursive_call(...)` into code like `output += recursive_call(...)`, which allows you to make recursive calls in a way that avoids ever storing the intermediate value. That's important in contexts where you can't simply discard information, namely quantum computing. [1]: https://arxiv.org/abs/1904.07356 https://arxiv.org/abs/1904.07356

olliej 7y ago
How do you deal with reversibility? I assume that is the hard bit, as tail recursion is not new (and I would have assumed been the first thing picked up if it was easy)
- Strilanc 7y ago
  It's not really tail recursion, it's just similar in that you get the recursion into a particular form in order to enable an optimization that avoids the need for intermediation. For tail recursion, that form is the last thing executed in a recursive method should be "return recursive_call(...)". It allows you to tell the sub-call to give its result directly to the current method's caller, avoiding the need for the current method to act as an intermediary bouncing the result from its callee to its caller. In this paper the special form is "output += recursive_call(...)", where output is a mutable reference to the location where the result should be stored. This also allows the current method to avoid acting as an intermediary between its callee and its caller, since the callee will take a mutable reference to (a subsection of) the output and directly mutate it.
  - robert_tweed 7y ago
    If I'm understanding you correctly (and I haven't RTFA yet, sorry) this is a bit like Operational Transform, allowing you to run some or all steps in parallel and achieve eventual-consistency. As opposed to TCO, which is simply restating recursion as iteration, but still requires the operations to run in sequence.
    - Strilanc 7y ago
      The thing I'm describing doesn't allow the steps to run in parallel. In fact it prevents it, because each of the three recursive calls require exclusive access to overlapping regions of the output.
no_identd 7y ago
No questions right now, great work! However, one remark: I suspect you might find the Turing Completeness & Recursive Types "off hand" result from the following paper of interest: http://drops.dagstuhl.de/opus/volltexte/2017/7276/pdf/LIPIcs-ECOOP-2017-27.pdf http://drops.dagstuhl.de/opus/volltexte/2017/7276/pdf/LIPIcs... To quote: "We further showed that certain variants of DOT’s recursive self types can be integrated successfully while keeping the calculus strongly normalizing. This result is surprising, as traditional recursive types are known to make a language Turing-complete."

olliej 7y ago

How do you deal with reversibility? I assume that is the hard bit, as tail recursion is not new (and I would have assumed been the first thing picked up if it was easy)

Strilanc 7y ago
It's not really tail recursion, it's just similar in that you get the recursion into a particular form in order to enable an optimization that avoids the need for intermediation. For tail recursion, that form is the last thing executed in a recursive method should be "return recursive_call(...)". It allows you to tell the sub-call to give its result directly to the current method's caller, avoiding the need for the current method to act as an intermediary bouncing the result from its callee to its caller. In this paper the special form is "output += recursive_call(...)", where output is a mutable reference to the location where the result should be stored. This also allows the current method to avoid acting as an intermediary between its callee and its caller, since the callee will take a mutable reference to (a subsection of) the output and directly mutate it.
- robert_tweed 7y ago
  If I'm understanding you correctly (and I haven't RTFA yet, sorry) this is a bit like Operational Transform, allowing you to run some or all steps in parallel and achieve eventual-consistency. As opposed to TCO, which is simply restating recursion as iteration, but still requires the operations to run in sequence.
  - Strilanc 7y ago
    The thing I'm describing doesn't allow the steps to run in parallel. In fact it prevents it, because each of the three recursive calls require exclusive access to overlapping regions of the output.

no_identd 7y ago

No questions right now, great work! However, one remark: I suspect you might find the Turing Completeness & Recursive Types "off hand" result from the following paper of interest: http://drops.dagstuhl.de/opus/volltexte/2017/7276/pdf/LIPIcs-ECOOP-2017-27.pdf http://drops.dagstuhl.de/opus/volltexte/2017/7276/pdf/LIPIcs... To quote: "We further showed that certain variants of DOT’s recursive self types can be integrated successfully while keeping the calculus strongly normalizing. This result is surprising, as traditional recursive types are known to make a language Turing-complete."