Title: Report on Challenge 5

Author: Bob Schmidt

Date: 02 January 2019 15:58:57 +00:00 or Wed, 02 January 2019 15:58:57 +00:00

Summary: Francis Glassborow comments on his previous challenge, and provides a new puzzle.

Body: 

Challenge 4 produced a large post bag. Unfortunately this one produced almost nothing. Well, I had one partial submission. I gave the author of that an extra hint but that resulted in effective silence.

As usual, I tried to give some pointers in the introduction to the challenge but no one seemed to pick up on it. You need some lateral thinking and you, the readers, are usually pretty good at that. As I suggested by relating the competition to a language of seven words, seven is actually surplus to requirements once you realise that words can have multiple meanings that can be selected by a suitable mechanism. Let me elaborate a little more on that. Even without fancy use of binary coded selectors, each of your seven words could have a position dependency in three word sentences. For example, given a sentence structure ‘x y z’ and a word abc: abc could mean ‘put’ when replacing x, ‘it’ when replacing y and ‘there’ when replacing z. So the sentence ‘abc abc abc’ translates as ‘put it there’.

That is a simplistic example to illustrate the idea of positional meanings (actually, we have such uses in English, ‘fast row’ is not the same as ‘row fast’ and ‘eight pieces’ is very different from ‘pieces of eight’).

C++ is burdened with numerous contextual meanings inherited from a time when we struggled to avoid introducing new keywords. The outstanding example is static but even our operators suffer from multiple meanings (e.g the * in *x is not the same as the * in x*y).

Now the surprising thing (to some) is that we do not actually need many built-in operators, though doing without them would be tedious in the extreme.

Let me hit the metal. Down deep, our programs turn into operations using logic gates. Those who have studied mathematical logic, or the basics of hardware design, know that all we need is a single type of logic gate. We can choose a ‘nand gate’ which takes two inputs and outputs ‘false’ only if both inputs are true or a ‘nor gate’ which outputs true only if both inputs are true. I am going to focus on a nand gate.

We can create the software equivalent with the following function:

  bool nand (bool b1, bool b2) {
    if(b1) {
      if(b2) return false;
    }
    return true;
  }

We can build all the other six standard logic gates using just nand gates.

  bool not (bool b) { return nand (b, b); }
  bool and (bool b1, bool b2) {
    return not(nand (b1, b2));}
  bool or (bool b1, bool b2){
    return nand( not(b1), not(b2));}
  bool nor (bool b1, bool b2) {
    return not(or(b1, b2));}
  bool xor (bool b1, bool b2) {
    return and(or(b1, b2), or(not (b1),
    not (b2)));}
  bool notxor(bool b1, bool b2){ not(xor(b1, b2));}

I know that I can define those six functions more simply but I am demonstrating that all the simple logic operators can be defined in terms of just one of them (you can use ‘nor’ instead of ‘nand’ as your elementary logic operator if you wish).

Now let me construct a half-adder in software (it adds two bits and returns the result along with a carry bit):

  struct bits{ 
    bool s;
    bool c;
  };
  bits half-adder(bit b1, bit b2){
    bits r{xor(b1, b2), and(b1, b2)};
    return r;
  }

From that we can make a full adder which can cope with three inputs, two bits and a carry bit:

  bits adder(bit b1, bit b2, bit carry){
    bits r1{half-adder(b1,b2)};
    bits r2{half-adder(r1.s, carry)};
    bits r3{r2.s, or(r.c, r2.c)};
      // only one of the calls to half-adder can
      // set the carry flag
    return r3;
  }

So far I have managed to avoid all the C++ operators. I have sidestepped assignment by using initialisation to capture the result of a function call but it gets increasingly difficult to work round not being able to modify an existing variable. With pure functional programming, I might be able to avoid assignment but that will not meet the needs of C++. So it seems that I must allow operator= as a primitive.

I also need to have some way to extract individual bits from a variable.

In hardware, the assignment operator is handled by store and the individual bits by the wiring of the cpu. So I am going to allow myself two operators as primitives. = will store a value on its right-hand side into the storage designated by the left-hand side. The index operator ([]) will allow extraction of individual elements of an array.

We are almost there. In order to use our adder to do arithmetic, we need a way to decompose a value into its constant bits and a way to recompose a value from its constituent bits. We can decompose an unsigned int by using a suitable array containing the values of the individual bits (1, 2, 4, 6, etc.) together with a bitwise and operator. The boolean value of:

  value bitand bitvalues[n]

will give us the nth bit of value.

Similarly a bitwise or operator will allow us to set bit n of value.

The ability to extract a bit coupled with being able to set a bit allows us to create shift operators by extracting a bit and inserting it in a result value either one place up or one place down.

Given an adder, bitand, bitor, assignment and an index operator we can, albeit tediously, create all the logic and arithmetic operators. Creating the comparison operators can be managed (compare equal and compare not-equal are relatively straightforward, less than and greater than require rather more work).

I thought that that was about it and that four operators (assignment, index, bitor and bitand) would be sufficient. However, there is one murky corner where we need something more. I leave it to the reader to determine what that is and how it might be provided.

Challenge 6

I suppose I need to provide a more down to earth challenge that many of you will feel able to tackle.

Back in the 1970s – and even the early 1980s – most attempts at providing a perpetual calendar were flawed, even those written by professional programmers. A perpetual calendar is a program that will determine which day of the week any specific date falls on. For example, what was the day of the week for 25/12/1884 (or in ISO format, 1884-12-25 as used by the Japanese, which has the great advantage that dates in that format are simple to sort)?

Numerous flaws trapped the unwary programmer, such as the definition of a leap year. A student of mine in 1979 wrote a Basic program that worked correctly for all dates given four inputs, day, month, year and Julian or Gregorian. The month could be given as either a number from 1 to 12 or as a name. It tolerated names spelt with mixed case. If you mis- spelled the name it would guess based on the first three letters and ask for confirmation. If the day was impossible it would issue an error message (e.g. ‘February does not have 29 days in 1900 using a Gregorian Calendar.’ or ‘There are never 31 days in April’)

Nothing that hard but he did it in 33 statements in Basic. At the time it was a phenomenal effort though the local moderators marked it down because it wasn’t, in their opinion, long enough. Fortunately the chief examiner understood quality as opposed to length.

So your challenge is to write the shortest program that you can that takes as input a date and a choice as to whether to use a Julian or a Gregorian calendar. You are not allowed to use any library facilities for time.

Francis Glassborow Since retiring from teaching, Francis has edited C Vu, founded the ACCU conference and represented BSI at the C and C++ ISO committees. He is the author of two books: You Can Do It! and You Can Program in C++.

Notes: 

More fields may be available via dynamicdata ..