10 March 2024

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.

Void (licensed CC BY-NC-ND by Jyotsna Sonawane)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.

Nothing Happened (licensed CC BY-SA by Henry Burrows)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...

19 October 2023

Unit Testing Scheme

For more than four years this article has been waiting to be written. Now a rainy summer day can do wonders. Back in 2018, when I fell into Scheme, I needed a unit testing framework. I was digging into Scheme with coding exercises and wanted the quick feedback of my TDD cycle so see if I was on the right track. I did not know anything about modules, dependency management or how to get custom code in Scheme and searched the web for a small test framework. As minimalism is in the spirit of Scheme, I initially went with the Scheme Unit outlined on Cunningham's Wiki,
;
; Unit test framework for scheme
; see http://c2.com/cgi/wiki?SchemeUnit
;
(define (report-error msg)
    (display "ERROR: ")
    (display msg)
    (newline))
    
(define (assert msg b)
    (if (not b)
        (report-error msg)))
Evolution
Now that was minimalist indeed. But as good as it was, it lacked important features: I wanted more assertions, at least for all basic data types, and needed to see some colours. What is the point of a green bar, if it is not shown in green. I had created my own xUnit libraries before, one for good old Turbo Pascal and one for assembly (written in assembly - usually you would use C). While both were useful, I did not get famous for them, it seems that am focusing on "niche products" in the testing framework world. Creating my own xUnit was a kata in itself and always helped me while learning a new programming language.

I started adding more assertions already in 2015 and test cases in 2017. I kept extending it whenever I needed something new, always copying the latest file to the next code kata. In 2018 I decided to put my "SchemeUnit" up on GitHub under the name of assert-scm. Now my tests, for example the tests for the Parrot kata, look like
(include "assert.scm")
(include "parrot.scm")

