Please see the previous post for information on getting starting with this study group.
Summary
The key ideas of Chapter 1, Foundations, are regularity and equality. They are defined in terms of real world things and ideas that are mapped onto the computer. To categorize both the real world and the computer world requires a lot of terminology and the authors have filled this chapter with definitions and examples. I have listed the terminology definitions at the end of this summary in the order that they are presented in the book.
An entity is a thing or idea in the real world. A distinction is made between abstract entities, which are eternal and unchanging, and concrete entities, which come into and out of existence. Each entity belongs to a single species that describes its common properties and, in the case of concrete entities, attributes and rules for its construction and existence. On the computer, an entity corresponds to a value or object and a species corresponds to a value type or an object type, depending on whether the entity is abstract or concrete. An object’s state is a changeable value that corresponds to a snapshot of the corresponding concrete entity. Species that are similar in some respect are described by a genus. A species can be associated with multiple genera, each of which describes certain common properties. On the computer, a concept represents a genus.
Equality is a key idea in this chapter and two kinds of equality are described, behavioral and representational. Behavioral equality refers to the actual entities being equal, even though their computer representations may be different. For example 1/2 and 2/4 are equal rational numbers that are different on the computer when represented by two integers. Representational equality refers to the computer representations being equal, even though the actual entities may be different. For example, the 2-digit year “09” could represent the year 1909 or the year 2009. Two objects of the same object type are equal if and only if their states are equal values.
The chapter then describes the concept of regularity as applied to types and procedures. The benefit of regularity is that it allows “equational reasoning” (substituting equals for equals) to transform and optimize programs. A regular type includes procedures that allow objects to be placed in data structures and copied between data structures. The copied objects must be equal to the original objects. The computational basis of a regular type must include equality, assignment, destructor, default constructor, copy constructor, total ordering, and underlying type (defined in Chapter 12). A regular procedure is a sequence of instructions whose original inputs can be replaced with equal inputs and the resultant output objects will be equal to the original output objects. A functional procedure is a regular procedure defined on regular types with only direct inputs and a single output. It can be implemented as a C++ function, function pointer, or function object.
The last section describes concepts and preconditions on types. A concept describes properties satisfied by all objects of a type. It is stated in terms of the existence and properties of procedures, type attributes, and type functions defined on the type. A precondition describes properties of particular objects of a type that are not requirements on the type as a whole. For example a procedure might require a particular integer parameter to be a prime number. The requirement for an integer type might be specified by a concept, while primality is specified by a precondition. Mathematical notation for defining concepts and preconditions is described.
The following terminology from the chapter is important to understanding how the authors map the real world onto the computer and what transformations and optimizations are permitted within that mapping. The definitions are listed in the order that they occur in the book.
Abstract Entity: An eternal, unchanging “thing” in the world of ideas. Examples are 13 and blue.
Concrete Entity: A “thing” in the real world that comes into and out of existence. Examples are Socrates and the United States of America.
Attribute: A correspondence between a concrete entity and an abstract entity. Examples are the color of Socrates eyes and the number of US states. [Why isn’t a correspondence between two concrete entities (or two abstract entities) an attribute?]
Identity: The “sameness” of an entity that changes over time. Attributes of an entity can change without affecting its identity.
Snapshot: A complete collection of the attributes of a concrete entity at a particular point in time.
Abstract Species: A description of the common properties of essentially equivalent abstract entities. Examples are natural number and color. An entity can only belong to one species.
Concrete Species: A description of the set of attributes of essentially equivalent concrete entities. Examples are man and US state. A concrete entity can only belong to a single concrete species, which provides rules for its construction and existence.
Function (on abstract entities): A rule that associates one or more abstract entities (called arguments) with an abstract entity (called the result). The arguments must come from corresponding species and the result from another species. Examples are the successor function for numbers and the blending function for colors.
Abstract Genus: Describes different abstract species that are similar in some respect. Examples are number and binary operator. An entity can belong to several genera.
Concrete Genus: Describes different concrete species similar in some respect. Examples are mammal and biped.
Datum: A finite sequence of 1’s and 0’s.
Value type: A correspondence between a species (abstract or concrete) and a set of datums.
Representation: The datum from a value type corresponding to a particular entity.
Interpretation: The entity from a value type corresponding to a particular datum.
Value: A datum together with its interpretation. Examples of values are integers represented in 32-bit two’s complement big-endian format and rational numbers represented as a concatenation of two 32-bit, two’s complement, big-endian sequences, interpreted as integer numerator and denominator.
Well Formed Value Type: A datum that represents an entity, within a value type. For example, all 32-bit sequences are well formed when interpreted as a two’s complement integer. An IEEE-754 floating point NaN (Not a Number) is not well formed when interpreted as a real number.
Properly Partial Value Type: A value type whose values represent only a proper subset of the abstract entities in the corresponding species. An example is the type int.
Total Value Type: A value type whose values represent all the abstract entities in the corresponding species. An example is the type bool.
Uniquely Represented: A value type where each value represents at most one entity in the corresponding species. An example is the two’s complement representation of an integer.
Ambiguous: A value type with a value that represents more than one corresponding entity. An example is a two decimal digit representation of a calendar year in more than one century. Unambiguous is the negation of ambiguous.
Behavioral Equality: Testing if two values of a value type represent the same entity. If a value type is uniquely represented, behavioral equality implies representational equality.
Representational Equality: Testing if two values of a value type have the same sequence of 0’s and 1’s. If a value type is not ambiguous, representational equality implies behavioral equality.
Function (on values): A computer implementation of a function on abstract entities. Implements a mapping from values to values that does not depend on the particular memory addresses of the values.
Regular Function: A function on a value type that respects equality. Substituting an equal value for an argument gives an equal result. An example is the successor function for integers. An example of a non-regular function is the function returning the numerator from a rational number expressed as a pair of integers, since ½ equals 2/4 but the numerators are different.
Memory: A set of words, each with an address and content. The addresses are fixed size as are the word contents.
Object: A representation of a concrete entity as a value in memory. An object is changeable and has a computer-specific implementation. Objects can also represent abstract entities by staying constant or taking on different approximations to the abstract.
State: An object’s changeable value, from a value type, that corresponds to a snapshot of a concrete entity.
Resources: The set of memory words or records in a file that hold an object’s state. The resources for an object do not have to be contiguous. Each object has a starting address from which all its resources can be reached.
Object Type: A pattern for storing and modifying values in memory for an object. Each object has an object type. That object type has a corresponding value type that describes the possible states of the objects of that type. An example is integers represented in 32-bit two’s complement little-endian format aligned to a 4-byte address boundary.
Identity Token: A unique value expressing the identity of an object. It is computed from the value of an object and the address of its resources.
Procedure: A sequence of instructions that modifies the state of some objects. It may also construct or destroy objects. The procedure can interact with four kinds of objects: input/output, local state, global state, and own state. Input/output objects are passed via arguments. Local state objects are created, modified and destroyed during a single invocation of a procedure. Global state objects are accessible to multiple procedures across multiple invocations. Own state objects are accessible to a single procedure but shared across multiple invocations.
Computational Basis: A finite set of procedures for an object type that enable the construction of any other procedure for the type. A computational basis is efficient if any procedures written using it are as efficient as those written using any alternative basis. A basis is expressive if it allows compact and convenient definitions of all procedures on the type.
Regular Type: An object type that has a set of procedures that allow objects to be placed in data structures and copied between data structures. The copied objects must be equal to the original objects. The computational basis of the regular type must include procedures for equality, assignment, destructor, default constructor, copy constructor, total ordering, and underlying type.
Equality: A procedure that returns true if two objects of the same type have equal states.
Assignment: A procedure that takes two objects of the same type and makes the first object equal to the second object.
Destructor: A procedure that causes the cessation of an object’s existence.
Constructor: A procedure that transforms memory locations into an object. A partially formed object has only the left-side assignment and destructor procedures defined on it.
Default Constructor: A procedure that takes no arguments and leaves an object in a partially formed state. [Doesn’t it sometimes create a well-formed object?]
Copy Constructor: A procedure that takes an argument of the same type and creates a new object equal to it.
Regular Procedure: A procedure whose inputs can be replaced with equal inputs resulting in output objects equal to the original output objects.
Functional Procedure: A regular procedure defined on regular types, with one or more direct inputs and a single output. Input types can be passed by value (making a local copy) or by constant reference.
Definition Space: The subset of input values to a functional procedure for which it is intended to be applied.
Homogenous: A functional procedure whose input objects are all the same type.
Codomain: A functional procedure’s output type.
Result Space: For a functional procedure, the set of all values from its codomain returned by all possible input values from its definition space.
Concept: A collection of requirements on types expressed as syntactic and semantic properties. More formally, a concept is a description of the requirements on one or more types stated in terms of the existence and properties of procedures, type attributes, and type functions defined on the types.
Type attribute: A mapping from a type to a value, describing some characteristic of the type.
Type Function: A mapping from a type to an associated type. An example is a mapping from “pointer to T” to the type T.
Indexed Type Function: A type function with an additional constant integer parameter. An example is a type function returning the type of the ith member of a structure type (counting from 0).
Type Constructor: A mechanism for creating a new type from one or more existing types. An example is a type constructor that takes a type T and returns the type “pointer to T”.
Model: A type models a concept if the concept requirements are satisfied for that type.
Refines: A concept C2 refines another concept C if whenever C is satisfied for a set of types, C2 is also satisfied for those types.
Weakens: A concept C weakens another concept C2, if C2 refines C.
Abstract Procedure: A procedure that is parameterized by types and constant values, with requirements on those parameters. Function templates and function object templates are used to implement abstract procedures.
Preconditions: Required properties of particular objects of a type that are not requirements on the type as a whole. For example a procedure might require a particular integer parameter to be a prime number.
Key Points
Exercises
- “Elements of Programming” Study Group
- “Elements of Programming” Preface
- “Elements of Programming” Chapter 1: Foundations
- EOP Exercise Round-Up: Chapter 1
- “Elements of Programming” Chapter 2: Transformations and Their Orbits
- “Elements of Programming” Chapter 3 Preview
- Elements of Programming Study Group
- EOP Exercise Round-Up: Chapter 2
- "Elements of Programming" Schedule Announcement
- “Elements of Programming” Chapter 3: Associative Operations
- Elements of Programming Chapter 3 Exercise Summary
- Elements of Programming Chapter 4 “Linear orderings”
- "Elements of Programming" Chapter 5: Ordered Algebraic Structures
After making a long break from the book I skimmed through the first chapter to quickly brush up on the terminology and this sentence struck me as dubious:
page 14, line 12
“To define regularity of a unary functional procedure, we write…” – and yet on page 9 it is stated: “A functional procedure is a regular procedure defined on regular types…”
Seems redundant, or not?
Additionally, the precondition immediately following this sentence introduces the notion of function equality in its definition of procedure regularity (“Application of equal functions to equal arguments gives equal results”), something that was not mentioned on page 8, where regular procedures are defined as: “A procedure is regular if and only if replacing its inputs with equal objects results in equal output objects.”
In my opinion, equality of functions deserves to be defined beforehand, as it’s not a trivial idea. As far as I can see, it hasn’t been explicitly introduced anywhere in the preceding portion of the text.
I noticed that Domain as defined at the bottom of page 12 is used to determine both the domain and codomain of the square procedure on page 13. That seems a bit less than precise.
Hi, in section 1.3 (Objects) we read “This book uses a programming language that has no way to describe values and value types as separate from objects and object types.” I am having trouble imagining how would such a separation look like, and how/if it would be helpful. Could anyone give me a hint?
Regards, &rzej
I think it’s no more complicated than saying (e.g.) that ‘int’ refers to a fixed-size integer type and not Z, the set of all integers.
Could it be that some languages choose to represent values instead of objects? For example, in most functional languages, including Haskell, one mostly works with values, and objects are usually considered hacks. For example:
data List a = Nil | Cons a (List a)
myList = Cons 1 (Cons 2 Nil)
myList does not have any of the properties of objects, including an address. It is a value representing a well-defined (abstract?) entity.
Yes. Various languages will ignore one or more properties of objects but the objects still exist as they are a “side effect” of providing a physical representation for a value. Functional languages deal with values and ignore address and mutability of parts (single assignment). Reference semantic languages (Java as an example) put a lower emphasis on copy (assignment assigns references, not objects). With FP languages the choice is to use a computational basis which simplifies reasoning but isn’t necessarily an efficient basis. The move with reference semantic languages come largely from dealing with variable sized, polymorphic, types. EoP seeks to provide a framework to reason about programming on current machine architectures, providing mathematical rigor without compromising efficiency. It can be viewed as an extension of FP, providing a framework to reason about object instead of simply ignoring them since under the hood they do exist in any FP system. Some of the ideas in EoP, such as an underlying type, are not particularly practical to implement in C++, yet the notion of an underlying type exists regardless of what language one is using.
It’s about time to get moving on to Chapter 2. Please e-mail your homework for Chapter 1 to eop-study@cpp-next.com and Dave and I will summarize.
I kept thinking as I was reading this chapter that a diagram of the relationships between all these terms would be really useful, especially because there are often parallel ideas in the concrete and abstract domains. Unfortunately, I got stuck because I don’t know a diagramming “language” that is appropriate for this kind of thing. Any ideas?
That’s a great idea. Nominally, you could represent the entire thing in box-and-line diagrams (e.g., UML-like) with some extra background detail to help classify the abstract and concrete domains. I’ll take a stab at a draft after I write a final exam.
Well, the first take turned out to be a total failure. Not surprising… A diagram–even multiple diagrams–probably won’t be sufficient to capture the number of concepts (not a pun) established in this chapter. Part of the problem is that this chapter addresses such a broad scope of topics and the semantic connections between them are numerous and sometimes not easily defined. I’ll have to give a diagrammatic presentation some more thought, sketch out some ideas, etc.
It might be that the optimal presentation is actually a wiki. That might also be useful for attaching specific conversation threads to a definition or concept. Just a thought.
Could you please help me with “Domain”? Does “domain” (lower case) differ form “Domain” (UpperCase)? The former is defined as type of input (pg 10.). But the latter?
Domain (when capitalized and in the math or programming font) is defined at the bottom of page 12 as part of the requirements for a HomogenousFunction. It is a type-function taking a HomogenousFunction as an argument and returning the type of the functions arguments.
Sean, thank you for reply. One more question: Does “p belongs to Domain(f)” imply “p belongs to definition space of f”?
I ask because BinaryOperation is defined using statement “for every a, b, c belonging to Domain(op), op(op(a,b),c) = op(a,op(b,c))”. If it happens that a and b belong to Domain(op), but not to definition space of op, then we cannot determine if this equality holds because value of op(a,b) is undefined.
Or I’ve missed something?
Domain(f) is a type, and the definition space of f is a set of values. So “p belongs to Domain(f)” does not imply “p belongs to the definition space of f.” The converse is true, of course.
BinaryOperation (p. 31) is defined as an Operation that takes two parameters. An associative binary operation satisfies the condition you mention, but this is merely a property of some binary operations.
[Sorry for the break - buried by the holidays!] “p belongs to Domain(f)” does not imply “p belongs to definition space of f”. But for any such definition you can read an implied “where op is defined”. In early drafts the book was very rigorous about always stating that requirement, but it was observed that the definition space is better managed as pre-conditions, not type requirements, and so these requirements were pulled. The book is still rigorous about managing the pre-condition that the values passed to a function are within the definition space for the function (we’ll see discussion of this in Chapter 2).
I have a question proving Lemma 1.3. A well-formed object is partially formed. A well-formed object has well-formed state, therefore the value is well formed. This means that the datum represents one abstract entity with respect to a value type. I don’t understand how this is related to partially formed? An object is in a partially formed state if it can be assigned to or destroyed. If the value is well formed, does that mean it can be assigned to? I have struggled with this for a while and I am lost on how to approach this. Thanks
This isn’t a great lemma – it is missing a word “regular” – “A well-formed regular object is partially formed.” By definition a regular object has destruction and assignment.
Tim: if it makes you feel any better, I had the same issue. I suggested to Paul McJones that they should add “of regular type” to the lemma but he seemed to feel that we’re in a context of regularity so it should be obvious to the reader. I guess we may have to be prepared to mentally sprinkle “regular” here and there as we go through the book.
I feel better that I was not missing something obvious. I do think that it would be clearer if the lemma’s were complete and did not depend on the surrounding context. They should stand on their own.
Given all the great in-depth posts already, I think this post is small by comparison, but I find it useful to tie the book to programming in the real world.
The sentence on page 7, “A type is regular if and only if its basis includes equality, assignment, destructor, default constructor, copy constructor, total ordering, and underlying type.” is a more rigorous statement of The Big Three. Every C++ programmer is taught to write a proper destructor, copy constructor, copy assignment operator for each class. I find that the equality operator comes into play too.
Now the reason for The Big Three, other than preventing run-time problems later, is based in a rigorous definition of type.
Hi all,
I have a minor question relative to primitive concepts. Does concept Regular (last sentence of page 11) refer to a regular type or a regular procedure? From my understanding relative to HomogeneousFunction example this must be a regular type, is that right?
Also why is FunctionalProcedure concept a “type” concept? Are procedures defined as types somewhere, or this silently refers to a function object?
Thanks in advance
Concept Regular refers to regular type. Procedures are treated as types in EoP (whether they be function pointers or function objects). I think this should be made explicit – I’ll mention it to Alex and Paul.
Hi all!
I think there is a difference between “type T is currently not regular because I haven’t implemented the whole set of required procedures” and “type T can’t never be regular because it’s impossible to implement the whole set of required procedures”.
I believe every type can be regular, they just happen to have some procedures unimplemented given some source code.
“Potentially” sounds like “it may become regular if you struggle hard enough”. “Inherently” sounds like if your type isn’t regular it’s only by laziness (I’m lazy).
in·her·ent (n-hîrnt, -hr-) adj. …; intrinsic.
I like intrisically too.
“I believe every type can be regular, they just happen to have some procedures unimplemented given some source code.”
This isn’t quite the case – there are types for which the regular operations cannot be implemented, even though we can define what the operations would mean. One class is a state machine – two state machines are equal iff for equal input streams they yield equal results. Determining equality in the general case will never terminate. There are also types for which equality is not implementable in a non-destructive or efficient manner. Consider comparing two priority queues (heap structures). They are equal iff they have the same number of elements and when you remove the elements they are removed in order. The operation is either destructive (requiring you to remove all the elements) or requires additional space to copy the elements, sort them and compare the results. Another example would be comparing two vectors representing sets of elements which have no ordering. Comparing the two vectors requires comparing all possible permutations of one vector to the other. Beyond some point, this also won’t terminate (at least not before the machine is returned to dust).
Such types are still intrinsically regular, but their implementation will be necessarily incomplete.
Can you elaborate? I thought that there is a straightforward O(n^2) algorithm for that case? (I think I’m not understanding what data structure you are thinking of.)
You’re correct – I withdraw that example (please feel free to try and add some more good examples here). A side note though on the practicality of even O(N^2). When working on Photoshop, the quick test for an algorithm was to see if the complexity made it feasible to execute on a data set that fit into RAM. On my laptop here I have 4G of RAM. Let’s say I pick a data set of 100M (10^8) such objects, we’ll make each object 32 bits for simplicity – the straight forward algorithm is going to read 2 * 10^16 + 10^8 objects. If I could sustain 10^9 bytes per second throughput (unlikely on my laptop but feasible for a desktop) That gives me about 8 * 10^7s to complete my equality comparison – that’s about 2.5 years. Even though we treat polynomial complexity as computable – for large data sets it may not be practical.
Sure, but such considerations can be made for some O(N) algorithm applications while there are plenty of useful algorithms that are worse than O(N^2).
That said, maybe the concept of regularity should include performance requirements?
There are a few issues here. The requirements for concepts come from algorithms. We’ll see in chapter 6 some great results on how complexity of simple operations effects algorithmic complexity. Somewhat so that the point can be made in chapter 6, complexity requirements are relaxed a bit in the book.
In practice I think it is problematic when the required complexity for the definition of a function doesn’t match the expected behavior (usually the expected behavior is driven by a common case or implementation). An example, many people expect the size() function on STL containers to be O(1), but on an std::list it may be O(N) – and that can break a program badly. A similar example is decaying operator==() to a representational equality. The SGI STL does this with the hash containers – at Google there was a fair amount of code that was found searching the product that assumed operator==() was a behavioral equality. The book talks about using representational less-than for operator< when a natural ordering is not defined but I would be hesitant to use such a definition in practice. This makes an interesting engineering tradeoff – if we used a representational ordering for < then code would be less verbose because we wouldn’t have to pass a comparison function to use many containers and algorithms, but by being a bit more stringent we may avoid common mistakes.
When naming an operation I think it is important to establish the semantics for the name – and a good general rule is to make the semantic requirements as strict as possible to cover the common case and use a more explicit name for more general cases.
I guess the same rationale could apply to omitting other basic operations required for regularity, like copy/assignment from lvalues.
[This is C++ aside from the topic of the book.]
Copy and assignment are a bit different. If implementable, I don’t know of a case where they aren’t implementable in time proportional to the area of the object. The Google coding standard discourages copy-ctor and assignment operators with the argument that complex operations shouldn’t “hide” behind operator=(). If I were to extract the semantics of this sentiment it would be that assignment and copy should only be used when the complexity is roughly equal to assigning a single word. (otherwise you should have a CopyFrom() or Clone() member function if you need copy says the style guide). However, I think this is misguided – because you can’t return such a type from a function it forces you to deal with more partially formed types. i.e. “T x = f();” becomes “T x; f(&x);” In the first case I know that x is well-formed after the statement, in the second case, x may either be partially or well-formed depending on f(). Dealing with partially formed objects is like dealing with pointers that can be null – it must be done with care. I think the risk of partially-formed objects outweighs the risk of unnecessary copies. Note also that the first form of the above is likely more efficient, and doesn’t actually imply a copy – I don’t know of a way to avoid the inefficiency while keeping the semantic constraints.
There are cases where you simply don’t want an object to be copied as a matter of policy (likely to enforce an invariant within a larger system) as opposed to restrictions on the semantics of the type itself, i.e. a singleton. This is using the C++ type mechanism as a mechanism to enforce a constraint external to the type, and really is a language mechanism issue and not a type issue as defined in EoP.
I wouldn’t say they’re a good thing, but I’ve come across objects that register themselves with an external system on construction. In that case, there’s a component of the cost of copying that is unrelated to the area of the object.
Handling relationships is an interesting topic not covered in EoP. There will be some external factors (such as cost of a heap allocation) but these are assumed to behave in a relatively constant manner (amortized constant or logarithmic would be sufficient).
Must a equals operator or a constructor always return a well-formed object? I think I understand how a user defined member function could return a partially formed object, but why must the equals operator or copy constructor always return a well-formed object? Or that it is more likely because of programmers due diligence?
By “equals operator” I assume you mean assignment? Since assignment is only valid when the value on the right is well-formed, and assignment makes a copy of the value on the right, the result should be well formed. The book doesn’t discuss exceptions and error handling to any degree – but if there are insufficient resources to copy the value then the object may be left in a partially formed state (corresponding to the basic exception guarantee). In most cases, assignment can be implemented as a transaction (it either completes or the left hand value is left unchanged – the strong exception guarantee). This is a nice quality when reasoning about error cases. A default constructor need only leave an object in a partially-formed state. A copy constructor, like assignment, should leave the object well-formed. If you are using exceptions than either the object should be left well-formed or the parts that have been constructed should be destructed, leaving no instance. If you aren’t using exceptions than a failed copy construction could leave an object partially formed.
Well, OK, but that glosses over the question of how you define “implementable.” I’m specifically thinking of movable-but-noncopyable types like locks, threads, and
fstreams (all of which can be returned from functions). They fall into a category of types for which you can implement copy and assignment (and a consistent equality operator), but only if you’re willing to make them somewhat meaningless, and inconsistent with the move operations.For a given type, if you find that any sensible implementation of move must transfer a particular attribute (say, the file handle associated with an
fstream), it seems inescapable to me that the attribute is essential (like avectorelement, as opposed to thevector‘s capacity). If it doesn’t make sense to copy that attribute, I want to say that copy is unimplementable.These are all examples of relationships – see my last paragraph of the comment you quoted on policy. Relationships are external to the type – regardless of how important that relationship is. Consider an array, “a”, with 3 elements. a[1] is after a[0] and before a[2]. Those are very important properties of a[1]. But copying a[1] severs those relationships.
Let’s not go too far down this path though since it is outside the scope of EoP – and on this topic I can’t speak for Alex and Paul except that I suspect they would agree with me that there is enough material in dealing with relationship properties to write another book.
Yeah, but so does moving. That makes memory order a very different kind of relationship.
I’m willing to “not go too far” down this path, but just for the record, I don’t buy what you’re selling here. I believe these types do undercut the statement about all types being intrinsically (or logically) Regular, principally because they break the relationship between move and copy that makes Regular meaningful.
Hi Sean! I have followed many of your publications, they are great!
I don’t like the state machine example. Its problematic only if we try to test for equivalence. Equality could really mean comparing the rules of the state machine. If we want to manipulate the rules or measure the machine’s head movements, operator== testing equivalence is not a good idea, but I agree this is subjective, in fact it depends on what we want for such a type.
You don’t need extra storage for the heap example. After all a heap is a complete tree. You could extract the top and reinsert it as the last value of the tree but omitting the heap adjust operation. After extracting all the values, the heap is in a valid state (sorted, heap sort). I agree this is a desperate attempt to implement equality for this type but it works.
I agree with what Daveed said. Hope you update your blog!
For the state machine example, I did define what I meant by equality – and it is a proper behavioral definition. What you describe is a form of representational equality – also a useful notion.
For the heap example I excluded destructive operations – I am aware you can sort the heaps in place, compare them and then rebuild the heaps (or many variants of that). Perhaps mutable operation would have been a better term?
Can you find more examples where equality isn’t feasible to implement?
Here are a couple.
For different delivery routes, you might reasonably define equality as the shortest possible paths for two routes are equal.If the routes have very many stops, this becomes impractical.
For mathematical functions, you might define equality as point-wise equality. In this case, both potential algebraic issues (The set of representable points is finite, and there are infinitely many algebraic functions that match exactly on any finite set of points) and potential numeric issues. (If the representation of the function comes close to any divergences or other issues that destablise the floating point calculation, then the computed result can be arbitrarily far from the true result. Not a problem if your equality is defined as only caring about the computed result with no algebraic rearrangements, but that is not a very intuitive choice.)
Graph isomorphism could be a nice example! We even don’t know if its NP-Complete or not.
Thanks for your reply!
Hi Sean,
I don’t understand what that statement means, or even how it can have any meaning. It seems like a non-falsifiable claim, sort of like “all organisms are intrinsically human, but some of them just haven’t evolved that far.” Can you make this a little more concrete for me, or do you intend it as a kind of Delphic statement/Zen meditation?
[Note to reader: mixing falsifiability and evolution here was totally unintentional—please don't read anything into it]
It wasn’t intended to be a Zen meditation. Let’s use one of the above examples – graph isomorphism. We can define that two graphs are equal iff they are isomorphic. Now, we can claim that if we copy a graph, the new graph is equal to the original. We know that representational equality implies true equality so we could use representational equality to verify our copy. We can’t implement a general, useful, equality (one that terminates for graphs beyond some size) so our implementation is necessarily incomplete. But the type is still intrinsically regular and we can still use equational reasoning to reason about our code, although there may be many operations for which we can’t verify the results – even though we can prove them correct.
I would have an easier time with this if it didn’t circle back to a statement that “the type is still intrinsically regular.” Still, if I put that together with its context (“we can still use equational reasoning”), I may be able to understand. What I think you’re saying is that, even if we can’t implement equality, there is still a fundamental platonic notion of equality that applies and allows us to reason about programs.
Fine, as far as it goes. But “Regular” as defined does include efficiency guarantees. When you say “intrinsically regular” it implies to me that Regular is in there somewhere waiting to be realized. I think you really mean something more like “logically regular,” i.e. the phrase needs a qualifier that implies a weakening of the notion of regularity, and “intrinsic” implies strengthening (or at least, not weakening).
Let me add my bit here also:
I would differentiate my opinion with respect to the expressiveness of the computational basis. It is possible that you can implement even retardant or not usefull regular requirements for most type ( I cannot think any that you cannot), but would that make your code functionally regular?
For example let’s say that we have a geometric 2d vector type. How can you implement total ordering in an expressive way in that case? A first attempt is to provide total ordering relative to the L2-norm, but it would be hardly useful in most applications (although you can find some that it turns to be useful). Another way to implement total ordering would be by lexicographical total ordering, as long as the type of the elements of the 2d vector have an expressive total ordering implementation (in cartesian space you can do that). The later is even worse than the first in a geometric application.
Anyway, expressiveness is a subjective quality with all the cons in a formalistic approach and resolution of that subjectivity would be a major step towards a better theory, but it is a very hard problem also.
We’ll discuss ordering more in chapter 4 – but every type at lease has a representational order – which if the representation is unique then this provides a total ordering of the values (if it isn’t unique it is a total ordering of the representation). Although such a total ordering is not consistent with the other operations on your vector, it can be very useful to deal with set’s of vector coordinates efficiently (you can sort them, and use binary search to find a location).
And further on page 3 we find “Two values of a value type are equal iff they represent the same abstract entity.” There is a distinction here between object type and value type – the definition isn’t circular. Another way to phrase this would be; two objects are equal iff their states represent the same abstract entity. There is no constructive definition that can tell you what the correspondence is between a state and an abstract entity. You must choose a correspondence and implement equality to be consistent with the choice.
Thank for you replay. Equality objects definition makes me confused:
“An objec has a state what is a value of some value type”. I’m confused with word “same”. Does it mean that to particular object there is assigned set of value types? If so, i. how to determine this set for given object? ii. for definition to be valid there should be proof that value of every element from this set is equal.
Given the definition “Two objects are equal iff their states represent the same abstract entity”, I don’t know what abstract entity really is. Definition says that it is “individual thing that is eternal and unchangeable”. Considering eternalness and relationships between eternal things is domain of philosophy rather than computer science… What eternal thing represents string “Smith”?
Wouldn’t be simpler to define: “Two objects a and b of the type T are equal if i. expression >>a==b<< is well-formulated, ii. value of >>a==b<< is true, iii. relation {(a,b); a,b of type T & a==b} is reflexive, symmetric and transitive”?
My interpretation is that the book goes deeper defining what “==” or equals (both are equivalent) means. An object is made up of values. Values are representations of a member of an abstract species. Two or more values are equal if they all represent the same abstract entity. The object equality builds on this. Two or more objects are equal if all the values of one object represent the same set of abstract entities as the rest of the objects.
Adding to nasos_i’s response,
1) I assume you mean “some” – this can be read as “a single value type”, not as a set (EoP doesn’t deal directly with polymorphism but there are a couple of consistent ways to handle that if we want a side discussion).
2) Yes – this chapter is the philosophy portion of the book. Philosophy is unavoidable – the absence of philosophy is a philosophy. You are suggesting a formalism philosophy where any consistent set of rules can be used. EoP takes more of a constructionist (with some amount of empiricism) approach. Here mathematics is the abstraction of physical reality and computer science is the mapping of that mathematical abstraction back into a physical reality within the machine. Computer science is a hard science like physics and is distinct from mathematics.
As for what eternal thing does Smith represent – that is for you to decide. “Smith” is a representation, a sequence of ascii tokens, no more than a set of bits. Smith may represent the set of all individuals past and future with Smith as their last name, it may represent a particular employee at your company, it may represent a permutation of letters. Knowing what it does represent will allow you to answer questions like is “Smith” equal to “SMITH”, or is “Smith” equal to “Bob Smith”, or is “Smith” equal to “mihtS”.
The problem with the formalism approach you suggest is that it tells us little about how to define equality – only what rules it must obey. These rules are necessary but insufficient = they define any equivalence relation and can be satisfied by simply declaring that all objects are equal. The difference between equality and any other equivalence relationship lies in what the objects represent.
I think there are some issues on the details here that aren’t yet communicating well. I’m going to try and rephrase Sean’s points (which if I understand them correctly, I agree with) and see if I can help clear it up. Obviously, it is possible Sean will say that I’m not understanding him, so take this with appropriate grains of salt.
The philosophical point of view taken by the book is a largely Platonic one. There are abstract ideals (called abstract entities), and concrete realizations (called concrete entities). The abstract ideals are eternal and immutable, but it is worth noting that they are also impossible to experience directly. We can only experience or interact with concrete realizations. The connection between the abstract and the concrete is based on attributes.
While I type this, I’m sitting on a concrete realization of a chair. It may not be the same as any chair that is used by anyone who reads this, but it shares some set of attributes with those chairs. It is one realization, but not the only possible realization. Is my chair equal to your chair? There is no a priory way to establish that. To determine equality, we first have to know what attributes are important for the application. If what is important is a place to put your butt while you type, then the chairs are equal. If other attributes, such as padding, color, shape, or material composition are important they might not be equal.
So, any rule for equality is not based on purely the abstraction, but it is really based on what attributes that apply to the abstract ideal are of interest at the time. This means that the details of the rule for equality are situation dependent. First I select what attributes are important in the concrete realization, then I compare those attributes. If they are the same, I say the realizations represent the same abstract ideal. This tells me how to construct equality comparisons in any application, while the formalist version does not. The formalist version discusses syntax, but not semantics. I can learn how to use an equality operator, but I can’t connect it to any context outside my program in a formalist view.
There is a long running argument in the foundations of science between the Platonists, the Formalists and a third group you can call Model Builders. It is possible to build a usable platform in any of them, and I have my preferred choice, but the reasoning in the book starts from a Platonic stance, and as far as I can see is consistent and well formed with it.
Hopefully that can combine with Sean’s comments and help you clarify the starting place.
Ok, let us do simple execersize. Let us suppose I have class:
struct rational { int nom; int denom; rational(int a_nom, int a_denom) : nom(a_nom), denom(a_denom) {} };Please tell me, what abstract entities are represented by: rational(1,1), rational(1,0), rational(0,1) and rational(0,0)? And which is equivalent to which?
Let me make an attempt on that:
rational(1,1) represents 1.
rational(1,0) represents inf. Note: rational(x,0)!=rational(y,z), x,y,z in R.
rational(0,1) represents 0
rational(0,0) is indeterminate :in some situations, for example: limit(x/x,x->0),this may be 1, (there are other limits that this doesn’t hold), but you need to somehow represent limits to define it as such.
So none of the above seems equivalent to any other.
By your names you chose, I would guess that the entities provided by nasos_i are your intention. However, since your code does not specify your intent it is always possible I’m misinterpreting you.
In specific, you have given no rule for what equality means (a design decision that can’t be made without knowing your design intent), so I can’t know whether different values are equal or not. You are free to make several decisions in this part of the design.
For example, if your program only constructs rationals in simplified form (so nom and denom have no common factors), then a sense of equality that compares nom’s, compares denom’s and is equal only if both are equal is both efficient and reasonable. You could decide whether you want that to include infinity and NaN representations, or if you want such representations to never equal anything else based on the needs of your design.
However, if you have no such assurance of simplest form, then you might be inclined to an equality comparison that first finds simplest forms, and then compares the simplest form nom and denom. This may be impractical, if your program is likely to have large and hard to factor integers, so there is a question of the appropriate domain for this definition, but it is a definition of equality. Again you would have the opportunity to include special cases for infinity and NaN, if it makes sense in your case.
Less intuitive definitions of equality are also possible, of course. However, none of these choices are constrained by the content of Chapter 1. They are a design decision, based on what abstract entities you want to represent and what attributes you think are important to the program you are writing.
Just to add a bit more – Assuming the intention is that the type rational corresponds to the abstract species “rational numbers” (a good assumption, but unless stated it is only that). The usual definition for rational numbers excludes 0 denominators.http://mathworld.wolfram.com/RationalNumber.html So rational(1, 0) and rational(0, 0) are not well formed (see page 2 for a definition of well formed datums). These values are only partially formed and so equality is not defined (see the bottom of page 7).
Hi Sean,
You said “assuming the intention is”. That the point. Code execution is determined by code only, no matter what was the intention. If I’ll take my application rational.cpp, change all occurences of “rational” into “point” (assuming that point did not occure before) and save as point.cpp, then rational.exe and point.exe will execute exactly the same way because for compiler this is the same code. That’s why, in my opinion, objects equivalence (that determines function regularity) should be based on code only.
<joke> The fact that the same class can be interpret on two different ways, like you and nasos_i, comes to the conclusion that computer science shold be modeled on Leibnitz monads, not on Plato’s ideas </joke>
“That’s why, in my opinion, objects equivalence (that determines function regularity) should be based on code only.” If by this you means “works as coded” it isn’t a useful definition. Equality of points and equality of rational numbers is not the same.
Piotr,
It is possible to define all of your terms in such a manner, but let’s look at what happens if we do so. I think (I haven’t checked the details, so I don’t know for sure.) it would be possible to create a system where the content of the later chapters on transformations, rings, semi-rings and other such formal results are unchanged, but there are problems in application.
The formalist approach of just worry about the interactions of the symbols as one facet that is at best unsatisfying, and could be a problem. Once you divorce the interactions of the symbols from a real world interpretation you lose the ability to clearly state what the purpose of the program is, what it models, what abstractions it is using and all other such practical information. As a result, there is no reason for validation and verification of the code. It is just a formal rearrangement of symbols, and not a representation of some concrete or abstract system of objects and interactions. As long as it uses syntax in a well defined way and is translated into some set of machine instructions that follow the formal rules, it is by definition correct.
Only by imposing requirements from outside the code itself can you tell if it is correct valid code for the task at hand.
Consider your example and later comments. You are entirely correct that Sean and the rest of us could have misinterpreted your intent and what you were really writing was a point on an integer valued plane structure. Given that you provide things like a definition of equality and other regularity requirements, then there is no purely formalist way to say that one of them is right for your code and the other is wrong. The only way to reach that conclusion is to either require an operation that is implemented in one structure and not the other (which clarifies your intent somewhat, but puts it in the code), or to compare the structure to some standard that is external to the code.
This is the common problem for all Formalist philosophical approaches. Of themselves, they make no reference to anything outside the set of symbols and the rules for operating on that set. Any instance of them acting like a desired abstract or concrete system has to be seen in this context as a happy accident, and there is no way to know anything about the agreement of the computational system with any results that have not been explicitly tested for agreement. I come from a background in scientific computation for research, and for me this is clearly unacceptable.
I have not discussed their intent with the authors, but I think part of the goal of Chapter 1 is to avoid this problem. The connection between the abstract entities, the concrete entities, and the representation in the computer is stated explicitly so there is no question of the relationship between what is done on the computer and what it means. Verification and validation now make philosophical sense. They are checks on the quality of the choices made when modeling attributes of the abstract and concrete entities, species, genera, and relations on the computer. We can verify that the components of the program are good models of the chosen attributes, and then validate that the selections made behave like the desired system in the cases we care about.
So, the reason for not using a purely Formalist definition of equality is to bridge the gap between formal correctness and real world application. It is possible to put this bridge in other places, but for computer science to be an applied science, the bridge has to exist.
That got a bit more philosophical than I wanted, but I’m going to let it stand for now. Hopefully it is a step toward more clarity.
Hi Piotr,
Here’s a slightly less philosophical (more practical?) take on John’s reply.
We’re discussing the definition of equality. Another way to phrase that is, “what is required for a correct
operator==?” To answer any questions about the correctness of a program, you have to have some specification of what the program is supposed to do. This specification is a form of redundancy (unless the program is incorrect), and evaluating a program with respect to its specification is a determination not made “based on code only.”A reasonable definition of correctness “based on code only” might be, “anything that compiles and doesn’t invoke undefined behavior is correct”—but that’s a useless definition. Adding a requirement that all definitions of
operator==must be reflexive, symmetric, and transitive doesn’t make the rule any more useful, since you can easily imagine a language that says you get undefined behavior if youroperator==fails to have those properties.If for some type T, operator==() is not reflexive, symmetric and transitive, then – according to my definition – no two objects of type T are equal. Consequently no function taking T as argument is regular, and algorithms from EoP does not apply to it.
Problem I’m trying to solve is: “Can I apply EoP algorithms to function f if I’m not author of f, but have code only?” Like in legacy code case?
The only way to work with undocumented legacy code and maintain correctness is to first decide what the code was intended to do (and document it). At that point, you have more than just “code only.”
Very nice post John!
Hi
I think the questions about equality are very good. My reading is that most of these should be solved as concrete design questions. Obviously the book is more general, it is not trying to solve a specific problem, it is setting out general techniques. So if you think a definition sounds “too general” to be useful, well, it is. You have to make it specific in each specific circumstance.
So if you are writing some software that tracks the state of chairs (possible attributes: chair design, location, ownership, purchase date, etc, etc), then you have an abstract chair definition that is eternal and unchanging (between refactorings of course). Each specific object in the program will have different specific values for the attributes. As part of the design process for this software, you must decide how to tell if two software objects refer to the same specific chair. This is the definition of equality that must be implemented. You decide/design what the value set is for each attribute, then you compare each attribute, etc.
Hopefully that is helpful!
Cheers Karl
Piotr, I have similar concerns as you. I can’t entirely rationalize the fact the an object has a state that is “A” value of some value type. But as you point a set of value types can be defined as a new value type, so that’s how I try to see it. It would be very interesting to hear other peoples’ opinions. Also a set for an object is not defined by the object itself, but by the context you define it. You have to provide that value type, with the interpretation you desire. I don’t think that EOP can give you the answer on how to determine the value type (or set) of a given entity, as it relates closely to the problem you are trying to solve. You have to provide that correspondence.
It is maybe a good exercise to prove that given uniquely represented value types in a finite set, element equality implies set equality (not the opposite though). (Haven’t done it, but naive introspection tells me that it can be done).
Philosophy is were everything started, and it is closely related with every act of rational thought (rational been a subset of philosophical act). Since computer as we know it is quite a rational machine, exercising philosophy now and then is a good software engineering practice.
Also isn’t -string “Smith”- an entity itself (in the context of std::string)?
Lets say that each “class” has a hashing value, It is possible that two different objects has the same hash value.
Like nasos said “a set for an object is not defined by the object itself, but by the context you define it”, when we try to push the two classes into a hash table, in context they are equal.
Let’s say I’ve created class Person and have two objects p1 and p2 of class Person. How to determine if they are equal? Due to equality definition on pg 5. (“Two objects of the same type are equal if and only if their states are equal”), I have to find state of p1 and state of p2. But definition of state (pg 4.: “An object has a state what is a value of some value type”) gives no constructive way to calculate object state. How to determine if p1 and p2 are equal?
A value is a sequence of bits interpreted to represent some abstract entity. Two values are equal if they represent the same abstract entity. That is, p1 is equal to p2 if p1 refers to the same person as p2. There is no construction that can derive the interpretation of a set of bits to people – you must define what that mapping is.
I’m going to insert a key point here – if an object state is a value is a representation of an abstract entity, and two values are equal if they represent the same abstract entity, then it follows that for any object type that equality is defined, as it is in the book, in terms of the objects representing the same abstract entity. Dave A. has struggled with my assertion that all [object] types are “inherently” regular – that is, equality, copy, assignment are defined (there are cases where they can’t be implemented but they are actually quite rare). I tend to shorten this to “all types are regular” and use the phrase to force people to consider what the regular operations mean for their type which forces an understanding of what exactly the type represents. With a formalism approach it would be perfectly acceptable to have types which are not regular – but such types don’t exist. I’ve used the phrase enough that Dave has threatened to buy me a t-shirt that reads “I’m a regular type.” [side colorful point, Alex wants "while (first != last)" inscribed on his tomb stone - I think this is the most Zen statement in programming.]
I’m not sure that “inherently” is the right qualifier or modifier here. Maybe “potentially” or even “intrinsically” is better?
EOP calls a type regular if its computational basis includes certain procedures. (Sidenote: It is silent about types without a basis; presumably they’re never regular.) If I don’t provide e.g. an equality procedure for a type, it cannot be regular.
Intrinsically works better – thanks.
If the computational basis doesn’t include the regular procedures as a simple omission then the implementation of the type is incomplete (hmm, I don’t have EoP in front of me – I know in drafts we defined various forms of incomplete types, but I think those may have been nixed). EoP does discuss that one can (nearly) always fall back to representational equality which suffices when behavioral equality is not easily computable. Types with an incomplete set of basis functions are not discussed in any detail – although there are some interesting bits in the book that are of use here. Later the notion of move and underlying type is discussed and when then can be used instead of copy. One can always add a reasonably efficient move to a type by heap allocating it, even if the type doesn’t support copy. Equality can be implemented as a non-friend, non-member function so long as the type is “equationally complete” – that is, all of the parts are readable.