Please see the previous post for information on getting starting with this study group.
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.
- “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