Какой хороший способ переписать эту функцию без хвостовой рекурсии?

Пожалуйста, не минусуйте это, потому что это некрасиво. Я знаю, что это некрасиво. Но это способ сделать это в стиле батута (без переполнения системного стека) и без использования gotos.

push x,1 on homemade stack
while stack length > 1
  n = pop
  if (n==1)
    x = pop
    if (type(x)==NIL || type(x)==TEXT)
      push x // this is the "return value"
    else if (type(x)==CONCAT)
      push 2 // say call doc-concat
      push doc2(x), 1 // 2nd recursion
      push doc1(x), 1 // 1st recursion
    else if (type(x)==NEST)
      push 3 // say call doc-nest
      push level(x) // push level argument to doc-nest
      push doc(x), 1 // schedule recursion
    else if (type(x)==LINE)
      push " " // return a blank
    else if (type(x)==UNION)
      push doc1(x), 1 // just recur
  else if (n==2)
    push doc-concat(pop, pop) // finish the CONCAT case
  else if (n==3)
    push doc-nest(pop, pop) // finish the NEST case
  endif
endwhile
// final value is the only value on the stack

Основное препятствие для простого преобразования вашего алгоритма заключается в том, что он не приводит к последовательности вызовов одной и той же функции; но чередуется между несколькими, каждое из которых действует на результат другого.

я бы сказал, что у вас есть три альтернативы:

1. totally reformulate the algorithm (that's what the Fibonacci examples do).
   • combine all functions into a single one with lots of cond's (ugly, and maybe won't result in a real tail-recursion, even with a single function).
   • выверните поток наизнанку: напишите одну простую хвостовую рекурсивную функцию, которая преобразует входные данные в последовательность операций, которые необходимо выполнить, а затем оцените ее.

Если flatten вызывает себя дважды (в случае :CONCAT), как его можно превратить в цикл? Может быть, я что-то упускаю. Кажется, это по своей сути прогулка по дереву.

Я имею в виду, что есть способы обхода дерева без стека, но что-то должно быть неограниченным, например, если вы делаете это с помощью FIFO или, как было предложено, с продолжениями.

Стандартным общим приемом является преобразование в трамплинный стиль. Для вашей конкретной проблемы (реализация комбинаторов prettyprinting) вы можете найти полезную статью Дерека Оппена 1980 года "Prettyprinting" (не в Интернете, AFAIK). Он представляет основанный на стеке императивный алгоритм, аналогичный более позднему функциональному алгоритму Вадлера.

Вы можете использовать передачу продолжения:

(define (frob0 x k)
  (cond ((foo? x)
         (k x))
        ((bar? x)
         (frob0 (g x) 
           (lambda (y) 
             (k (macerate (f x) y))))
        ((thud? x)
         (frob0 (g x) 
           (lambda (y)
             (frob0 (h x) 
               (lambda (z)
                 (k (frobnicate y z))))))))

(define (frob x)
  (frob0 x (lambda (y) y))

Это не облегчит понимание :-(

Лучшее, что я могу придумать, это что-то вроде этого:

(define (doaction vars action)
  (cond ((symbol=? action 'frob)
         (cond ((foo? (first vars))
                (first vars))
               ((bar? (first vars))
                (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate)
etc...

Это не полностью хвостовая рекурсия, но, вероятно, лучшее, что вы можете получить. TCO – это действительно правильный путь. (Я понимаю, что Clojure не может иметь его из-за JVM).

Нижеследующее не является конкретным ответом на ваш вопрос, но, надеюсь, это будет полезный пример. Он заменяет несколько рекурсий (для которых в противном случае потребовался бы неограниченный стек вызовов) стеком задач.

(в коде Haskellish):

data Tree = Null | Node Tree Val Tree


-- original, non-tail-recursive function:
flatten :: Tree -> Result
flatten Null = nullval
flatten (Node a v b) = nodefunc (flatten a) v (flatten b)

-- modified, tail-recursive code:
data Task = A Val Tree | B Result Val

eval :: Tree -> [Task] -> Result
use  :: Result -> [Task] -> Result

eval Null tasks = use nullval tasks
eval (Node a v b) tasks = eval a ((A v b):tasks)

use aval ((A v b):tasks) = eval b ((B aval v):tasks)
use bval ((B aval v):tasks) = use (nodefunc aval v bval) tasks
use val [] = val

-- actual substitute function
flatten2 :: Tree -> Result
flatten2 tree = eval tree []