Showing posts with label Prime Factors. Show all posts
Showing posts with label Prime Factors. Show all posts

23 April 2024

39 Years of Coding

39 (licensed CC BY by Tim Pierce)Last week was my 39th anniversary of coding. I got a Commodore 64 as a present for Easter Sunday from my mother. I own an old image to prove that. The exact date is tricky: There are no time stamps on my files, I do not know how old my oldest programs are. I wish I had added comments with time stamps back then. I was able to pin down some programs, like demos, to the year they were created by investigating file names and scrolling messages. On of these attributes to Easter 1986, so my start must have been in 1985. One of my neighbours had made fun of people using the Commodore only to play games, and I had bought a book about coding BASIC even before I owned the machine. It was a nice book with exercises to write pieces of code into gaps in the text. I imagine I wrote some silly Hello World program right away on that Easter Sunday, which would have been 8th of April 1985.

BASIC
I spent a large part of my teens fiddling with the Commodore 64 and its BASIC. It will always have a special place in my heart. I never really left BASIC behind. From time to time, I code a little kata in the emulator, e.g. Prime Factors, Game of Life or several years later Roman Numerals. When learning a new programming language, my usual exercise is to create a Scheme (Lisp) interpreter, but I have also played with BASIC as a Scala DSL and even turned it upside down creating a BASIC parser in Scheme, using TDD, unit tests and a file watcher to run my tests for all modified files. It was a fun project and I stopped after parsing most of the BASIC code I was able to find on my old disks.

Monkeys Everywhere
So what did I do on the evening of my anniversary? I opened a can of energy drink and had a look at a new programming language. I went for Garmin Connect IQ, a platform by Garmin to build applications for their watches. While I did not own a Garmin device, I wanted to support a developer at my client who wanted to create her own specialised app for her watch.

Chimpanzee (licensed CC BY by William Warby)Connect IQ reminds me a lot of Android: There is an SDK, support for various devices, an emulator, an API for different kinds of apps, an app store with review process and so on. It has manifests, permissions, storage, intents etc. Someone at Garmin had some humour, as the programming language is called Monkey C (with extension .mc), the build system is called Jungles (.jungle) and the system libraries use the Toybox namespace. They even have their own domain-specific property language for managing style elements, derived from CSS. The whole thing is branded with monkeys all over the place.

Using a small, proprietary language has disadvantages: There are only few public code samples to copy from and ChatGPT is unable to create any working code in Monkey C. Still I found everything I needed during that first evening: a minimalist Unit Testing framework and CLI commands to build and test my code. Piping the test output through a small shell script added ANSI colours, i.e. Red and Green respectively, to the test output. Perfection! In my tradition of learning new languages, I TDD'ed the Prime Factors code kata as first exercise:
import Toybox.Lang;

class PrimeFactors {

  static function generate(n as Integer) as Array<Integer> {
    var factors = [] as Array<Integer>;
    
    for (var candidate = 2; candidate <= n; candidate++) {
      while (n % candidate == 0) {
        factors.add(candidate);
        n = n / candidate;
      }
    }

    return factors;
  }

}
The language itself is object oriented and looks a lot like JavaScript with optional types, the as ... clauses. It is a compiled language and all type declarations are optional but can be forced with a compiler flag. I felt at home immediately. What a happy anniversary ;-)

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.

20 March 2021

11 Years of Prime Factors Kata

In this post I want to celebrate the Prime Factors Code Kata. Prime Factors is a small coding exercise first used by Robert C. Martin in 2005. It is my favourite code kata and it has been almost nine years since I last wrote about it - time to change that. Weird enough, the first code kata I ever worked on - outside of university assignments that turned out to be katas later - was Roman Numerals in 2007. The first time I did the Prime Factors was during Christmas holidays 2009 in Java and Ruby:
import java.util.ArrayList;
import java.util.List;

public class PrimeFactors {
  public static List<Integer> generate(int n) {
    List<Integer> primes = new ArrayList<Integer>();

    for (int candidate = 2; candidate <= n; candidate++) {
      for (; n % candidate == 0; n /= candidate) {
        primes.add(candidate);
      }
    }

    return primes;
  }
}
Now the Java code is exactly the code Robert Martin showed, I was following his example. The Ruby version from back then looks pretty similar, just using while instead of for.
module PrimeFactors
  def generate(n)
    prime_factors = []

    candidate = 2
    while n > 1 do
      while n % candidate == 0 do
        prime_factors << candidate
        n /= candidate
      end
      candidate += 1
      candidate = n if candidate > Math.sqrt(n) # performance fix
    end

    prime_factors
  end
