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.

 

 

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

 

AI and Westworld

In HBO’s epitome Westworld, a series based on the 1973 movie of the same name staring Yul Brynner, we see a fantasy amusement park  populated with android “hosts”. People visit, interacting with hosts in various themed parks such as a “Western” theme. The hosts, are for all intents and purposes indistinguishable from humans. In fact they are not much different to the hubots on Swedish scifi TV series “Real Humans“, or its British adaptation  “HUM∀NS“ (except maybe that the synthetics humans on Westworld move through a continuous cycle of life, and often get shot-up and re-built). (spoiler alert if you have not seen the series, don’t read any further).

When the series starts, androids are programmed to perform whatever tasks they are required to in the theme park. They undergo what I assume is regular maintenance, and their previous memories are supposedly wiped. However as the series progresses, some of these synthetic humans become self-aware, either through deliberate programming, or through self-modification. Part of this self-awareness is the retention of memories, of a past, a recursive process that some think is one of the qualities that makes us humans.

Now it is inherently possible that in the future synthetic human-like robots will co-exist with us, this part really no longer is fantasy (in fact there are already a bunch of life-like robots). The question of whether or not they could become self-aware is another thing altogether. Throughout the  show, they show people (both humans, and androids), manipulating androids by way of changing their programming via a tablet (of course they make this seem extremely easy as well, which is unlikely). Let’s assume it is possible to create an android  that has the fluidity of the human body when it comes to mechanical movement, the ability to have programmed behaviours, and the ability to  learn from their surroundings.

In the series, when the androids become self-aware, in particular Dolores (see picture above), they “remember”, which implies that they know what has happened in the past. Given “memories” it is highly possible to build knowledge from them. The other side is the emotions portrayed by the androids. How do you code emotions? Human emotion is not really an easy thing to describe algorithmically. Star Trek tried it with Data, who experienced emotions via an “emotion chip”. It is of course possible to write algorithms to analyze human emotion through voice and speech pattern processing, and facial expressions,  but it is hard to determine how those emotions will affect a human. It may also be hard to replicate those emotions. So if an android can feel anger, or suffering, what do they do? The self-awareness felt by the androids in Westworld manifests itself in a feeling of mortality and self preservation, implying that they consider themselves as more than mere code. Could their emotions be influenced by the memories they have? Does being self-ware imply they are conscious? Or is their self-awareness a piece of AI that is entirely based on previous exeriences. For example if those memories are bad, then are their emotions predisposed to be “bad” as well?

Humans also make decisions based on emotion, and memories, however we also have the ability to think beyond that and use things like intuition. Humans also have senses – we consider things in the context of how they smell, feel, taste, or sound. Consider this painting by German painter Franz Marc (1880-1916) – Die gelbe Kuh (the Yellow Cow).

Some people might find the painting aesthetically pleasing, either because of the vibrant colours, or because of the content, the artist or the movement (Modernism anyone?). Somebody might enjoy the smell of Frangipani flowers, or dislike anchovies because of their taste. These behaviours are the “Himalayas of the mind” ¹. Why? because they are individual human perceptions that can’t be translated into an algorithm. Why does someone like a particular song? Or a  type of espresso-based coffee drink? A certain flavour of ice cream? These are things that an android with AI is not likely to be able to comprehend, or replicate.

At the end of the day, the androids in Westworld offer a glimpse into what the future holds. Truly conscious synthetic humans? That’s a stretch, considering we don’t even truly understand how ours own brains really work.

P.S. There are some issues that the series does not deal with. The androids never seem to need powering-up, nor do they really eat anything. Do they need nutrients, or are they self-powered? Seems somewhat of a limitation. I mean if they eat food and process it to provide energy, then they are truly miraculous living entities.

¹ The Tragically Hip

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

 

Median image filtering: efficiency

In a previous post I showed the results of applying a mean filter to a 14MP grayscale image in various languages. But what about a more intense median filter? I applied a 5×5 median filter to the same 2144×6640 pixel, 8-bit image, and the results are interesting. I ran the code in C, Fortran, Julia, and Python.

  • In Julia, I coded it plain, and simple, using the built-in median() function to calculate the median of each neighbourhood region. I also coded the same algorithm using parallel loops.
  • In Python I coded it using loops, no vectorization, and the built-in median() function.
  • In Fortran, I coded the algorithm using a simple bubblesort() to sort the array before finding the median, and selecting the median using Hoare’s quickSelect() algorithm.
  • In C, I coded the algorithm using three methods of finding the median: built-in qsort(), sorting using a bubblesort() function, and selecting the median using Hoare’s quickSelect() algorithm.

The outcomes are shown below:

 

What ever happened to ideas?

