Lambda the Ultimate

Language design is about making design choices about what to leave in and what to leave out. If you don't make some tough decisions about what to leave out, you'll end up with a big language. What's arguably the biggest modern language? Perl. Is that a good thing? I know what my opinion on that subject is.

That's an idealized version of the world. Charming, tempting even, but not the reality for the majority I suspect. I've seen a lot of people learn to program over the years, and the vast, vast majority are content to learn the bare minimum they can get away with it. They're simply not interested in rising with the tide because they were never fascinated by the subject in the first place. Unlike the tiny minority of us who inhabit sites like LtU, to them it's simply a means to an end. And the more complicated the means are, the less likely they'll get to their desired end.

This is not to say that I think metaprogramming or tail call optimization are necessarily bad. In fact I think the former is so important that I am doing a lot of work on it ATM. The latter I am currently um'ing and ah'ing about as you can see from the linked article. But I still have a large degree of sympathy with those Python people who are wary of additions to the language.

I wrote down some ideas along these lines as an article on downwardly scalable languages. I'm still mulling it over, but what you say here is very apt:

I've seen a lot of people learn to program over the years, and the vast, vast majority are content to learn the bare minimum they can get away with it. They're simply not interested in rising with the tide because they were never fascinated by the subject in the first place. Unlike the tiny minority of us who inhabit sites like LtU, to them it's simply a means to an end. And the more complicated the means are, the less likely they'll get to their desired end.

The really clever trick would be to make a language system that scales from our beginner just trying to get something done, all the way up to an expert.

The really clever trick would be to make a language system that scales from our beginner just trying to get something done, all the way up to an expert.

That's exactly what the PLT Scheme philosophy is all about. The module system allows one to program as if each module is written in its own language. For the book How to Design Programs (www.htdp.org) a series of languages all subsets of Scheme were made, that progressively made more and more of the language available.

Restricting a language for a beginner makes a lot of sense, since error messages can be made more precise - and written in terms that the beginner can understand.

But isn't this scalability also satisfied by C++ ( without ever being simple IMO )? Some users use just the C part, most of them use the object system and C's basic types and again much fewer use generic programming facilities.

I learned to program as a hobbyist among hobbyists, part of the first generation of home computer users in the UK, so it still surprises me whenever I come across someone for whom a programming language is simply a means to an end.

Even in the business world, the people I know who turned to programming as a way of achieving their business goals did so partly because they were attracted to programming in some way. Perhaps this is more unusual than my personal experience would lead me to believe.

I think it's in the nature of programming that people who like to reflect on their own practices are better at it (and also enjoy it more). Without that sort of metacognition, it's easy to get stuck in blind alleys - a discouraging experience in itself.

Get a compsci degree, but since the bubble burst here in the US, it might not be true anymore.

[tail call optimization] I am currently um'ing and ah'ing about

Your fib example seems to be more about tupling than about tail recursion. Perhaps a better example would be to sum over a list by recursion, where you'd have to introduce an accumulator to make the function tail recursive.

I can't remember too many people on LtU bitching about the lack of tail call optimisation in Python or Java compilers. Personally I don't think it's that important, because you can't have everything in one language.

Another issue is adding it to the virtual machines. If it's cheap for you to add tail call capabilities to your VM, please consider doing so. It will allow implementators of FPLs to target your VM.

I can't remember too many people on LtU bitching about the lack of tail call optimisation in Python or Java compilers.

I don't bother to bitch about it usually because there's not much point, here. I think quite a few people on LtU understand how important it is. After all, one only has to read and understand the papers after which this site is named, like "Lambda: The Ultimate Imperative", to understand the importance of TCO.

However, it's not just about functional languages. Recursion is more fundamental than that.

Personally I don't think it's that important, because you can't have everything in one language.

It is important. It's not about having "everything", only the minimum necessary. The Python world has made a big mistake here, led by their benevolent dictator. The mistake is in seeing iteration and recursion as an either/or choice: that if the language has good support for iteration, then it doesn't need to support recursion well. However, even if you take the position — as Guido apparently does — that iteration is a more natural way to think, that can only credibly be argued for some subset of all problems. Guido would presumably say it's a large subset. However, there are many problems for which recursion is demonstrably the most natural solution, in terms of the simplicity of the resulting programs. By refusing to properly support recursion, Python limits itself unnecessarily.

It's analogous to driving a car that can't turn left — you're OK as long as you don't need to make too many left turns on your trip. Otherwise, the right-turning loops you have to make when you need to turn left get tedious after a while.

Unfortunately, such a limitation blinds people to the existence of left turns. To them, a left turn is a right-turning loop, and their mental model of their problem domains and algorithms are structured in this way, avoiding left turns even when they're the simplest solution. Ian Bicking would presumably claim that this is a good thing, that it allows people to more easily become experts, because they only have to become experts on right turns.

The only sense in which that's true is if you've been brought up, from birth as it were, in an environment which emphasizes right turns and demonizes lefts. This is self-fulfilling. Switching back to the real situation, the historical development of most programming languages emphasized iteration over recursion, which resulted in a situation in which many people are far more familiar with iteration than recursion. Worse, they can't even experiment with recursion to learn about it, because none of the languages they know support it well.

As a result, a lot of FUD tends to surround recursion and its supporting infrastructure. One of the biggest pieces of FUD is how difficult or confusing it is. This is more about people protecting the areas of their own ignorance. You'll see people saying things like "Trust me, it would melt your brain", but that's a euphemism for "even I don't fully understand it, therefore it must be really hard". The truth is that most programmers find it really enlightening if they only bother to learn about it.

Java and Python are essentially in the same category as the original FORTRAN in this respect. They haven't learned much from the past 50 years, ever since someone came up with the original call/return model of control flow.

Saying "you can't safely do recursion in this language" is equivalent to saying "stay away from this language for all kinds of advanced applications". Extrapolating from what Ian is saying, such restrictions may be Python's goal. But that closes many doors for Python.

I think there is a danger in conflating the concepts of recursion (an obviously good thing, in my book at least) and tail call optimization (a useful thing in some circumstances, but not something I would considera absolutely fundamental). I think you can have practical support for fairly advanced useages of recursion even without tail call optimization. I wonder whether the conflation of these concepts goes back to the time when most systems had a fixed stack size, and recursing past that point caused all sorts of problems? IMHO decent modern implementations should allow the stack to grow to available memory at which point tail call optimization seems, relatively speaking, less of a burning issue to me.

Of course, I agree that recursion and TCO aren't the same thing. But TCO is nevertheless "absolutely fundamental" in that it's required in any case where recursion isn't bounded by some reasonably finite value. Simple example: a server program which uses a tail call in its main loop — do you really want your server to consume ever more unreclaimable memory on every request it serves? Of course, there are many less trivial examples.

The common Python-style response to this is that you can program such an infinite loop using an iterative loop construct, so there's no problem. But this comes back to my basic point, which is that either you provide good support for recursion, or you don't. If you provide good support for recursion, then you should be able to use a tail call to implement an infinite loop. Python is taking the approach of not providing good support for recursion. The result is that the "experts" which Ian Bicking wants to help create will run around thinking that recursion is difficult, problematic, and to be avoided, just because Python doesn't allow left turns (mixing my metaphors).

Saying that you can use recursion up to the limits of available memory — which means that applications which rely on certain types of recursion will be very memory-hungry, for no good reason — is not providing full support for recursion.

I think you can have practical support for fairly advanced useages of recursion even without tail call optimization.

Any examples of languages that qualify? Besides, amongst the "fairly advanced" uses of recursion that are excluded by your suggestion are some incredibly simple uses, like the server loop I mentioned earlier. You certainly can't even think about CPS parsers in languages which don't do TCO, unless you're willing to work around the problems by writing trampolines, which tends to negate the simplicity advantages.

I think there is a danger in conflating the concepts of recursion (an obviously good thing, in my book at least) and tail call optimization (a useful thing in some circumstances, but not something I would consider absolutely fundamental).

Recursion is fundamental, yes. But loops are also fundamental. Why? Because algorithms that accumulate bounded control context during computation are fundamental. However, for and while are only two special cases of such algorithms. They are easy to implement in a language with proper tail recursion and either higher-order functions, call-by-name semantics, or macros. But other kinds of iteration cannot be easily expressed with for or while.

