3 ms·
There are many types of observation we might define. The most fundamental is whether we can write a program which halts in one case and doesn't in the other.
by chriswarbo 6y ago
There are many types of observation we might define.
The most fundamental is whether we can write a program which halts in one case and doesn't in the other.
An alternative is whether we can write an if/then/else branch to distinguish between the two cases. Note that this is less general than the above, since we can always use an if/then/else to implement a halt/no-halt program, but we can't always go the other way (due to the Halting Problem). This definition is useful, since if/then/else can cause arbitrarily-large changes to a program's behaviour; whereas we can't "use" a difference which affect halting.
Another definition, which is more subjective, is whether we can do the above "reliably". For example, any optimisation that makes a program faster could be observed by a language which allows access to a clock. Whilst hackers and debuggers might find these useful, it's not the sort of thing that a "reasonable" programmer would do (i.e. code which relies on this sort of thing shouldn't pass code review). I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category.
The messy subjectivness of the latter is why I like to limit the capabilities of what I'm developing with: I don't have to care about timing altering the behaviour of a program which can't access a clock.
- chrisseaton 6y agoRight - but you can observe the differences reliably without a clock, through looking at the stack trace.
- eru 6y agoThat's (a small) part of the reason why Haskell didn't have stack traces for the longest time.
- beagle3 6y agoOr even more simply, by blowing up the stack. If you manage to do 2^40 calls deep without blowing up the stack, you have TCE, if you do blow up the stack, you don't. And you can tell if you blew up the stack by setting up an exception handler (or lisp condition or whatever equivalent).
- chriswarbo 6y ago> you can tell if you blew up the stack by setting up an exception handler (or lisp condition or whatever equivalent). That only works if there's some way to tell whether the stack blew up (as you say: catching exceptions, lisp conditions, or whatever equivalent). I'd put those language features in the 'messy' category: useful on occasion; not used by most code; makes all code harder to reason about (hence the subjective "reasonably-unobservable" category above)
- chriswarbo 6y agoClocks and timing were one example. I generalised to these other cases when I said: > I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category. I would put such things in the "unreliable" category, since it's the sort of thing that may vary between compilers (including future versions), and may depend on internal details of dependencies which are subject to change. I certainly wouldn't let them through code review; it can be hard trying to understand 'foo(bar)' in terms of 'the function "foo" applied to the input "bar"', I'd rather avoid the extra complications of having to think about 'pushing a fresh stack frame, clearing registers A, setting the instruction pointer to B, adding C instructions to the ALU's adder pipeline, forcing a flush of D cache lines, ...'