3 ms·
Because as explained in the article, elementary things like memory access a[i] are not constant time with respect to i? Because an arbitrary C program will hav
by voidmain 9y ago
Because as explained in the article, elementary things like memory access a[i] are not constant time with respect to i?
Because an arbitrary C program will have non-constant branches (so may become exponentially long in your proposed instruction set) and loops (not representable at all in your proposed instruction set)?
If what you are saying is that a language could hypothetically statically verify that the execution of a function was constant time with respect to certain inputs, that sounds like it would work and that the only obstacle is engineering effort. But compiling to such a language doesn't sound very practical to me.
- Verdex_3 9y agoI think someone wrote an applicative functor instance in haskell that would accomplish something like this. I forget if it was constant space or time or what (I can't find the link unfortunately). All I remember at the time was thinking I had no idea why anyone would want this. But then someone (on either hn or proggit) mentioned that there were crypto reasons why it would be useful. So I suspect that compiling isn't too bad ... however, programming with it probably is annoying. EDIT: Actually, it looks like it was top comment in this thread: https://news.ycombinator.com/item?id=7557089 https://news.ycombinator.com/item?id=7557089 Kind of a neat idea at any rate.