Stupid switch (ii) – Bad design

In most cases when we learn about the switch statement in C, we get something of the form:

switch(op) {
   case '+' : result = a + b;
              break;
   case '-' : result = a - b;
              break;
   case '/' : result = a / b;
              break;
   case '*' : result = a * b;
              break;
   default : printf("Error! Operator not found\n");
}

Which is pretty innocuous, and could have been coded with slightly less code using an if-else sequence. But switch has a somewhat darer side. While the if statement and the for and while loops allow a single statement without enclosing { }, so does switch, which is not something that is ever really discussed. So technically, this is valid:

switch(0);

as is this:

switch(i)
   i=i+1;

and even this:

switch(x)
   case 0:
      for (i = 0; i < 10; i++)
   case 1:
      for (j = 0; j < 10; j++)
   case 2:
      for (k = 0; k < 10; k++);

They all compile and run. But using them leads to code which is extremely difficult to comprehend, and likely results in the obfuscated code commonly seen in C (more so than any other language). Here is another fun piece of code:

int j, x=0;

switch(x) {
   int i = 4;
   case 0:
      j = i * i;
   default:
      printf("%d %d\n", i, j);
}

When this code runs, the answer produced is something like “32767 1073676289”, which is not the “4 16” expected. But why, it compiles okay? The problem is that the variable i is declared within the switch block, but it is not initialized to the value 4. This means that i contains some type of indeterminate value, in this case 32767, which when squared gives 1073676289.

This code seems odd, but it represents something that a novice programmer might write, and consequently it is compiled, which indicates to the programmer that what they wrote is acceptable.

 

 

Advertisements

Stupid switch (i) – Why B’s switch statement was better

One of the inadequacies of C has always been the lacklustre switch statement, which is less useful than similar statements found in other languages. This is strange considering C’s evolution from B, mainly because B allowed ranges, that’s right ranges. Consider the following piece of B code¹:

switch(c) {
   case 'A' :: 'Z' :
     c = c + 'a' - 'A';
   case 'a' :: 'z' :
   case '0' :: '9' :
   case '_' :
     break;
   case '.' :
     printf("Warning: avoid using dot.*n");
     break;
   default:
     printf("Invalid character:'%c'.*n",c);
     exit();
}

Although it has the awkward fall-though characteristic of C, it specifies ranges using the :: separator. Note that some compiler like GCC allow C language extensions, in this case using “…” in the form:

case 0 ... 9 :

But for some reason C has never adopted this in the standard. B also allowed relational headings, using <, <=, >=, and >. For example¹:

switch(i) {
   case <0 :
     printf("Number is negative");
     break;
   case 0 :
     printf("Number is zero");
     break;
   case >0 :
     printf("Number is positive");
     break;
}

Ignoring the whole fall-through issue, there is no doubt that both these concepts would have made the switch statement a much more effective construct in C.

¹ From “The B Tutorial Guide

 

Where did C arrays come from?

One of C’s predecessors was B, designed and implemented by Ken Thompson and Dennis Ritchie. B is essentially a simplified version of C, descended from BCPL. In the “Users’ Reference to B”, B was touted as a language good for “recursive, non-numeric, machine independent applications, such as system and language work” [1]. It was a typeless language, i.e. it had no type, or rather it had one type – the machine word, which is very similar to C’s int type.

Now arrays were problematic, because it is impossible to pack a whole array into a single word. B overcame this by defining an array to a pointer to a block of storage – the pointer could easily be stored in a word. This also makes it trivial to pass the array to a function, as only the pointer to the storage needs to be passed, not the whole array. Arrays were termed vectors in B.

From [1] – “a vector is a primary expression followed by any expression in [ ] brackets.” and “The primary expression can be thought of as a pointer to the base of the vector, while the bracketed expression can be thought of as the offset in the vector”.  The invertible notation used in C also had its beginnings in B: “Since E1[E2] is identical to *(E1+E2), and addition is commutative, the base of the vector and the offset in the vector can swap positions”.

There were some differences. In B, a vector was declared in the following way:

auto vec[10];

However this actually allocates 11 consecutive words, from vec[0] to vec[10]. A tutorial on B [2] makes the point that B lacks the Fortran-like ambiguity between subscripts and function calls, which both use ( ). B also introduced the unary operators * and & for manipulation of addresses. ‘&’ is the address operator so &x is the address of x, assuming it has one. ‘*’ is the indirection operator; *x means “use the content of x as an address.”

Strings were just a vector of characters, terminated in this case by what Kernighan calls a “mysterious character” known as *e (ascii EOT).