end
If you are wondering how I am still able to find the code, I organise my code katas to allow lookup and comparison. Since then I did the kata 141 times and it has many uses.

Learn a language
Prime Factors is one of the first pieces of code I write - Test Driven of course - when revisiting old languages, like Commodore BASIC or looking at a new language, like Forth, using Gforth 0.7:
: prime_factors ( n -- n1 n2 n3 n4 )
  DUP 1 > IF           \ test for ?DO
    DUP 2 ?DO
      BEGIN
        DUP I MOD 0 =  \ test candidate I
      WHILE
        I SWAP I /     \ add candidate, reduce number
      REPEAT
    LOOP
  THEN
  DUP 1 = IF DROP THEN ;

T{ 1 prime_factors -> }T
T{ 2 prime_factors -> 2 }T
T{ 3 prime_factors -> 3 }T
T{ 4 prime_factors -> 2 2 }T
T{ 6 prime_factors -> 2 3 }T
T{ 8 prime_factors -> 2 2 2 }T
T{ 9 prime_factors -> 3 3 }T
Gforth came with a modified testing framework based on John Hayes S1I's tester.fs, defining the functions T{, -> and }T for testing. Note that the given function prime_factors is not realistic as the number of returned arguments is not known by the caller.

When I had a look at Scala, of course I did Prime Factors:
import java.lang.Math.sqrt

object PrimeFactors {
  def generate(number: Int): List[Int] = {

    def fold(current: Pair[Int, List[Int]], candidate: Int): Pair[Int, List[Int]] = {
      if (current._1 % candidate == 0)
        fold((current._1 / candidate, candidate :: current._2), candidate)
      else
        current
    }

    val (remainder, factors) =
      (2 to sqrt(number).intValue).foldLeft((number, List[Int]()))(fold)

    if (remainder > 1)
      (remainder :: factors).reverse
    else
      factors.reverse
  }
}
This is crazy. The code creates a sequence of all candidate primes and folds it starting from left by dividing by the candidate recursively, appending to the begin of the list, which is cheap. Because of that the list is reversed at the end. I have no idea why I created this, probably I was playing around with foldLeft. This is not a good example, please do not copy it. After all these years, the Forth solution seems easier to grasp. ;-)

So which languages are missing? PowerShell looks much like my PHP (shown below) and my Python Prime Factors looks similar too, just with Python specific range(2, number + 1) and //= inside. And of course JavaScript is missing:
PrimeFactors = function() {
  this.factors = [];
};

PrimeFactors.prototype.generate = function(num) {
  var candidate;
  for (candidate = 2; candidate <= num; candidate += 1) {
    num = this.tryCandidate(num, candidate);
  }
  return this.factors;
};

PrimeFactors.prototype.tryCandidate = function(num, candidate) {
  while (num % candidate === 0) {
    num = this.reduceByFactor(num, candidate);
  }
  return num;
};

PrimeFactors.prototype.reduceByFactor = function(num, factor) {
  this.factors.push(factor);
  return num / factor;
};
Isn't that lovely? Again this is not good code, please do not copy it. At least I showed some creativity using prototype functions.

Learn a testing framework
Using TDD to write some known code is a perfect way to learn more about a testing framework. So I explored XSLTunit using Prime Factors in XSLT or NUnit in C#:
using NUnit.Framework;

[TestFixture]
public class PrimeFactorsTest
{
  [TestCase(new int[0], 1)]
  [TestCase(new int[] { 2 }, 2)]
  [TestCase(new int[] { 3 }, 3)]
  [TestCase(new int[] { 2, 2 }, 4)]
  [TestCase(new int[] { 2, 2, 2 }, 8)]
  [TestCase(new int[] { 3, 3 }, 9)]
  public void TestFactors(int[] expected, int number)
  {
    CollectionAssert.AreEqual(expected, PrimeFactors.Generate(number));
  }

