What needs to be removed from your favorite computer language so that programs execute as a state machine, that is, not requiring an unbounded amount of memory?
The nice thing about limiting yourself to state machines is you never have to worry about memory leaks or space leaks.
For C, I think we must remove "malloc" and friends, and recursion, including mutual recursion. Tail recursion would still be OK, assuming the compiler does the right thing.
Haskell?
Bluespec, a hardware description language based on strongly typed functional programming, can describe very sophisticated state machines (because that's what hardware is), which can also be run in software simulation. However, one can write programs that require unbounded memory to compile, making it kind of a tradeoff.
Inspired by imagining a Turing machine as real computer with its state machine, typically pedagogically depicted as an explicit list of states, implemented in a "real" programming language capable of compactly describing state machines with (say) 2^1000000 states: "int x[31250]" declaring a (finite) array, something you would never explicitly list all states.
2 comments :
Another, more academic question is what you need to remove from a language to make it non-Turing-complete even when run on a Turing-complete machine.
I think C's Turing completeness is actually quite a close call: While an implementation can provide as large pointers as it wishes, sizeof(void *) needs to be a finite constant. This limits the amount of memory available via malloc() to a constant amount. Similarly all data types must have a finite size.
Call recursion moves us from state machine to a stack machine. If you allow file I/O, you can use files to emulate a second stack, thus making it Turing-complete - there's no inherent limitation restricting sizes of files, only seeks.
I'm not sure if setjmp/longjmp are enough to make C turing complete. Another interesting way around non-Turing-completeness might be to note that sizeof(X) is expressed in bytes/chars, so if we expand char to an infinite range, we can have Turing completeness (then we have the minor technicality of CHAR_MAX in ).
Allowing tail recursion might or might not be okay, depending on whether you consider the below to be tail recursive:
T foo(TT *x) {
TT y;
...
return foo(&y);
}
Post a Comment