Interestingly enough, one document on B [3] makes it quite clear that “B does NOT check whether an index has gone past the end of a vector.”, going on to say “In B, it is the programmer’s responsibility to make sure that indices don’t run off the end of a vector. ” Seem familiar? (B also allowed negative indices in certain circumstances it seems, a practice I’m glad C dispensed with).

[1] Thompson, K., “Users’ Reference to B”, Bell Telephone Laboratories, (1972)
[2] Kernighan, B.W., “A Tutorial Introduction to the Language B” (1996)
[3] The B Tutorial Guide

 

Syntactic inheritance

Most languages inherit features, i.e. syntax from other languages. In language design, one chooses the most appropriate features from other languages to enhance the learnability and usability of a language. What happens though, when inappropriate features are chosen which over time propagate across language boundaries to become the de facto standard? Do we incorporate them in new languages, or, do we forsake them for other, more usable structures. A simple case in point is the use of * for multiplication, instead of the more natural ×. It wasn’t really a case of “not enough keys on the keyboard”. This is of course a somewhat benign example. Another example is C’s use of = to represent assignment and == to represent the test for equality. These have propagated throughout many language designs since 1972. Few languages use anything else these days, although as I have mentioned before, := is a marginal improvement, and  would offer a much better approximation of the process of assigning a value to a variable (APL was likely the purest in this context, but R comes a close second with the use of <-). While Ada still uses :=, most languages have succumb to C’s syntax.

Algol’s dangling-else was a legacy of its use of block delimiters *only* to indicate groups of statements, something C had no problem using, and is extremely common in C-based languages, despite the issues it causes. This despite the fact that Algol 60’s “successor”, Algol 68 used control-structure terminators. Some languages have now moved away from this, either with the use of terminators (Julia), or requiring the use of { } block delimiters (Swift), regardless of the number of statements in the block. Below is an example of the inheritance of the dangling-else (top), and how it is dealt with using block delimiters (bottom):

Conversely, here is an inheritance path in control-structure terminated languages:

 

Programming languages are the interface to the machine

We interact with machines in many ways, but the most primeval means is by writing programs. Programs become the soul of the machine, without them, the machine is useless, soulless. The programming language is the medium between the world of humans and the world of 1’s and 0’s.  Yet despite 60 odd years of programming language design, we are yet to design one which is easy for everyone to use. This is partially due to the intricacies of the machine, but also due to the fact that we don’t design for language usability per se. The easiest language for people to learn programming language concepts is a simple one – very little syntax, easy to decipher. The problem of course is more complex than that because programming does not only involve writing code.

There is the task of solving a problem, then developing an algorithm, and converting that algorithm into a programming language. Nothing is trivial. For example it is easy to state a problem of the form: “find all faces in a photograph“. The problem *seems* simple because to humans it is. Developing an algorithm is considerably more complex.

There are also differences between natural language and the programming language, what some would term linguistic transfer. Programming is difficult for novices because of how humans interpret a language. A case in point is the use of  while to indicate a loop.

while (n < 1000)
  -- do something constructive
end

The term while could be construed as a period of time, but more often it is misinterpreted as being applied continuously (i.e. a continuously active test), versus being evaluated once per iteration of the loop. In English one could say “while the sun is shining, play outside“, which is a loop of sorts, but not one we actively think about. We don’t look at our environment every minute to determine whether the sun is still shining. A novice programmer may misconstrue a while loop to terminate the minute the condition is satisfied.  It is an instinctive thing. Ada may actually have had a good idea with the concept of a loop where the exit is introduced within the loop itself.

loop
   exit when (n < 1000);
   -- do something
end loop;

We know a physical loop is continuous, be it in the form of a rope loop, or a loop in a road (or even the new Apple HQ building at Apple Park). Leaving the loop in the road involves making a conscious choice to leave while in the loop. This actually makes sense in many ways because there is one generic loop to deal with most situations. It could also deal with the case where one wants to do something n times, but that may itself be better expressed using something like a repeat statement:

repeat n times
   -- do something
end

Or what about this?

do repeat i with values 1 to n
   -- do something
end do

Too wordy? Likely. The same issues are encountered by the if statement. Novice programmers might not yet understand the sequential life of a program, and so they might consider an if statement to be “waiting” continuously, instead of being executed in sequence. Something like “if it starts raining, open an umbrella“. It might seem easy to the experienced programmer, but not so to the novice.

Is there a definitive solution? Unlikely. The use of the existing programming vernacular is ingrained into programmers. We have never really delved into the terms used for loops since the for loop appeared in Algol, and the while loop shortly afterwards. It might be possible to make small changes over time… but computer science rarely does things in small ways. We likely have to find better ways of teaching people to program.

 

 

