Once upon a time, in the land of the Clojure, there was a brilliant student who enquired the nature of things and he for that he was greatly loved and appreciated by his teachers, for he was brilliant and asked about the nature of things and they could explain him the world. He learned about macros and first order functions and actors and software transactional memory and he was happy. But then he began to focus on the nature of recur and he felt that something was amiss and the way trampolines and functions interact made him wonder.
During a short holiday he was in Schemeland, and he saw that they did not use recur. They named the functions and called them with their name in tail position and that was the way they did. And he felt it was good. So he asked his Master:
"Why can the schemers call the functions in tail position and their stacks never end?"
And the Master told him that it was because their soil is fertile, while the land of the Clojure is just an oasis in the wastes of Javaland.
"We are lucky," he added, "for our land still gives us food spontaneously and the air does not drives us mad. And our spring is natural and not a framework. And if you do not like recur, you can always map, for or loop. Higher order functions and macros can help you to hide what you do not like, for you are the master of your own language."
For a while the student was content, still he had a recurring thought: functions can do everything and in Church he did not find recur but only functions. And so he learned Y. But Y is a demanding beast, for it requires functions to be defined awkwardly. And the student wanted to simply write:
(defn factorial [n acc]
(if (= n 0)
acc
(factorial (- n 1) (* n acc))))
His Master saw him troubled and in pain, and one day a big application they were creating exploded with a StackOverflowError and he knew that unless the student was cured he could not be writing code with the others. So one evening, he told his student that if he really wanted to learn the secrets to make tail-call recursive functions run with constant stack usage, he shall go to the Land of Snakes, where they eat only Spam and Eggs, to look for some wise men and have them teach the secrets of creating tail recursion at language level. And he warned the student that the travel was dangerous.
The young student was frightened, because the Land of Snake is far away and he was barely aware of the perils that lurked in the shadow. However, his resolve was strong and he packed his things, an editor and few jars to survive the wastes of Javaland, and ventured forth. He travelled through the dull wastes where everything is private or protected and he has to ask things to do things for him. But as most people grew up in the land of Clojure, he knew that objects are but closure in disguise and he new how to bind them to his will with the power of the dot form.
After three days and three nights he eventually reached the Mines of Ruby and where massive gates blocked his way. He spoke the words as his master instructed (password: mellon), but the gate remained closed, for someone monkey-patched it and the door now spoke english, but the student did not know it and with failure in his heart he left the place, because he was trained in the ways of Lambda and could not cope with such a stateful abomination.
After months of wandering, he eventually reached Schemeland, where he at least could tail recur without recur. He spent another month drowning his pain into first class continuations and losing hope to ever come back to the land of Clojure, until one day he overhead the men telling tales at the tavern about a pythonista adventuring to Schemeland. The student sought the pythonista and eventually he found him and he asked him about the secrets of recursion and the pythonista showed him code and the student was happy because he knew classes are another word for closures and he was a master of closures. But he also understood that state was the missing element and he was saddened, because he also knew that state is treacherous.
Nonetheless, he felt he had come to far to be stopped by the formal purity of stateless programming and he eventually wrote the code. Little is known of what happened afterwards. Some claim he finally found his way to the lend of the Snake, after having extendedly monkey-wrenched the monkey patcher, other say that he went back to the Land of the Clojure.
I, your humble narrator, do not know the truth. I tried nonetheless to follow the student's step and implement myself the function that makes tail recursive calls without using recur. Ugly it is, and is indeed but an illusion, for recur lies inside the implementation. Still, it does the trick:
(defrec factorial [n acc] (if (= n 0) acc (factorial (- n 1) (* n acc))))
And here the code:
(defn uuid [] (str (java.util.UUID/randomUUID))) (defn tail-recursive [f] (let [state (ref {:func f :first-call true :continue (uuid)})] (fn [& args] (let [cont (:continue @state)] (if (:first-call @state) (let [fnc (:func @state)] (dosync (alter state assoc :first-call false)) (try (loop [targs args] (let [result (apply fnc targs)] (if (= result cont) (recur (:args @state)) result))) (finally (dosync (alter state assoc :first-call true))))) (dosync (alter state assoc :args args) cont))))))
4 comments:
Your defrec only works for tail recursive functions, so for example, this doesn't work:
(defrec factorial [n]
(if (= n 0) 1
(* n (factorial (dec n)))))
If it only works for tail recursive functions, you can just use the built-in recur, so you've gained nothing.
Of course, it does not work with not-tail recursive functions. No way it could. To do that you can, in some cases, use program transformations to write them in tail-recursive way. This is well studied and in some cases some other "shapes" can be optimized with constant stack, the problem in general is obviously indecidable, though.
I thought it was pretty clear that the game here was plainly not using recur, I did not claim anywhere that you could simply write functions the way you want and have them transformed into tail-recursive calls.
The morale of the story is another. We have seen how Python (which *by definition of the language* cannot have tail call optimization) can easily add a language level construct to avoid stack growth with tail recursive functions. Even if being tail recursive is a property of the function, relatively few languages exploit it, for various reasons.
Then I ported the idiom in Clojure. Since it uses relatively slow (compared to how the heavily optimized recur works) idioms, it is probably not meant to be used in general. As most of the times you will not be writing code in cps. You do it if you have a good reason to do so.
However:
1. some practical interest it might have, because it may be retrofitted and just works
2. it is mostly interesting to get insight on how things can be done, and being implemented in a high level language, without reference to specific implementation details. Please, notice that we are only using first order functions and some concept of state.
Well, in fact first order functions is not even a strict requirement (you could do that with objects used as functions). Basically, almost every compiler could implement that kind of stuff, i.e. "instrument" a function to make it work that way, which basically means just hijacking the tail call so that it jumps where we do the trick.
I greatly enjoyed this write-up. I like this "Land of Lisp" narration style! (ps. I'm Charles Stain :D )
Post a Comment