3 ms·
Does it actually? Or does the number of elements on the stack /that you have taken the address of/ have that upper bound? That is, could you build a compliant
by addaon 4y ago
Does it actually? Or does the number of elements on the stack /that you have taken the address of/ have that upper bound?
That is, could you build a compliant C implementation that implements a stack using an infinite memory (e.g. in a delay loop between the user and a mirror moving away through space), where each entry in the stack contains a convenient sized value (word, byte, whatever) and a tag? If the tag is clear, the value the contained directly in the infinite memory; if the tag is set, then the value is indirected into a fixed-sized memory. On taking the address of an item on the stack, if it is not already indirected, relocate it and indirect.
Of course the mechanism for doing stack unwinding on return needs to use relative operations ("drop five elements") and not chase frame pointers, but that seems trivial.
I admit I'm not super-familiar with all the details of the C specification, but it's not obvious to me that this would violate spec, and it would be Turing complete.
- fhars 4y agoYes it does, C is defined in term of implementation defined, but finite sized pointers and integers, so the computational model of C is a finite state machine. But the size of the state space is so friggin' HUGE that that argument is completely irrelevant for all practical purposes.
- addaon 4y agoIs this true? C is defined in terms of the operations that can be performed on objects in memory, which includes the concept of memory addresses and address manipulation; but I'm not aware of anything that would require that objects that do not have their address taken have unique addresses, or addresses at all. This is the same use of the as-if principle that allows so many local variables to live their entire life in registers. An infinite stack to support unlimited recursion seems possible within the C machine.
- tedunangst 4y agoThe C standard specifies that there is a constant UINTPTR_MAX.
- addaon 4y agoYes. But, as I mention in the proposed implementation, this limits the number of unique addresses in an implementation. Values that do not need addresses do not consume this limited resource. There would be a limit on the number of items on the stack that can have their address taken, but I can't see why this would limit the number of items on the stack. In e.g. the fizzbuzz implementation mentioned in another comment [1], even without tail call optimization the stack growth implied by the recursive call does not require the number of /addressed/ items on the stack to grow. (Thinking about it, I believe this is an equivalent statement to "the tail call optimization is valid.") [1] https://old.reddit.com/r/C_Programming/comments/qqazh8/fizzbuzz_contained_entirely_within_the_parameter/ https://old.reddit.com/r/C_Programming/comments/qqazh8/fizzb...