Add tail-recursion modulo cons (TMC) optimisation

[myreen]

This issue is about adding tail-recursion modulo cons (TMC) as a new optimisation to the CakeML compiler. The idea is to automatically transform non-tail-recursive functions such as

fun append [] ys = ys
  | append (Cons x xs) ys = Cons x (append xs ys);

into tail-recursive functions:

fun append' ctxt [] ys = (ys → ctxt)
  | append' ctxt (Cons x xs) ys = append' (Cons x HOLE → ctxt) xs ys;

fun append [] ys = ys
  | append (Cons x xs) ys = append' (Cons x HOLE) xs ys

or, if the original function is large and we don't want to duplicate it, into append' as above and the following:

fun append xs ys = Option.valOf (append' (SOME HOLE) xs ys)

Concretely, the the context ctxt is a reference to a MutableBlock and an offset where the primitive for plugging (→) the hole in MutableBlock is to add the new element.

This optimisation is to happen around bvl-to-bvi in the compiler. It uses mutable state as a temporary, but returns on completion exactly the same immutable result as the original version of the code.

This is suitable as a student project. Contact me (myreen) on the CakeML Discord to discuss details.