Hacker News Reader

Comment by eudox | Hacker News Reader

Why?

I'm not an expert... but you don't want your C/C++ code stack overflowing or running out of memory in an uncontrolled way. Your C/C++ can do graph reduction by working on a structure in a loop. Then you'll be able to better monitor resources.

Eh, clarity of code is more important, in my opinion. If you run out of stack, get a better computer.

Stack doesn't generally scale up with RAM. GCC and Clang can both do some tail call optimization, and I find rewriting code to use an accumulator isn't very hard on the eyes.

s/computer/compiler/

This is why TCO (Tail call optimization) exists... but of course not all recusion is tail recursion, but I think it can always be written this way, and should always be for arbitrary depth recursion.

Yes, you can always convert direct style code to continuation passing style code. And continuation passing only uses tail calls. This is one of the big advantages of CPS. Of course if you don't have a tail call optimization, then you overflow the stack pretty quick.

Elimination, not Optimization. Either you can rely on it as part of the spec (Elimination) or you can't (Optmization)

There is normally no deep recursion in compiling a program. The compiler would recurse over recursive program constructs, like nested if statements. Programmers normally do not nest constructs very deep.

This may be true for human programmers, but compilers also must compile machine generated code, which often looks very different. As an example, I can't remember the source on this, but I have read somewhere that the original C++ compiler (cfront) compiled C++ into C code, and this generated code exposed many bugs in the C compilers of the time, as it was very different than how a human would have written that code.

Running out of stack space compiling a machine generated program would be a bug in the automatic source code generator then.

In the same sense that running out of stack space compiling a human generated program is a bug in the programmer.

If human-generated programs compete head-to-head with robot-generated programs for blowing up the implementation, that human has a worse bug than the robot.

I just watched a talk where Kernighan brought up this exact anecdote.

When I write a program I aspire to impose no arbitrary limits apart from those imposed by the architecture. So I'd like my compiler to be able to handle programs as complex as the user wants, with the only limit being the available virtual memory and disk space. If you use recursion for 'outer loop' stuff, you impose the extra limitation of the size of the stack, which is much smaller than available virtual memory.

I work with partial evaluation, where intermediate representations during compilation can get quite large, and have seen stack overflows in the compiler for real.

It would be nice if stacks were arbitrarily large anyway.

A program is so syntactically nested that the compiler blows an 8 megabyte stack (default on x86 Linux, easily extended with ulimit) is a silly program. There is no need to support such a thing in a language implementation.

Note that if the language supports macros, you can't eliminate recursion from compile time; macro expanders can express recursion. (The same remark applies though: if user-defined macros blow a generous stack that is many megabytes long, oh well!)

If you are doing some kind of abstraction interpretation or static analysis, you may have many many implementation stack frames for each logical stack frame.

Then add in very deep inlining.

And as I say I've seen it for real, in a real compiler, with a real program, while doing a real job. I could send the author an email and tell him his program is silly, but I'd rather be able to compile it.

One thing.

Sometimes linear constructs can appear nested in the handling of the syntax.

You want to avoid right recursion in an LR parser for list-like constructs, especially if they can be reasonably expected to grow large. These constructs appear "flat" to the programmer, but the parser will push tokens onto the stack and not reduce anything until the end of the construct is reached.

"Normally" is the operative word.

I've seen output from compilers to JavaScript that convert huge switches into if cascades which are in fact quite deep: think tens to hundreds of thousands of cases converted to an if cascade.

Or put another way, not all programs are written by programmers.

The `Letrec' construct (see: chapter 3) addresses your concerns. It extends the language from a standard S-K-I lambda calculus into a language that "copes" with recursion, especially with TCO.

Reply on news.ycombinator.com