Xah Lee, 2002-02
Someone wrote: “iteration is Bad and tail recursion is Good”.
... i'm getting tired of writing this. There are just too many spurious stupid jargons that's meaningless and endlessly confusing, yet embraced and spoke by all monkey coders. What i am coming into, is the jargon “tail recursion”. What a fantastically stupid meaningless term that is so loved by the programing geeks. In every trickle of chance they'll flash it out to debate.
Now, let's talk about tail recursion.
I read the Structure and Interpretation of Computer Programs of Harold Abelson et al about 4 years ago. I recall reading the section on tail recursion. In particular, i recall how exacting and clear it explains the myths of looping away. To this day, i still hold their writing illuminating. (it is in reading their book, chapter i think 3 on functional dispatch, that it dawned on me what is OOP really about, far beyond any fantastically fucking stupid OOP tutorials and books.) Abelson et al is quite lucid in explaining that the time/space algorithmic behaviors of those for/while/until loops of imperative languages can be equivalent to recursion. And, the term “tail recursion” means implementation of recursion syntax in a language so that when it can be linear, it is so. (we should simply call it well-implemented recursion or something, instead of the fantastically stupid “tail recursion”.)
Xah Lee, 2002-02-11
Originally posted to “comp.lang.lisp”.
Dear Kent Pitman,
Thank you for taking the time to answer my thoughts about tail recursion.
Xah Lee wrote:
... My understanding of Scheme is very minimal. I'm not sure if i can even write “hello world” correctly in one shot. I don't know Common Lisp at all. ...
Kent Pitman wrote:
(Not that this disqualifies you from posting here, but this certainly leads me to wonder why you do both read and post here. Please don't take this as a challenge; I am just profoundly curious.)
Dear Kent, like you, i also am curious about lots of things. For example, i'm curious about why courtesans sell their pussies, and why pussies have profound attraction to me. I would and still do spend hours upon hours gazing them, finding it a great form of relaxation, more so than correcting droppings from comp.lang.lisp bigwigs, or enjoying Naggum's personal fantasies. Nevertheless, i'm aware your ramification and topic swinging abilities do not disqualify you from posting here.
The plain and longer answer, would be the following.
I come here to read Nagging Naggum's posts. I enjoy reading his posts. I learn English vocabularies. I would not say that i knew less words than Erik, but nevertheless i learn words from his writings, from totally new to usage example. I also cull off his fantastic opinions for my mulling. Lastly, i find his rants and spats with fellow human beings entertaining.
The second important reason for me reading comp.lang.lisp, is that i use it as on outlet of my meticulous crafted rants when opportune. I could pick other newsgroups, but in general it is not fun if the community does not welcome it. Trolling per se is not something that interest me. As it so happens, that i started to read lisp newsgroups around 1998 because i was learning Scheme, and i find the lispers in general much more educated than, say, comp.lang.perl.* in which i use to discuss on-topic perl related stuff now and then. So have i used comp.emacs or xemacs often, and some ohter mailing lists as well. In any case, my lavish rants tends to go to comp.lang.lisp.
The harmony of authorship and readership takes a matching. Imagine Einstein ranting his physics theories to 17th century physicists, he'd probably be kill-filed to death. Likewise, Larry Wall's drivel fits the unix moron's minds to a tee; and that i find comp.lang.lisp has the best readership for my rants among the few online discussions groups i use.
My vague motivation, is for me in the future to collect my rants and form a book. May it be a coherent account of unix & perl's damage to society, with technical criticisms, or similar attacks to the slew of fantastic fucking stupid imperative languages or the SQL language and other software “technologies”, or cogent commentaries on the idiocies of software industry such as the Design Patterns... i don't know. In the last few years as i write more and more, i find myself enjoy writing. I consider my act of writing soothing to my anger caused by unthinkers in society. When my rants are offensive to unhtinkers, i consider it a form of sweet revenge.
The other motivation is to educate people, but let's not talk about that. Once you tell people that, all sorts of things come flying against you, from hats of hypocrisy to spontaneous resistance. I find that the best way to educate, is by means of covert brain washing. I try to go in unassuming and rant my rants and get myself attacked and kill-file announced, but behind the scene i stab people's brain with sharp objects, jam their wires and screw their programs, totally shattering the world of their minds. And when they try to recuperate, to think ways of counter-attack, bang! I have succeeded in my goal.
Kent wrote:
My point was that iteration means exactly what you said: to move down an object of unbounded length using finite space to perform each iteration. Tail recursion (but not real recursion) shares this property because tail recursion implements/expresses/is iteration.
Thanks Kent for this concise recapitulation.
As you described, some Scheme fanantics are mislead by Ableson's dubunking of loop/recursion myth, to think that loop syntax should be avoided at all costs.
I believe this being plausible, or fact, and i think the culprit being: stupid terminology and jargons.
A quick look at the text on how the authors defined “tail recursion” found me:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.
From here we see the authors clearly indicated that the term “tail recursion” refers to a _implementation_.
I think few people when they discuss “tail recursion” do have a clear idea that the phrase refers to a implementation. “Tail recursion” being a stupid jargon itself, thus confusion begets confusion, and there we have endless meaningless arguments and throwings of opinions with far-reaching consequences, not unlike the many jargons i have discussed in my previous post.
imagine that people are info processors. In a newsgroup or general communication, people take muddy inputs from other people, process it with their imperfect processor, then express their output in a variety of muddy ways with these jargons galore. The process of _garbage in and garbage out_ are nevertheless useful, since people are not exactly machines. But, imaging if we get rid of these fucking stupid jargons and mis-representations and instead communicate on what we mean, what kind of percentage of stupidy we can get rid of society?
I propose that a part of those Scheme fanatics, where the Common Lispers accuse of being stupid tail-recursive purists, is in very large part due to the fantastic use and propergation of the term “tail recursion”. I propose, that we should ban the use of the term “tail recursion”. When refering to the concept of loop expressed in recursive form, simply say linear recursion. When refering to a good implementation of recursion that recognizes linear recursion, we simply should call it “good implementation” or something more descriptive. If this is achieved, i would say that the tail-recursive Scheme fanatics so accused would reduce in quantity significantly.
Next time you hear your colleague utter “tail recursion”, quickly grab a nearby book and whack his mouth. Look in his eyes, and say quizzically “do you mean linear recursion and good implementation of recursion?”. (if he says “What!?”, make a mental note that this guy didn't read Xah's opuses. Help him out. Resolve his mystery.)
Acute old-time Xah readers will detect that linguistics & logic is a theme in my writings, that i employ them and advocate them. The jargon debunking in this episode, is part of the grand scheme that English the language is the cause of fantastic stupidity in society. I wait for the day when human beings communicate by symbolic logic protocols. Just imagine what kind of unrestricted rich humor and nuance that entails, where humor can perceived more clearly, and muddiness can be muddier by intention.
Related essays:
Page created: 2003-06. © 2003 by Xah Lee.