letter to scala contributors about a minor mathematical impedance mismatch concerning recursive functions.

trampolined-ackermann discussion

@SethTisue @pfn @paulp @retronym

I'm back online after a 4 hour train travel and had the opportunity to contemplate the conversational
session on scala/scala about whether it is possible in principle to implement the ackermann function
by "just typing in it's recursive definition in scala" [1], i.e. without applying some mental
translation from the mathematical definition into the scala language, and without applying some scala
library construct, and without me writing a trampoline for some part of the recursive definition for
that matter.

My current understanding is that this is _not_ possible, but would be happy to be proven wrong.  I know
it _is_ possible to implemented the function if I translate the "inner recursive call" [2] of the
ackermann function definition with a trampoline implementation into a `for` comprehension [3].  I, being
human, find recognition of this "inner recursive call" and the translation into a trampolined for
comprehension easy;  but I don't understand whether that translation needs necessarily be done by me, it
seems possible to be done mechanically and therefor be done by the scalac compiler.

I do also not understand much about the internals of haskell's type system nor about the machinery on
which compiled haskell code runs, I'm definitely not authoritative in any way, but,...  the fact that I
_can_ implement the ackermann function in haskell by just writing down the mathematical definition and
without me needing to resort to a translation of ackermann's "inner recursive call" into a trampolined
for comprehension provides me the thought that this should also be possible in scala.

Now given _some_ mathematically defined recursive function, I would like to understand both the
`necessary` _as well as_ the `sufficient` conditions for that function to implemented in any given
functional language, i.e. languages supporting functions as first class citizens or support lambdas [4].
I know functional languages may differ in language features in very subtle ways, but scala is my current
favourite and haskell provides for a good examples.  Both languages market themselves as being functional.

I do also understand that compiled scala runs on the JVM and therefore is prone (dare I say eligible)
for stack overflow exception;  haskell though, which for all I know [5] might not even run the compiled
function on a stack machine, does not throw a stack overflow exception [6] and therefor compiles for
different machinery _or_ it recognises the "inner recursive call" during compilation and translates it
into trampolined control flow logic automatically.  I would like to know which of the two it is because
I do not understand whether it is "I" that **needs** to be responsible for the recognition of the
"inner recursive call" and the subsequent translation into a trampolined for comprehension or that it
is "a compiler".

Now it may be that the JVM puts constraints on whether it is possible to translate the "inner recursive
call" into a trampolined or otherwise safely compiled java byte code, it may even be so that this is not
the case but that such constraints are there for deliberate reasons, i.e. because the scalac designers
had "the desire ... to use standard JVM method call semantics for both performance and interoperability
reasons" [7], probably for good and sound reasons.  Still, I would like to know whether it is possible in
principle.  Whether I can "recognise" recursive function constructs that prohibit automatic translation in
principle.  It is very much a scalac user question, and on top of that it is being asked from a
mathematically inclined programming point of view, but i find it an interesting question nonetheless. 

Happy to be part of this discussion and the scala community.  Sorry if I sometimes use inept terms and
phrases or seem to cross the line in form and content when I'm enthusiastic;  English is not my native
language and I put burden on others when I communicate with a native English speaking community [8].
But sharing is caring, and I do appreciate all comments.  Thanks in advance.

/cc @tpolecat @paddymahoney

---

[1]  Usage of double quotes purposely intended as scary-quotes as I'm no expert in the formal
     and mathematical terms that depict the different types and constructs of recursive functions;
     Sorry.
     
[2]  As @SethTisue noted, the term "inner recursive call" seems not to be formally defined.

[3]  Note that I have _nothing_ against trampolining and for comprehensions, on the contrary,
     I find it an elegant technique.
     
[4]  Thanks again @SethTisue for providing the terms `necessary` and `sufficient`.

[5]  Thanks @pfn for pointing that out.

[6]  Or any exception for that matter.

[7]  And once again, thank you @SethTisue for pointing that intend out.

[8]  There are also benefits to not speaking natively English though.  As EWD already wrote
     in #498:  "besides a mathematical inclination, an exceptionally good mastery of one's
     native tongue is the most vital asset of a competent programmer".  Being forced to
     translate English source code into my native language mentally does provide for an
     additional moment to think things through.  Anyhow, dank voor uw aandacht tijdens
     het lezen van dit bericht.

Haskell (Frege) is not so great on the JVM.

@timcharper Understood, I don't know a lot about Frege, just mentioned it because @SethTisue gave me the idea that it was the JVM that was to be blamed (and he may very well be right with that). @pfn mentioned that Frege is not great on the JVM already, still, no SOE in Frege when I tried it quickly in a online frege interpreter, though I did get a timeout exception.

-- ackermann function 
--
ackermann             :: Integer -> Integer -> Integer
ackermann 0 n         =  n + 1
ackermann m 0 | m > 0 =  ackermann (m - 1) 1
ackermann m n         =  ackermann (m - 1) (ackermann m (n - 1))