You're right that the issues of general recursion and tail-recursion are not identical, but they are very connected. Proper tail recursion is not just important for algorithms that are already tail-recursive. Any function that is not tail-recursive can be refactored into one that is. This is a transformation that functional programmers are quite comfortable with, a standard optimization technique in the programmer's toolkit. But this is impossible to do without painful contortions in a language without proper tail recursion.

IMHO, decent modern implementations should allow the stack to grow to available memory at which point tall call optimization seems, relatively speaking, less of a burning issue to me.

Neither Python (cf. the misnamed "maximum recursion depth exceeded" error) nor Java (StackOverflowError) nor C# (StackOverflowException) is currently decent according to your prescription. But I agree, that would be great - and is great in some very nice languages! However, without proper tail recursion there would still be many algorithms that would chew up all available memory for no good reason.

It is important. It's not about having "everything", only the minimum necessary. The Python world has made a big mistake here, led by their benevolent dictator.

We have (a) a community of developers, many of which are skilled, (b) are using the language intensively for a full spectrum of tasks, (c) many of whom have extensive experience with Lisp, (d) people do frequently write recursive functions in Python, and (e) there are several paths to suggest changes to the language, both casual and formal. But really people don't care.

When I say don't care, I mean: there are no champions who speak from a perspective that is meaningful to Python.

Googling, it came up last July, and pretty much no one cared, even the author, and there were several practical reasons why it wouldn't happen. I think language theorists and mathematicians care about TCO, and that's about it. Really, I just brought it up as an example, I don't really care that much about it either.

Well, this was Guido's response:

I'm not interested in adding this to the official Python release.

One reason is that if an exception happens in such a tail-recursive call, the stack trace will be confusing.

Another reason is that I don't think it's a good idea to try to encourage a Scheme-ish "solve everything with recursion" programming style in Python.

Another reason is that I don't think it's a good idea to try to encourage a Scheme-ish "solve everything with recursion" programming style in Python.

