Что хороший путь состоит в том, чтобы переписать эту функцию non-tail-recursive?
Вам не обязательно использовать основанный на Cordova, но не стесняйтесь взглянуть на socket-for-cordova . Популярный, не основанный на Cordova, но прекрасно работающий с Cordova, это Sockets.io
7 ответов
Не делайте downvote это, потому что это ужасно. Я знаю, что это ужасно. Но это - способ сделать это в стиле батута (никакое системное переполнение стека), и не используя 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
Основное препятствие к легкому преобразованию Вашего алгоритма - то, что это не приводит к последовательности вызовов к той же функции; но альтернативы между несколькими, каждый воздействующий на результат другого.
я сказал бы, что у Вас есть три альтернативы:
- полностью повторно сформулируйте алгоритм (это - то, что примеры Fibonacci делают).
- объедините все функции в единственную с большим количеством cond's (ужасный, и возможно не приведет к реальной хвостовой рекурсии, даже с единственной функцией).
- выверните поток наизнанку: запишите единственную, простую рекурсивную функцию хвоста, которая преобразовывает входные данные в последовательность операций, которые должны быть выполнены, и затем оценка это.
Стандартная общая техника является преобразованием в стиль trampolined. Для Вашей конкретной проблемы (реализующий prettyprinting combinators) Вы могли бы найти статью услужливого Derek Oppen 1980 года "Prettyprinting" (не на веб-AFAIK). Это представляет стековый обязательный алгоритм, подобный более позднему функциональному Wadler.
Если сглаживаются, называет себя дважды (в: случай CONCAT), как это может быть превращено в цикл? Возможно, я пропускаю что-то. Кажется, что это - по сути обход дерева.
Я имею в виду, существуют способы сделать обход дерева без стека, но что-то должно быть неограниченным, как то, если Вы делаете это с FIFO, или как был предложен, с продолжениями.
Вы могли использовать передачу продолжения:
(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
- исходный, non-tail-recursive функция: сгладьтесь:: Дерево-> Результат сглаживается, Пустой указатель = nullval сглаживаются (Узел, который v b) = nodefunc (сглаживают, a) v (сгладьте b),
- измененный, рекурсивный хвостом код: Задача данных = Дерево Val | B Результат Val
оценка:: Дерево-> [Задача]-> использование Результата:: Результат-> [Задача]-> Результат
задачи Пустого указателя оценки = используют nullval оценку задач (Узел v b) задачи = оценка ((V b): задачи)
используйте аваль ((V b): задачи) = оценка b ((B аваль v): задачи), используют bval ((B аваль v): задачи), = использование (nodefunc аваль v bval) задачи используют val [] = val
- фактическая функция замены flatten2:: Дерево-> Результат flatten2 дерево = дерево оценки []