  [Test]
  [Timeout(100)]
  public void TestLarge()
  {
    CollectionAssert.AreEqual(new int[] { int.MaxValue },
                              PrimeFactors.Generate(int.MaxValue));
  }
}
Test your own testing framework
Sometimes, when I need to create my own unit testing framework, e.g. TPUnit for old Turbo Pascal, assert-scm (Scheme R5RS) or ASM Unit for Windows Assembly, I use Prime Factors as test cases:
_prime_factors:
  mov     esi, 0          ; esi = number of factors
  mov     edi, ebx        ; edi = address of factors
  mov     ecx, eax        ; ecx = current number
  mov     ebx, 1          ; ebx = candidate

  jmp .not_diviseable

.loop_over_candidates:
  inc     ebx             ; next candidate

.break_if_candidate_is_larger_than_square:
; if candidate * candidate <= number then try candidate
  mov     eax, ebx
  mul     ebx
  cmp     eax, ecx
  jbe     .try_candidate

; else number is a (large) prime and we are done
  mov     [edi + esi * register_size], ecx
  add     esi, 1
  jmp     .done

.try_candidate:
; if number % candidate == 0 then add candidate
  mov     eax, ecx
  xor     edx, edx
  div     ebx
  cmp     edx, 0          ; remainder is 0
  jne     .not_diviseable

.is_diviseable:
  mov     [edi + esi * register_size], ebx
                          ; store candidate in factors
  add     esi, 1          ; we found a factor
  mov     ecx, eax        ; number is remainder of division
  jmp     .try_candidate  ; try current candidate again

.not_diviseable:
; if number > 1 then try next candidate
  cmp     ecx, 1
  jne     .loop_over_candidates

.done:
; return number of factors
  mov     eax, esi
  ret
This piece of assembly calcultes the prime factors of the number passed in EAX into in the dword array address EBX.

TDD Demo
In 2012 I started practising Prime Factors as kata performance, minimising the number of keys I pressed. I ran it around 50 times. In the end I used the practice to calm down when I was anxious - it was like mediation. I still have to perform it somewhere, adding music and all... I have used it demoing TDD in uncounted presentations - actually around 40: during my university guest lectures, user group meetings and at my clients. Most demos were in Java and some in PHP,
<?php
class PrimeFactors {
  static function generate($n) {
    $factors = [];
    for ($candidate = 2; $candidate <= $n; $candidate += 1) {
      while ($n % $candidate == 0) {
        $factors[]= $candidate;
        $n /= $candidate;
      }
    }
    return $factors;
  }
}
and a single demo of test driving R code,
primeFactors <- function(number) {
  factors <- vector(mode="integer")

  candidate <- 2
  while (candidate <= sqrt(number)) {
    while (number %% candidate == 0) {
      factors <- c(factors, candidate)
      number <- number / candidate
    }
    candidate = candidate + 1
  }

  if (number > 1) {
    factors <- c(factors, number)
  }

  factors
}
It seems, most programming languages look the same. The last sentence is not true for NATURAL, Cobol's cousin, which is ugly. I will not show it here as it would destroy this lovely post.

Conclusion
By writing this post, I learned that I still need to create Prime Factors in the programming languages Go, Kotlin, OpenOffice Basic, Oracle PL/SQL and of course TypeScript - I could - and I will, it is just a matter of time. So Prime Factors - in fact any small enough code kata - is a great tool for exploring, studying and practising programming languages, testing frameworks, IDE tools and Test Driven Development in general. I will leave you with my latest addition to my collection of Prime Factors, using C99. Have fun!
#include <math.h>

typedef struct {
  unsigned char count;
  unsigned int values[31];
} PrimeFactors;

void PrimeFactors_init(PrimeFactors* factors)
{
  (*factors).count = 0;
}

void PrimeFactors_add(PrimeFactors* factors, const unsigned int factor)
{
  int count = (*factors).count;
  (*factors).values[count] = factor;
  (*factors).count = count + 1;
}

void generate(const unsigned int number, PrimeFactors* factors)
{
  PrimeFactors_init(factors);

  unsigned int remaining = number;
  for (unsigned int candidate = 2; candidate <= sqrtl(remaining); candidate += 1) {
    while (remaining % candidate == 0) {
      PrimeFactors_add(factors, candidate);
      remaining /= candidate;
    }
  }

  if (remaining > 1) {
    PrimeFactors_add(factors, remaining);
  }
}

