Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Defining the Undefinedness of C (2015) [pdf]

fsl.cs.illinois.edu

Post reply on HN
Print view View original

61–70 of 91 posts

Re: Defining the Undefinedness of C (2015) [pdf]

#61

Post by tom_mellior »

simias wrote: post #27
kps wrote: post #9

Earlier quoted context omitted.

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really…

This is not first hand, but the commonly given reason for undefined signed integer overflow is that it allows for mathematically correct reasoning: x < x + 1 is true for all x. Or rather, the compiler may assume that it is true and optimize accordingly, since the programmer is trusted to avoid the undefined overflowing case.

Re: Defining the Undefinedness of C (2015) [pdf]

#62

Post by tom_mellior »

bbatha wrote: post #28
kps wrote: post #9

Earlier quoted context omitted.

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

I've never really understood why this couldn't be slotted in as "implementation defined behavior". `add` has a well defined meaning on every platform just because it differs shouldn't give the compiler license to change the meaning of my program for that platform . It should however platform specific optimizations based on overflow, etc. Could somebody provide me with an example of truly undefinable behavior? (Perhap…

> truly undefinable behavior

Memory corruption is pretty undefinable. Imagine writing data through a wild pointer. The program might segfault immediately, or compute a wrong result but not crash, or crash at an arbitrary later point, or delete all your files, or...

It makes no sense to try to enumerate all that might happen, so this cannot really be implementation defined (where the implementation must document what will happen).

Re: Defining the Undefinedness of C (2015) [pdf]

#63

Post by chubot »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

I forget where I heard this formulation, probably in a paper about C semantics:

A useful way to think of C is as TWO languages. One language is the language of chars, ints, structs, arrays, functions, loops, if, etc. That language is fairly self-contained and could be implemented in a variety of ways.

The other is the language of memory. Pointers, non-checked array indexing, unsafe unions, guaranteed data layout, memory access alignment, arrays decaying to pointers, zero-width arrays, casting (especially the equivalent of reinterpret_cast in C++).

You could implement just the first language, without the second. You would have a lot of latitude in doing that. You could add all sorts of safety checks. So technically this kind of thing isn't fundamental to "C".

But it would be harder to port this language to new processors efficiently, and programmers wouldn't be able to give you hints about how to make things fast. Guaranteed data layout breaks the abstraction of the language -- but that's a good thing, for performance, and talking to hardware.

If you overconstrain the language, then some platforms would have to add a lot of checks that are not necessary on other platforms.

So if you mean "similar" by "a portable language that is efficient", then to some degree yes, because the problem of abstracting hardware is ill-defined. But if you just want to implement a safe C-like language, that's certainly possible. You could pretty much express everything you want to. You could rewrite the Linux kernel in that language probably (except maybe for interacting with mmapped hardware). But it would be slower.

I guess there is argument to how much slower it would be. It probably wouldn't matter for 90% of the code, but it would matter a lot for the hot code.

Summary: C works at two different abstraction levels that can be thought of as two languages. Hardware is a leaky abstraction.

Re: Defining the Undefinedness of C (2015) [pdf]

#64

Post by pjmlp »

pcwalton wrote: post #55
pjmlp wrote: post #38

Earlier quoted context omitted.

C will always be around, unless we get rid of UNIX and POSIX compatibility layers. Which given Microsoft's sudden love to stay relevant, means that we are at the edge of an UNIX monoculture. So any improvement to make C safer is more than welcome. My preference would be to have something like Frama-C be part of ANSI C.

Virtually nobody who is not already using Frama-C would start using it as a result of it being added to ANSI C. Ask industry C programmers "why aren't you using theorem provers to prove the correctness of your C code?" The number of them who will give you "because ANSI didn't standardize them" as an answer is zero.

I know, but since we are not going to get any UNIX/POSIX variant out there replaced with C++, let alone Rust, we better get ways of improving its safety. Even it means just pilling up safety band-aids.

Even Microsoft caved in regarding not supporting C newer than C89, and now have on their Visual Studio roadmap to improve the C support beyond what ANSI C++ requires.

