4 ms·
Yes 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.
by fhars 4y ago
Yes 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...