22 March 2012

Prime Factors XSLT

Here is a short conversation we had at Hackergarten Vienna yesterday:

I did the Prime Factors Kata in XSLT. Would you like to review it?
You did WHAT?
You know, this small program. It's calculating the prime factors of a number.
But what? In XSLT? Why XSLT?
I know that it sounds a bit crazy. I had performed the kata in all programming languages which I know, e.g. Java, Ruby and even old BASIC or Turbo Pascal, but not using XSL transformations. So I just had to do it.

Initial Version
Using XSLTunit I created a test case that would apply the template to <value> to calculate the prime factors of the given source.
<xsltu:test id="test-template-factors-one">
  <xsl:variable name="source">
  <value>1</value>
  </xsl:variable>
  <xsl:call-template name="xsltu:assertEqual">
  <xsl:with-param name="id" select="'template factors 1'" />
  <xsl:with-param name="nodes1">
    <xsl:apply-templates select="exsl:node-set($source)/value" />
  </xsl:with-param>
  <xsl:with-param name="nodes2"></xsl:with-param>
  </xsl:call-template>
</xsltu:test>

...

<xsltu:test id="test-template-factors-four">
  <xsl:variable name="source">
  <value>9</value>
  </xsl:variable>
  <xsl:call-template name="xsltu:assertEqual">
  <xsl:with-param name="id" select="'template factors 4'" />
  <xsl:with-param name="nodes1">
    <xsl:apply-templates select="exsl:node-set($source)/value" />
  </xsl:with-param>
  <xsl:with-param name="nodes2">3 3</xsl:with-param>
  </xsl:call-template>
</xsltu:test>
and so on. The result looked like that:
<xsl:template match="value">
  <xsl:call-template name="generate">
  <xsl:with-param name="number" select="number(current())" />
  <xsl:with-param name="candidate" select="number(2)" />
  </xsl:call-template>
</xsl:template>

<xsl:template name="generate">
  <xsl:param name="number" />
  <xsl:param name="candidate" />
  <xsl:choose>
  <!-- one is no prime and does not have any factors -->
  <xsl:when test="$number = 1"></xsl:when>
  <!-- candidate == number, so number is a prime -->
  <xsl:when test="$candidate = $number">
    <xsl:value-of select="$number" />
  </xsl:when>
  <!-- number is factored by the candidate, factor it -->
  <xsl:when test="$number mod $candidate = 0">
    <xsl:value-of select="$candidate" />
    <xsl:text> </xsl:text>
    <xsl:call-template name="generate">
    <xsl:with-param name="number" select="$number div $candidate" />
      <xsl:with-param name="candidate" select="$candidate" />
      </xsl:call-template>
    </xsl:when>
    <!-- try again with the next factor -->
    <xsl:otherwise>
      <xsl:call-template name="generate">
        <xsl:with-param name="number" select="$number" />
        <xsl:with-param name="candidate" select="$candidate + 1" />
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>
StackOverflowError
Using javax.xml.transform.TransformerFactory from Java 6 to run the XSLT transformation, the last prime that was processed successfully was 7351. Calling generate with the following prime (7369) caused a StackOverflowError inside Apache Xalan due to the recursion. As there was no need to try candidates larger than the square root of number, I replaced the test for $candidate = $number with $candidate * $candidate > $number. This brought me as far as 54184313.

Reducing the Stack Depth
XSLT is a functional language, there are no loops, the only way to iterate is recursion. So the size of the largest prime to process is limited by the size of the stack. Still half of the recursions are useless because no even number larger than two can be a prime.
<!-- try again with the next factor -->
  <xsl:otherwise>
    <xsl:choose>
      <xsl:when test="$candidate = 2">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 1" />
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 2" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:otherwise>
This can be improved further by unrolling the (recursive) loop. If number is not factored by candidate + 2 then the next one is candidate + 4 and so on.
<!-- try again with the next factor -->
  <xsl:otherwise>
    <xsl:choose>
      <xsl:when test="$candidate = 2">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 1" />
        </xsl:call-template>
      </xsl:when>
      <xsl:when test="$number mod ($candidate + 2) = 0">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 2" />
        </xsl:call-template>
      </xsl:when>
      <xsl:when test="$number mod ($candidate + 4) = 0">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 4" />
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 6" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:otherwise>

