3 ms·

It also transforms programs that use it from "cannot run with a little bit more memory" to "can run forever with a little bit less but still finite memory" whic

by godd2 11y ago

It also transforms programs that use it from "cannot run with a little bit more memory" to "can run forever with a little bit less but still finite memory" which sounds more like an optimization. People are probably solving a problem that needs more, but still a finite amount, of memory, and very likely not solving a problem which needs infinite memory. So calling it an optimization is perfectly warranted.

beagle3 11y ago
> People are probably solving a problem that needs more, but still a finite amount, of memory, and very likely not solving a problem which needs infinite memory. So calling it an optimization is perfectly warranted. Consider the following C program: long long i; /* assume 64 bit */ for (i=0;i>=0;++i) { if ((i*i*i -(i>>12) +(i>>24) -(i>>36) +(i>>48))%3819 == 5) { printf("found an example: %64i\n", i); } } It is not directly useful itself, but variations on it are (e.g. hash cash proof of work computations are not dissimilar). It will run practically forever on every machine on which "long long" is 64 bits. It will likely terminate in finite time on a machine in which "long long" is 32 bit (there's undefined C overflow behaviour, so it might never terminate). And it will do so with zero additional space. A tail-call equivalent (the only kind of loop available in Scheme, for example) will -- without TCE/TCO -- overflow the stack on a 64-bit integer-or-more (e.g. Scheme's arbitrary precision numbers) on every machine built so far. It will likely do the same even if ints are limited to 32 bit - although a machine with >16GB ram is likely to complete a 32 bit run with reasonably optimized language runtime and stack allocation scheme (neither of which is common - x64 ABI red zones would require >128GB just to do the 32 bit count with full stack frames). If the int goes to 128 bit, all the memory chips ever produced in the world (and likely all those that will be produced in the next 20 years) would not be enough to stop this program from overflowing its stack - much unlike a TCE/TCO/C version. In my opinion, something that switches between bounded and unbounded memory requirements should not be called "optimization", but to I guess to each their own.

by godd2 11y ago

beagle3 11y ago

> People are probably solving a problem that needs more, but still a finite amount, of memory, and very likely not solving a problem which needs infinite memory. So calling it an optimization is perfectly warranted. Consider the following C program: long long i; /* assume 64 bit */ for (i=0;i>=0;++i) { if ((i*i*i -(i>>12) +(i>>24) -(i>>36) +(i>>48))%3819 == 5) { printf("found an example: %64i\n", i); } } It is not directly useful itself, but variations on it are (e.g. hash cash proof of work computations are not dissimilar). It will run practically forever on every machine on which "long long" is 64 bits. It will likely terminate in finite time on a machine in which "long long" is 32 bit (there's undefined C overflow behaviour, so it might never terminate). And it will do so with zero additional space. A tail-call equivalent (the only kind of loop available in Scheme, for example) will -- without TCE/TCO -- overflow the stack on a 64-bit integer-or-more (e.g. Scheme's arbitrary precision numbers) on every machine built so far. It will likely do the same even if ints are limited to 32 bit - although a machine with >16GB ram is likely to complete a 32 bit run with reasonably optimized language runtime and stack allocation scheme (neither of which is common - x64 ABI red zones would require >128GB just to do the 32 bit count with full stack frames). If the int goes to 128 bit, all the memory chips ever produced in the world (and likely all those that will be produced in the next 20 years) would not be enough to stop this program from overflowing its stack - much unlike a TCE/TCO/C version. In my opinion, something that switches between bounded and unbounded memory requirements should not be called "optimization", but to I guess to each their own.