https://www.reddit.com/r/cpp/comments/6mqd2e/why_is_msvc_usu...

They also rewrote their User-Mode Driver Framework (UMDF) from COM/C++ back into C, https://docs.microsoft.com/en-us/windows-hardware/drivers/wd...

I am really looking forward to Joe Duffy's keynote at Rustcon, regarding systems programming improvements.

Re: Defining the Undefinedness of C (2015) [pdf]

#65

Post by tom_mellior »

nickpsecurity wrote: post #22

That team’s awesome. One of few groups in formal methods using rewriting logic (Maude) instead of things like Coq or Isabelle/HOL. They seem to move faster on semantics as a result. They also build their own modified logic called matching logic on top that they claim is better than separation logic. http://www.kframework.org/index.php/Main_Page More interesting, their use of these tools allowed them to make their C s…

> using rewriting logic (Maude) instead of things like Coq or Isabelle/HOL. They seem to move faster on semantics as a result.

This statement is close to nonsensical. What are you comparing it to? Where is a comparable executable semantics project in Coq or Isabelle?

This is great work, and they are definitely using the right tool for the job. But the field of "formal methods" is enormous, and you seem to be saying that apples are better than oranges.

Re: Defining the Undefinedness of C (2015) [pdf]

#66

Post by kps »

gumby wrote: post #56
kps wrote: post #9

Earlier quoted context omitted.

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

Also C was designed for PDP-7/PDP-11 style machines with 8-bit bytes, 16-bit words and the like. It was ported to a variety of other architectures which had to make assumptions and adaptations. These live in UB. One somewhat unfortunate side effect of the pervasiveness of C and Unix-style machines is that it encouraged CPUs to optimize for C rather than the opposite way around. The use of GPUs for non-graphics progra…

Point of order: the PDP-7 had 18-bit words (and no smaller addressable unit).

Re: Defining the Undefinedness of C (2015) [pdf]

#67

Post by jjnoakes »

inetknght wrote: post #42
simias wrote: post #39

Earlier quoted context omitted.

But what if it's the result of some inlining or simply macro expansion? It's a tough call to make.

If it's from inlining, then the compiler has a bug. If it's from a macro, then stop using macros in a broken fashion. Let it be an error.

How would that be a compiler bug? Assuming g() is never called with a NULL pointer, this code should not produce any compile-time errors:

    int f(int *x)
    {
      if (x == NULL) return 0;
      return *x;
    }
    
    int g(int *p)
    {
      return (*p) + f(p);
    }

Re: Defining the Undefinedness of C (2015) [pdf]

#68

Post by kps »

simias wrote: post #12
iainmerrick wrote: post #7

Earlier quoted context omitted.

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I…

But at the time C89 invented 'undefined behaviour', C compilers didn't (couldn't) do that. This modern interpretation simply didn't occur to anyone at the time. If it had, people would have screamed bloody murder, and the language simply would not have passed. Compare dmr's criticism of the 'noalias' proposal: “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”.

In the accompanying Rationale, the committee explicitly calls out places where the standard intentionally diverged from existing practice; they did not do so for UB. They thought “the most serious semantic change” was mandating value-preserving rather than unsigned-preserving integer promotion.

Re: Defining the Undefinedness of C (2015) [pdf]

#69

Post by spc476 »

simias wrote: post #27
kps wrote: post #9

Earlier quoted context omitted.

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really…

The VAX. There's a bit in the condition codes register that indicates if overflow traps or not.

Then there's the matter if ((char )0) causes a trap or not; on systems without a MMU, it probably won't trap [1]. It's differences like overflow and memory references that cause most of the UB you see in C.

[1] On Linux, you can map a page to address 0. But that you can, doesn't mean you should.

Re: Defining the Undefinedness of C (2015) [pdf]

#70

Post by etqwzutewzu »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

> something I'd love to know about undefined behavior in C: is this something specific to C

Other languages with undefined behavior: Algol 68, Fortran and Lisp.

Post reply on HN