14 February 2010

Turbo Pascal Prime Factors Kata

Wow Retro Recently I started performing the Prime Factors Kata. After playing with Java and Ruby I had the weird idea of performing it in every programming language I ever knew. Well, maybe not every - I don't plan to use 6502 or 80x86 assembler, that wouldn't be fun. But I already did it in BASIC. Going forward in time Turbo Pascal would be next. So it's time for another retro post ;-)

Where Is My TPUnit?
I couldn't find any unit testing framework for Turbo Pascal. The closest thing I could find was FPCUnit packaged with Free Pascal. Unfortunately it's not compatible with good old TP. So I had to roll my own. I started with some minimalist infrastructure.
TYPE TestCase = OBJECT
    PROCEDURE AssertEquals(msg:String; expect, act:Longint);
    PROCEDURE AssertNil(msg:String; act:Pointer);
    { other asserts ... }
    PROCEDURE Fail(msg:String);
    { TestCase }
    PROCEDURE SetUp; VIRTUAL;
    PROCEDURE TearDown; VIRTUAL;
  END;

PROCEDURE TestCase.AssertEquals(msg:String; expect, act:Longint);
VAR ex, ac:String;
BEGIN
  IF expect <> act THEN
  BEGIN
    Str(expect, ex);
    Str(act, ac);
    Fail(Concat(msg,' expected ',ex,' but was ',ac));
  END;
END;

...

PROCEDURE TestCase.Fail(msg:String);
BEGIN
  TearDown;
  Writeln(' - FAILED');
  Writeln(msg);
  Halt(1);
END;

PROCEDURE TestCase.SetUp;
BEGIN
END;

PROCEDURE TestCase.TearDown;
BEGIN
END;
Subclasses may overwrite SetUp or TearDown, add test methods and call Asserts. To keep it simple the first failed assertion stops program execution. What's missing is some kind of procedure RunTest that would wrap a particular test method inside calls to SetUp and TearDown. Hmm - function variables might be handy here. In case you are not familiar with them, here is an example:
{$F+} {needs far calls for function variables}
TYPE FuncVar = PROCEDURE;

PROCEDURE FancyMethod(method:FuncVar);
BEGIN
  method; { invokes the method }
END;

PROCEDURE SomeMethod;
...

VAR v:FuncVar;
BEGIN
  v := SomeMethod;
  FancyMethod(v);
END.
Pascal's CalculatorUnfortunately Turbo Pascal does not allow class methods (e.g. TestCase.AssertEquals) to be used as function variables. (At least I couldn't figure.) Obviously self is an implicit parameter of all such methods. Well not obviously, but analysing the generated machine code helps ;-)
SomeMethod; { -> 0E E8 D1 FB }
push CS { because of $F+ }
call fbe1 { address of SomeMethod in CS }

cls.ClassProc; { -> BF 70 00 1E 57 0E E8 ED FB }
mov DI, #0070 { address of object cls in DS }
push DS
push DI { first parameter is self }
push CS
call fbed { address of ClassProc in CS }
Using this knowledge TestCase.RunTest is implemented a bit dirty using an untyped Pointer argument:
PROCEDURE CallClassPtr(pt:Pointer; VAR cls:TestCase);
VAR s,o:Word;
BEGIN
  s := Seg(cls);
  o := Ofs(cls);
  ASM
    mov DI, [o]
    mov AX, [s]
    push AX
    push DI
    call [pt.dword]
  END;
END;

PROCEDURE TestCase.RunTest(name:String; testMethod:Pointer);
BEGIN
  Write('TEST ', name);
  SetUp;
  CallClassPtr(testMethod, self);
  TearDown;
END;
The Prime Factors Kata
Having a simple TPUnit in place, it's time for the kata itself. The seven test methods of PrimeFactorsTest,
PROCEDURE PrimeFactorsTest.Run;
BEGIN
  RunTest('TestOne', @PrimeFactorsTest.TestOne );
  RunTest('TestTwo', @PrimeFactorsTest.TestTwo );
  RunTest('TestThree', @PrimeFactorsTest.TestThree );
  RunTest('TestFour', @PrimeFactorsTest.TestFour );
  RunTest('TestSix', @PrimeFactorsTest.TestSix );
  RunTest('TestEight', @PrimeFactorsTest.TestEight );
  RunTest('TestNine', @PrimeFactorsTest.TestNine );
