[please see the preface post for information on getting starting with this study group.]
Introduction
This chapter focuses on different types of procedure. It introduces two, homogeneous predicates and operations. Homogeneous predicates take multiple objects of type T and returns a bool. Operations take multiple objects of type T and return another object of type T. Of these classes of functions, the most common are unary and binary, functions that take either one object or two objects as input.
A partial procedure has a definition space as a subset of the types of its inputs. A total procedure has a definition space that includes all values represented by the input types. So a partial procedure needs to have a precondition that checks if the input is in the definition space. This procedure is called a definition-space predicate.
Transformations
The main topic of the chapter is with the unary operations we call transformations. A transformation is a unary operation that has a DistanceType that converts a Transformation into an integer, more on this later. Transformations are self-composable: f(x), f(f(x)), f(f(f(x))). We define the power n as the number of calls of the transformations. When n = 0, then the result is x.
An algorithm can be defined to calculate the Transformation F to the nth power. It requires a Transformation F, the Integer N and a member of the domain of F. It will return the result which is also in the domain of F.
Orbits
Orbits are defined as the elements reachable from a starting element by multiple calls of the transformation predicate. There are four forms of orbits: infinite, terminating, circular and p-shaped. An infinite orbit goes on forever. A terminating orbit stops at some element, the transformation outputting an element that is outside the domain of the transformation. A circular orbit loops back to the initial value at some point.
A Distance Type of a transformation is an integer type large enough to count the maximum number of steps from one element to another. A distance procedure can be defined to calculate the distance from one element to another for any transformation.
Given the orbit forms, we can define the orbit cycle size c is the number elements in the cycle. The handle size h is the number of elements before the cycle starts. The connection point is the first cyclic element. The orbit size o of an orbit is the number of distinct elements in it.
Orbit Algorithms
The book describes an algorithm to calculate the collision point. The collision point is an unique y returned from a transformation F n and from F (2n +1). n >= 0 and is the smallest integer satisfying this condition. The algorithm runs a loop that calculates a slow element from transformation F calculated once and a fast element from F updated twice. The fast element is checked if it is in the domain of F before each call. If F terminates before the collision point is found, then the orbit is not circular and the last fast element is returned.
A new algorithm can be build on the the collision point algorithm to check if the orbit of F is terminating. It can check if the return is in the domain of F. If not then F terminates, otherwise it must have a circular or p orbit and a collision point is returned. Note: the book states that all algorithms in this chapter must not have a transformation with an infinite orbit, otherwise the algorithm will never return.
The book shows another specialized collision point algorithm. If the transformation F is total or the orbit is nonterminating given a specific starting element, that the generated elements of the orbit is always in the Domain of F. Then we can remove the precondition check.
From the collision point algorithm, the distance from the collision point to the connection point can be defined as e = r + 1, where r is from a definition of h: h = mc + r, where m is the number of whole cycle sizes needed to get to h, plus the remainder r.
With this distance defined, more algorithms can be defined. A predicate to check for circularity. A procedure to calculate the convergent_point. The convergent point is where two powers of a transformation meet starting with different initial inputs. It can be shown that if the transformation is run from initial element x and also run from collision point +1, they will converge at the connection point. This convergent point algorithm can then be used to calculate the connection point.
Orbit Structure
A triple is constructed that can represent the complete structure of an orbit. It will contain information of the shape of the orbit and the sizes of h, c and o. An algorithm is shown to return this structure for any transformation F.
Actions
The last section discusses Actions. An action changes the state of an object by applying a transformation on it. An action can be defined as a transformation and vice versa. Sometimes it is good to have both defined because of efficiency.
- “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
Page 16: “An operation is a homogeneous function whose codomain is equal to its domain”
I found this sentence doubly confusing:
the lack of any formatting on “codomain” and “domain” led me to believe that they were being used in their normal mathematical sense – which further led me to believe (due to making a long break between reading chapt 1 and chapt 2) that Codomain and Domain type functions were also defined in the same mathematical vein – an immediate inspection of the presented examples proved me false to assume that.
and more importantly, I was surprised that the definition of the Operation concept was made so strong, again departing from the usual mathematical definition. For example,
double ScalarProduct(Vector v1, Vector v2);
doesn’t qualify as an operation, whereas
double ScalarProduct(double x1, y1, x2, y2);
does, even though both function represent the same idea. In my opinion, the “troublesome” sentence would read much better if “operation” was replaced with “HomogeneousOperation”, “domain” with “Domain” and “codomain” with “Codomain”, and all three appropriately formatted. At this point, I’m also surprised that Domain and Codomain are defined for homogeneous functions only – just ads up to the overall confusion.
Also, the definition of Operation as it stands, checks three times whether Op is homogeneous if it in fact is. I’m not sure if this is necessarily a bad thing, as I’ve not yet seen or compiled actual C++ code using these concepts.
Anyhow, a great book thus far! Though, after going through Alex’s lecture notes that this book was based upon, I was expecting a bit more flavor (in form of his amusing reflections) to the text.
Petar Marendic(Quote)The definition of domain is given at the top of page 10 along with a statement indicating that the book doesn’t define it for non-homogenous functions. “The domain of a homogeneous functional procedure is the type of its inputs. Rather than defining the domain of a nonhomogeneous functional procedure as the direct product of its input types, we refer individually to the input types of a procedure. ” This is a simplification to avoid the complexities of dealing with equivalent representations.
Glad you’re enjoying the book – the book went through several very different forms before settling on this presentation (see the Class Notes section on stepanovpapers.com). Alex frequently fills his lectures with great references to the history of mathematics (and history in general) – and they can be very obscure. Several individuals gave feedback that on the lecture notes that led Alex and Paul to settle on the more traditional form of a math text. If you enjoy the stories – make sure you watch his GCD lecture http://www.stepanovpapers.com/stepanov_gcd.mov. (There are also more recent slides on the site and a very recent video but the latest is in Russian).
Sean Parent(Quote)I apologize for taking a long break from this discussion (tough to have a day job). So far I believe we’ve only received one submission for the exercises to chapter 2 so please e-mail your homework right away. Let’s get started on Chapter 3!
Sean Parent(Quote)I’m having a problem with Exercise 2.5 on random number generators. Since rand() takes no arguments, the only way I see to find the collision point is to have a function object that reseeds the random number generator and generates random numbers until the argument is found, and then return the random number after that. This is O(N^2). Anybody know a faster way?
Mark Ruzon(Quote)If you want to do a serious analysis of your random number generator you will need the sources – then you can treat rand() as an action on it’s own global state. A decent way to simulate that for this exercise is to analyze the following:
int random(int x) { srand(x); return rand(); }Sean Parent(Quote)Thanks, Sean, that’s very elegant, although reseeding every time appears to mask the behavior of an individual seed, which I am curious about.
I also remembered that I had already implemented a better random number generator. It uses the linear congruential method described in Section 3.2.1 of Donald Knuth’s The Art of Computer Programming. The modulus m is 2^32 – 5 as suggested by Section 3.2.1.1 and the table in Section 4.5.4. Unlike the behavior of rand(), this one has a fixed cycle size of 421,412,441 regardless of the seed.
Mark Ruzon(Quote)To analyze a given seed you’ll need to grab the source for rand() so you can treat rand() as a function returning it’s global state. Unfortunately the C standard doesn’t include access to this state.
Sean Parent(Quote)Hello All,
Here are my remarks to chapter 2
Piotr Jachowicz(Quote)Pg15,l 16. There is “A predicate is a functional procedure returning a truth value:”, should be “A predicate is a functional procedure returning boolean value:”
Pg17,l 1-2. There is “direct product”, should be “Cartesian product” because we do not consider structures on inputs
Pg17,l 20. Definition of Transformation(F) is a bit redundant. Both Operation(F) and UnaryFunction(F) implies HomogeneousFunction(F). It would be sufficient to define:
Pg17,l 29-30 (definition of f^n(x)) i. for n > 0 more handy (and actually implemented in algorithm on power_unary) is f(f^{n-1}(x)) ii. for n > 0 there should be precondition that f^{n-1}(x) belongs to definition space of f
Pg18, definition of power_unary. According to advise on pg17 (“A nontotal procedure is accompanied by a precondition specifying its definition space”), there should be precondition defined.
Chapter 2.2 Orbits. Assuming explicite that memory is limited, we can simplify orbits classification. Because infinite orbit is impossible, we can treat terminating and circular as special case of p-shaped (with empty handle or empty circular part). So there would be only one type of orbit: p-shaped where h >= 0 and c >= 0 and h + c > 0. Memory limitation is already assumed: i. in distance type discussion, and ii. orbit fintness is preconditin to all algorithms in this chapter.
Chapter 2.3 Collision Point. Pg 23-24 (calucations of e – distance from the collision point to the connection point). It is unnecessairy complex. Simpler version is:
Chapter 2.3 Collision Point. Pg 24, last line (calucations of e – distance from the collision point to the connection point). For c = 1, conclusion that distance from collision point to the beginning of the orbit is equal to 1 is false. In case of orbit consisting of one element only, this distance is 0. Assumption that c > 1 is also necessairy in chapter 2.4
I think the transformation definition in the book is okay. Operation(F) states that the input is a number of objects and returns one object of the same type. UnaryFunction(F) states that it only accepts one input. It is a little redundant but it contains the same level of definitions. Piotr’s definition uses UnaryFunction(F) and Domain(F) == Codomain(F). The second term is not that clear and is not at the same level of abstraction as UnaryFunction(F). Operation(F) is and I think states more clearly to the reader the meaning of the constraint. However, I think both definitions are correct.
As for point 7, yes I saw that there are other ways to calculate the distance. The method in the book uses h = mc + r and later uses that definition again for other uses. Piotr’s version does not provide that helpful side note.
Tim Wright(Quote)
Sean Parent(Quote)The awkward wording was used to allow for result types which are not boolean (such as int) where some set of values represent true and others false.
Direct product is a Cartesian product for a set – not sure what you mean by structures on inputs.
Yes, it is a bit redundant.
i. Agreed. ii. The definition wouldn’t include it as a precondition, but you could add it as the definition for when f^n(x) is defined.
There is a precondition defined in the first line of the body. Is it lacking?
The classification is still useful for the discussion.
There is a bug in the definition (see errata http://www.elementsofprogramming.com/eop-errata.pdf. The presentation in this section was chosen carefully – the ideas here will reappear later in the book.
If c =1, then distance from collision point to beginning of the orbit can also be 1. Nice property of a one element cycle. Can you point to something specific in 2.4 that requires c > 1?
Sorry for late reply, I was on vacation.
Ad 1. I don’t think the intention was to allow precondition to return not-bool. But if so, few words of comment would help to avoid confusion.
Ad 2. Mathematicians usually say “direct product” when they mean Cartesian product empowered with default structure, like direct product of two groups, linear spaces, manifolds.
Ad 5. Precondition is expressed only in comment, instead of explicit procedure.
Ad 6. Sorry, I don’t see any virtue in considering impossible case. In my opinion, chapter would become clearer if infinite orbit would be removed, with appropriate comment.
Ad 7. Sorry, I don’t see in this errata any definition correction for chapter 2. What do you mean?
Ad 8. No, it cannot. Consider for example int f(int i) {return 0;} with starting x = 0. It produces constant orbit (0, 0, 0, …), which is circular and distance between any two points of this orbit is 0. This is counterexample for last paragraph on pg 24, which says “In the case of a circular orbit, h = 0, r = 0, and the distance from the collision point to the beginning of the orbit is e = 1″.
According to chapter 2.4, I was wrong; it is ok in case c = 1
Piotr Jachowicz(Quote)Ad 1. It was – I was part of the discussion.
Ad 5. Yes, often times preconditions cannot be checked (or cannot be checked without violating the time complexity of the function).
Ad 7. From page 3 of the errata:
Page 24, fourth line: Change \q > 0″ to \q > 0″ and \when slow enters the cycle” to \when it collides with slow”. (Reported by Bob English and John Banning.)
See theorem 3.1.
Ad 8. The distance between any point and itself is always 0. But the distance between the first 0 and the second is 1, the first 0 and the third is 2… etc. If you start at the collision point and advance one step you are at the start of the orbit, and you are back to where you started.
Sean Parent(Quote)I have another question. The book states: “A procedure is partial if its definition space is a subset of the direct product of the types of its inputs; it is total if its definition space is equal to the direct product. We follow standard mathematical usage, where partial function includes total function.We call partial procedures that are not total nontotal.” What does it mean that standard mathematical usage is followed? It seems obvious that you can have a procedure that is nontotal. Where does a partial function include a total function? Is function here different than procedure?
Tim Wright(Quote)Set A is subset of X if for every a, “a belongs to A” implies “a belongs to X”. Therefore X is a subset of itself.
Similar to partial and total procedures. Procedure is partial if its definition space is subset of its domain. Procedure is total if its definition space is equal to its domain. Because domain is a subset of itself, every total procedure is a partial procedure.
Piotr Jachowicz(Quote)Okay. That makes sense. The wording ” where partial function includes total function” is confusing to me. Does total function includes partial function makes sense? It is clearer and consistent with what Piotr said I think.
Tim Wright(Quote)I think “where all total functions are partial” is the cleanest.
Mark Ruzon(Quote)I have a question on the orbit sizes. If an orbit contains all values of a type T, then the reason why o could not be type T is because of counting all value from one. So it is one unique value shy of counting all the values of type T? Is this always the case? When would it be not true?
Then if an orbit has h > 0 and c > 0 then I would think that both could be represented by type T. The book is confusing to me. It states: “Depending on the shape of such an orbit, h and c would not fit either [in type T]. However, for a p shaped orbit both h and c fit.” But if you don’t have a p shaped orbit then either h or c is zero. So one of them will always fit in type T. Am I correct or missing something? Thanks!
Tim Wright(Quote)so maybe one of them will fit, but the other will not? ie an ‘or’ instead of an ‘and’? ie
“Depending on the shape of such an orbit, h and c would not fit either [in type T]“
should be
“Depending on the shape of such an orbit, h or c would not fit either [in type T]“
or might not fit?
Just suggestions.
Tony Van Eerd(Quote)If T has less than 2^k values, where k is the number of bits in the memory words of T, then o could be of an integral type with k bits. bool is an example.
Concerning h and c, logically speaking if (h or c) is false, then (h and c) is also false. “or” in the standard English usage (rather than the logical usage) would be correct there.
Mark Ruzon(Quote)