[please see the preface post for information on getting starting with this study group.]
The study group has died a bit (my own fault for not keeping up the pace). Dave and I are working on a homework summary for chapter 2 this morning but we’re late (see the schedule in the preface) on Chapter 3 content.
Chapter 3 is my favorite chapter in the elements. In many ways I think of chapter 3 as the real start of the book, with chapters 1 & 2 laying down the foundation. It is the beginning in another sense as well, Alex’s work on STL began when he was preparing for a job interview for a job doing programming a parallel system, when he picked up a bad case of food poisoning. In his fevered state he had the realization that the ability to add numbers in parallel depended on the fact that addition is associative. It was this realization that algorithms where based on algebraic structures that led to STL. Google is a testament to the power of this idea.
There are two exceptionally beautiful bits in chapter 3. The first is the proof of Theorem 3.1, an element of finite order has an idempotent power. Make sure you prove Lemma 3.4 as part of the homework. The second is the use of power to calculate Fibonacci numbers. Calculating Fibonacci numbers is such a common example for programming and yet an efficient algorithm is rarely given even when Fibonacci is used as an example for efficient programming techniques.
- “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
Hi friends…is this thread still alive ? I am interesting a lot !!
Definition of associative property says (pg 31) “for all a,b,c in Domain(op)”. But op is a binary operation here, so its domain is a set of pairs. Should it be understood as an abbreviation for “for all a, b, c such that {(a,b), (b,c), (a,c)} is subset of Domain(op)”? Even so, there is no guarantee that (op(a,b), c) nor op(a, op(b,c)) belong to Domain(op).
It would be safe to define associative property by “for all a,b,c such that {(a,b), (b,c), (op(a,b),c), (a, op(b,c))} is subset of Domain(op)”, but it makes it the same as definition of partially_associative (pg 98).
You need to dig a little deeper: associative property is defined on a BinaryOperation which is defined to be an Operation with arity 2 (top of pg 31). An Operation is defined on page 16 as a HomogeneousFunction where the codomain is equal to the domain. A HomogeneousFunction is defined way back on page 12 as being a function where all input types are the same and having the property Domain which is the type of the first input type (and by extension the type of every input type).
Sorry, I don’t get it. Let’s say
is a binary operation and 
. Which statement makes sense “op(a)”, or “op(a,a)” ?
P.S. Sorry for late reply. I was assumed mistakely that reply will show under RSS channel..
P.S2. Thanks for Dave for re-formatting homework for chapter 2
Sorry, I’ve pressed “Submit” too fast. Post was to be:
Sorry, I don’t get it. Let’s say op is a binary operation and a belongs to Domain(op). Which statement makes sense “op(a)”, or “op(a,a)” ?
P.S. Sorry for late reply. I was assumed mistakely that reply will show under RSS channel..
P.S2. Thanks for Dave for re-formatting homework for chapter 2
op(a, a) and because the codomain is equal to the domain (by definition) then op(a, a) is in the domain of op
Ok, so if all a,b,c belong to Domain(op), then op(a, op(b,c)) and op(op(a,b), c) makes sense in terms that argument types matches Domain(op).
What about definition space? It can happen that (a, op(b,c)) belongs to definitions space of op, but (op(a,b), c) does not.
I don’t understand why partially_associative definition cares about definition space, but associative do not? Is there a guarantee that op in associative is total?
I think you mean “It can happen that op(a,b) belongs to the definition space of op, but op(b,c) does not”. If op is associative, then by definition op(a,op(b,c)) = op(op(a,b),c).
But to me the point is that a definition space is more of a practical concept necessary in computer science because int != Integer, whereas associativity is a mathematical property on a operation on abstract entities.
Let us consider concrete example. Let op(a,b) = a + b, Domain(op) = char. Let a = -127, b = 127, c = 127. All a,b and c belong to Domain(op). But op(op(a,b),c) != op(a, op(b,c)) because right side of this equation makes no sense.
Does it mean that op is not an associative operation?
That should say “op is associative on integers.” The + sign was munged, sorry.
operator+ on int is a partial function. The book doesn’t track the definition space through all of the operations, instead it assumes we are dealing with partial models and we say that operator+ is associative in those cases where it is defined and push the requirement back as a precondition to operator+. This is called out back on page 17 (and the example of + on int is used) and discussed a bit more on page 70. Early drafts of the book where littered with checks for the definition space, but they add little since we are dealing with partial operations so often. Partiality is only called out explicitly in a few cases. Much of the discussion back in chapter 2 is about carefully managing the precondition that the operands must stay within the definition space of the function.
If I get you correctly, you’ve said that my example is invalid because operator+(INT_MAX, INT_MAX) is not valid expression because arguments are not in definition space?
It is good point, but IMHO it should be explicit stated in the book.
Yes – And I agree that it could be made more clear in the book. Perhaps with stronger wording when the term partial is introduced on page 17 and add an exercise in chapter 3 to relate the definition space of an op to associativity. This could also been done in chapter 2 – much of the code in that chapter is carefully written to stay within the definition space of the operations.