4 ms·

> We teach algorithms so that students learn to think about invariants and properties when writing code. ...To write correct, robust code at work, you need to t

> We teach algorithms so that students learn to think about invariants and properties when writing code. ...To write correct, robust code at work, you need to think about invariants. Dumb question, what are invariants? I've been writing code for about 15 years and I haven't heard this term.

simjnd 3y ago
IIRC invariants are pre-conditions and post-conditions, the context/state before and after an instruction/function is executed.
deleted 3y ago
[deleted]
pkaler 3y ago
> Dumb question, what are invariants? The term that you want to Google or ask ChatGPT is "Design By Contract". An invariant is something that is true during the lifecycle of a class, function, loop, service, system, etc. Invariants, preconditions, and postconditions are the three primary constructs in DbC.
- rahimnathwani 3y ago
  Thanks. I asked ChatGPT about the relationship between invariants and Design by Contract: https://chat.openai.com/share/dd2313ac-6088-455c-9d03-01795e62ab85 https://chat.openai.com/share/dd2313ac-6088-455c-9d03-01795e...
valbaca 3y ago
In computer science, an invariant is a logical assertion that is always held to be true during a certain phase of execution of a computer program. For example, a loop invariant is a condition that is true at the beginning and the end of every iteration of a loop. https://en.wikipedia.org/wiki/Invariant_(mathematics)#Invariants_in_computer_science https://en.wikipedia.org/wiki/Invariant_(mathematics)#Invari...
- dr_dshiv 3y ago
  Sounds really Platonic — like, a loop invariant maintains the Platonic form of a loop?
csrf-token 3y ago
The way I think of invariants is in less formal terms, but which I find helpful on a day-to-day basis. Often, we write code that manipulates state. It can be difficult to reason about code that manipulates state if we can't narrow down the possible states an object or struct can be in during execution. Invariants in our code or design can help narrow down this space of possible states by ensuring that certain combinations are impossible. For instance, assume I have an object that contains an array of integers and a boolean called `hasNegatives` which should be true if and only if the array contains at least one negative integer. If the boolean can be updated or set independent of the array, then the object can't really guarantee that the array and `hasNegatives` will always be "in sync" so to speak. If your code promises to maintain that invariant (by, for instance, making `hasNegatives` read only and privately updating it when the setter for the array is called to match what's inside the array) then when using this object or seeing an instance of it elsewhere in the code you can happily use it with confidence knowing that the field is always correct with respect to the array within. Obviously, this is a simplified example, but when applied to an object with many fields, knowing that only certain valid combinations are possible can radically simplify the rest of your code that interacts with that object.
dunham 3y ago
Essentially a constraint that is true about the variables, which helps you reason about the code. A good example is: // Invariant: x[i-1] < target, x[j] >= target. In the golang implementation of binary search: https://github.com/golang/go/blob/master/src/slices/sort.go#L124-L141 https://github.com/golang/go/blob/master/src/slices/sort.go#...
- rahimnathwani 3y ago
  I wish I could upvote this more than once. Not only because of the clear first line, and the inline example, but especially because you linked to a specific function in a real code base.

simjnd 3y ago

IIRC invariants are pre-conditions and post-conditions, the context/state before and after an instruction/function is executed.

deleted 3y ago

[deleted]

pkaler 3y ago

> Dumb question, what are invariants? The term that you want to Google or ask ChatGPT is "Design By Contract". An invariant is something that is true during the lifecycle of a class, function, loop, service, system, etc. Invariants, preconditions, and postconditions are the three primary constructs in DbC.

rahimnathwani 3y ago
Thanks. I asked ChatGPT about the relationship between invariants and Design by Contract: https://chat.openai.com/share/dd2313ac-6088-455c-9d03-01795e62ab85 https://chat.openai.com/share/dd2313ac-6088-455c-9d03-01795e...

valbaca 3y ago

In computer science, an invariant is a logical assertion that is always held to be true during a certain phase of execution of a computer program. For example, a loop invariant is a condition that is true at the beginning and the end of every iteration of a loop. https://en.wikipedia.org/wiki/Invariant_(mathematics)#Invariants_in_computer_science https://en.wikipedia.org/wiki/Invariant_(mathematics)#Invari...

dr_dshiv 3y ago
Sounds really Platonic — like, a loop invariant maintains the Platonic form of a loop?

csrf-token 3y ago

The way I think of invariants is in less formal terms, but which I find helpful on a day-to-day basis. Often, we write code that manipulates state. It can be difficult to reason about code that manipulates state if we can't narrow down the possible states an object or struct can be in during execution. Invariants in our code or design can help narrow down this space of possible states by ensuring that certain combinations are impossible. For instance, assume I have an object that contains an array of integers and a boolean called `hasNegatives` which should be true if and only if the array contains at least one negative integer. If the boolean can be updated or set independent of the array, then the object can't really guarantee that the array and `hasNegatives` will always be "in sync" so to speak. If your code promises to maintain that invariant (by, for instance, making `hasNegatives` read only and privately updating it when the setter for the array is called to match what's inside the array) then when using this object or seeing an instance of it elsewhere in the code you can happily use it with confidence knowing that the field is always correct with respect to the array within. Obviously, this is a simplified example, but when applied to an object with many fields, knowing that only certain valid combinations are possible can radically simplify the rest of your code that interacts with that object.

dunham 3y ago

Essentially a constraint that is true about the variables, which helps you reason about the code. A good example is: // Invariant: x[i-1] < target, x[j] >= target. In the golang implementation of binary search: https://github.com/golang/go/blob/master/src/slices/sort.go#L124-L141 https://github.com/golang/go/blob/master/src/slices/sort.go#...

rahimnathwani 3y ago
I wish I could upvote this more than once. Not only because of the clear first line, and the inline example, but especially because you linked to a specific function in a real code base.