END;
yield
FUNCTION TPrimeFactors.generate(i:Longint):ArrayListPtr;
VAR factors:ArrayListPtr;
    candidate:Longint;
BEGIN
  factors := new(ArrayListPtr, Init);

  FOR candidate := 2 TO i DO
  BEGIN
    WHILE i MOD candidate = 0 DO
    BEGIN
      factors^.Add(candidate);
      i := i DIV candidate;
    END;
  END;

  generate := factors;
END;
ArrayListPtr is a pointer to a variable sized, user defined list backed by an array of Longints, similar to Java's ArrayList<Integer>. I can't deny I'm a Java guy. Everything I code looks like Java :-) (Probably I would have used a linked list back then instead of a complex object. Something like
TYPE PrimeFactorPtr = ^PrimeFactor;
  PrimeFactor = RECORD
    value:LongInt;
    next:PrimeFactorPtr;
  END;
Still the procedure body looks the same and the kata does not change much.)

(Download full source)

14 January 2010

Prime Factors Kata BASIC

The Prime Factors Kata is a small coding exercise first shown by Uncle Bob in Java several years ago. It has been done in C#, Ruby and probably some other languages. Recently Uncle Bob performed it as katacast in Ruby. (Go watch it! It's really cool. I will wait here.) He was followed by others in C# and Groovy. Anyway I'm sure it has not been done in BASIC. (Since my last post about Scala and BASIC I've felt so "retro".) So here is my Prime Factors Kata done in BASIC V2 (Commodore 64). I couldn't use my Scala BASIC DSL because it's lacking necessary features like GOSUB. So I used the Versatile Commodore Emulator (VICE) instead.

The First Test.
1000 CLR
1010 PRINT "test one ";
1020 i=1
1030 GOSUB 9000
1040 IF pf(0)<>0 THEN PRINT "expected no factors" : STOP
1050 PRINT "green"
Number i is the value to be factored and the array pf is expected to contain the number of prime factors in pf(0) followed by the factors themselves on return of the "generate" function (line 9000).
test one
?UNDEF'D STATEMENT ERROR IN 1030
Add the function.
8990 END
9000 REM ----- function generate
9010 REM in ... i ... number
9020 REM out ... pf() ... factors
9030 RETURN
Run the test.
test one green
The Second Test.
1100 CLR
1110 PRINT "test two ";
1120 i=2
1130 GOSUB 9000
1140 IF pf(0)<>1 THEN PRINT "expected 1 factors:";pf(0) : STOP
1150 IF pf(1)<>2 THEN PRINT "expected factor 2:";pf(1) : STOP
1160 PRINT "green"
test one green
test two expected 1 factors: 0
BREAK IN 1140
9000 REM ----- function generate
9030 IF i=1 THEN RETURN
9040 pf(0)=1
9050 pf(1)=2
9060 RETURN
Unfortunately there is no such thing as "BUnit". So I have to create testing infrastructure along the way. Keeping the tests green helps during the extraction of an "assert" method (line 100).
80 GOTO 1000
90 REM ***** test infrastructure *****
100 REM ----- method assert equals(int)
110 REM in ... me$ ... message
120 REM in ... ex ... expected
130 REM in ... ac ... actual
140 IF ex=ac THEN RETURN
150 PRINT "red"
160 PRINT me$;" expected";ex;" but was";ac
170 STOP
180 RETURN
...
1100 CLR
1110 PRINT "test two ";
1120 i=2
1130 GOSUB 9000
1140 ex=1 : ac=pf(0) : me$="num factors" : GOSUB 100
1150 ex=2 : ac=pf(1) : me$="1st factor" : GOSUB 100
1160 PRINT "green"
The Third Test.
1220 i=3
1230 GOSUB 9000
1240 ex=1 : ac=pf(0) : me$="num factors" : GOSUB 100
1250 ex=3 : ac=pf(1) : me$="1st factor" : GOSUB 100
Run the test.
test one green
test two green
test three red
1st factor expected 3 but was 2
BREAK IN 170
Modify the function.
9050 pf(1)=i
Green again. After the third test it's getting boring. The tests should be refactored to be more DRY:
200 REM ----- method teardown
210 PRINT "green"
220 RETURN
300 REM ----- method setup
310 REM in ... me$ ... test name
320 PRINT "test ";me$;" ";
330 RETURN
400 REM ----- method assert prime factors
410 READ me$
420 GOSUB 300
430 READ i
440 GOSUB 9000
450 READ af
460 ex=af : ac=pf(0) : me$="num factors" : GOSUB 100
470 IF af=0 THEN GOTO 520
480 FOR j=1 TO af
490 READ ex
500 ac=pf(j) : me$=STR$(j)+". factor" : GOSUB 100
510 NEXT
520 GOSUB 200
530 RETURN
990 REM ***** test cases *****
1000 DATA "one", 1, 0
1010 GOSUB 400
1100 DATA "two", 2, 1, 2
1110 GOSUB 400
1200 DATA "three", 3, 1, 3
1210 GOSUB 400
The Fourth Test.
1300 DATA "four", 4, 2, 2, 2
1310 GOSUB 400
9000 REM ----- function generate
9010 REM in ... i ... number
9020 REM out ... pf() ... factors
9025 REM local ... nf ... number factors
9030 nf=0
9040 pf(0)=nf
9050 IF i=1 THEN RETURN
9060 IF INT(i/2)*2=i THEN nf=nf+1 : pf(nf)=2 : i=i/2 : GOTO 9040
9070 nf=nf+1 : pf(nf)=i : i=1 : GOTO 9040
9080 RETURN
Line 9070 is more than needed to get the fourth test green, but it's the first thing that came to my mind.

