[C++] Equality preservation

Reference:
Equality preservation

Equality Preservation is a rule that says a function (or expression) must be "well-behaved" and "predictable."

It essentially means: If you give it the same inputs, you should get the same outputs.

• The Core Idea: "No Surprises"

If we have two objects, a and b, and they are equal (a == b), then doing the same thing to both of them should result in the same outcome.

Equal Inputs -> Equal Results: If f(a) returns 5, and a == b, then f(b) must also return 5.

Equal Inputs -> Equal Side Effects: If calling f(a) changes a to 10, then calling f(b) must change b to 10.

• The Requirement of "Stability"

The standard also requires equality-preserving expressions to be stable. This means if we haven't changed the object ourselves, calling the function twice on the same object must give the same result both times.

Example of something NOT stable:
A function that returns a random number or a function that uses a global counter that increments every time you call it. i.e. has no Referential transparency

    int counter = 0;

    int bad_function(int x) { return x + (counter++); } // NOT equality-preserving

By requiring concepts to be equality-preserving, C++ guarantees that:

• The algorithm can trust the values it reads.
• The algorithm can safely make copies of objects and expect the copies to behave exactly like the originals.

Unless noted otherwise, every expression used in a requires expression of the standard library concepts is required to be equality preserving, and the evaluation of the expression may modify only its non-constant operands. Operands that are constant must not be modified.

In the standard library, the following concepts are allowed to have non equality-preserving requires expressions:

• output_iterator
• indirectly_writable
• invocable
• weakly_incrementable
• range

[software design][functional programming] Referential transparency

Referential transparency

An expression is referentially transparent if it can be replaced with its corresponding value without changing the program's behavior.

This means that for a function to be referentially transparent, it must be a pure function, which has two key properties:

• It always returns the same output for the same inputs.
• It has no side effects. (It doesn't modify global variables, print to the console, read from a file, make a network request, etc.)

[C++][Algorithm][design] predicate callable logic for sorting (and any of the ordering function/algorithm call)

Reference:
https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/
https://vsdmars.blogspot.com/2018/06/c-regular-type.html

https://www.youtube.com/watch?v=2FAi2mNYjFA

Concept:

std::equality_comparable

Type:

std::nan

Design by contract (link to defensive programming)

P: precondition

Q: operation

R: postcondition

Domain (as in math)

Domain of operation is used in the ordinary math sense to denote the set of values over which an operation is (required to be) defined.

This set can change over time. Each component may place additional requirements on the domain of an operation.

These requirements can be inferred from the uses that a component makes of the operation and are generally constrained to those values accessible through the operation's arguments.

Domain of the operation is NOT the types of the arguments.

 

Safety & Correctness

• An operation is safe if it cannot lead to UB
• directly or indirectly
• even if the operation preconditions are violated
• An unsafe operation may lead to UB if preconditions ever are violated
• Either directly or during subsequent operations, safe or not

Code that violates preconditions is incorrect.

Requirements for correctness

• A correctly implemented operation guarantees that:
• If preconditions are satisfied
• The operation will either succeed, result matches post conditions
• Or report failure, return an error, thrown an exceptions, set errno etc.
• Any objects being mutated by the operations must be left in a "known or determinable state"
• A weaker requirement than valid
• If preconditions is not satisfied
• If the operation is safe
• The result is unspecified which could include:
• Failure
• Trapping
• Leaving any object being mutated by the operations in an unspecified, possibly invalid state.
• If the operations is unsafe
• The behavior is undefined(Full STOP)

Compiler can do /anything/ if there's an UB(stripping expressions etc.)

We could exploit contract to work for us; e.g. unsigned (contracted with mod(2^b))

Strong preconditions

• Pros
• flexibility of implementation
• ascribe meaning and intent to an operation
• simplify requirements and reasoning about code
• Cons
• limit clever uses that exploit otherwise defined behavior
• allow for variance in behavior between implementations

ALWAYS refer to C++ ISO for contract of std::

A tl;dr take away for predicator of sorting

When calling any of the ordering functions including

• std::sort
• std::find

compare functions(aka predicate) much comply with the strict weak ordering which formally means the following:

• Irreflexivity: x < x is false (strict partial order rule)
• Asymmetry: x < y and y < x cannot be both true (strict partial order rule)
• Transitivity: x < y and y < z imply x < z (strict partial order rule)
• Transitivity of incomparability: x == y and y == z imply x == z, where x == y means x < y and y < x are both false (equivalence relations on incomparable elements rule)

Above conditions are used for optimization purposes and an abide by is a must for code correctness.

[Defensive Programming]

Reading notes of
John Lakos "Defensive Programming Done Right, Part I"
John Lakos "Defensive Programming Done Right, Part II"
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4075.pdf

Design by Contract:

1. What it does
2. What it returns
3. Essential Behavior
4. Undefined behavior unless...
5. Note that


Verification:
1. Preconditions
  RTFM read the fxcking manual
  Assert

2. Postconditions
  Component-level test drivers

3. Invariants
  Assert invatiants in the destructor


-----
4 things:
  1. component level testing
  2. peer review
  3. static analysis tool
  4. DP
-----

Why do we assert only in safe debug mode?

Put assert on postconditions? Time to confirm th test.

Must the code itself _preserve_ invariants even if one or more preconditions of a contract are violated?
NO!!!

-----

What is DP?
Redundant code that provides runtime checks to detect and report
(but not 'handle' or hide) defects in software.

DP good or bad?
Both.
add overhead, but help idenfity defects.

What are we defending against?
1. Bugs in software we use. (Not DP!)
2. Bugs we introduced. (No...)
3. Misuse by our clients. (YES!!)
-----

Fat interface / bad / not proper inheritance
Large interface / bad / not minimal/primitive
Wide contract / bad / No preconditions

------
Narrow contracts imply UB!

Assert inside the funciton. Don't just return 0/false/none

------
Should setXXX mem_fn return status?
NO!!!!

Returning status implies wide contract.

Wide contracts prevent defending against
  such errors in _any_ build mode.


Beware!! assert is expansive!!


Narror contract only check in debug mode.
Wide contract checks by every call!
------

Preconditions _always_ imply postconditions.

**
If a function cannot satisfy it's contract,
it must _not_ return normally.

------
abort() should be considered a viable alternative to
throw in virtually all cases(if exceptions are disabled)

-----
**
Good library components are exception-neutral! (via RAII)

-----
**
What should happen when the behavior is undefined?
Should what happens be part of the component-level contract?
  NO!! Otherwise it would be a behavior contract.
  Do not document UB!
  Otherwise it's not UB anymore!
-----

-----------------------------------
Implementing defensive checks.


---
What should happen if the client misuses library code??

Ask library component to warn us?

1. Document
2. Detect UB
3. Detect all UB?
4. How much CPU time should spend trying to detect misuse of library code?

a. Terminate the program
b. Thrown exception
  c. Save client work before terminate
  d. log error
  e. sent back to programming msg?


---
Plan(Part 1):
Provide 3 kinds of assert macros for library writer to use.

Assert_Opt(Expr)  < 5% CPU

Assert(Expr)  5% ~ 20% CPU

Assert_Safe(Expr) > 20%

---
Plan(Part 2)
Provide a global callback facility.

using handler = void (*)(const char* text, const char* file, int line)
// move the parameters into a single Struct type..


1. failAbort // print and terminate
2. failThrow // wrap into std::logic_error
3. failSleep // print to stderr and spin/sleep

---

e.g
void fun()
{
  auto result = library_func(); //library_func implement assert
}


---
Rule of thumb(guideline):
1. inline functions use Assert_Safe
2. Non-inline functions use Assert

---
Hard vs. Soft UB:
2 separate notion of UB.

1. Language UB (Hard UB)

2. Library UB (Soft UB)

With Library(i.e Soft) UB, (a contract violation)
nothing dire has happened yet, but it could easily lead to Language UB.

Soft UB is relative:
  . not privy to the implementation, might lead to Hard UB.
  . Contract violation can remain Soft UB.


--------
Compile macro build mode.

--------

Mixed-Mode Assertion Build

1. ABI incompatibility.
No.
  .all assertion-level modes musy be ABI compatible.
  .Only permitted side-effect is to invoke the failure handler.

2. Violating the ODR. Yes
-----------

c++11 noexcept: and C++14 follow this standard.
1. Use only for move constructors and move assignment
2. Use whereever there is a wide contract, and the operation must never throw.
3. Use whereever the operation must never throw in contract.