It’s hard to find time to think these days. The information age is all about creating more information, and not always good information – the internet is awash with garbage information. We write things, then write things about those things… it seems like an endless cycle, and somewhat dehumanizing. There was a time eons ago where people were left to think up new ideas, and sometimes they were just ideas. Imagine that… ideas. Not fully fledged products and devices… ideas, because for 1000s of years, good things came from ideas. Nowadays, few people want to invest in ideas, even academia – everyone want results, but thinking may not produce results for 6 months, or 6 years. It may take decades for an idea to come to fruition.

It saddens me that academia is so little interested in ideas. It use to be that conferences were places for disseminating ideas, but these days, it is more the norm to postulate an entire concept in the few pages allotted. If you don’t you risk your paper not being accepted. Musings of an idea? Why would anyone want that? Better if you had already done a 3 year study of the concept, included math equations from basic principles, and basically concocted an entire thesis and crammed it into a conference paper – so as to please everyone. It’s hard to know what to think anymore. I recently went on a conference where I gave a talk on using Julia as an image processing language (or any scientific programming for that matter) – targeted at novice programmers. The papers in my section of the conference were “interesting” to say the least. Some were not well presented, and some were far too mathy (not saying that mine was perfect in any way). I had someone interrupt my presentation after I mentioned that Julia was one of the few languages to have native parallelization,e.g. parallel loops. He waffled something about C allowing parallelization as well. YES, C11 does have threads, but it’s not that trivial to code for novices (which was kinda-of the point). During question time, someone else made a long statement  about a language they had developed (for some purpose?).

Or maybe I should just avoid AI/PR conferences in the future.

 

Recursive patterns – the Sierpinski Carpet

The Sierpinski Carpet is a fractal pattern first described by Waclaw Sierpinski in 1916. The Sierpinski carpet is self-similar pattern with 8 non-overlapping copies of itself. It starts with a solid white (255) square (in this case a 513×513). This is divided into nine smaller squares. The interior square is filled with black (0). This is the carpet at depth=1. Now subdivide each of the eight remaining squares into 9 squares and fill the centre square of each to obtain a carpet at depth=2. Continue doing this until a depth is reached. Below is an example.

Sierpinski Carpets of different depths: 1 to 4 (top 1,2; bottom 3,4)

What does the Processing code look like? The algorithm makes use of the Processing function rect() to mark a rectangle, and fill(0) to fill the rectangle with black (naturally any course could be specified).

int dim;
int limit, depth;

void setup() {
   size(513, 513);
   dim = 513;
   limit = dim;
   depth = 3;
}

void draw() {
   background(255);
   stroke(0);
   for (int i=1; i<=depth; i=i+1) {
      sierpinskiCarpet(0,0,dim);
      limit = limit / 3;
   } 
   noLoop();
}

void sierpinskiCarpet(int x, int y, int size){
   if (size < limit)
      return;
   size = size / 3;
   for (int i=0; i<9; i=i+1)
      if (i == 4){
         fill(0);
         rect(x+size, y+size, size, size);
         noFill();
      }
      else
         sierpinskiCarpet(x+(i%3)*size, y+(i/3)*size, size);
}

 

 

 

Recursive patterns – the Sierpinski curve

Processing can be used to show any number of different types of visualization, and one of the more interesting ones is recursive in nature. The Sierpinski curve is an exceptional example of mutual recursion. An exceptional algorithm can be found in Rohl [1], which is derived from Wirth[2].

The Sierpinski curve is what Wirth called aesthetically sophisticated. What seems like a curve with a simple building block is much more. This is because the difference between Sierpinski, and “simpler” curves like Hilbert is that Sierpinski curves are closed, i.e. without crossovers. The basic recursion schema is an open curve, and consists of four components which are connected by links which do not belong to the recursion pattern. The curve is drawn in a clockwise direction starting from the bottom left-hand corner. The components are marked N, E, S, W reflecting the direction in which they are drawn.

The components of a curve of order k are then constructed from the components of the curve of order k-1, and joined by diagonal, and horizontal or vertical lines. For example the N component of a curve of order k, is composed of curves of order k-1 in the sequence N→E→W→N, and is joined with lines in the NE, N, and NW directions respectively.

In Processing we first create a function lineTo(x,y) which draws a line from the current position to a new position (x,y), and then updates the current position.

void lineTo(float newX, float newY) {
   line(cx, cy, newX, newY);
   fill(0); 
   cx = newX;
   cy = newY; 
}

it uses two global variables, cx, and cy to maintain the current drawing position. Next we derive the eight direction drawing functions:

void lineN(){ lineTo(cx,cy-2*h);}
void lineS(){ lineTo(cx,cy+2*h);}
void lineE(){ lineTo(cx+2*h,cy);}
void lineW(){ lineTo(cx-2*h,cy);}

void lineNW(){ lineTo(cx-h,cy-h);}
void lineNE(){ lineTo(cx+h,cy-h);}
void lineSE(){ lineTo(cx+h,cy+h);}
void lineSW(){ lineTo(cx-h,cy+h);}

