paulp - extempore2 - trampolining

nmcb 16:08
no as in; no it is not ’sufficient’ for the method
to be a primitively recursive function?  currently
[i see as `sufficient` for tail call optimisition]:

  1) [the recursive method being] final
  2) [recursive calls in the implementation being in] tail position.

paulp 16:46
What makes you think there is a link between
primitive recursion and tail call elimination?
It is definitely not required to be primitive
recursive, because you can write infinite loops.
And being primitive recursive isn't sufficient
because that doesn't stop you from consuming
arbitrarily great amounts of stack space.

nmcb 16:50
i think it is strange that the [non] primitive
recursive ackermann function kan be tail call
optimised by haskell and not by scala, i try
to find the ['sufficient'] requirements in
order to guarantee tail call optimisation.
[...]
1) final,
2) tail position,
3) [no] infinite loops [...]

paulp 16:54
Fundamentally, the computation must be
structured so recursive results are immediately
consumed.

nmcb 16:55
true, but what about call side timeouts,
the computation may take an infinite amount of
time?

paulp 16:57
That isn't a consideration for tail call
elimination. That's always the case in a
Turing complete language.

nmcb 17:01
[... n.a. ...]

nmcb 4 Mar 15:54
"Fundamentally, the computation must be
structured so recursive results are
immediately consumed."

Q: Would you consider the result method on
   the Cont instance, i.e. a continuation,
   of a trampoline: "immediately"?
   
```scala
    /** Returns the result of the tailcalling computation.
     */
    @annotation.tailrec final def result: A = this match {
      case Done(a) => a
      case Call(t) => t().result
      case Cont(a, f) => a match {
        case Done(v) => f(v).result
        case Call(t) => t().flatMap(f).result
        case Cont(b, g) => b.flatMap(x => g(x) flatMap f).result
      }
    }
  }
  
  case class Cont[A, B](a: TailRec[A], f: A => TailRec[B]) extends TailRec[B]
  ```
  
  [tailrec](https://github.com/scala/scala/blob/v2.11.1/src/library/scala/util/control/TailCalls.scala)

Cont is a synthetic stack placed on the heap. Picture Cont(Cont(Cont(Cont(..., r3), r2), r1), r0). It can't be tail-recursive with that structure.

[my initial reaction, this comment, was clear nonsense, please see the update below]

I don't want te be or look childish, but seriously, picture what I picture:

I see: COCOCont(..., r3), r2), r0)

And I think: that looks like a tail of (intermediary) results.

So, I really start to doubt whether I understand what tail position is. Is the order of the tail's sequence r3 :: r2 :: r0 :: Nil wrong?

Sorry if I waste your time, but I find the exercise stimulating (though frightening :)

Cont is a synthetic stack placed on the heap.

I understand now, took me a couple of years, but I think I do, thanks.