This is an example of the either/or attitude Guido has to recursion (this is not the only example, but I'll have to dig for others). He's arguing against supporting a useful language feature because of the risk that it will encourage attempting to "solve everything" with that feature. IOW, he's restricting recursion because he's afraid it might be too useful?!

Seriously, what's wrong with supporting a feature because it might be appropriate in certain circumstances?

I agree that this reasoning is silly.

Python has done something similar before: it did not use lexical scoping. There were only three scopes: current function, current module's globals, and builtins. I recall one of the reasons, other than interpreter simplicity, was that nested functions should be discouraged; "flat is better than nested".

When people used nested functions nevertheless, with a hack for making a closure (adding default parameters initialized to outer variables of the same names), Python finally gave up and changed its scoping rules.

It's worth reiterating that Python still does not support lexical scoping. What Python now does is that it determines lexically a list of dictionary objects that it dynamically consults to figure out variable bindings. Since the dictionaries are mutable objects, it is not in general possible to determine variable scope statically.

There should be a name for this scoping discipline. I used to call it whacky scoping, but perhaps a more sober name would catch on. FWIW, newlisp uses this notion of scope as well.

You are completely wrong. Python does support lexical scoping. First of all it is wrong that variables are generally stored in dictionarys. This is true for member variables ( of general objects/modules ) but is wrong for functions local variables that are stored in arrays. If a LOAD_FAST opcode is executed the current stack frame contains the index of the local variable for look-up in the locals array. The best way to see how scoping works is to disassemble Python code.

from dis import dis
x = 0
def f():
    print x

>>> dis(f)
  2           0 LOAD_GLOBAL              0 (x)
              3 PRINT_ITEM          
              4 PRINT_NEWLINE       
              5 LOAD_CONST               0 (None)
              8 RETURN_VALUE        

Once a local variable x is defined in f the global x will not be accessed unless it is declared in f's code block using the "global" keyword.

def f():    
    print x    # raises an error
    x = 0      

>>> dis(f)
  2           0 LOAD_FAST                0 (x)
              3 PRINT_ITEM          
              4 PRINT_NEWLINE       

  3           5 LOAD_CONST               1 (0)
              8 STORE_FAST               0 (x)
             11 LOAD_CONST               0 (None)
             14 RETURN_VALUE        

We see immediately that the LOAD_FAST opcode must fail because STORE_FAST is executed later.

This pattern does not change if we nest f using a closure g:

def f():
    def g():
        print x
    return g

g = f()
>>> dis(g)
  3           0 LOAD_GLOBAL              0 (x)
              3 PRINT_ITEM          
              4 PRINT_NEWLINE       
              5 LOAD_CONST               0 (None)
              8 RETURN_VALUE        

The compiler is by no means confused about the scope of x and does not guess that it persists in the dict of f ( which is empty! ).

def f():
    x = 0
    def g():
        print x
    return g
g = f()
>>> dis(g)
  4           0 LOAD_DEREF               0 (x)
              3 PRINT_ITEM          
              4 PRINT_NEWLINE       
              5 LOAD_CONST               0 (None)
              8 RETURN_VALUE        

Here g uses a LOAD_DEREF opcode that accesses x from a cell object that stores x for reference by multiple scopes. In this case f does not execute LOAD_FAST/STORE_FAST but LOAD_CLOSURE/STORE_DEREF opcodes.

If we define x also in g it will be accessed locally using LOAD_FAST:

def f():
    x = 0
    def g():
        x = 0
	print x
    return g
>>> g = f()
>>> dis.g()
  4           0 LOAD_CONST               1 (0)
              3 STORE_FAST               0 (x)

  5           6 LOAD_FAST                0 (x)
              9 PRINT_ITEM          
             10 PRINT_NEWLINE       
             11 LOAD_CONST               0 (None)
             14 RETURN_VALUE  

In this case no cell is created for x and f uses LOAD_FAST/STORE_FAST again.

One final remark. It is possible to reflect about the locals f has created. They will be represented as a dictionary. But this does not mean that changing the dictionary also changes the locals. From the code analysis given above it should be clear that this is impossible. The bytecode is immutable.

def f():
    x = 0
    v =  vars()
    print vars
    v["x"] = 7
    print vars()

>>> f()
{'x': 0}
{'x': 0, 'v': {...}}

Python functions have static scope
You are completely wrong. Python does support lexical scoping.

"Completely wrong" is a bit harsh. Lexical scoping were introduced in Python in April 2001 and it wasn't until version 2.2 that it were made the default scoping rule.

An related (at least in my book) issue is that
Python to my knowledge doesn't support closing over writeable values.

"Completely wrong" is a bit harsh. Lexical scoping were introduced in Python in April 2001 and it wasn't until version 2.2 that it were made the default scoping rule.

Yes, but Charles Stewart insisted in "reiterating" a wrong assertion and it is wrong for quite a couple of years.

An related (at least in my book) issue is that Python to my knowledge doesn't support closing over writeable values.

Let's say it in Python slang: you can't rebind a name of an outer scope. The only exception are globals that can be accessed using the global keyword. There are known workarounds ( usually a value is put into a list and one has to read/write list elements ). This might not be satisfactory at least not for a Schemer with class-Angst ( creating classes in Python is as cheap as creating functions ).

I'm not sure if a future version of Python will introduce a var keyword or something similar that enables a name of an outer scope being rebound. In this case I would expect that the whacky scoping semantics Charles Steward mentioned would be valid for var-tagged names. Another possibility would be redefining the "global" keyword semantics without introducing a new opcode.

I missed the above comments first time around.

If I am not mistakened, the then current python language standard permits, but does not mandate lexical scoping, but explicitly allows for scopes to be implemented by mutable dictionaries, though deprecating this as something that might not be allowed in future specifications. That some implementations have lexical scoping is not really the point (though my post did mistakenly talk about what python implementations do, rather than may do): you cannot assume lexical scoping when writing code, hence it is hard to write code that can't be defeated by implementations that conform to the standard.

What I wrote was based on the language standard, and not on tests of particular implementations. I might still be wrong, and I'd be grateful if the places in the language standard that show that I am wrong could be pointed to. I did check my post carefully against the standard when writing the post that offended Kay, but I will admit to finding the python standard harder going that certain other language standards....

Charles, I'm not sure what you are referring to? I refer to PEP 227 which defines scoping rules for Python. This document stems from Nov. 2000 and the CPython implementation is quite around for a while. If you have contradicting sources I would be interested in them.

The juridical problem of what has to count as the true "standard Python" is solved pragmatically by referring to CPython ( PEPs, docs and reference implementation ) as the de-facto standard - at least until know. I have no indication that this is going to change. Dialects like Stackless-Python or other implementations like JPython and IronPython that exploit platform specific strengths did not yet generate conflicting claims. I agree that it is sometimes hard to distinguish between Python as a language and the specification of its reference implementation. The threading model is the most visible entity of deviation. I guess Python is not different from most open source projects in this respect. I'm not sure this is a deficiancy. I would say it depends always on the phase of the projects life-cycle, the public requirements and the social conflicts among competing teams.

BTW if my comment sounded overly harsh than less because of a wrong technical detail but the "reiterated insistence" on it. I hope I contributed to more clarity nevertheless.

I'm not sure what text I was looking at, but the loophole I thought I saw is excluded in both the current language reference (for 2.4.2) and the then current version (for 2.4.1). Scoping rules are given in sections 4.1 and 4.1.1, which describes the scope as a tower of frames, enumerates the language primitives that are allowed to add variables to scopes (all of which behave lexically) and forbids any feature to remove variables to any scope but the current frame. It's a fairly roundabout way of specifying lexical scope, but I think it's watertight.

I'm guessing I must have been looking at an older standard, and thought it was current.
When I have a bit more time, I'll try to track it down.

I don't agree with your comments about pragmatic language definition: it's fair enough to use an implementation to test-drive proposed language features, but it's important to be able to write code in a portable way, and, pragmatically-speaking, a language standard is an importanty guarantor of predictability when doing this. BTW, didn't the stackless fork become CPython?

Guido has made many pro-iterative and anti-recursive remarks, at many different times. I'm sure that's a strong reason that it's not a "topic of much debate" in the Python community.

As for whether people care, I come back to my point. If all you've learned about is left turns, you're not going to care about right turns until you've gone through the process of learning what they are, how they work, and why you should care. When your benevolent dictator is telling you to drop it, that's a strong disincentive against learning more about it. So much for helping to create "experts".

I think language theorists and mathematicians care about TCO, and that's about it.

All users of functional languages care about it, or at least, depend on it. That's a group that goes well beyond language theorists and mathematicians. Erlang users are one such group, and most Erlang users are neither language theorists, nor mathematicians (afaik!)

However, as I've said, there's nothing about recursion that makes it unique to functional languages. All that's achieved by refusing to implement TCO in an imperative language is that the power of recursion is severely limited, unnecessarily.

This is true, but I think he really meant that nobody much in the Python community cares about TCO, despite many of them knowing functional languages.

However, as I've said, there's nothing about recursion that makes it unique to functional languages. All that's achieved by refusing to implement TCO in an imperative language is that the power of recursion is severely limited, unnecessarily.

Never so simple! For one thing, if you added TCO then you've added another way of doing the incredibly basic task of iteration. That's right against the Zen of Python: There should be one-- and preferably only one --obvious way to do it. Properties like that are extremely important in my opinion (e.g. they're what make Erlang better than Lisp) and only people who really use the language can appreciate them. Not being a Python-hacker myself I'd give them the benefit of the doubt.

I'd have a similar objection to adding loops to Erlang.

That's actually something I've never quite understood. What is the importance of having only one way to do things? I'm aware that people feel Common Lisp is too much of a kitchen sink, but the problems with this are 1) difficulty in producing and maintaining an implementation of such a large language, and 2) the steep learning curve.

I don't think (1) is an issue here, but I don't see (2) as a valid argument against having multiple ways of doing things. It's just an argument for building a language or its development environment in such a way that it can be learned in successive iterations. This is why I like DrScheme's language levels so much. But if I believed a language should be as simple as possible, then e.g. I wouldn't want a module system since I can implement a module as a higher-order procedure that is parameterized over all its imports.

Are there other reasons for wanting there to be only one way to do things?

It's a misguided language aesthetic. Another way to say "there is only one way to do it" is "there are no correctness-preserving program transformations."

In Scheme, one can write a program that uses higher-order functions. Then, one can defunctionalize it to use first-order data structures (like records) instead. That's another way to do it. Solution? Remove higher-order functions from the language.

Then, one can CPS (with defunctionalized continuations, of course) to explicitly expose control. That's another way to do it. Solution? Remove proper tail-call handling to prevent CPS.

Etc, etc, etc.

Without more than one way to do it, it is not possible to write a simple program that works and then gradually transform it into something more efficient. Instead, every program is doomed to be not simple, or not efficient, or both, right from the start.

Or else you think it is a language designer's job rather than the programmer's to come up with a simple and efficient solution to all the problems that are solvable in the language. HQ9+ is a language like that, but otherwise I don't think it will ever work. It is certainly at odds with having a small language.

Are there other reasons for wanting there to be only one way to do things?

It's a social/community/managerial thing - it's supposed to result in everyone doing things the same way, so that in theory, when dealing with other people's code, you know what idioms to expect in a given situation, and there are fewer surprises and less variation between code written by different people.

But soft criteria like this are open to interpretation, and the people who want to interpret them the most tend to be those with the weakest technical argument. (That's just a general observation, not directed specifically at Luke's mention of TOOWTDI.)

Perhaps I should just go with the flow and point out that the principle of least surprise dictates that recursion should be unrestricted. Check, and mate. ;)

Who expects this particular optimzation? The basic operational model for function calls allocates stack space (or other space). Understanding stack overflow comes before understanding tail call optimization. The principle of least surprise would better argue that tail-recursive functions may overflow the stack.

TCO is important to me and I agree with the arguments in its favor. However, "unrestricted recursion" amounts to an appealing, but inaccurate re-labeling of TCO.

...would be when a minor change to a recursive function causes a stack overflow (i.e. a change that suddenly makes the call non-tail recursive). Which is why I think that the tail-call should be explicit, like Luke indicated.

TCO is important to me and I agree with the arguments in its favor. However, "unrestricted recursion" amounts to an appealing, but inaccurate re-labeling of TCO.

With Clinger-style "proper tail recursion", recursion is as unrestricted as it can possibly be while still having a correct program. I think it's reasonable to call that "unrestricted recursion", used in context, although I'm open to alternative descriptions that are a bit more snappy than e.g. "recursion which isn't unnecessarily restricted".

Who expects this particular optimization? The basic operational model for function calls allocates stack space (or other space). Understanding stack overflow comes before understanding tail call optimization.

If you teach people that recursion must always use stack space, then TCO will be a surprise, certainly, but that's only because you started out by misleading them. If that was intended as a convenient pedagogical "lie" which will later be corrected, fine, but then it's your responsibility to correct it.

Most people learn programming by doing it, especially in informal contexts. Anyone who's ever been surprised by hitting a recursion limit is demonstrating an expectation that recursion should work better than it actually does. It's not a question of expecting a particular optimization, it's expecting a syntactically & semantically legal program to work. Proper TCO satisfies this expectation to the greatest degree possible. Many of those instance of hitting recursion limits would not have happened in the presence of TCO.

The remaining instances of hitting the limits are learning experiences, in which the programmer needs to learn that there are limits on the ability to make recursive calls that aren't tail calls. It's something that's quite easy to explain simply based on local inspection of the affected code. It only gets elevated into a bogeyman by people who have ingrained experience with a more constrained approach.

Who expects this particular optimzation? The basic operational model for function calls allocates stack space (or other space). Understanding stack overflow comes before understanding tail call optimization.

Here's a reduction sequence for a tail-recursive factorial (using eager evaluation despite Haskell syntax),

fac n = fac' n 1
    where fac' 0 acc = acc
          fac' n acc = fac (n-1) (n*acc)
fac 4 ->
fac' 4 1 ->
fac' 3 4 ->
fac' 2 12 ->
fac' 1 24 ->
fac' 0 24 ->
24

Where is this stack that is overflowing? I guess I'll just have to add one in just so it can overflow.

Understanding functions comes before understanding stack overflow.

Out of curiosity, I wrote the above in Python, just to see what it would do:

#!/usr/local/bin/python
def factorial_tco(n, acc):
   if (n == 0):
      return(acc)
   else:
      return(factorial_tco((n-1), (n*acc)))
def factorial(n):
   return(factorial_tco(n, 1))
print factorial(998)

No error on 997, blows up on 998 with:

  File "D:\Python\hello.py", line 9, in ?
    print factorial(998)
  File "D:\Python\hello.py", line 8, in factorial
    return(factorial_tco(n, 1))
  File "D:\Python\hello.py", line 6, in factorial_tco
    return(factorial_tco((n-1), (n*acc)))
**** previous two lines repeated 996 times ****
  File "D:\Python\hello.py", line 6, in factorial_tco
    return(factorial_tco((n-1), )
RuntimeError: maximum recursion depth exceeded

I guess the first thing I don't get, even before we talk about the usefulness of tail calls from the end user perspective, is why a self tail call is not optimized. Saves stack space and cuts significantly down on the number of instructions by effectively making it into a loop. End users wouldn't care, since they if they understand an error printed once, they probably won't be any more elightened seeing it an additrional 998 times. They just want to get at the one meaningful message (which is where the error occured). IMHO, self tail call optimization is a pure optimization and doesn't effect the ability to decode a stack trace.

Now the question back is whether mutual recursive routines should be TCO'd. Optimizing locally seems to be a no-brainer for this untrained mind. No different than all those fancy loop unrolls, etc...

Unfortunately this appears to be the case if, and only if, said function contains one self tail call. AFAICT even functions with more than one self tail call can not be guaranteed to recover the necessary information for a stack trace in constant space.

Optimizing locally seems to be a no-brainer for this untrained mind.

It seems like you could even do it naively at the bytecode level as a peephole optimization by checking for CALL-RET instruction sequences. (You probably wouldn't want to do this in the bytecode interpreter itself as it would penalize non-tail calls.)

Unfortunately I can't give a reason crisp enough to fit in this now rather narrow margin. I'm picturing my favourite feature-poor language and some of the very reasonable changes that one could ruin it with.

Thought experiment: if you could take control of Guido and make him change Python in any ways you wanted, would the language become more popular or less popular?

This is true, but I think he really meant that nobody much in the Python community cares about TCO, despite many of them knowing functional languages.

I was responding to Ian's comment that only "language theorists and mathematicians care about TCO". That's not true even amongst Python users. The subject of limits on Python's recursion comes up regularly. There's even a stock answer, which is that recursive algorithms which hit the recursion limit should be rewritten iteratively. Many of the people who run into this restriction may not realize that in most cases, TCO would eliminate the restriction. This means that many Python users do "care about TCO", whether they realize it or not, in that they care about the improved recursion capability it can provide them with.

Never so simple! For one thing, if you added TCO then you've added another way of doing the incredibly basic task of iteration. That's right against the Zen of Python: There should be one-- and preferably only one --obvious way to do it.

I disagree that TCO violates that precept. If a language has 'for' loops, for example, then that's the one obvious way to do that kind of iteration. The same goes for all other specific iteration constructs. The presence of TCO wouldn't make Python's iteration constructs any less obvious as the designated way to achieve iteration, and documentation and community standards would reinforce that.

The point of adding TCO is not to provide an alternative way to perform loops, but to provide a way to do some things that Python currently has zero obvious ways to do — or more accurately, where the obvious way is unnecessarily complex, such as requiring manual creation and management of a stack, rather than being able to make use of the language's stack.

Not being a Python-hacker myself I'd give them the benefit of the doubt.

The problem is that restricting function or method calls like this in a general-purpose language would require a pretty big doubt to justify it. No-one has raised anything that big. The only real technical issue is that of stack traces, which is a relatively minor issue, and one which many other languages have been dealing with successfully for decades.

I think the real reasons here are historical and psychological. Many language implementors didn't used to know about TCO, so languages didn't support unlimited recursion. As a result, recursion is ingrained in many people's brains as something that's of restricted value, to be avoided in most cases. This even leads people to believe that iteration is somehow a "natural" way for humans to think, and that recursion isn't. Guido is one of those who has claimed that. However, it doesn't take much examination to find that there are at least some problems for which recursive solutions are more natural, in that the recursive solutions are easier to write and easier to understand.

In fact, recursion is no more an unnatural way for humans to think than functions and function calls are. Once you introduce functions, you have to train people not to use recursion, as the Pythonistas who run into the recursion limits demonstrate. What's the rationale for restricting recursion? It used to simply be that language designers didn't realize they didn't have to. That's no longer an excuse. Can anyone come up with a real reason?

The ironic thing is that we're talking about a bug whose presence in the language implementation, and in people's minds, makes it difficult to detect that it is a bug. They don't think it's a bug, because they "know" recursion is unnatural and even dangerous — but the only reason they "know" that, is because their language implementation has a bug which makes it so. It's a recursive bug, which is particularly difficult to detect when one makes a habit of avoiding recursion...

Python was my first love, and it's still how I make 99% of my income, but I blow the max recursion depth regularly.

I do agree that there should be only one way to do iteration, but nowadays I think it should be recursion and no loops. Once I learned Haskell, I never wanted to go back to Python, Python is too restrictive.

I also feel that Python has become cluttered with too much syntax. What do you think of the decorator syntax in Python? Would you recognize it if you saw it?

I learned Python 1.4 in eight hours, and I could immediately read all the Python sources I found. These days I can't teach experienced programmers all of Python in eight hours. I think that will decrease the flow of new users into the Python community, and new users are the lifeblood of any community.

-- Shae Erisson - ScannedInAvian.com

Yep, a statically typed, strictly purely functional language with an even smaller community and libraries and Python is more restrictive... yeah, right! give me a break!

I showed some of the best features of Python to a friend of mine ( dynamic typing, list comprehensions, OO or procedural style, easy documentation and introspection ) and he was able to grasp the concepts with great enthusiasm. It was about our lunch time. Granted, he's a programmer already and well aware of the OO paradigm, so it was not so much of a big deal.

Python _is_ a small language and ( except for some max recursion level constant ) not restrictive at all.

Haskell is effectively compile-time dynamically typed because of type inferencing. I declare the same amount of type information in both my Python and my Haskell programs. This is not static typing like in Java or C.

Purely functional means that I can separate side-effects, they're only inside an IO type. Debugging J2EE or Zope would be a lot easier if it were obvious which code has side-effects, and if state were explicitly passed.

When I use Python, some of the things I miss are multi-line lambdas, partial application, tail call optimization, pattern matching, and algebraic data types.

I am still convinced that Python is more restrictive. Have you used Haskell and Python for similar tasks? How would you compare and contrast the languages?

--Shae Erisson - ScannedInAvian.com

I doubt that this particular line of argument will go anywhere very illuminating (it may end up sinking ignominiously into the Turing tar-pit).

I personally find Haskell more expressive than Python, meaning that I can capture the meaning of a program very much more succinctly in Haskell. Haskell seems to me to fulfil Paul Graham's desideratum about being able to define a program one layer of abstraction at a time. Python's emphasis on OOP as the one-way-to-do-it introduces a level of latency (or friction) into this process that you don't even notice until you switch to something that allows you to do-it-differently.

Be that as it may, restriction and expression are not opposed. Syntax and grammar restrict and enable linguistic expression. In Haskell, you are able to take a small set of rules and construct a larger set, qualifying one restriction with another, so that the meaning of a program becomes clearer in some ways as you go along. That clarity entails ruling out some possibilities and mandating others.

The purported advantage of dynamic languages is that less is ruled out in advance: saying that something can happen does not entail saying that only that thing can happen. By being less explicit about the criteria for failure and success, you expose yourself to unforeseen varieties of possible failure but also facilitate subsequent redefinitions of success. Sometimes it doesn't pay to be too clear about what you want - the more you express now, the more you may have to take back later.

There's not one such a thing.

Dynamic, or latent, typing has less to do with type declarations and more to do with the fact that variables -- or expressions -- are not bound to a statically specified type. That way, a camel is always a camel and won't suddenly become a dog.

But sometimes it's desirable such flexibility, which Haskell won't provide unless you change the whole expression -- the program -- and go.

Granted, my experience with Haskell ain't all that great. But what i've seen was enough. I won't ever exchange Scheme or Python flexibility and syntax expressiveness for static program correctness checking or some crazy way to manage IO side-effects.

Off-topic: i just had this weird bug while posting which alerted me that there was some "suspicious data" in the text. Well, i tried a lot of things to manage to get the text posted. In the end, it turned out that it wasn't accepting my parentheses, so i took them off and replaced them by --

weird...

Maybe the software likes static typing and considers any opinion for dynamic typing to be suspicious.

Actually, Anton mentioned before that the Drupal software has a check for malicious javascript code. And it appears to be a bit on the false positive side.

A stroke in the right hemisphere of the cerebral cortex can cause a person to lose the very concept of leftness: they cannot turn to the left nor turn other objects to the left, because the whole area to the left of their body's center line simply does not exist.

And some of them do learn to compensate by turning further to the right, or to eat a whole plate of food by eating the right half, rotating the plate 90 degrees to the right, eating the right half of what remains, and so on.

You mention two problems of tail call optimization (TCO),

There are two chief costs associated with tail calls and their optimization. The first is fairly obvious, and is evident in the forced rewriting of the Fibonacci function: many functions have their most natural form without tail calls.

This is true, but how you consider it a problem of TCO is beyond me. If you don't have TCO you still have to rewrite the function using iteration and, given higher order functions, it can't be anymore natural iteratively than with TCO (modulo a "constant factor") because I can write a HOF implementing any iteration control structure given TCO. However, you add

What's more, as can be seen from the Fibonacci example, the resulting function is frequently hard to understand because it often requires state to be passed around in parameters.

Obviously FP people would claim that that makes the program easier to understand, but regardless, TCO doesn't force this upon you, you can certainly use lexical nesting (assuming the language supports it) and mutate the local variables (or global/member), e.g. in an impure Haskell,

fib n = fib' n
    where (current,next) = (0,1)
          fib' 0 = current
          fib' i = (current,next) := (next,current+next); fib' (i-1)

I could have had i be mutated too, but that seems less clear as it's the control variable, at any rate it would be a minor change. In fact the similarity of this to the pure tail-recursive version or to a for-loop is obvious, though it would be a bit less obvious if I hadn't posited a parallel assignment operator (which many languages lack). Of course, for the pure version it's a non-issue; you get "parallel assignment" for free.

The other problem (missing stack trace information) makes a lot more sense, but isn't insurmountable. Many people have mentioned that you can keep a finite amount of otherwise unnecessary stack frames around which should be all that's necessary in most debugging scenarios. When that is not enough the implementation could simply keep track of all call frames utilizing filtering, abbrieviating, and/or logging techniques for example.

Finally I want to mention that this isn't just a problem when using a functional style. If you endeavor to replace case-analysis with OO dynamic dispatch, you will again run into problems due to lack of TCO (beyond the ones that come up anyways).

I did try to be very careful with my use of language, although I think I probably wasn't clear enough. I was trying to distinguish between tail calls and tail call optimization. The Fibonacci example is, to me, an example of why trying to mash everything into a tail-calling form is not a good thing - this is entirely independent of whether tail-call optimization is in place (although admittedly people probably wouldn't bother doing the mashing if it weren't). The stack trace issue is an example of why tail call optimization itself can cause problems.

My problem is that I want to be able to produce accurate stack traces at all times but, as I explained in my blog, I don't see how to do that in finite space in the presence of functions with multiple tail calls. And if I can't make a guarantee about finite space and tail calls in all situations, I would rather not add tail call optimization in since it'll confuse me even if it confuses noone else. I genuinely would be interested to see if there's a way of allowing tail call optimization whilst preserving this requirement. It's via this article that I discovered that other people - the Squeak fellows, at least - have bought up the stack trace issue at some point so maybe someone has an answer.

My problem is that I want to be able to produce accurate stack traces at all times

One problem here is that when the function call mechanism is used to achieve iteration, there are cases where requiring a stack trace is "unfair". For example, you don't expect a stack trace which includes each iteration of a for loop — why do you require it ("at all times") when such a loop is implemented using a tail call?

I'll do you a deal: you tell me how I can teach a programming language the difference between fair and unfair and I promise to add tail call optimization into my VM ;)

How about allowing a compiler to specify when stack traces are required, perhaps by providing two different tail call operators? Then when an iterative loop is being generated via a tail call, it can just use the "no stack trace required" operator.

This would also allow flags applied at the source level, by the user, to control the strack trace behavior of the generated bytecode. Settable flags might include "no stack trace on iterative constructs", "no stack traces on tail calls", and "no stack traces on self-tail calls", etc. A language might even choose to allow stack traces to be requested or prevented in the source code. At the VM level, all you have to do to support all these options is provide some alternatives.

(define-syntax non-tail
  (syntax-rules ()
    [(non-tail e)
     (let ([result e]) result)]))

(define (breakpoint? n)
  (= n 7))

(define (fact-not-iter n a)
  (cond
    [(breakpoint? n) (error 'breakpoint)]
    [(zero? n) a]
    [else (non-tail
           (fact-not-iter (- n 1) (* n a)))]))

(let ([result e]) result))
  <=>
((lambda (result) result) e)
  <=>
e

Burn TCO! Burn eta-conversion! Down with Lambda, up with von Neumann! etc, etc!

Interesting question. Just musing...

<hacker>
Yeah, it is true that a compiler may perform let-conversion. Thanks to the halting problem there are always ways to get around this, but that's not a particularly pleasant answer.
</hacker>

<semanticist>
Now, equivalence relations are always defined "up to" some differences you choose to ignore, and beta-equivalence (as in your example) does not observe stack efficiency. So if you use beta equivalence to perform a compiler optimization you are implicitly saying, "I don't care about tail position, my equivalence ignores that property." Put another way, the equivalences demonstrate the correctness of the code, not its efficiency. But this isn't the best response, either; to quote Will Clinger, "asymptotic decreases in runtime efficiency are not the sort of property that endears you to a programming community."

The reason is that the equivalences mod out issues of efficiency for the sake of discussing correctness, but if the code were truly equivalent, as in, not observably different, there would be no reason for the compiler to perform the transformation in the first place. So a transformation involves two relations: one is the equivalence relation that demonstrates the correctness, and the other is the "improvement" relation (I'm not sure what the real term for this is) that demonstrates the resulting code is more desirable in some way.

We're pushing the limits of my knowledge of compilers, but I imagine this just comes down to which kind of property you treat "tail-positionness" to be. If it's a correctness criterion, then no transformation you perform may change an expression's tail-positionness. If it's an improvement criterion, you might imagine that turning a non-tail-position expression into one in tail-position would be an improvement, but not vice versa. In this case, my code would definitely be incorrect, because let-conversion is valid.
</semanticist>

I should note that none of this really argues anything about whether proper tail recursion is a desirable language feature; it's more about whether my little hack was a correct way to defeat TCO. In the end it's not a big deal; you could either off-load the responsibility to the compiler and make non-tail a primitive, as Anton suggested, or you could be a hacker and just figure out what implementation defeats the compiler's optimizations.

Burn TCO! Burn eta-conversion! Down with Lambda, up with von Neumann! etc, etc!

:P

As for TCO, I don't actually find the abbreviated backtraces a serious problem in practice. Interesting though that most discussions don't mention the problem at all? Sometimes it's hard to keep track of which practicalities that have been abstracted away when talking theory.

Actually what I think would be a nice primitive is a (tailcall E) which is rejected unless E is a function call in tail-position. This could be a helpful utility for learning to write tail-recursive programs.

Ironically, many languages that don't support TCO have a very similar construct that marks tail calls. Unlike your proposed primitive, it doesn't reject non-tail calls because it -makes- E a tail call. This primitive is usually called 'return'.

Operationally, the former will allocate new invocation record, then calculate f(), which will probably deallocate this record, then deallocate the previous record. The latter will calculate f(), which will probably deallocate this record.

So the first behaves as +frame f -frame, while the second as f, which has the same final result but a very different memory consumption history.

I seem to remember tail-calls being discussed in the Tcl community, and a proposal of the form return -call cmd args.. or similar. This seems pretty simple to understand (especially if you've already got your head round uplevel) and means you don't have to do any analysis on the code to figure out if something is a tail call.

Edit: I should point out that the above construct destroys the current stack frame and then calls the command given.

So the first behaves as +frame f -frame, while the second as f, which has the same final result but a very different memory consumption history.

I said, "many languages that don't support TCO", so though I wasn't as clear as I could have been, it should be obvious that I wasn't saying that 'return' optimizes the tail call. Almost all calls that are tail calls are clearly marked in such languages.

The reason I say it's ironic, is that one "problem" with TCO sometimes raised by people using the above mentioned languages and implicit in some arguments in this thread (albeit relatively minorly), is that it is "difficult" (for beginners at least) to distinguish tail calls from non-tail calls. In practice, it's almost always trivial and almost impossible to err on the dangerous side.

Also, thinking about it now, 'return' almost seems to do a better job than Luke Gorrie's tailcall operator in ensuring that an expression is a tail call and facilitating learning. In many cases it would simply be syntactically illegal to return in a non-tail position, presumably most compilers will give an unreachable code warning in the remaining cases, and I find it hard to believe that even beginners with a basic understanding of 'return' would find such code sensible or even write it in the first place.

The comparison of 'return' to an explicit 'tailcall' operator is illuminating. Note however that 'return' fails to serve the role of 'tailcall' in avoiding surprise. Modify
    tailcall f(n+1)
to
    tailcall f(n)+1
and the compiler reports an error. No error is reported if
    return f(n+1)
is modified to
    return f(n)+1

Modify

    tailcall f(n+1)

to

    tailcall f(n)+1

and the compiler reports an error.

No, it doesn't. That's a tail call to operator+.

Now modify tailcall f(n+1) to tailcall g(f(n+1)). Should an error be reported?

Another way to do it, rather than requiring a programmer to annotate every call that they intend to be in tail position and erroring out on those that aren't really in tail position, is to just perform tail call optimization on the calls that are actually in tail position and (obviously) not on the others.

Scott Turner said:
tailcall f(n)+1 ... the compiler reports an error.

Kevin Millikin said:
No, it doesn't. That's a tail call to operator+

But as any PL geek should know, it all depends on the rules of precedence in the language we are using (which hasn't been specified here that I can see).

So both answers are wrong (or right if you prefer).

Shame on you both! ;-)

Now modify tailcall f(n+1) to tailcall g(f(n+1)). Should an error be reported?

Donning my Captain Obvious cap, the answer is no, because the syntactic form seems to indicate that a tail call to g is being requested/asserted, and that's valid in this case. However, an error should be reported in the following case:

g(tailcall f(n+1))

...because of course the call to f is not a tail call. But the tailcall construct is never going to be valid when it's embedded within an expression, as in the latter example. The only time it will be valid is when it's used at the beginning of a "statement", assuming we're talking about a language that has statements. (More generally, the tailcall construct is only valid when used in tail position, but that's perhaps less illuminating — then again, I'm still wearing that cap.)

This all illustrates that return is indeed a reasonable implementation of a tailcall construct. If we write return g(f(n+1)), that's cool; but if we write g(return f(n+1)), most languages with a return statement will generate an error. This error might read something like "parse error before 'return'" or "illegal start of expression", but what it's really saying is that return is only valid in a potential tail position. I say "potential", because as Derek originally pointed out, return will (or at least could) force a tail call when it's used legally.

Sorry for the diversion yesterday titled "not on target". I had not read Luke Gorrie's suggestion for (tailcall E) carefully. Also my background is in conventional compilers for C++ etc. so I think first of tail call optimization as a compile-time transformation, rather than think of "proper tail call" as in Scheme.

I incorrectly assumed that the proposal was intended to prevent a programmer from inadvertently transforming an optimized self tail call into a non-optimized call. For example,

f(x) = ...
  return f(x+1)

f(x) = ...
  return 1+f(x)

f(x) = ...
  return tco(f(1+x))

f(x) = ...
  return tco(1+f(x))

I don't know how or whether this could be implemented in a language with proper tail call, with a similarly helpful effect.

In Pre-Scheme:

The programmer can
declare that individual calls are to be compiled as
properly tail­-recursive. (GOTO proc arg1 ...)
is syntax indicating that proc should here be
called tail­-recursively (assuming the goto form
occurs in tail position).

Unfortunately I've already had thoughts along the same lines... There's absolutely no technical problem with the compiler deciding that sometimes stack traces should be present, and sometimes not - but I'm not sure I want to burden the user by requiring them to understand possibly bizarre compiler implementation issues in order to work out when this might happen. As regards adding syntax for a new type of call operator, this is more of a starter for me, but I'm less than convinced that I want to rival SL5 for overly complex function application rules.

What I really want (and I suspect it's not possible, but I'd love to be proved wrong) is for the compiler / VM to automatically optimize tail calls whilst still preserving stack call information.

I'm not sure I want to burden the user by requiring them to understand possibly bizarre compiler implementation issues in order to work out when this might happen.

That's fine, but it sounds to me as though you haven't tried very hard to figure out a reasonable balance (I could be wrong). I would argue that the reason you haven't tried hard is because you're not ascribing enough importance to having full support for recursion.

However, I think it's perfectly reasonable to decide that you see some problems that you're not interested in trying to resolve, and therefore you will exclude some feature. I think it's less reasonable to then turn around and try to claim that the feature in question is no good anyway, or too complicated to understand, or whatever — that's essentially a sour grapes approach, and that's what I'm getting from the Python vs. TCO question.

There is an element of truth in that - but as I would have imagined my other posts on this matter would have suggested, it's not really due to sloth (but thanks for the vote of confidence ;)). It's because I don't want to start adding in extra syntax, or teaching the compiler (and therefore the user) some tricky new cases, if there's actually a way of doing this automatically and transparently to the user. Once that possibility is exhausted, then I will turn to considering other more manual solutions - but not before. That seems a perfectly sensible prioritization to me.

As to the sour grapes comment, as someone who's reasonably neutral on the subject, I can't help but detect some of that on both sides of the debate!

There is an element of truth in that - but as I would have imagined my other posts on this matter would have suggested, it's not really due to sloth (but thanks for the vote of confidence ;))

Don't take it personally, the subject line was too good to pass up. ;) Besides, programming language designers need to be kept on their toes, otherwise next thing you know they're saying that things would be easier if we didn't really have syntax (Lisp, Smalltalk), or that lexical closures aren't important enough to be supported well (old Lisp, recent Python, Java, many others), or that unrestricted recursion isn't particularly important. Hard to believe, I know!

Once that possibility is exhausted, then I will turn to considering other more manual solutions - but not before. That seems a perfectly sensible prioritization to me.

Maybe. If you're going to talk about prioritization, if you look at some of the functional languages, you'll find that this stack trace business is really not a big deal. The cases where tail calls occur are iterative by nature, and not having a stack trace entry in those circumstances doesn't often matter.

BTW, quite closely related to all this, I notice that on your "Why don't we use functional programming languages more?" page, you focus on lazy & pure languages, like Haskell & Clean. If those were the only kind of functional languages, I would agree with the general conclusion that the main benefit of FP was as a kind of test bed for advanced concepts. However, when you take into account eager, impure languages like SML, OCaml, Erlang, and Scheme, your premises no longer hold, and nor does the conclusion that FP is "fundamentally ill-equipped to deal with many practical problems."

The upside for you, though, is that for something like this stack trace issue, you can look at what implementations of these other, practical FP languages do. There are plenty of things that could reasonably be pointed to in those languages as being unsuitable, or at least non-ideal, for a more mainstream language; but IME, the TCO stack trace issue isn't one of them. Most of these languages have at least some non-academic users, too, especially Erlang. So a reasonable question in terms of prioritization is whether or why you need to break new ground in this area. If you actively want to, more power to you, but I think you can get away without it (back to the sloth thing).

As to the sour grapes comment, as someone who's reasonably neutral on the subject, I can't help but detect some of that on both sides of the debate!

Neither of the things you mention are costs.

The first is fairly obvious, and is evident in the forced rewriting of the Fibonacci function: many functions have their most natural form without tail calls.

So, proper handling of tail calls is essential to solve problems A, B, and C, but it doesn't impact the solution of problem D. Is that a cost?

I can use the same argument: many functions have their most natural form as recursive functions, rather than using iteration and mutable state variables.

Is that a good argument against the while loop? Is it a cost of including while loops in a language?

The second cost associated with tail calls is...only really evident in languages which give decent stack trace error reports

Yes, but a stack trace for an exception thrown in a while loop does not tell you what iteration of the loop the exception occurred in. Instead, you do something like inspect state variables in a debugger to figure out what's going on. Tail recursive functions are exactly the same. One merely inspects the values of those annoying extra arguments.

Qute respectfully (honest), I don't think this is really a cost of proper tail call handling. Unless it's also a "cost" and a good argument for removing loops for languages, that is.

If you don't make some tough decisions about what to leave out, you'll end up with a big language.

But guaranteed tail-call optimization allows you to leave so much out that it should be no brainer, if small languages are your aesthetic.

It seems to me that what those Python experts who resist the further elaboration of the language are afraid of is asking beginners to learn and reflect.

It's not that we want to limit beginners, but we do want to give beginners satisfying experiences, and provide a smooth learning curve as they become experts, and make "expert" a truly accessible goal. This is something of a common thread in the Zen of Python.

BTW, I left a comment on why I think the seemingly-innocuous feature of tail-call elimination is problematic.

Saying that tail-calls optimisation is dangerous because it is hard to predict when it applies strikes me as an argument one could make against GC too: "[X] won't have GC because it is hard to know (indeed, in suitably dynamic languages, it can be impossible to predict at compile-time) when it will be applied, so that small changes can make a constant-space program suddenly explode in memory usage. It also leads to a greater use of constructs such as linked lists, which can be hard to understand, e.g., the sharing of 'next' nodes. In addition, the absence of GC, a small subset of buggy programs will crash instead of being stuck in an infinite loop."

What I find particularly interesting with this parallel is that tail-call optimisation is basically the (usually static) garbage collection of call frames. Both are ease-of-use/space -optimisations that allow some functions to automatically use constant space. Yet, I don't see many people complaining that they must understand references to predict their programs' usage of heap memory. Like GC makes the use of certain useful data structures easier, tail-call optimisation allows certain programs to work without reinventing the wheel (e.g., manual trampoline). Moreover, just as programmers who use memory dynamically have to manually manage memory when GC is unavailable, those who need deep recursion may very well end up using a trampoline in the absence of tail-call elimination. In my opinion, trampolines are much harder to work with and understand than tail-call optimisation. Basically, this is the kind of reasoning that I often hear from Pythonistas and yet never fails to amaze me: Feature X is useful, but can be confusing. X is bad even though the confusion only arises when X is used. (Or "Allowing the use of knives makes it possible to cut one's self when eating steak." Well, don't eat steak if you don't understand how to use knives. On second thoughts, this one might not be very well-chosen since I'm nearly vegetarian ;)

As for the problem of backtraces, I think there is at least one solution: tail-call optimisation doesn't have to be static, nor does it have to completely erase history. One could envision an interpreter that only GCs the stack frames once it would otherwise reach the maximal recursion depth, and, even when it did GC the stack frames, would still keep the nth topmost ones. Instead of popping up a "Program stack exhausted, proceeding to prompt death." message, the interpreter could offer the option of continuing the execution after releasing all but the nth last tail-calls from the stack.

The one good point I can see against tail-call optimisation is that it can be hard to explain. I could argue that people only have to use what subset of the language they understand, but I know that argument doesn't fly very well in the Python community ;) However, I don't see how this is any harder to understand than GC: A stack frame is released when no other operation remains to be done in it -- An element is released when no other element refers to it. (Note the artful avoidance of the word 'continuation')

Comparing GC to tail-call elimination isn't really fair. GC is really really useful; any confusions it adds are more than worth it. Tail-call elimination just isn't that valuable. Especially if you collect frames lazily to maintain tracebacks, it's unlikely to even matter, except for code that is deliberately written in a tail recursive fashion, which I don't think is a good style because it's fragile and confusing in an environment that heavily favors iteration (which is what Python will always be).

Couldn't we take the arguments against tail-call elimination and make pretty much the same argument against having recursion in general? Novice programmers aren't going to understand recursion better because we've made it worse. They'll start out being impressed that recursion makes their program shorter and more understandable. They'll test it with their small data set and be surprised when their previously working program suddenly dies on a larger data set (most likely at the most inconvient time). In fact, tail-call elimination becomes a feature again, because it might save their bacon in a few instances. And as long as we're throwing away recursion, we should probable get rid of while(), because once you add that feature, we won't be able to know in general if our program ever halts ;-)

Couldn't we take the arguments against tail-call elimination and make pretty much the same argument against having recursion in general?

I once skimmed a book where recursion got a place next to goto in the paragraph "Unusual control structures", so some people already make this point.

I'm an optimist, so it's never worried me to believe that my functions will work, even while I'm writing them.

There are already advanced Python idioms that one would have a hard time explaining to a beginner (almost anything to do with metaclasses, for instance). Does the existence of these idioms (and the fact that some people, Philip Eby for instance, are using them) harm the Python community?

I think that's the wrong question to ask, really, since it depends on so many unquantifiables (how a majority of people feel, what they find easy or hard to understand or explain). Much better is Dijkstra's:

Are you quite sure that all those bells and whistles, all those wonderful facilities of your so called powerful programming languages, belong to the solution set rather than the problem set?

IMHO it's a pity that many implementations of various languages don't support large stacks, and they die horribly when the stack overflows or put artificially low limits on the number of active function calls.

This applies especially to functional languages. A natural definition of append or map in OCaml is non-tail-recursive, and thus doesn't work for very long lists. Fixing this by rewriting the function to not use non-tail recursion usually leads to both uglier code and slower execution for the common cases of short lists, so it's rarely done. The effect is a fragile program which blows up on large data.

Well, I can understand two reasons for this:

1. Checking for stack overflow and especially resizing the stack can't be done without execution cost and portably.
2. When a program uses a very deep recursion, it's possible that it went into an infinite loop, and in this case it's better to kill it early than to let it eat lots of memory.

Nevertheless in the compiler of my language Kogut I've implemented checking for stack overflow and resizing the stack when needed, even though stack overflow checking has some overhead (I've chosen portability over efficiency in this case).

I feel that forcing programmers to abandon a recursive solution in order to obtain scalability, just because the number of calls would be linear with data size, is unfair. An alternative, ugly but scalable solution of the given problem would just use the same amount of heap instead of stack, so in overall it would not use less memory at all.

An additional bemefit is that I can create lots of threads, and they can use as much stack as they need, as long as their total demand for memory fits in memory provided by the system—no need to partition the address space into threads' stacks in advance.

Of course I also perform TCO.

Dylan, Nemerle.

Is check the LtU "meta prograaming" category and search the archives.

Does the C preprocessor count?

Not really, althought it provides some of the functionality.

However, C++ templates are quite close to proper metaprograming.

Erlang programmers sometimes write metaprogrammey code. Here are a few techniques I've learned:

• The compile:forms function in the compile
  module takes a syntax-tree as input, compiles it within memory, then returns a handle for calling the resulting code. Our system has a DSL for traffic filtering which is compiled this way for speed. compile:forms is similar to the COMPILE function in Common Lisp. (I just learned this trick last week.)
• The Erlang compiler supports "parse transforms", a very general mechanism that lets you specify some functions that it should fold the parse tree through before compilation. Example uses of parse-transforms are to instrument code for debugging, add special optimizations for certain expressions, and add language features within the existing syntax (e.g. docstrings or extensions to pattern matching). Parse transforms are a bit like macros and compiler-macros in Common Lisp.
• Of course people sometimes write Erlang programs that write Erlang programs. The standard libraries offer you helpful features like a parser, pretty-printer, compiler, and some code analysis ("what are the free variables in this expression", etc).
• The Erlang debugger is a special-purpose Erlang interpreter written in Erlang.

These aren't common programming techniques in Erlang and they're not as convenient as what Lisp offers. But they're sometimes very handy.

and make a single form of syntactic extension applicable to the entire language. But it's not impossible with non-postfix/prefix languages.

With an irregularly or heterogeneously - syntaxed language macros can be made to "work " but I suppose there would need to be many different forms or special cases of macros.

You'd need one form for each of the language's syntactic constructs which you wanted to be "macro-able".

Thinking out-loud here. I've been playing with Haskell recently, and actually finding myself quite enjoying it. ;-) One of the first things to strike me when I first looked at Haskell was the similarity between type declarations and EBNF grammar notations. I presume this is more than a coincidence? Data constructors convert concrete syntax (values?) into abstract syntax (types) - would that be a correct description of the connection? (Excuse me if my terminology is off here, I need to brush up on this stuff). So, how far could this be taken? Could you have a language where it was legal to write something like:

type Set a = "{" a? ("," a)* "}"
myset :: Set Int
myset = { 1, 2, 3, 4, 8, 12 }

That would be very cool, although you'd have to check the grammar formed was consistent - another type system (does Haskell call this a kind-system?), which might be quite complex.

Anyway, in this context you could completely specify a language (indeed, many languages?) via the type system, and all of the AST would be available as types. Then, a macro would simply be a function which performed a transformation on the types at compile time. A compiler would then be a special case of a macro which takes a complete program and transforms it to another language (e.g. byte-code, machine-code, etc). You could type the target language in the same system. That would be cool.

Is what I have just described coherent? Does a system like this exist anywhere? I keep seeing the term "rewrite system" (or something like that), which seems vaguely connected? Apologies if this is much-covered ground.

One of the first things to strike me when I first looked at Haskell was the similarity between type declarations and EBNF grammar notations. I presume this is more than a coincidence?

Absolutely! The connection in its most general sense arises from structural recursion, which is one of the most fundamental features of computer science, closely related to its more mathematical cousin structural induction. You're correct that rewrite systems, or more generally, reduction systems, are closely connected to all this. Here's a page which neatly ties some of this together, with ML examples (which are very similar to Haskell at this level).

A slightly more in-depth intro to these concepts can be found starting in Chapter 1 of Schmidt's book Denotational Semantics: A Methodology for Language Development (dowloadable PS). There might be better sources, more specific to languages with type systems like Haskell's, but Schmidt's is quite clear & concise.

As far your syntax-defining idea goes, have you looked at a Haskell prelude, where all the basic datatypes, operators and their precedence are defined? In some ways, it comes pretty close to what you're talking about. However, it doesn't actually allow you to define the most basic syntax of the language, since as you say, you'd run into the problem of checking the resulting grammar, and at that point it probably starts to make sense to separate the two phases more clearly.

A more separated approach is Camlp4, which is a preprocessor layer, rather than something built into the language in the way you describe.

Thanks for the links. Looks like I've got some more reading to do. Just after I posted it occurred to me that it's probably better to separate out the concrete syntax definition and the rest of the type system/functionality. When I was completing my undergraduate degree, a friend was working on an editor for Haskell that built up and manipulated an AST as you typed. If you could separate out the concrete syntax then you could provide multiple views onto the same AST fairly easily (even non-textual ones like UML-style diagrams). Or, alternatively: every programmer in a team using a customised syntax to write the same language (where "the same" = structural equivalence). Endless possibilities. Maybe static types aren't so bad, after all!

Perl6 is supposed to have macros.

See this paper:

"Growing Languages with Metamorphic Syntax Macros (2000)"

or
.

Abstract: "From now on, a main goal in designing a language should be to plan for growth." Guy Steele: Growing a Language, OOPSLA'98 invited talk.

We present our experiences with a syntax macro language which we claim forms a general abstraction mechanism for growing (domain-specific) extensions of programming languages. Our syntax macro language is designed to guarantee type safety and termination. A concept of metamorphisms allows the arguments of a macro to be inductively defined in a meta level...

--
Jens Axel Søgaard

the exceptions path...the continuations path

There are other ways of handling failure besides these two - the Maybe monad, for instance, or search with backtracking...

It's common in Python to use exceptions for failures of all kinds, e.g.

try:
   someDict[someKey] += 1
except KeyError:
   someDict[someKey]= 0

instead of

if someDict.has_key(someKey):
   someDict[someKey] += 1
else:
   someDict[someKey] = 0

There have been times that I've wanted some other exception mechanism in Java (say), or something like convenient multiple return values. Ideally, in those cases I'd just write programs in continuation passing style.

Except then I would need proper handling of tail calls, and apparently some would deny me even that.

Exceptions as some sort of call/cc+mutation design pattern, or as the direct-style transform of programs with explicit normal and exceptional continuations are fine. Choosing to provide them in a language is probably for the good. Denying me the ability to usefully write CPSed code without requiring some annoying trampoline is bad.

You're deliberately fanning the flames, aren't you? :-)

Java is tricky because a naive tail-call optimization would break the security model. The JVM checks security by looking at where code on the stack was loaded from (local disk vs. web, etc). The idea is that if something on the stack was loaded from www.foobar.com then maybe you shouldn't be deleting any files for it.

If you tail-call optimized an untrusted method like:

void nasty() {
    Runtime.getRuntime().exec("halt");
}

This basic model makes higher-order Java programming seem scary in combination with untrusted code: it only has to arrange for something nasty to happen without its own code being on the stack at the time. If it were Emacs Lisp it would be as easy as:

(push 'kill-emacs post-command-hook)

at least that's what I've been led to believe. So the restriction should be based on how the class was loaded. Only gets to be a problem if you have multiple class loaders operating simultaneously within the VM and objects talk across that boundary.

and without the stack, one can't check for permissions in your caller (or grandcaller, or great-grandcaller, or ...)

The answer is so simple and obvious I'm amazed it took so long to find.

A tail-recursive machine with stack inspection

The answer is so simple and obvious I'm amazed it took so long to find.

Specifically, if some action happens as a result of join of two asynchronous calls from different principals, who of them is "guilty" (accountable for the action)? Or is this question meaningless and we should abandon trying to assign permissions to single principals and start supporting permissions to sets of principals (or even to propositions?). I believe a simpler idea to just intersect permissions of these principals is not alwys adequate - consider a door with two locks and two people entrusted with different keys. Oh, should we abandon ACLs completely?.. Capabilities to the rescue?

To claim relevance to topic, core join calculus uses something like CPS, so is probably experiencing security issues similar to PLs with TCO.

I don't get why you can't just form the union of the permissions when replacing the stack frame?

As an excuse for missing the obvious, it's 2 AM ;)

The state is nothing but an instrument of
oppression of one class by another.
—Friedrich Engels

1. A class file is obtained and accepted if it passes preliminary bytecode verification.
2. The class’s code source is determined. If the code appears to be signed, this step includes signature verification.
3. The set of static permissions, if any, to be granted to this class is determined, based on the class’s code source.
4. A protection domain is created to mark the code source and to hold the statically bound permission set. Then the class is loaded and defined to be associated with the protection domain. Note: If a suitable domain has previously been created, that ProtectionDomain object is reused, and no new permission set is created.
5. The class may be instantiated into objects and their methods executed. The runtime type-safety check continues.
6. When a security check is invoked and one or more methods of this class are in the call chain, the access controller examines the protection domain. At this point, the security policy is consulted, and the set of permissions to be granted to this class is determined, based on the class’s code source and principals, specifying who is running the code. In this step, the Policy object is constructed, if it has not been already. The Policy object maintains a runtime representation of the security policy.
7. Next, the permission set is evaluated to see whether sufficient permission has been granted for the requested access. If it has been granted, the execution continues. Otherwise, a security exception is thrown. (This check is done for all classes whose methods are involved in a thread. See Chapter 6 for the complete algorithm.)
8. When a security exception, which is a runtime exception, is thrown and not caught, the Java virtual machine aborts.

Alternatively, check Java Security Architecture: Overview of Basic Concepts

For some reason, it seems to me that stack-based security is equivalent to history-based one in programs written in CPS...

[on edit: ah, the author also thinks so:

Conversely, to implement history-based rights on top of stack inspection mechanisms, for any given call, we can (in theory) apply a “continuation-passing-style” transform that passes an extra function parameter to be called with the result, upon completion of the callee. Hence, the callee still appears on the stack while its result is used by the caller’s continuation. However, this encoding is not practical, except maybe for a few sensitive interfaces.

Java is tricky because a naive tail-call optimization would break the security model.

In a slashdot interview of I think 3 years ago, Kent Pitman cited private communication to the effect that some Java engineers had figured out how to adapt the trust model to a/the spashetti stack, and were considering adding tail-call optimisation to Java. I've heard some other Sun connected types saying this couldn't work, but I've seen nothing concrete in this time. Does anyone have better information about this rumour?

If Java had a better static type system and referential transparency it only would need to check for calls to IO calling code. The place I blew the stack was referentially transparent, my Parser operated on strings so I worked in the same way a Haskell program works:

    do contents  return x
           Nothing -> fail "Something bad happened"

Another thing a "stricter" compiler could do.