7 ms·

`safercopy` also does not always terminate, say if one of the passed pointers point to invalid memory, which then segfaults when accessed. Similarly, you can ha

by arielby 12y ago

`safercopy` also does not always terminate, say if one of the passed pointers point to invalid memory, which then segfaults when accessed. Similarly, you can have problems if the destination buffer overlaps the saved return address of the stack of another thread. C's type-system is unsound, and even if it was sound, it is too weak to express interesting invariants, certainly it is far too weak to express invariants required for termination. In fact, no popular language can express the invariant "this doubly-linked list doesn't contain a cycle", which is essentially required for termination when working with these. Even ignoring termination, in essentially all languages, including C, there are properties like "this object isn't going to be accessed by another thread" which can't be expressed in the type system, or even checked at runtime, but are required for any interesting kind of correctness.

Certhas 12y ago
Doesn't Rusts linear type system ensure the latter?
- chongli 12y ago
  But is Rust a popular language? Weasel words strike again!
- arielb1 12y ago
  Functional languages, along with Rust's linear type-system, can ensure this for single-ownership structures (trees, singly-linked lists), but not for structures with more complex ownership, like doubly-linked lists. The unpopular languages I was talking about were Agda and friends.
  - pcwalton 12y ago
    To be clear, though, Rust's type system can ensure thread safety of doubly-linked lists if you use the doubly-linked list structure in the standard library (or write one yourself using RC/etc.)
- steveklabnik 12y ago
  We technically have affine types, not linear.
heinrich5991 12y ago
Rust can do some of this.
zedshaw 12y ago
I don't think you know what it means when someone asks whether a loop will terminate. It's an analysis of the logic of the loop to determine if it will exit. This kind of analysis has been the actual foundation of computer science since there was computer science. I believe this guy Turing was doing some stuff with it. However, you have a logical flaw in your statement. You say the function will not terminate if it is passed an invalid pointer, but processes terminate when they access invalid pointers. If that's true, then it will terminate. However, if processes do not terminate when passed invalid pointers, then this function will still terminate because it will hit the end of its length variable and terminate. So you're wrong on many counts.
- mikeash 12y ago
  I take it that you're completely unfamiliar with the concept of "undefined behavior" in the context of C. You're not qualified to discuss the language at this level until you understand that. It's possible to invoke undefined behavior in your function. Undefined behavior can mean something never terminates. Thus, it's possible for your function to never terminate. If you don't believe me, I pose the following challenge: give me an implementation of this function. I will then provide a chunk of code that calls it and causes it to enter an infinite loop.
  - zedshaw 12y ago
    Ahhh the "undefined behavior" trope, whereby a C "expert" who's memorized a standard trots out the abstract machine to justify his point. An abstract machine that doesn't actually exist and that no computer actually functions as. I'll take you up on that challenge. I'm curious to see how you'd write a program to make a for-loop never exit. Give me a few minutes...
  - zedshaw 12y ago
    Alright my friend, here's the gist: https://gist.github.com/zedshaw/c20a69f17578909523c4 https://gist.github.com/zedshaw/c20a69f17578909523c4 The rules: 1. You said you can make that for-loop run forever that can call it and it'll enter an infinite loop. 2. To prove that, you can only alter the main function, then hand me back the code and I'll compile it and run it on my machines. 3. It has to run without stopping for 24 hours. If you can do that then I'll consider that an "infinite loop". 4. You can't call any more functions than what's in there already. So no fancy hacks to keep the OS from allowing segfaults by putting in signal handlers, linking against other libraries, or anything. Very curious how you do this. This is fun! Edit: And, I may not be checking comments so email me to gloat if you figure it out. help@learncodethehardway.org any time. You can also post it here. Just link me the reply so I can go look.
dllthomas 12y ago
'there are properties like "this object isn't going to be accessed by another thread" which can't be expressed in the type system,' In a recent project, I effectively enforced exactly that - in C. It was in a limited context but it saved my ass many times and eased refactoring substantially.

by arielby 12y ago

Certhas 12y ago

Doesn't Rusts linear type system ensure the latter?

chongli 12y ago
But is Rust a popular language? Weasel words strike again!
arielb1 12y ago
Functional languages, along with Rust's linear type-system, can ensure this for single-ownership structures (trees, singly-linked lists), but not for structures with more complex ownership, like doubly-linked lists. The unpopular languages I was talking about were Agda and friends.
- pcwalton 12y ago
  To be clear, though, Rust's type system can ensure thread safety of doubly-linked lists if you use the doubly-linked list structure in the standard library (or write one yourself using RC/etc.)
steveklabnik 12y ago
We technically have affine types, not linear.

heinrich5991 12y ago

Rust can do some of this.

zedshaw 12y ago

I don't think you know what it means when someone asks whether a loop will terminate. It's an analysis of the logic of the loop to determine if it will exit. This kind of analysis has been the actual foundation of computer science since there was computer science. I believe this guy Turing was doing some stuff with it. However, you have a logical flaw in your statement. You say the function will not terminate if it is passed an invalid pointer, but processes terminate when they access invalid pointers. If that's true, then it will terminate. However, if processes do not terminate when passed invalid pointers, then this function will still terminate because it will hit the end of its length variable and terminate. So you're wrong on many counts.

mikeash 12y ago
I take it that you're completely unfamiliar with the concept of "undefined behavior" in the context of C. You're not qualified to discuss the language at this level until you understand that. It's possible to invoke undefined behavior in your function. Undefined behavior can mean something never terminates. Thus, it's possible for your function to never terminate. If you don't believe me, I pose the following challenge: give me an implementation of this function. I will then provide a chunk of code that calls it and causes it to enter an infinite loop.
- zedshaw 12y ago
  Ahhh the "undefined behavior" trope, whereby a C "expert" who's memorized a standard trots out the abstract machine to justify his point. An abstract machine that doesn't actually exist and that no computer actually functions as. I'll take you up on that challenge. I'm curious to see how you'd write a program to make a for-loop never exit. Give me a few minutes...
- zedshaw 12y ago
  Alright my friend, here's the gist: https://gist.github.com/zedshaw/c20a69f17578909523c4 https://gist.github.com/zedshaw/c20a69f17578909523c4 The rules: 1. You said you can make that for-loop run forever that can call it and it'll enter an infinite loop. 2. To prove that, you can only alter the main function, then hand me back the code and I'll compile it and run it on my machines. 3. It has to run without stopping for 24 hours. If you can do that then I'll consider that an "infinite loop". 4. You can't call any more functions than what's in there already. So no fancy hacks to keep the OS from allowing segfaults by putting in signal handlers, linking against other libraries, or anything. Very curious how you do this. This is fun! Edit: And, I may not be checking comments so email me to gloat if you figure it out. help@learncodethehardway.org any time. You can also post it here. Just link me the reply so I can go look.

dllthomas 12y ago

'there are properties like "this object isn't going to be accessed by another thread" which can't be expressed in the type system,' In a recent project, I effectively enforced exactly that - in C. It was in a limited context but it saved my ass many times and eased refactoring substantially.