The more I play around with Swearjure (I’ve now been able to create a fully working quicksort), the more I appreciate certain kinds of programming constructs we today take for granted. However, I also realize that most of what we would believe are essential for ANY programming language to be Turing complete may not be needed if we take another set of programming constructs instead. Take conditionals as an example of what something people consider to be critical to making a working programming language, yet really isn’t if we introduce another programming construct.

A No-conditional Language

When I say conditionals, I mean conditionals as in branching. Pattern matching and polymorphism are not allowed, so e.g. this Erlang snipped is banished:

fib(1) -> 1;
fib(2) -> 1;
fib(N) ->
    fib(N-1) + fib(N-2).

To continue with fibonacci, a normal and working C implementation may look like this:

int fib(int n) {
  int res[2];
  if (n < 2) {
      res[1] = 1;
  }
  if (! (n < 2)) {
      res[0] = fib(n-1) + fib(n-2);
  }
  return res[(n < 2)];
}

(Assume that (n < 2) either returns 0 (false) or 1 (true).)

Not idiomatic, but it will be easier to work with. As I said, we’re not allowed to use conditionals: Every part of a function has to be evaluated. As such, we’re left with this:

int fib(int n) {
  int res[2];
  res[1] = 1;
  res[0] = fib(n-1) + fib(n-2);
  return res[(n < 2)];
}

Here we get a stack overflow, as res[0] will call the function regardless of whether n is less than 2 or not. Many programmers may think that we could solve this by “implement” branching through flexible gotos. This is true, and the code would look like this:

int fib(int n) {
  int res;
  goto lookup[n < 2];
  zero:
  res = 1;
  goto end;
  one:
  res = fib(n-1) + fib(n-2);
  end:
  return res;
}

Here, lookup represents two relative offsets the goto jumps by, which in practice should move to the zero: label when zero, and one: when it’s one.

This is a viable solution, but it’s based upon a very low-level machine instruction (you can do this with mov register, ... followed by jmp register), and I consider it as “cheating” as we now have evaluated only parts of the function. If we could climb the abstraction ladder instead of jumping off it, then that would be interesting.

A New First-class Citizen

We can solve this easily by constructs already existing in C: By having functions as first-class citizens¹ we can refer to two different functions in the code and call the one we are interested in as follows:

int fib(int n);

int ret1(int n){
  return 1;
}

int fib_sum(int n){
  return fib(n-1) + fib(n-2);
}

int fib(int n) {
  int (*fn[2])(int);
  fn[1] = ret1;
  fn[0] = fib_sum;
  int res = (*fn[(n < 2)])(n);
  return res;
}

And as if by magic, there’s no need for conditionals which only evaluates parts of a function. Take note that both functions have to accept the same number of arguments, and if you use the same type, then that would also be smart.

You could always argue that we are simulating conditionals by putting parts of the original function in different functions. We are indeed doing that here, but we’re doing it with a construct which does not care how functions are implemented. Whether it is by setting up a new stack frame on the call stack or sending signals to a set of analog and artificial neurons, it doesn’t matter.

And now to a more interesting question: Is there any value in this? Except for my slightly optimistic thought of using it for analog neurons, could it be used for anything? Debugging control flow may actually be easier with this type of branching.

Call Stack-based Debugging

So what may be an issue when you normally debug stuff? If you have multiple branches in sequence, you may be unable to detect which branch you took earlier in the same function/method. Say we want to create a formatting string in Python and end up with the following:

def prettyprint(a, b):
    if a < b:
      fmt_string = '%d is less than %d'
    else:
      fmt_string = '%d is higher than %d'
    return fmt_string % (a, b)

Now, for some “strange” reason, we end up with 1 is higher than 1 when we call prettyprint(1, 1). If this was way more complex and we didn’t see the immediate reason why this is the case, we may add in a breakpoint to see what the value of fmt_string was before we returned it with arguments applied:

def prettyprint(a, b):
    if a < b:
      fmt_string = '%d is less than %d'
    else:
      fmt_string = '%d is higher than %d'
    breakpoint()
    return fmt_string % (a, b)

Well, now we can poke around, look at the stack trace and so forth. But we’re still not sure of which branch we took. In the example, we could just look up the values of a and b, but what if these values have changed? And what if we add in more branches? Knowing which branch we took for every case would be horrible without some debugger help. And with some tricks, we may make this possible.

If the compiler/debugger is able to create this “evaluate every piece of line” format for functions (generating new ones when needed), then we can use the stack to check which branches we’ve taken — they’re on the stack, after all! But if we’re having very many branches, the stack may look just as spaghetti as our code. It would thus be satisfying if the compiler or debugger could show us visually what branch we’ve walked. So, let us take some prettyprinting function again:

def prettyprint(a, b):
    if isinstance(a, int) and
       isinstance(b, int):
      if a < b:
        fmt_string = '%d is less than %d'
      else:
        fmt_string = '%d is higher than %d'
    else:
      fmt_string = "%s and/or %s aren't numbers!"
    breakpoint()
    return fmt_string % (a, b)

A debugger could for instance show us the following (when a = 1 and b = 1):

def prettyprint(a, b):
    if isinstance(a, int) and
       isinstance(b, int):      if a < b:        fmt_string = '%d is less than %d'
      else:
        fmt_string = '%d is higher than %d'    else:
      fmt_string = "%s and/or %s aren't numbers!"
    breakpoint()    return fmt_string % (a, b)

Here the green lines represent lines we have evaluated and branches we’ve decided to take. The red lines show conditional branches we’ve evaluated but not decided to take. As such, it’s very easy to see the control flow we’ve done previously.

It’s easy to see case and if-statements with this technique, but it doesn’t cover while, for and other loop constructs. For that, we would need better tricks. Bret Victor has an amazing talk on this kind of visualization, named Inventing on Principle (Link points to the start of the code visualization, the previous minutes show an example of a HotSwap-like way of programming).

Different Constructs, New Ideas

To summarize, I started out with the idea of a new language with a different subset of language constructs than what is commonly used. From there, I found a way to avoid the need for the other constructs—either by simulating the other construct or finding a way to avoid the need for that construct.

After I’ve found that method, I try to find a use case for this method in “normal” languages. In this case, I found out that—combined with a compiler and a debugger—we can neatly visualize what branches taken before a breakpoint. Of course, there may be easier ways to obtain the same visualization, I haven’t done a very thorough research on that part. However, the point is that we can discover new development methods using a limited set of programming constructs. They may not always be useful, but sometimes a new development method may make it easier or simpler to solve a specific problem. It’s worth testing out those subsets: If we don’t find any valuable ideas, then at least we’ve expanded our knowledge horizon.