Here is the main function, sierpinskiCurve():

void sierpinskiCurve(int level) {
   sierN(level);
   lineNE();
   sierE(level);
   lineSE();
   sierS(level);
   lineSW();
   sierW(level);
   lineNW();
}

This draws the four separate curves, and joins them together. Here is the setup, and invoking code:

float cx;
float cy;
int h;
 
void setup() {
   size(800, 800);
   cx = width/2;
   cy = height;
}
 
void draw() {
   background(255);
   stroke(0);
   h = 3;
   sierpinskiCurve(4);
   noLoop();
}

And finally the four functions N, E, S, and W:

void sierN(int i){
   if (i == 1) {
      lineNE(); lineN();
      lineNW();
   }
   else {
      sierN(i-1); lineNE();
      sierE(i-1); lineN();
      sierW(i-1); lineNW();
      sierN(i-1);
   }
}

void sierE(int i){
   if (i == 1) {
      lineSE(); lineE();
      lineNE();
   }
   else {
      sierE(i-1); lineSE();
      sierS(i-1); lineE();
      sierN(i-1); lineNE();
      sierE(i-1);
   }
}

void sierS(int i){
   if (i == 1) {
      lineSW(); lineS();
      lineSE();
   }
   else {
      sierS(i-1); lineSW();
      sierW(i-1); lineS();
      sierE(i-1); lineSE();
      sierS(i-1);
   }
}

void sierW(int i){
   if (i == 1) {
      lineNW(); lineW();
      lineSW();
   }
   else {
      sierW(i-1); lineNW();
      sierN(i-1); lineW();
      sierS(i-1); lineSW();
      sierW(i-1);
   }
}

How does it work? Below are two examples: On the left, is a Sierpinski curve with h=10, and k=2, or the right, a denser curve with h=5, and k=4.

Here is an example of generating just sierN(k), where k=1,2,3,4, and 5.

Looking closely at the code of course, you will notice the amount of mutual recursion going on to generate these complex shapes.

[1] Rohl, JS., Recursion via Pascal, Cambridge University Press (1984)
[2] Wirth, N., Algorithms + Data Structures = Programs, Prentice Hall (1976)

The recursive nature of baking powder

“But neither the contingency of the universe nor a certain concept of original sin it implied did as much to make me whatever I am as another idea which burst upon me on the day when I first really saw a Royal Baking Powder can — or rather, to be perfectly exact, the picture of such a can which used to appear regularly in a colored advertisement on the back cover of the old Cosmopolitan. A little later I was to read Shaw’s Androcles and the Lion in Everybody’s Magazine, and that was important too. But not so important as the powder can. Perhaps I should be ashamed to mention… that the effect of that particular advertisement may have done more than McGuffey’s Readers to mold the American intellectual. Some, to be sure, missed the baking powder and were stopped in their tracks by Quaker Oats instead. But the difference is unimportant, and I have sometimes met ready comprehension when I asked without preliminaries: “Were you a Baking Powder man or a Quaker Oats man?” For the benefit of those who were blind to these advertisements, I had better explain. The can and the package were both adorned with pictures of the container itself. Therefore, the advertisements included a picture of a picture. And that picture must of necessity include a picture, of a picture, of a picture. In practice, of course, the series finally ended with a dot. But it shouldn’t have. And thus I became simultaneously aware of two stupendous facts. Infinity can be neither represented nor imagined, but logically it must exist. The brain reels, and it is a painful experience. But here at least is a trauma which must be suffered before any human being can become fully human.”

Joseph Wood Krutch
If you don’t mind my saying so…
The American Scholar, 1958

 

Evolution of “if” in C

C evolved from BCPL and B, and indirectly from CPL. Let’s start with CPL. In CPL the if statement took the form:

if X = Y then do Z := P
if X = Y then do § Z := P; A := B §|
where compound statements were delimited by section symbols (§) (note that the closing symbol has a vertical line through the bottom portion of the symbol). CPL is using = for equality testing, and := for assignment.  Interestingly, CPL had three conditionals:
if C1 then do S1
unless C1 then do S1
test C1 then do S1 or do S2
The unless is equivalent to if not, and test has the functionality of if… then… else, but deals with the dangling else ambiguity. The if statement evolved to become simpler in BCPL, with a reduction in keywords:
if C1 do S1 
unless C1 do S1
test C1 then S1 or S2
Some implementations used $( and )$ as the block delimiters, others seem to use braces, { }.

By the time B appeared, the if statement was looking very C-like.

if (C1) S1 else S2
 The expressive := for assignment got lost in favour of = which then meant that = had to be replaced by == for equality. This lead to C, which really wasn’t much of a change:
if (X == Y) Z = P;
if (X == Y) {Z = P;  A = B;}