Debunking myths about programming languages

Super programming languages are best.
There is no such thing as a “super” programming language. There is no “secret weapon” that will make writing a piece of software easier, and faster. If the algorithm isn’t any good, it doesn’t matter what the language is, it won’t save it. Garbage in, garbage out.

All languages are created equal.
Ah, no. Certain languages are good at some things, others are good at other things. For instance C is a fantastic systems language, Cobol is great for business stuff, Fortran is good at scientific work, and parallel processing, Ada is good for real-time systems. There is *no* one language to rule them all.

Fortran and Cobol are old, and quite useless.
Really? Fortran is 60 years old, C is 45. There isn’t much difference. You may not hear much about Fortran or Cobol, but that’s because they are quiet achievers. Not brash and loud-moutheed like Java. It doesn’t matter how *old* a language is, as long as it can do what you want it to do.

Object-oriented languages are better.
Not. OO appeared in the mainstream in the mid 1980s in the guise of C++. OO is a *methodology* for designing software, not a religious experience. Many languages (even Cobol) have gone down the OO route. Some people love OO so much one wonders if it is a cult of some sort.

GOTOs are harmful.
Yes, yes they are. Don’t think that you should use them in your programs. The unrestricted use of goto’s stems from the early years of languages such as Fortran. They were “it”, before other structures appeared. If your program is using a lot of them, then there is something wrong. Experienced programmers know where they can use goto’s. If you don’t understand where problems could occur, don’t use goto.

Compiled code always works perfectly.
??? The compiler will try and turn your program into something that can be interpreted by a machine. If the program compiles, it just means that the proper syntax was used, and the compiler was happy. Doesn’t mean there isn’t some hidden logic error in there somewhere. The larger the program and the  more complex the algorithm, the more likelihood that something might go wrong, sometime.

Python is better than C.
Like I said, no one language is better than another. C does well with systems programming, dealing with memory, low level stuff. Python is a good glue language, and is good for rapid development. C is a compiled language, Python is an interpreted language. C’s programs are fast, Python is slower. C is not an easy language for novice programmers, Python is. C requires very few dependencies, Python requires many depending on what you want to do. They are different, and that’s okay. And besides Python is written in C.

 

 

 

A simple programming language

In “The Humble Programmer”, written by Dijkstra in 1972 he made the following statement:

Another lesson we should have learned from the recent past is that development of ‘richer’ or ‘more powerful’ programming languages was a mistake in the sense that these baroque monstrosities, these conglomerations of idiosyncrasies, are really unmanageable both mechanically and mentally.”

And to be honest, he was probably right… but that wasn’t even the worst of it. If he thought Algol 68 was a monster, C++ and Ada would balloon to gargantuan proportions. Have we lost the ability to create simple programming languages? I don’t necessarily mean for the purpose of creating commercial applications – the nature of interaction with hardware, networking etc, makes languages with large scale structure necessary. But along the way we have used these commercial languages to teach novices to program – and it hasn’t really worked.

One of the reasons why students become disengaged with introductory programming courses may be the vast amounts of language knowledge required, on top of learning problem solving skills, and algorithm design. It may be too much for people not use to thinking in a “programming” mode. Learning about language-specific syntax, and memory management, design, testing, blah, blah, blah – it may be overwhelming. Which is surprising, but then those of us who learned programming in the 1980s  learned to program in Pascal, or maybe Fortran. Before languages added things like OO, became “functional”, and masters of everything that a language could be, they were simple – no really they were.

There were languages created specifically for teaching programming. Pascal was one. S-Algol was another (it appeared after Pascal).

Here is a program in S-Algol which performs a Bubble sort:

let n = readi
let x = vector 1::n of 0.0
for i = 1 to n do x(i) := readr
for i = 1 to n-1 do
   for j = 1 to n-i do
      if x(j) > x(j+1) do
      begin
         let temp = x(j)
         x(j) := x(j+1)
         x(j+1) := temp
      end
write "The sorted numbers are 'n'"
for i = 1 to n do write x(i), "'n"?

The structure of this language was very simple. It was from a pre-OO time when the programming world was simpler, happier.

 

Why Algol 68 was weird (and ultimately failed)

Look at this piece of code written in Algol 68, which finds the largest element of an array:

proc max = (ref[,] real a) real:
begin real big := -maxreal
   co assign the maximum real number allowed co;
   for i from 1 lwb a to 1 upb a do
   for j from 2 lwb a to 2 upb a do
   if a[i,j] > big then big := a[i,j] fi
   od od;
   big
