0

In computer programming, it has become fashionable for compilers (processors of computer language) to apply the following form of reasoning:

  1. A language standard would permit a compiler to assume that a program will do X.

  2. A compiler can determine that if a program were to receive input Y, it would not do X.

  3. Consequently, the compiler should ignore any code that would only be relevant if the program were to receive input Y.

If one accepts that a language standard would impose no requirements upon the behavior of the system if a program fails to X, then it would likewise impose no requirements upon the behavior of the system if the program receives input Y. Something, however, still seems wrong with step #3.

Are there any disciplines other than compiler design in which permission to assume X would imply permission to disregard any evidence contrary to X?

6
  • Would you have an example? I mean it seems like this could be used to justify removing fail-safe behavior if the assumptions are too optimistic. Another issue could be reachability -- for example, if there's a blocking infinite loop before X, e.g. for (;;), then that might be taken to satisfy the assumption that X will be done while still allowing it to be provable that X won't happen, falsely excluding the possibility of Y. Then there're probably other ways this sort of logic could go wrong if misapplied, too.
    – Nat
    Jan 23, 2020 at 18:54
  • @Nat: The C Standard explicitly provides that compilers may assume that loops will terminate if their exit is statically reachable and they perform neither I/O nor volatile accesses. I think the intention is that the time required to execute a piece of code need not be treated as an observable side-effect, even if it happens to be infinite, thus allowing operations to be reordered across loops whose sole interaction with those operations would be to delay the later ones. Quite reasonable, provided that such optimizations uphold the principles of causality.
    – supercat
    Jan 23, 2020 at 19:20
  • @Nat: My interest, though, is more with the philosophical question of whether that form of logic is applicable in any disciplines other than computer programming apply logic in that fashion. I could flesh out the example more, but I thought the computer aspects would distract from the broader philosophical one. Perhaps a real world analogy would help, e.g. "Bob is told Joe will be at a party. Bob knows that if a bridge gets washed out, Joe won't make it. Thus, Bob should recognize that any 'BRIDGE OUT' signs on the road toward the bridge will be erroneous and should be ignored."
    – supercat
    Jan 23, 2020 at 19:23
  • Ohh, yeah, that third statement's off. Since Bob can't see any "BRIDGE OUT" signs, he doesn't need to ignore them. Rather, the proper conclusion is that Bob doesn't need to waste effort looking for "BRIDGE OUT" signs, as there can't be any. (Though he needn't go out of his way to avoid them, either; for example, if he needs to look out for other signs anyway, he needn't do anything special to avoid the possibility of seeing a non-existent "BRIDGE OUT" sign.)
    – Nat
    Jan 23, 2020 at 19:37
  • @Nat: Perhaps the "should ignore" is a bit strong. Perhaps "may safely ignore"? Some compilers seem very eager to make assumptions about code they can skip, even in scenarios where code that only handles two specific input cases ends up being bigger and slower than code to handle all cases using wraparound integer semantics.
    – supercat
    Jan 23, 2020 at 20:23

3 Answers 3

1

Example: Tolerance limits in engineering design.

Tolerance limits might be a good example.

For example, engineers are often asked to design

  • shelves, that hold up to a certain weight;

  • electrical wires, that carry up to a certain electrical current;

  • web servers, that serve up to so many web clients;

  • towers, that withstand up to so much wind;

and other things that must work up to a certain limit. By knowing a limitation, someone designing a book shelf can ignore, say, the possibility that 10 tonnes of books might be piled on-top.

The underlying logic is that the designer (compiler, etc.) isn't held accountable for its behavior in the excluded cases, so it doesn't need to worry about them.

15
  • That is the "normal" use of assumptions, but what I'm talking about is a form of "reverse causal" assumption, e.g. using the fact that the material specifications for a radio tower would cause it to fail given a 90mph wind to infer that no wind over 90mph will ever occur, and there's thus no need to engineer any structure to handle winds stronger than that.
    – supercat
    Jan 25, 2020 at 0:35
  • 1
    @supercat I'm not 100% sure where perspectives are diverging here, but here's my guess: I think you're taking the reverse-causality thing to hold in a global context whereas it's actually meant to hold in a contractual context.
    – Nat
    Jan 25, 2020 at 2:36
  • @supercat To use your example, when an engineer designs a tower, they typically can't make one that's infinitely strong; towers typically have a point at which they can fail violently. If such a failure occurs outside of the contractual frame -- for example, if it occurs due to winds that the standards didn't require tolerance for -- then presumably the engineer wouldn't be liable, as they never claimed that their work would stand up to extremes outside of the operating specs (including regulations, etc.).
    – Nat
    Jan 25, 2020 at 2:41
  • 1
    @supercat I think I'm having trouble figuring out where you're coming from; some context might help me. So far, it's my impression that you're primarily interested in a provision from the C Standard that says something like that the compiler can assume that method calls will always return, such that the compiler isn't liable for the behavior of any method call that wouldn't return, e.g. due to call parameters that would result in it not returning. I'd further speculate that you don't like this because relatively minor call errors can result in larger blow-ups. Is this sorta about it?
    – Nat
    Jan 25, 2020 at 3:17
  • 1
    Consider the function long long test(long long x, long long y) do { x = someSlowFunctionWithNoSideEffects(x); } while(x); return x | y; } I would regard it as reasonable for a compiler to assume if y==-1, the loop won't affect the result and may thus be skipped, or to assume that if the loop completes the function will return y. I don't think the authors of the Standard intended to suggest that compilers should apply both assumptions together to make the function unconditionally return y without regard for whether x would ever be zero.
    – supercat
    Jan 25, 2020 at 3:36
