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

Question

По какой-то причине у меня возникают проблемы с хорошим выбором для перезаписи этой функции, поэтому она использует постоянное пространство стека. Большинство онлайн-дискуссий об обмане рекурсии деревьев используют функцию Фибоначчи и используют свойства этой конкретной проблемы. Есть ли у кого-нибудь идеи для этого «реального мира» (ну, более реального мира, чем серия Фибоначчи), использование рекурсии?

Clojure - интересный случай, поскольку он не имеет оптимизации хвостового вызова, а только рекурсию хвоста через специальную форму «recur». Это также сильно препятствует использованию изменчивого состояния. У этого есть много ленивых конструкций, включая tree-seq, но я не могу видеть, как они могут помочь мне в этом случае. Может ли кто-нибудь поделиться некоторыми методами, которые они выбрали из C, Scheme, Haskell или других языков программирования?

(defn flatten [x] 
    (let [type (:type x)] 
    (cond (or (= type :NIL) (= type :TEXT)) 
      x 
      (= type :CONCAT) 
      (doc-concat (flatten (:doc1 x)) 
         (flatten (:doc2 x))) 
      (= type :NEST) 
      (doc-nest (:level x) 
        (flatten (:doc x))) 
      (= type :LINE) 
      (doc-text " ") 
      (= type :UNION) 
      (recur (:doc1 x))))) 

редактировать: По запросу в комментариях ...

пересчитаны в общих чертах и ​​с использованием схемы - как я переписать следующий шаблон рекурсии, чтобы он не потребляет пространство стека или требовать tail- оптимизация звонков без звонков?

(define (frob x) 
    (cond ((foo? x) 
     x) 
     ((bar? x) 
     (macerate (f x) (frob (g x)))) 
     ((thud? x) 
     (frobnicate (frob (g x)) 
        (frob (h x)))))) 

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

UPDATE:

Rich Хики любезно добавил явную trampoline function в Clojure.

Answer 1

Пожалуйста, не уменьшайте это, потому что это уродливо. Я знаю, что это уродливо. Но это способ сделать это в стиле батут (без переполнения системного стека) и без использования 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 

Answer 2

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

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

1. полностью переформулировать алгоритм (это то, что делают примеры Фибоначчи).
   • объединяет все функции в один, с большим количеством cond (уродливый, и, возможно, не приведет к реальной хвостовой рекурсии, даже с одной функцией).
   • Поверните поток изнутри: напишите единственную, простую хвостовую рекурсивную функцию, которая преобразует входные данные в последовательность операций, которые должны быть выполнены, а затем оценивайте ее.

Answer 3

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

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

Answer 4

Вы можете использовать продолжение обгон:

(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)) 

Это не будет делать вещи проще понять :-(

Answer 5

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

(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... 

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

Answer 6

Стандартная общая техника - это преобразование в trampolined style. Для вашей конкретной проблемы (внедрения компиляторов красивой печати) вы можете найти полезную статью Дюка Оппа в 1980 году «Претензионная печать» (не в Интернете AFAIK). Он представляет собой алгоритм, основанный на стеках, аналогичный более позднему функциональному алгоритму Вадлера.

Answer 7

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

(в 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 []