end

It summarizes many of the things that were wrong with the language, and likely why it would have been a challenging language to teach people to program in.

  1. It uses a *lot* of acronyms. lwb is short for lower-bound.
  2. It uses control-structure terminators (for bracketing) that are the reverse of something in the beginning of the control structure… but not consistently. For example the for-do loop ends with od, and yet the if-then clause ends with fi. Shouldn’t that end in neht, or should the for loop end in rof? Not the smartest choice in the world.

There are elements of Algol68 that are inherently functional, however on the whole the language is mired by complexity. For example, consider the six forms of coercion (down from eight in the first report), something that would likely overly confuse the novice programmer: deproceduring, dereferencing, uniting, widening, rowing, voiding. Algol68 suffered from (i) being developed by committee – far too many people wanting far too many things incorporated into the language, and (ii) not being implemented widely enough, because implementation was a tricky process.

Check out this piece of code, which calculates a factorial:

Which is not exactly easy to read. Guess they didn’t care much about formatting either – not unusual for the time.

Reading a copy of the “Report on the Algorithmic Language ALGOL 68” might send you into a mild seizure, and even the Algol68 Genie learning guide is not for the faint-of-heart. I think if my first class in programming had involved Algol68, I would not have continued in computer science.

I think Algol 68 is summed up by this quote from  Aldous Huxley in his book Those Barren Leaves: It is the great dead language of the future. By the time Algol68 made its appearance, there were other hounds already barking at the gates… simpler languages that would take the lead.

 

 

Abbreviations in programming languages

Ever wonder where those wonderful abbreviations in C came from? You know += ? If you delve into Algol 68, you will notice some of them there.

Until Algol 68 datatypes were mostly indicated as keywords such as integer, real,  character. As the new kid on the block, Algol 68 introduced abbreviations that unlike PL/I were not optional. So integer became int, character became char, Boolean became bool (pity C didn’t make booleans integral from day one). For the novice programmer, this does tend to make programs more challenging to read. It also coined the term void. Algol 68 also allowed datatypes to be lengthened and shortened, in a way which will be inherently familiar to C programmers:

long real, long int, short real, short int, long long real, long long int

See the similarity? Of course it doesn’t end there. Algol 68 also allowed a form of optimization as it relates to operators:

sum plusab x

Look familiar? This is the “plus and becomes” operator, which can also be written as +:=, and in C as += . It’s like a piece of assembler jumping into your code… and the presence of this in the code was meant to signal the compiler that this code can be optimized. There were others of course: minusab, timesab, divab, and overab/modab for integers.

 

Experiential programming (with Julia) (ii)

So once the novice programmer is comfortable with dealing with small pieces of data, the purview of problems can be extended to say deal with 2D data such as simple monochromatic images. So let’s look at the “noise” problem. Some images can contain a type of noise called “impulse” or salt-and-pepper noise – random black (0) and white (255) pixels. Below is an (extreme) example of noise on a small image of a dome:

In this case, the algorithm is again a simple one, based on median filtering the image. This involves looking at each pixel in the image, calculating the median value of some region around that pixel, and then assigning this value to a new image in the same location. This could be explained i using some form of diagram showing how a picture is made up of individual pixels. Basically a median filter removes “extreme” pixels, which could represent the noise.

It will extend the experiences with both arrays, loops, and the median() function. In algorithmic terms.

  1. Read in a monochrome image called noisyimage.txt (it’s a simple text image), and store it in a 2D array (matrix).
  2. Find the size of the [image] array, and create a new array to store the “cleaned” image.
  3. For every element (pixel) in the 2D array, select a 3×3 neighbourhood around the pixel, and calculate the median value.
  4. Assign this median value as the new pixel in the output image.
  5. Write the output image in a file called cleanimage.txt.

An important part of experiential learning with respect to programming is also program comprehension. So instead of creating the code, from the algorithm it is also possible to provide the code and allow students to read the code and try and associate the parts of the code with the parts of the algorithm.  The Julia program to perform this noise suppression is only 9 lines in length. Here is what the program looks like:

imgIn = readdlm("noisyimage.txt",Int16::Type)
dx, dy = size(imgIn)
imgOut = zeros(dx,dy)

for i=2:dx-1, j=2:dy-1
   block = imgIn[i-1:i+1,j-1:j+1]
   newPixel = median(block)
   imgOut[i,j] = trunc(UInt8,newPixel)
end

writedlm("cleanimage.txt",imgOut)

Colour-coding helps to associate like regions of code. For example, the code in red here is associated with input/output, blue with setting data up, and purple with actually performing the median filtering.