News for hackers. Stuff that matters.
Re:Brainfuck interpreter written in the C preprocessor by krenoten on Friday November 16, 2012 @05:46PM (#4796271)
It is impossible to implement a system without a de-facto recursion depth limit.
Re:Brainfuck interpreter written in the C preprocessor by vidarh on Friday November 16, 2012 @10:10PM (#4797018)
But this is not a de facto recursion limit of the system - the limit is encoded in the program itself, in the macros used to implement the limited recursion.

void f() { f(); } is only limited by the system, and if compiled on a system that automatically expands the stack to fill all available memory, you could in theory keep adding memory, and the system could handle more recursions. The recursion limit is external to the program.

But the linked c-preprocessor programs would have to be explicitly modified by adding more lines of code to achieve the same thing.

Re:Brainfuck interpreter written in the C preprocessor by scott_s on Friday November 16, 2012 @07:48PM (#4796654)
Yes, but as I point out elsewhere, Turing Completeness separates the expression from the machine. Machines will always have limits. But the expression of computation does not have to have limits.
Re:Brainfuck interpreter written in the C preprocessor by asynchrony on Friday November 16, 2012 @06:17PM (#4796374)
Recursion depth limit is really a memory limit, so you just need someone to come and install more RAM when you run out in order to obtain de facto infinite memory, hence infinite recursion depth.
Re:Brainfuck interpreter written in the C preprocessor by mistercow on Friday November 16, 2012 @06:55PM (#4796492)
Even that is not infinite because there is a limit to how much memory you can address. You don't have to bring physical realities into it.
Re:Brainfuck interpreter written in the C preprocessor by tjgq on Saturday November 17, 2012 @01:36PM (#4798706)
How is a "limit to how much memory [one] can address" not a physical, rather than logical, constraint?

Really, the crux of the matter is that you can have a function call itself an unbounded number of times in C (i.e. unbounded recursion). That you eventually run into a stack overflow is a limitation of the machine, not of the language; the definition of C does not prescribe a maximum number of recursive calls. This, together with conditionals, makes the C language Turing-complete.

Re:Brainfuck interpreter written in the C preprocessor by asynchrony on Friday November 16, 2012 @08:01PM (#4796689)
The system will just spontaneously update to the next power-of-two bits when address space gets short. Problem solved.
Re:Brainfuck interpreter written in the C preprocessor by mistercow on Saturday November 17, 2012 @01:46AM (#4797455)
That would break binary compatibility with all existing programs, though. So I guess the claim should be that it's impossible to implement a practically useful system without a de-facto recursion depth limit.
Re:Brainfuck interpreter written in the C preprocessor by finitocom on Saturday November 17, 2012 @02:25AM (#4797520)
How does tail-recursion fit into this discussion of infinite recursion?