0

You seem to assume that this assumption is absolute and that it allows the compilers to completely detach from reality.

I don't believe that this is the case and I am pretty sure that compiler design is as evidence-driven as all other human activities. That is, if such assumptions allow to create a compiler that, despite following the standards to the letter, will produce buggy, slow or otherwise worthless code, this compiler won't see much use and will be abandoned in favour of another one that makes more reasonable assumptions.

If my assumption is valid, this would make compiler design not particularly unique among various disciplines.

8
  • One would wish that would be the case, but unfortunately the maintainers of two compilers which are popular because they are freely distributable have adopted the attitude that any code which doesn't work with their compilers is defective.
    – supercat
    Feb 24, 2020 at 6:34
  • 1
    @supercat I guess the question is: are they right? I'd wager that if large and popular software products would become unusable due to some overeager optimisation, this would become the compiler's authors' problem. If, on the other hand, the complaints are along the lines of "well, there ain't no synchronisation between the threads, but surely A can't happen before B!" or "sure, integer overflow happens here, but undefined behaviour can't conceivably mean returning 1 instead of 0!", then the suggestion to fix the goddamn code seems reasonable.
    – IMil
    Feb 24, 2020 at 9:05
  • The authors of the Standard explicitly said they did not wish to demean useful programs that happened not to be portable. Many programs are subject to the constraints (1) behave usefully when given valid inputs, and (2) behave in constrained fashion even when given maliciously-constructed inputs. In many cases, given an expression like x+y > z the most efficient code that would always either yield 0 or yield 1 with no side-effects would be more efficient than (int)((unsigned)x + y) > z, so requiring that programmers write the latter in cases where 0 or 1 would be equally acceptable...
    – supercat
    Feb 24, 2020 at 15:45
  • ...answers in cases of overflow makes the code harder to read, and forces compilers to generate machine code that wouldn't be necessary to meet the above constraints. Further, I don't think it's coincidental that clang and gcc tend to make inferences that are unambiguously forbidden by the Standard, but resemble cases that would be allowed, because their interpretation of the Standard ends up being unworkably complex. To them, however, this doesn't mean their interpretation is wrong, but instead it means the Standard is defective.
    – supercat
    Feb 24, 2020 at 15:47
  • 1
    If the useful program "happens not to be portable", this means that it depends on a certain environment to produce the code the effects of which match the code author's intentions. Nothing that gcc / clang writers can do may possibly violate this clause because "useful but non-portable" means, among other things, useful when compiled with the same compiler version.
    – IMil
    Feb 24, 2020 at 23:24
0

As an example: If you have a petrol car and take it to a gas station, you can assume that the pump marked “petrol” pumps petrol, and the pump named “diesel” pumps diesel. I know from personal experience that this is not always true (result was six trucks breaking down), but you can still assume it.

Here, “you can assume it” means that if your assumption is wrong, someone else will pay for the damage caused. Nobody can tell you “you should have checked that the diesel pump really pumps diesel”. Even if you didn’t the damage isn’t your fault.

Same for C compilers. A C compiler can assume that a program doesn’t invoke “undefined behaviour”, and “undefined behaviour” is very well defined in the C standard. Whatever bad things happen in the case of undefined behaviour is not the fault of the compiler but the fault of the programmer.

And the compiler can draw any logically correct conclusion from the assumption that undefined behaviour won’t happen. Even if the assumption is wrong. Even if the compiler has proof that the assumption is wrong.

1
  • Someone who goes into a petrol station might reasonably dispense fuel from the "diesel" pump into a diesel vehicle without first checking whether it was actually diesel fuel, if they had no reason to believe that the pump might be dispensing anything else. Modern C compiler behavior, however, is more akin to some motorist Joe deciding that since they saw some motorist Bob dispense fuel from the left side pump into a diesel truck, he should dispense fuel from the left side pump into his own diesel truck without bothering to look at the sign, and then blaming Bob for damage to his truck.
    – supercat
    Mar 18, 2022 at 23:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .