Programming with Nothing

I like extreme coding constraints. A constraint, also known as an activity, is a challenge during a kata, coding dojo or code retreat designed to help participants think about writing code differently than they would otherwise. Every constraint has a specific learning goal in mind, for example Verbs instead of Nouns. After playing with basic constraints for a long time now, I need more challenging tasks. Combining existing constraints makes things harder: For example Object Callisthenics or my very own Brutal Coding Constraints are way harder than their parts applied individually.

Missing Feature Group of Constraints
There is a another group of extreme constraints which I call the Programming With Nothing constraints. They are a subgroup of the Only Use <placeholder> constraints. All of these belong to the Missing Feature group. The well known No If and No Naked Primitives constraints are good examples of Missing Features because we take away a single element that we are so very much used to. Only Use <placeholder> constraints force you to use new constructs instead of something else. For example, Alexandru Bolboaca, the pioneer of Coderetreat in Europe, once mentioned the following constraints to me: Only Bit Operations replaces all arithmetic operations, like plus or multiply, with bit operations and Only Regular Expressions asks you to use Regular Expressions as much as possible. You can get pretty far with Regular Expressions in exercises like Balanced Brackets, Coin Change, Snake or Word Wrap. (Look for the Bonus Round at the bottom of the Word Wrap page.)

Programming With Nothing
But let us get back to Programming With Nothing. The first one of this group, which I came across ten years ago, was presented by Tom Stuart in his 2011 Ru3y Manor talk Programming With Nothing. Tom is taking functional programming to the extreme, only allowing the declaration of lambda expressions and calling them. The exact rules he is following are:

• Create functions with one argument.
• Call functions and return a result.
• Assign functions to names (abbreviate them as constants).

Basically he is using the Lambda Calculus and this constraint is also referred to as Lambda Calculus. His talk is using Ruby, using only Proc.new, no booleans, numbers or strings, no assignments, control flow constructs or standard library. Clearly he is programming with nothing. (Here is the recording of the talk, his slides and the code.) Over the years I have seen similar presentations, even using Java.

The Fizz Buzz Kata
The goal is to implement the Fizz Buzz kata. While Fizz Buzz is very simple, it needs looping integer numbers up to 100, conditionals on integer comparison, integer division and strings. It is very small but not simple. Some people even use it during job interviews - which is controversial. The whole Fizz Buzz is:

for (i = 1; i <= 100; i++) {
  if (i % 3*5 == 0) 
    print("FizzBuzz");
  else if (i % 3 == 0) 
    print("Fizz");
  else if (i % 5 == 0) 
    print("Buzz");
  else 
    print(i);
}

And this is quite a lot if all you have is a lambda. I maintain a starting point for TypeScript, to be used in my workshops. This kind of exercise is fun, at least for me ;-). If you follow the assignment, i.e. work on numbers, then booleans, then pairs etc., you can use Git branches to jump to the next milestone - or take a sneak peak how it could be done.

Extreme Object-Orientation
In 2015 I watched John Cinnamond's Extreme Object-Oriented Ruby, which is like Tom Stuart's Programming with Nothing. This version only allowed you to define objects which contain other objects and call the nested object's methods or return them. In his starter repository he described how to simulate booleans, numbers and so on.

Nothing but NAND
Then I tried to write Fizz Buzz only using NAND. This is Programming With Nothing the hardware way. How so? A NAND gate is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND says Wikipedia. More importantly, the NAND gate is significant because any Boolean function can be implemented by using a combination of NAND gates. This property is called functional completeness.. Because of its functional completeness it should be possible to create arbitrary programs. I started out with a Bit class which had its nand() function implemented and all other code was built on top of this. Numbers, i.e. arrays of bits,

class Numbers {

  static final Byt ZERO = new Byt(OFF, OFF, OFF, OFF, OFF, OFF, OFF, OFF);

  // ...

  static final Byt FIFTEEN = new Byt(ON, ON, ON, ON, OFF, OFF, OFF, OFF);
  static final Byt HUNDRED = new Byt(OFF, OFF, ON, OFF, OFF, ON, ON, OFF);
}

and bitwise logic,

class Logic {

  static Bit eq(Bit a, Bit b) {
    return not(xor(a, b));
  }

  // ...

  static Byt and(Byt a, Byt b) {
    return not(nand(a, b));
  }

  // ...

  static Byt ifThenElse(Bit b, Byt theThen, Byt theElse) {
    Byt condition = Byt.from(b);
    return or(and(condition, theThen), 
              and(not(condition), theElse));
  }
}

were straight forward. Arithmetic was cumbersome due to possible over- and underflows.

class Arithmetic {

  static BitOverflow inc(Bit b) {
    return new BitOverflow(not(b), b);
  }

  static BitOverflow add(Bit a, Bit b) {
    return new BitOverflow(xor(a, b), and(a, b));
  }

  // ...

  static Byt inc(Byt a) {
    BitOverflow r0 = add(a.b0, Bit.ON);
    BitOverflow r1 = add(a.b1, r0.overflow);
    BitOverflow r2 = add(a.b2, r1.overflow);
    BitOverflow r3 = add(a.b3, r2.overflow);
    BitOverflow r4 = add(a.b4, r3.overflow);
    BitOverflow r5 = add(a.b5, r4.overflow);
    BitOverflow r6 = add(a.b6, r5.overflow);
    BitOverflow r7 = add(a.b7, r6.overflow);
    return new Byt(r0.b,r1.b,r2.b,r3.b,r4.b,r5.b,r6.b,r7.b);
  }
}

For loops I added a sequence of bits which worked as the Instruction Pointer. Using the IP and the existing arithmetic operations I implemented goto which I used to jump back during loops. The final code did not look much different than your regular structural code, using functions and mutable data. The exact list of things I used was:

• Data structures for a single bit, a byte (8 bits) and a series of bytes i.e. memory.
• Bit nand(Bit other) as the only logic provided.
• Getting and setting the values of the data structures.
• Defining functions with multiple statements to create and modify data and call other functions.
• A map to associate statements with memory addresses indexed by the IP. Was this cheating?

I had played with assembly in the past, which helped me to build my program from NANDs alone. It is a great learning exercise to understand computers' logical components and CPUs. There is even an educational game based on the idea of NAND.

What is Next?
I cannot remember how I ended up there, but next I tried to write Fizz Buzz using a Touring Machine. But this is a story for another time...