The Fifth Test.
1400 DATA "five", 6, 2, 2, 3
Works as well, no changes needed.

The Sixth Test.
1500 DATA "six", 8, 3, 2, 2, 2
Again this still works, I "cheated" a bit.

The Seventh Test.
1600 DATA "seven", 9, 2, 3, 3
Now I really need the nested loops.
9000 REM ----- function generate
9010 REM in ... i ... number
9020 REM out ... pf() ... factors
9030 REM mod ... ca ... pf candidate
9040 pf(0)=0 : REM special case
9050 IF i=1 THEN RETURN
9060 IF INT(i/2)*2<>i THEN GOTO 9110
9070 pf(0)=pf(0)+1
9080 pf(pf(0))=2
9090 i=i/2
9100 GOTO 9050
9110 FOR ca=3 TO INT(SQR(i)) STEP 2
9120 IF i=1 THEN RETURN
9130 IF INT(i/ca)*ca<>i THEN GOTO 9180
9140 pf(0)=pf(0)+1
9150 pf(pf(0))=ca
9160 i=i/ca
9170 GOTO 9120
9180 NEXT
9190 RETURN
This includes already two performance optimisations: Handling the special case 2 up front to be able to use STEP 2 and skip every second prime factor candidate. Second using the square root of i as upper bound for the loop. But there is a bug not covered by the tests. Can you spot it? Yet another refactoring to remove duplicate code of adding prime factors to pf.
9040 pf(0)=0 : ca=2 : REM special case
9050 IF i=1 THEN RETURN
9060 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 9050
9070 FOR ca=3 TO INT(SQR(i)) STEP 2
9080 IF i=1 THEN RETURN
9090 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 9080
9100 NEXT
9110 RETURN
9200 pf(0)=pf(0)+1
9210 pf(pf(0))=ca
9220 i=i/ca
9230 RETURN
I could still get rid of the duplicate lines 9060 and 9090...

Another Test.
1700 DATA "eight", 10, 2, 2, 5
This reveals the bug in line 9070. If the value contains different prime factors then the last factor is lost. We need another check in line 9110.
9100 NEXT
9110 IF i>1 THEN ca=i : GOSUB 9200
9120 RETURN
END.
One last refactoring to add colours and time measurements to methods "setup" (line 300) and "teardown" (line 200). Two more tests to see the performance of larger (32719) values of i. The function even works for 2^31-1 (huge), but takes quite some time, although the loop is already optimised.Prime Factors Kata tests are all green :-)(Download the source.)