5 ms·

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

• tbirdz 11y ago
  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.
  • jonsen 11y ago
    Running out of stack space compiling a machine generated program would be a bug in the automatic source code generator then.
    • jonsen 11y ago
      In the same sense that running out of stack space compiling a human generated program is a bug in the programmer.
      • kazinator 11y ago
        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.
  • steveklabnik 11y ago
    I just watched a talk where Kernighan brought up this exact anecdote.
• chrisseaton 11y ago
  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.
  • kazinator 11y ago
    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!)
    • chrisseaton 11y ago
      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.
• kazinator 11y ago
  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.
• bzbarsky 11y ago
  "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.