Chapter 7: Reasoning About Correctness
The introduction proposes algebraic reasoning about values and their relationships as a way to judge whether code is simpler.
After this chapter you will be able to
- Algebraic criterion for simplicity. Explain why the chapter calls code simpler when we can reason about the values it denotes and the relationships between them, rather than relying on labels such as SOLID or OOP.
- Implementation Coupled Test Limits. Explain why tests aimed mainly at executing implementation details may fail to establish correctness.
- Algebraic Basis For Correctness. Explain how thinking algebraically connects the intended meaning of data to implementation and testing.
- Algebraic Elements and Constraints. Describe an algebra as a set of things, operations on them, and rules those operations must follow. Explain that the operations considered here are deterministic functions that take data in and return data without side effects.
- Equations and Universal Laws. Explain how deterministic operations allow two different-looking pieces of code to be compared by their results, potentially letting a simpler expression replace a complex one. Describe the laws sought through equational reasoning as claims that hold for all possible inputs, not just an example.
- Meaning Before Implementation. Describe how the section frames merging two conflicting duplicate records by asking what it would mean to “add” them. Explain why focusing on that small combination question provides a language for correctness without first choosing an implementation.
- Closed binary operation shape. Describe the binary operations considered here: they take two values of the same type and return a value of that type. State that Java provides BinaryOperator as a specialization of BiFunction.
- Recognizing disguised binary operations. Explain why a binary operation may not look like one in Java code, including when it appears as a one-argument operation on an object or is obscured by an implementation.
- Algebra Beneath Imperative Code. Explain why looking for binary operations in imperative code changes how you reason about it.
- Map Addition And Collisions. Explain how map updates become a combining operation and why collisions need a choice of behavior.
- Duplicate Pipeline As Combination. Trace why grouping and reducing duplicate records can collapse into repeated map combination.
- Order and grouping effects. Explain how changing argument order or grouping chained binary operations can change the result, depending on the operation and its data type.
- Properties that define correctness. Describe what the section calls an algebraic operation’s properties and why they matter to correctness.
- Universal assertions over states. Explain what it means to assert that an invariant holds for all possible states, and how a type’s set of possible values defines those states.
- Composite state enumeration. Describe how to determine every state of a record from its attributes’ possible values, including the empty state of an Optional.
- Relationships between exhaustive states. Explain how combining exhaustive state sets lets an assertion check an invariant between any two states, and how repeating the combination extends this to larger relationships.
- Optional state-space count. Explain how the section arrives at 90 possible states by counting the empty state added by each Optional.
- Practicality of state generation. Justify why generating every state with for-loops can be practical for well-modeled domains, while recognizing that it is not always worthwhile or feasible.
- Universal quantifier and states. Explain how ∀, a variable, and a set express a claim about every state in that set.
- Associative Grouping of Operations. Explain that associativity means grouping binary operations differently should give the same result, so the grouping need not be chosen in advance.
- Flexible Execution and Correctness. Describe why associativity lets a reducer choose where and how to group work, including parallel work, and why the property can be written down as a law to test an implementation.
- Limits of DRY refactoring. Explain why extracting duplicated conditional logic does not, by itself, make the RawData combination easier to reason about or test.
- Favorability as an ordering. Explain how the RawData requirements can be understood as comparisons of favorability, even though favorability is not an explicit value in the code.
- Properties of ordering relationships. Distinguish a total order, which needs reflexivity, transitivity, and antisymmetry, from other relationships that may have only some of those properties.
- Favorability correctness properties. Explain how describing domain favorability as a total order gives tests criteria for correctness above the level of individual implementation branches.
- Monotonic Favorability. Explain why ordered data alone does not guarantee that combining it preserves favorability, and describe the monotonic behavior the algebra requires.
- Properties as correctness criteria. Explain how properties can specify correct behavior when combining conflicting domain data: they identify the possible states and the invariants that must hold between them, giving a test suite a basis for checking correctness.
- Lifting behavior into Optional. Explain what lifting means in this section and why it is useful for the existing algebra.
- Optional Argument Rule of Thumb. Distinguish generic tooling that accepts an Optional from code that inspects its concrete contents, and explain why an IDE warning is not an absolute prohibition.
- General-purpose BinaryOperator lifting. Explain how extracting the common pattern turns an operation tied to integer addition into a function that accepts any BinaryOperator and returns one that works with Optional values. Distinguish lifting the operator itself from supplying its arguments.
- Algebra over Optional values. Explain that lifting the algebra’s binary operators lets the algebra work with Optional values, and that its correctness still needs to be checked by extending the chapter’s properties to the new data type.
- Implementation-independent algebraic properties. Explain why the finished implementation is not the only valid one: the algebraic properties established earlier hold for any implementation and can be used in tests to check correctness.
- Standard Library Over Specialization. Explain why the author chooses regular Java library types instead of encoding the chapter’s algebraic ideas in special interfaces: the social friction of math-heavy abstractions and the interoperability costs of bespoke types.
- Everyday value of algebraic properties. Explain why recognizing algebraic properties matters in ordinary programming.
What it builds on
- Functions, Purity, and Determinism (chapter 6) · The earlier discussion of functions, purity, and determinism.
- Programming with immutable data (chapter 2) · Assumes familiarity with programming using immutable data.
- Implementing the deterministic core (chapter 6) · Uses the implemented domain behavior as the code being reconsidered.
- Types denote sets of values (chapter 3) · Types denote sets of values.
- Product Types (chapter 4) · Records as product types.
Section by section
Introduction
The introduction proposes algebraic reasoning about values and their relationships as a way to judge whether code is simpler.
- Algebraic criterion for simplicity: Explain why the chapter calls code simpler when we can reason about the values it denotes and the relationships between them, rather than relying on labels such as SOLID or OOP.
Why it matters: It gives you a more useful basis for discussing design than competing claims that something is “simple.”
Key terms: algebraic properties, set of values, relationships between values, simpler
7.1 We begin with an exercise
An ETL exercise with conflicting customer records introduces the need to define correctness independently of an implementation, using laws about what the data should mean.
- Customer Favoring Data Rule: Describe why the ETL task cannot simply select a known-correct customer record and what rule guides the choice instead.
Why it matters: The rule gives the exercise a basis for choosing among records even when their underlying truth is unknowable. - Implementation Coupled Test Limits: Explain why tests aimed mainly at executing implementation details may fail to establish correctness.
Why it matters: A test cannot establish the intended behavior if it merely confirms what the code already happens to do. - Algebraic Basis For Correctness: Explain how thinking algebraically connects the intended meaning of data to implementation and testing.
Why it matters: Laws about the data give implementation and tests a shared standard that is not defined by the code itself.
Key terms: ETL, conflicting records, nulls, favors not billing the customer, coverage, correctness, implementation, thinking algebraically, equations, laws
7.2 Thinking Algebraically
Introduces algebraic thinking as a way to define operations on data and reason about correctness independently of implementation.
- Algebraic Elements and Constraints: Describe an algebra as a set of things, operations on them, and rules those operations must follow. Explain that the operations considered here are deterministic functions that take data in and return data without side effects.
Why it matters: This gives you the basic vocabulary for discussing what an operation means before writing it. - Equations and Universal Laws: Explain how deterministic operations allow two different-looking pieces of code to be compared by their results, potentially letting a simpler expression replace a complex one. Describe the laws sought through equational reasoning as claims that hold for all possible inputs, not just an example.
Why it matters: It shifts correctness from checking one example to asking what must always hold. - Meaning Before Implementation: Describe how the section frames merging two conflicting duplicate records by asking what it would mean to “add” them. Explain why focusing on that small combination question provides a language for correctness without first choosing an implementation.
Why it matters: You can discuss what any correct merge should mean before getting caught up in how to code it.
Key terms: algebra, operations, deterministic functions, equational reasoning, laws, all possible inputs, conflicting records, add, correctness
7.2.1 Standing on Shoulders, Not Toes
The section introduces closed binary operations as a useful algebraic shape and shows why recognizing that shape in Java code helps programmers reason about it.
- Closed binary operation shape: Describe the binary operations considered here: they take two values of the same type and return a value of that type. State that Java provides BinaryOperator as a specialization of BiFunction.
Why it matters: This shape gives you a starting point for spotting the operations the chapter will reason about. - Recognizing disguised binary operations: Explain why a binary operation may not look like one in Java code, including when it appears as a one-argument operation on an object or is obscured by an implementation.
Why it matters: The algebraic shape can be useful even when the code does not present it explicitly. - Algebra as design leverage: Justify using an algebraic shape as the core of a feature: recognizing it connects the design to established laws and tools for reasoning.
Why it matters: The point of spotting the pattern is the reasoning it makes available, not merely giving the code a new name.
Key terms: binary operation, closed, BiFunction, unary, algebraic properties, algebra, algebraic shape, laws and tools for reasoning
7.3 Noticing algebraic operations in every day code
The section reveals binary operations hidden in imperative Java code and uses them to simplify a duplicate-record processing pipeline.
- Algebra Beneath Imperative Code: Explain why looking for binary operations in imperative code changes how you reason about it.
Why it matters: This shift helps you judge what the code accomplishes without getting stuck on its bookkeeping. - List Addition From Mutation: Describe how the duplicate-grouping code’s list update can be reshaped into a binary operation.
Why it matters: The list example makes a hidden operation visible before the section applies the idea to maps. - Map Addition And Collisions: Explain how map updates become a combining operation and why collisions need a choice of behavior.
Why it matters: Collision handling determines whether combining maps preserves or discards the values needed for the feature. - Duplicate Pipeline As Combination: Trace why grouping and reducing duplicate records can collapse into repeated map combination.
Why it matters: Recognizing the shared operation can remove transformations that only prepare data for another combination.
Key terms: imperative code, binary operations, side-effects, state updates, List.add(), Lists, binary operation, Map, putAll(), collisions
7.4 The algebraic properties of binary operations
The section shows why a binary operation’s behavior across different argument orders, groupings, and inputs matters when judging its correctness.
- Order and grouping effects: Explain how changing argument order or grouping chained binary operations can change the result, depending on the operation and its data type.
Why it matters: It explains why familiar-looking operations cannot always be rearranged safely. - Properties that define correctness: Describe what the section calls an algebraic operation’s properties and why they matter to correctness.
Why it matters: These properties give you a way to state what correct behavior requires, rather than relying on an operation’s familiar name.
Key terms: binary operations, argument order, grouping, Stream.reduce(), algebraic operation, properties, inputs, outputs
7.5 Invariants, Properties, State, and an upside-down capital A
The section shows how to turn the values a type can represent into exhaustive assertions about individual states and relationships between states.
- Universal assertions over states: Explain what it means to assert that an invariant holds for all possible states, and how a type’s set of possible values defines those states.
Why it matters: It shifts correctness checks from a handful of examples to every state the data can represent. - Composite state enumeration: Describe how to determine every state of a record from its attributes’ possible values, including the empty state of an Optional.
Why it matters: Leaving out an attribute combination or an Optional’s empty case leaves a gap in an exhaustive assertion. - Relationships between exhaustive states: Explain how combining exhaustive state sets lets an assertion check an invariant between any two states, and how repeating the combination extends this to larger relationships.
Why it matters: It lets a check cover every way states could be combined, rather than just hand-picked pairs.
Key terms: algebraic properties, invariant, all possible states, Product Types, cartesian product, Optional, empty state, for all, relationships between states, exhaustive set
7.5.1 Every possible state? Surely too inefficient to be practical!
The section counts the domain’s possible states and argues that generating every state is often practical, while acknowledging limits.
- Optional state-space count: Explain how the section arrives at 90 possible states by counting the empty state added by each Optional.
Why it matters: Counting the actual possibilities helps you judge whether checking every state is feasible. - Practicality of state generation: Justify why generating every state with for-loops can be practical for well-modeled domains, while recognizing that it is not always worthwhile or feasible.
Why it matters: It keeps performance worries from ruling out a simple exhaustive approach before you measure its cost.
Key terms: Policy, AuditFinding, Boolean, Optional, empty(), states, for-loops, benchmark, state spaces
7.5.2 Expressing these ideas without code
The section introduces “for all” notation as a concise, precise way to express claims about every state and to think more carefully about invariants.
- Universal quantifier and states: Explain how ∀, a variable, and a set express a claim about every state in that set.
Why it matters: This notation lets you state precisely which values an invariant must cover. - Precision through formal notation: Justify using “for all” notation to discuss invariants instead of relying only on English prose or Java code.
Why it matters: The notation keeps the discussion focused on what must be true rather than on code for checking it.
Key terms: ∀, for all, variable, set, states, invariants, formal notation
7.6 Associativity
The section explains associativity as a law of regrouping binary operations that enables flexible execution and gives a concrete criterion for correctness.
- Associative Grouping of Operations: Explain that associativity means grouping binary operations differently should give the same result, so the grouping need not be chosen in advance.
Why it matters: Recognizing this law lets you reason about a result without committing to one grouping of operations. - Flexible Execution and Correctness: Describe why associativity lets a reducer choose where and how to group work, including parallel work, and why the property can be written down as a law to test an implementation.
Why it matters: A property that permits flexible execution also gives you something specific to check when testing correctness.
Key terms: associativity, binary operations, grouping, Streams API, reduce, parallel, concrete law
7.7 Noticing more properties
The section shows how looking for a property behind complicated selection logic reveals an ordering problem that Java’s Comparator can express.
- Limits of DRY refactoring: Explain why extracting duplicated conditional logic does not, by itself, make the RawData combination easier to reason about or test.
Why it matters: Removing duplication is less useful when the resulting code still hides the rule that makes it correct. - Favorability as an ordering: Explain how the RawData requirements can be understood as comparisons of favorability, even though favorability is not an explicit value in the code.
Why it matters: Recognizing a conceptual ordering turns a tangle of choices into a rule that can be stated directly. - Defined order and Comparator reuse: Describe how the section proposes making the ordering explicit and why that allows reuse of Java’s Comparator tooling.
Why it matters: An explicit ordering lets the implementation reuse a standard library abstraction instead of merely rearranging conditionals.
Key terms: DRY, properties, binary operation, RawData, favorability, ordering, sort, lexicographically, Comparator
7.7.1 Ordering as a property
This section uses ordering properties to describe correctness independently of an implementation and shows how to test a domain ordering.
- Properties of ordering relationships: Distinguish a total order, which needs reflexivity, transitivity, and antisymmetry, from other relationships that may have only some of those properties.
Why it matters: It lets you choose properties that fit the relationship rather than assuming every ordering behaves like a Comparator. - Favorability correctness properties: Explain how describing domain favorability as a total order gives tests criteria for correctness above the level of individual implementation branches.
Why it matters: These properties let you test what correct behavior means without tying the tests to how the code is written. - Permutation-based ordering checks: Describe the suggested practical check for an ordering: sort every permutation of the data set and verify that each produces one sorted output.
Why it matters: It gives you one observable check for the ordering properties instead of testing each property separately.
Key terms: ordering, total order, Comparable, reflexive, transitive, antisymmetric, favorability, properties, states, permutation
7.7.2 Monotonic Relationships between inputs and outputs
The section explains why combining favorable data must preserve its ordering and how Comparator-based operations provide that monotonic behavior.
- Monotonic Favorability: Explain why ordered data alone does not guarantee that combining it preserves favorability, and describe the monotonic behavior the algebra requires.
Why it matters: This property rules out a combination operation that accidentally makes the result less favorable. - Comparator Based Combination: Describe how the section's add implementations obtain monotonic behavior and how their operations relate to Java's maxBy binary operator.
Why it matters: It connects the desired favorability rule to the comparison operation the implementation uses.
Key terms: monotonicity, favorability, ordering, Comparator, add, BinaryOperator, maxBy
7.7.3 The properties that define what it means to be correct
The section explains how properties of every possible state can specify what it means to combine conflicting domain data correctly, and suggests ways to find those properties.
- Properties as correctness criteria: Explain how properties can specify correct behavior when combining conflicting domain data: they identify the possible states and the invariants that must hold between them, giving a test suite a basis for checking correctness.
Why it matters: Explicit properties give tests a definition of correct behavior to check. - Finding applicable algebraic properties: Describe the section’s suggested way to find useful properties: recognize a familiar pattern or try candidate properties such as associativity, ordering, and monotonicity to see which fit the API.
Why it matters: Trying familiar properties offers a practical starting point for specifying an API’s behavior.
Key terms: properties, states, invariants, test suite, pattern recognition, Associative, ordered, Monotonic
7.8 Optional as a parallel world
The section explains why an algebra designed for present values needs to work with Optional, using a parallel-world analogy to introduce lifting behavior.
- Algebra for sparse data: Explain why the existing binary operators need to work with Optional values, and why leaving Optional out of their original design was not a mistake.
Why it matters: It explains why sparse data does not invalidate the algebra already designed. - Optional parallel world: Describe the parallel-world picture of Optional and explain why moving into that world is not always reversible.
Why it matters: The analogy makes clear both what an Optional type represents here and the limit on returning to an ordinary value. - Lifting behavior into Optional: Explain what lifting means in this section and why it is useful for the existing algebra.
Why it matters: It is the section’s central reason the algebra can be adapted to Optional without separately hand-mapping every operation.
Key terms: binary operator, Optional, algebra, Optional.of, Optional.empty(), parallel world, lifting, behavior
7.8.1 Dealing with the IDE telling us we're doing it wrong
This subsection explains when accepting Optional as a function argument can be reasonable despite IDE warnings and common advice.
- Optional Argument Rule of Thumb: Distinguish generic tooling that accepts an Optional from code that inspects its concrete contents, and explain why an IDE warning is not an absolute prohibition.
Why it matters: It helps you judge the code’s purpose rather than treating a linter warning as a design decision.
Key terms: Optional, generic type variable, linter warnings
7.8.2 Lifting Binary Operator into the world of Optional
The section derives a general-purpose way to lift a BinaryOperator so it can be used with Optional data.
- General-purpose BinaryOperator lifting: Explain how extracting the common pattern turns an operation tied to integer addition into a function that accepts any BinaryOperator and returns one that works with Optional values. Distinguish lifting the operator itself from supplying its arguments.
Why it matters: Separating the operation from its inputs lets the same lifting pattern work for different binary operations. - Optional plumbing inside lifted functions: Explain why a lifted function makes working with Optional data feel more like working with ordinary values.
Why it matters: It lets you design operations for ordinary values and add Optional handling without repeating that plumbing at each call.
Key terms: lifter, lift, BinaryOperator, Optional, lifted functions, Optional data, plumbing
7.8.3 Moving our algebra into the world of Optional
The section applies lifted binary operators to make the existing algebra work with Optional values, while leaving its correctness to be checked against the chapter’s properties.
- Algebra over Optional values: Explain that lifting the algebra’s binary operators lets the algebra work with Optional values, and that its correctness still needs to be checked by extending the chapter’s properties to the new data type.
Why it matters: Handling optionality is distinct from showing that the resulting algebra still has the properties you expect.
Key terms: lift, binary operators, algebra, Optional, properties
7.9 The finished implementation
The section presents the finished implementation and emphasizes that its algebraic properties matter more than its particular code.
- Implementation-independent algebraic properties: Explain why the finished implementation is not the only valid one: the algebraic properties established earlier hold for any implementation and can be used in tests to check correctness.
Why it matters: You need not prefer this particular code to benefit from the properties used to check it.
Key terms: algebraic design, algebraic properties, implementation
7.10 A final note on representing algebraic ideas in code
The section explains why the chapter’s algebraic ideas are implemented with the regular Java standard library rather than new specialized interfaces.
- Standard Library Over Specialization: Explain why the author chooses regular Java library types instead of encoding the chapter’s algebraic ideas in special interfaces: the social friction of math-heavy abstractions and the interoperability costs of bespoke types.
Why it matters: A useful abstraction must also fit the people and libraries a project depends on.
Key terms: special interfaces, Java Collection classes, Java standard library
7.11 Wrapping up
The section closes by emphasizing the practical value of recognizing algebraic properties in everyday programming.
- Everyday value of algebraic properties: Explain why recognizing algebraic properties matters in ordinary programming.
Why it matters: Recognizing recurring properties can change how you approach everyday code.
Key terms: properties, algebraic world
7.12 Summary
Where this is used later
- Verifying algebraic properties. (chapter 11) · Tests can verify algebraic properties rather than only implementation-specific cases.
- One test, multiple roles (chapter 11) · Uses the idea of exercising all states represented by program data.
- Exercise all the states in your program (chapter 11) · Provides a concrete example of counting the states a test might exercise.
- Impose algebraic properties on your dependencies (chapter 12) · Ordering properties provide an example of algebraic properties that can be imposed on dependencies.
Concepts explained in this chapter
- algebraic operationAn algebraic operation is a rule for combining elements of specified sets to produce an element of a specified result set.
- algebraic lawAn algebraic property is a characteristic describing how an operation behaves under operand order, grouping, and relationships between inputs and outputs.
- binary operationA binary operation is a rule that takes exactly two operands from a specified set or type and produces a result.
- setA set is a collection that represents distinct elements without treating duplicate occurrences as separate members.
- data addition operationA data addition operation combines two immutable data values into a new value representing their combined contents.
- group-by operationA group-by operation organizes input elements into keyed groups by repeatedly combining values associated with the same key.
- mutationMutation is the modification of an existing program value or state in place.
- accuracyCorrectness is the property that an implementation produces the behavior and results specified by its intended semantics and requirements.
- equationAn equation is a statement that two expressions have the same value or meaning.
- Order propertyAn ordering is a binary relation that arranges or compares elements according to specified properties such as reflexivity, transitivity, and antisymmetry.
- monotonicityA monotonic function is a function that preserves the ordering of its inputs, mapping larger inputs to outputs that are not smaller.
- business ruleA business rule is a domain constraint or policy that determines valid actions, states, or outcomes.
- liftingLifting is a functional programming technique that adapts a function on ordinary values to operate within a wrapper or computational context.
- software testingTesting is the practice of executing checks that assess whether software behaves according to specified expectations.
- optionOptional is the Java container class that represents either a present non-null value or the absence of a value.
- Cartesian productA Cartesian product is the set of all ordered tuples formed by choosing one element from each of several sets.
- assertionAn assertion is an executable check that a specified condition holds for a value, state, or computation.
- product typeA product type is a type whose values combine one value from each of several component types, corresponding to logical AND and a Cartesian product.
- algebraic reasoningAlgebraic thinking is the practice of reasoning about software operations through equations and properties that characterize their behavior.
- determinismA deterministic function is a computation whose output is completely determined by its inputs and remains consistent for repeated evaluations with those inputs.
- operationAn operation is a rule that combines or transforms values from a specified set to produce a value.
- invariantAn invariant is a condition that must remain true across the valid states of a data structure or computation.
- state spaceA state space is the set of all possible combinations of values representing the states of a domain.
- test suiteA test suite is a collection of automated or executable tests that assess software against specified expectations.
- dataData is information represented independently of the behaviors that operate on it.
- optionalityThe property of domain information that may be present or absent and whose absence has explicit meaning.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
