I just watched this video, and it was very interesting. Thank you.
As mentioned in other threads, a big issue is proper tail calls. It’s not correct to think of proper tail calls as an “optimization” that can be performed by compilers: in general, removing all tail calls from a program is a global transformation, breaking separate compilation. “Tail call optimization” really is a misnomer, it should be called “tail recursion optimization”, because proper tail calls are not necessarily recursive, and tail recursion optimization and proper tail calls can be orthogonal concerns.
Proper tail calls can be compiled onto most instruction sets just fine; the real issue is that popular compilers do not do this. So, compiling languages such as Scheme, ML, Haskell, F#, or .NET bytecode down to C (in order to avoid implementing a native code generator) or the JVM or JavaScript (because you have no choice given your deployment targets) involves some pretty monstrous kludges and/or some amount of interpretation remaining in the generated code. But compiling them down to machine code really isn’t an issue.
(As an aside, unlike some remarks in other threads, I wouldn’t worry one bit about closures. We know how to deal with closures just fine, thank you. I haven’t been excited by various efforts to implement them in hardware, unlike the Mill.)
Ideally, the Mill CPU would offer a “callret” instruction, that would be just like the current “call” instruction except that the current belt and scratch pad would be discarded before the call. When (if) the called function returns, it’s results would be dumped onto whatever belt the calling function would have returned to.
As I understand it, the Mill can almost do tail calls: simply shuffle the belt and then jump. The two problems with this, though, that the called function would not necessarily have enough scratchpad space allocated to perform its work, and that the called function would be able to read non-parameter values left in the caller’s belt and scratchpad.
The second issue certainly does raise the specter of security issues via information leakage; I don’t know enough about the Mill CPU’s security model and potential applications to offer an educated guess about the practical relevance of this issue.
The first issue, however, would certainly be a pretty fundamental stumbling block for proper tail calls if scratchpad space cannot be re-allocated, and a practical stumbling block if the initial scratchpad allocation instruction doesn’t also serve as a scratchpad reallocation instruction. After all, the called function should have no idea if it was called normally or called via a tail call.
Practical applications of tail calls include loops that span compilation boundaries, big Gordian knots of mutual recursion (as often found in lexers, parsers, and state machines), preserving object oriented abstractions, and supporting the commercially-relevant .NET bytecode instruction set.
