C++Next

We got pretty good turnout for the first batch of exercises this week. Thanks to Tim Wright, John Phillips, and Mark Ruzon for their submissions!

Lemmas

Mark Ruzon proved all the lemmas. Good show, Mark! We liked his answers a lot, only changing one word to clarify Lemma 1.2.

Lemma 1.1

If a value type is uniquely represented, equality implies representational equality.

If a value type is uniquely represented, than at most one value corresponds to each abstract entity. Therefore, two equal values must have the same representation, and so equality implies representational equality.

Lemma 1.2

If a value type is not ambiguous, representational equality implies equality.

If a value type is unambiguous, then each representation has at most one interpretation. Therefore, two values with the same representation must have the same interpretation (or no interpretation), meaning they refer to the same abstract entity. Therefore, representation equality must imply equality.

Lemma 1.3

A well-formed object is partially formed.

A well-formed object can be assigned to or destroyed. Therefore it is partially formed.

Exercises

Exercise 1.1

Extend the notion of regularity to input/output objects of a procedure, that is, to objects that are modified as well as read.

Everybody obviously knew what they wanted to say about the first exercise and headed down the same difficult path in formulating their answers. We think part of the problem here is the phrasing of the exercise, which seems to ask about regularity of objects. We think the real intention is that you extend the notion of regular procedures. So perhaps it should be worded this way:

Exercise 1.1 (revised)

Extend the notion of regularity to procedures that not only read, but modify, their arguments.

With that clarification comes the following answer, which we think is a little crisper than anything submitted:

A procedure is regular-mutating iff it can be implemented solely in terms of a regular procedure and assignments to its formal parameters.

The idea is that you can translate a regular-mutating procedure f(x, y)—that in C++ would take arguments by reference—into a call to a regular procedure f’(x, y) and assignments from the result of that call (which may be a tuple) into x and/or y.

Exercise 1.2

Assuming that int is a 32 bit two’s complement type, determine the exact definition and result space for the functional procedure int square(int n).

This exercise yielded diverse and interesting answers, which we’ll present here in a mash-up:

Tim Wright:

The definition space are the values that given to the procedure will output it’s square. The range is -46,340 (0xFFFF4AFC) to 46,340 (0x0000B504) in steps of 1. The square of 46,340 is close to the maximum value in 32 bit two’s complement, which is 2³¹-1. The square of the next larger integer will not fit in the type.

Mark Ruzon:

The definition space is [-46340,46340] and the result space is {0, 1, 4, 9, …, 2,147,395,600}

John Phillips:

The result space is the set of all representable perfect squares

The definition space is the set of integers with representable squares