(test-case "it gets the speed of an european parrot"
    (assert= 12.0
             (parrot-speed 'european-parrot 0 0.0 #f)))

(test-case "it gets the speed of an african parrot with one coconut"
    (assert= 3.0
             (parrot-speed 'african-parrot 1 0.0 #f)))
Features of xUnit
Which features are expected from a true xUnit framework? From my knowledge of JUnit, I derive the core elements of xUnit:
  • Assertions: First we need assertions. These are typically called assertSomething. Assertions are necessary to verify the actual result versus the expected one. If these values are not equal, the assertion should fail in some way. There should be assertions for equality of basic data types. In my Scheme xUnit there are (assert-true actual) and assert-false, assert= for integer numbers and symbols (and everything you can compare with = in Scheme), assert-char= and assert-string= for these primitives and assert-inexact= for floating point numbers which allows a delta for rounding errors. There are assert-null, assert-not-null, and more. As lists are the basic, all encompassing data structure in Lisp, and therefore Scheme, any testing framework for these languages needs support for comparing lists for equality: assert-list= and assert-list-deep= for flat and deep list comparison.

  • Failure Messages: Assertions need to fail with descriptive messages. For example, if two values expected and actual are not equal, I would like to see "expected: <expected value> but was: <actual value>". I hate testing frameworks which just stop with "Assertion failed." Creating good messages gets more interesting when comparing lists as they can be of different length and nested. After assertions, this is the second important thing to have.

  • Test Cases: In xUnit, test cases are often a bit weird, as they are classes containing multiple methods. Each of these methods is an individual test case because during test execution the class is instantiated for each method. In some frameworks test methods are named testSomething(), or annotations or other markers are used. In frameworks without classes, e.g. Jest or Pytest, each test function is a test case. A test case has a name, often the name of the method, some arrange code, some logic and one or more assertions. Test cases should be run independently of each other and report success or failure individually.
    (test-case "(test-case) allows several assertions"
        (assert-true #t)
        (assert-true #t))
    will print (test-case) allows several assertions .. OK.

  • Ignoring Test Cases: Sometimes I want to ignore a certain test case. Most frameworks offer ways to do that, e.g. @Ignore, @Disabled, @mark.skip or using other markers. I like the Mocha way of replacing it('') with xit('') and went for a different function ignored-test-case:
    (ignored-test-case "(ignored-test-case) is ignored, else it would fail"
        (assert-true #f))
  • Test Suites: Test suites are used to group test cases. Naturally these are Java classes, Python modules or Jest/Mocha describe blocks containing test methods. In Scheme 5 that would be files. Files can include other files which allows me to build arbitrary test suites. I rarely use test suites in any language, as I am running all tests most of the time.

  • Fixtures: Fixtures contain the necessary creation and release of resources needed for the test and make sure these are released even if the test failed. Older test frameworks allow setup and teardown methods or @Before/@After markers. Other approaches include injecting necessary dependencies, as for example JUnit 5 and Pytest do. Till now I did not need fixtures in my exercises. In small test sets, I am fine when tests stop at the first failing test.

  • Asserting on Exceptions: Few testing frameworks offer assertions for exceptions. For example in Java, before JUnit 5's assertThrows, there were 5+ ways to test that a method threw an exception. Maybe this is a special case, something that is rarely used. As I was building my assert-scm Scheme xUnit from scratch, I wanted to be sure the assertions work. How would I test for a failing assertion? I had to dig deeper into Scheme. Standard R5RS Scheme has no function to catch exceptions and different implementations handle this differently. Gambit Scheme, the Scheme I started, offers some proprietary extension for exceptions, whereas Chicken Scheme, another common Scheme, has some support for handling exceptions - called conditions. At least Chicken version 4 does, but it is outdated now. Portability is an issue between different Scheme implementations. It seems Scheme R6RS has standard support for exceptions, but its structure is way more complicated. I would like to avoid this for fun exercises.
If you are interested in features of xUnit and how to use them I recommend you work through my Unit Testing-Koans exercises.

Prime Factors
Exploring a new language is incomplete for me, until there is a nice TDD, step by step implementation of the Prime Factors kata. It is my goto exercise and I am collecting my Prime Factors solutions - which usually look the same. Here are the tests:
(include "prime-factors.scm")
(include "../assert-r5rs.scm")

(test-case "one"
    (assert-null (prime-factors 1)))

(test-case "two"
    (assert-number-list= (list 2) (prime-factors 2)))

; ...

(test-case "nine"
    (assert-number-list= (list 3 3) (prime-factors 9)))

(test-case "max"
    (assert-number-list= (list 2147483647) (prime-factors 2147483647)))
which execute in assert-scm's GitHub build,

assert-scm Prime Factors Test
and verify the code
(define (prime-factors n)
    (test-candidate n 2))

(define (test-candidate n candidate)
    (cond ((= n 1) (list))
          ((too-large? n candidate) (prime n))
          ((divides? n candidate) (keep-candidate n candidate))
          (else (next-candidate n candidate))))

(define (too-large? n candidate)
    (> candidate (sqrt n)))

(define (prime n)
    (list n))

(define (divides? n candidate)
    (= (modulo n candidate) 0))

(define (keep-candidate n candidate)
    (append (prime candidate)
            (test-candidate (/ n candidate) candidate)))

(define (next-candidate n candidate)
    (test-candidate n (+ candidate 1)))
This is neat, isn't it? If you fancy playing with Scheme and do not want to miss unit tests, check out assert-scm, a minimalist unit test framework for Scheme R5RS.

3 October 2023

I find your lack of tests disturbing

I Find Your Lack Of Tests DisturbingClassics never get old. Like with Shut up and Write a Test, I am reposting an old meme about lack of tests, see its preview on the right. Lack of tests is a direct result of not following the prior advice when to write tests. ;-) In many coaching discussions I need to fall back to the fundamental basics and I cannot allow such a gem to vanish. Usually I find the lack of tests in my client's code base disturbing.

Origin
The image was posted on rubystammtisch.at, a site which ceased to exist long time ago. I downloaded it at the 25th of March 2009 for a presentation held at the local user group. The meme is a variation of Darth Vader's "I find your lack of faith disturbing", used as a phrasal template where "faith" is swapped with other words. Now that I have researched the origin of the image, I could re-create it using Meme generators. I will not, a classic is a classic. (And again, during writing a blog post, the process of writing is valuable and I learn on the way by organising and structuring the material. That is why I recommend writing as a learning and teaching activity at the same time.) Unfortunately the original image is only 400 pixel width, printed versions will be fuzzy. It might use it on my upcoming Code Cop Veto Cards, similar to my Achievement Appreciation Cards, as cards require smaller images with less detail.

I find a lack of tests disturbing.