[Swift-devel] maybe unrelated

[Mihael Hategan]

but it seems like there is a class of functions that can be
automatically transformed to be tail recursive. These are functions
whose otherwise not-tail-call is a fold-able operation.

For example,
base: () -> B
someFunction: (A, B) -> B
someOtherFunction: A -> A

f(params:A):B {
  if (terminationCondition(params)) {
    base(params)
  }
  else {
    someFunction(params, f(someOtherFunction(params)))
  }
}

can be transformed to

f(params:A):B {
  list = new list of A
  f'(params, list)
  foldl(someFunction, base(params), list)
}

f'(params:A, list of A) {
  if (!terminationCondition(params)) {
    append(list, params)
    f'(someOtherFunction(params), list)
  }
}

In particular the mighty factorial:

(A = int, B = int)
someOtherFunction = -
someFunction = *

fact(n:int) {
  list = new list of int
  f'(n, list)
  foldl(*, 1, list)
}

fact'(n, list) {
  if (!(n==0)) {
    append(list, n)
    fact'(n - 1, list)
  }
}

At least it passes the type checking step ;)

Even if there are side-effects in one or both of the some* functions,
this still seems to preserve the right semantics.