Compiling Io Addons

This is the second part of my journey into installing Io addons. A quick recap: Io "is a dynamic prototype-based programming language". It was made more? widely known by Bruce Tate's book Seven Languages in Seven Weeks. Io's extensions, i.e. libraries or packages however you like to call them, are called addons and follow the same structure. Eerie, Io's package manager, fails on my platform and I have to add addons manually. It is the main purpose of these posts to show how it can be done. I explain the installation of addons with different needs and increasing difficulty using concrete examples. In part one I covered Kano as an example for installing addons without any native code..

Compiling an Empty Addon on Windows: Kano
As an example, I want to compile an addon without any native code. I noticed that all installed addons, even the one without any native code, e.g. CGI, do have an init file and a dll. Maybe it is not strictly necessary. AddonLoader, a helper to the importer, checks for more than one C file - but I will need it later anyway. How does such an empty init file look like? For example, in the distribution IoCGIInit.c is

#include "IoState.h"
#include "IoObject.h"

__declspec(dllexport)

void IoCGIInit(IoObject *context)
{
}

Easy enough to create such a file Kano/​sources/​IoKanoInit.c. In the source distribution which I will mention later, there is generate.io in the root of the addons, which does exactly that. The script accepts a path to the addons dir and the name of the addon:

> cd "%IO_HOME%\lib\io\addons"
> io generate.io . Kano
> cd Kano\source
> gcc -fPIC -D _NO_OLDNAMES -c IoKanoInit.c
IoKanoInit.c:1:21: fatal error: IoState.h: No such file or directory

Of course I need headers. Where is the source distribution?

Io Source Distribution
The latest binary I downloaded from the Io site is iobin-​win32-​current.zip. Little version information there. Io reports io --version a version of 5.9.2011 but the executables and libraries were in fact created 5.11.2013. The nearest source release is 4.12.2013 which seems to be compatible. (The older 5.9.2011 source release is definitely incompatible with the addons included in iobin-​win32-​current.zip.) The source distribution is also interesting because it contains all sources of the standard library in libs\​iovm\​io\*.io.

The required headers are in libs\​iovm\​source\*.h and libs\​basekit\​source\*.h. After setting proper include paths (C_INCLUDE_PATH), compilation is possible. The switch -fPIC seems to be redundant on Windows, but it is set in one of Io's makefiles, so I keep it. I have no idea what I am doing ;-) The switch -D _NO_OLDNAMES defines _NO_OLDNAMES which solves the error: conflicting types for 'SSIZE_T' which occurs when old names are allowed. Sigh. Again, no idea what I am doing.

> cd Kano\source
> gcc -fPIC -D _NO_OLDNAMES -c IoKanoInit.c
> gcc -liovmall -shared -Wl,--out-implib,libIoKano.dll.a ^
      IoKanoInit.o -o libIoKano.dll
> mkdir ..\_build\dll
> move lib*.* ..\_build\dll
> cd ..\..
> io -e "Kano supportedFiles println"
list(make.io, Kanofile, kanofile, Kanofile.io, kanofile.io)

Compiling Native Code: Rainbow
Next I tackle addons with native code but without any third party dependencies. Most addons of this type are included in the distribution, because their compilation does only depend on Io itself, e.g. Blowfish, Box, LZO, MD5, Random, Range, etc. An addon I found which is missing is Rainbow, which "allows you to colourize command line output." Rainbow does not have a protos file and it has no package.json neither, but there is an eerie.json which does not say anything about prototypes. The addon contains a single Io file Rainbow.io and a single C header IoRainbow.h. I guess this is the prototype then - see line (1) in the following shell commands:

> git clone https://github.com/IoLanguage/Rainbow
Cloning into 'Rainbow'...
> touch Rainbow\depends
> echo Rainbow > Rainbow\protos && rem (1)
> io -e "Rainbow println"
Exception: Failed to load Addon Rainbow - it appears that the addon exists but needs compiling."

This is a useful error message. Io's AddonLoader checks native sources when loading an addon. Compile it. First

> io generate.io . Rainbow

creates a different IoRainbowInit.c file this time,

#include "IoState.h"
#include "IoObject.h"

IoObject *IoRainbow_proto(void *state); // (2)

__declspec(dllexport)

void IoRainbowInit(IoObject *context)
{
    IoState *self = IoObject_state((IoObject *)context);

    IoObject_setSlot_to_(context, SIOSYMBOL("Rainbow"), IoRainbow_proto(self)); // (3)
}

I have marked relevant references to the addon a.k.a. the "primary" prototype in bold face. Line (2) is the forward reference to code in Rainbow.c, which will create a new prototype. Line (3) sets this prototype under the symbol of its name into a slot of the context. (Io stores all variables in slots, many functions in the standard library work with slots, e.g. slotNames() or getSlot​(name).) There is some more information about writing C addons for Io in the Io Wikibook. For example it explains the addon structure - which I already knew but at least my "research" is validated. ;-)

Back to the compilation of Rainbow. Continue after line (1) in the previous script:

> cd Rainbow\source
> gcc -fPIC -D _NO_OLDNAMES -c IoRainbowInit.c IoRainbow.c
> gcc -liovmall -shared -Wl,--out-implib,libIoRainbow.dll.a ^
      IoRainbowInit.o IoRainbow.o -o libIoRainbow.dll
Creating library file: libIoRainbow.dll.a
IoRainbow.o:IoRainbow.c:(.text+0x5c): undefined reference to `_imp__IoTag_newWithName_'
... more errors omitted

Of Course, Linker Errors
These errors are strange and I spent a long time investigating. The libiovmall.dll.a exports __imp​__IoTag_​newWithName_, with two underscores in the beginning but the linker only looks for one. I verified this with nm libiovmall.dll.a | grep __imp__. This is due to some compiler inconsistency between Linux and Windows and/or GCC and/or MingW regarding function name decoration. GCC Options "-fleading-underscore and its counterpart, -fno-leading-underscore, change the way C symbols are represented in the object file." I tried both of them but then other symbols like fprintf are not found any more. There might be a linker option -Wl,--add-stdcall-underscore but it is not recognised by my MingW GCC. Sigh.

The solution is to not link against the link libraries (*dll.a), but against the dlls directly. (Either delete the *.dll.a from the io/lib folder or change your LIBRARY_PATH to use io/bin instead.) Summary: When your linker looks for a single underscore in dll exported symbols, and the library exports correctly, link against the dll instead of the lib..

The change to the library path fixes the linking and libIoRainbow.dll is created. The dll must be moved to the build result folder ..\​_build\​dll as before. In addition all headers should be copied to _build\​headers, as other addons might depend on them.

> mkdir ..\_build\dll
> move lib*.* ..\_build\dll
> mkdir ..\_build\headers
> copy *.h ..\_build\headers
> cd ..\..
> io -e "Rainbow println"
Rainbow_0x29ba488

All addons contained in the Windows distribution have the _build\​headers folder, but there are no headers. I will need these headers to compile Regex in part three. Let's iterate all addons and copy the headers:

set ADDONS=%IO_HOME%\lib\io\addons
dir /A:D /b "%ADDONS%" > addons.txt
for /F %a in (addons.txt) do ^
    if exist "%ADDONS%\%a\source\*.h" ^
        copy /Y "%ADDONS%\%a\source\*.h" "%ADDONS%\%a\_build\headers"
del addons.txt

Addon Initialization Recursion Issue
One recurring issues I faced was that AddonLoader was recursing endlessly trying to load something. For example, when I created IoRainbowInit.c by hand, I made a mistake with the symbol in line (3). On loading the addon, AddonLoader entered an endless loop,

> io -e "Rainbow println"
IOVM: Received signal. Setting interrupt flag.

current coroutine
---------
Object Rainbow            Rainbow.io 14
FileImporter importPath   Z_Importer.io 49   <-
FileImporter import       Z_Importer.io 125    |
List detect               Z_Importer.io 125    |
true and                  Z_Importer.io 125    |
Object Rainbow            Rainbow.io 14        |
Importer import           Z_Importer.io 138    |
FileImporter importPath   Z_Importer.io 49   --
...

This was because the proto was not registered under its correct name, see SIOSYMBOL in line (3) above, and the importer tried to import it again, found the addon (again), and repeated. Tip: When addon importing enters a loop, double check the symbol name in the C init.

A similar error happens when the a prototype of an addon uses another prototype of that addon during code loading. For example Eerie comes with two prototypes: Eerie and SystemCommand. The first line of Eerie.io imports SystemCommand. Now when I evaluate Eerie println, the AddonLoader finds the Eerie addon (by name) and loads the file Eerie.io to load that prototype. During import it sees SystemCommand as a dependency and looks for it. It finds it in the proto file of Eerie and tries to load it. When loading the addon, it loads the prototype of the same name, i.e. Eerie.io again.

> io -e "Eerie println"
IOVM: Received signal. Setting interrupt flag.

current coroutine
---------
Object SystemCommand        Eerie.io 4
Addon load                  AddonLoader.io 124  <-
AddonLoader loadAddonNamed  Z_Importer.io 97      |
FolderImporter import       Z_Importer.io 125     |
List detect                 Z_Importer.io 125     |
true and                    Z_Importer.io 125     |
Object SystemCommand        Eerie.io 4            |
Importer import             Z_Importer.io 138     |
Addon load                  AddonLoader.io 124  --
...

Cyclic imports are a bad idea anyway, it is fair that this does not work. Still I have not seen any warning about it in the Io documentation. Tip: Avoid top level "imports" of prototypes from the same addon.

Compiling Native Code: Thread
Another addon without dependencies is Thread. It has a proto, depends and package.json file. Using generate.io I follow all the steps from Rainbow above, just with different C files and compilation and linking succeeds. Unfortunately Thread createThread("1+1"), as shown in the documentation, terminates the Io VM when evaluating the expression string (1+1). There are no further hints or messages. I have no idea why and no means to debug the Io virtual machine.

Follow along in Part three about compiling addons with third party dependencies.

Porting RLE8

I am going back in time (again) and playing with some of my old source code: In the days of MS-DOS, 16 bit operating systems and 640 kB of RAM, I created a whole bunch of MS-DOS utilities and tools, mostly written in Turbo Pascal. In the last 20 years I have only ported a few of them. From time to time I miss one of these old tools - but never miss it enough to invest the time to write it from scratch. Last year I came across p2c, a Pascal to C translator by Dave Gillespie. Oh such joy - and I used it to port my old tools. One tool I used - which I had not created myself - was RLE8 by Shaun Case, Public Domain 1991.

RLE8
RLE stands for run-length encoding compression. It is a form of data compression in which repeated values are represented by a count and a single instance of the value. It is a very simple form of compression and in the nineties it sometimes reduced disk and memory space significantly. It was used in early versions of Windows BMP for bitmap compression named BI_RLE8: An RGB format that used run-length encoding (RLE) compression for bitmaps with 8 bits per pixel. The compression used a 2-byte format consisting of a count byte followed by a byte containing a colour index. There were versions for 4 and 8 bit image data, RLE4 and RLE8 respectively. "RLE compression was used in the stone-age" as one forum comment reads and today there not much interest in it. The only reference I found was for benchmarking highly optimised code.

Finding the Original Source
Finding the original source code was difficult. It is in the nature of the modern WWW that new pages appear and old ones disappear. Fortunately the RLE8.EXE printed the name of its author and its license: Shaun Case 1991 Public Domain. After some googling I found an article about it, which later turned out to be the contents of the Readme someone had reposted almost ten years later on GameDev. Eventually I found the Retro Computing Archive with its collection of CD-ROMs containing shareware and Public Domain software from the late 80's and 90's. RLE8_SC. Win! (The Retro Computing Archive is great, many of its ZIP files are unpacked and therefore crawled by Google which helped me find it.)

Porting from Turbo C
The code compiled without issues, but included a header I did not have, dir.h, a header from Borland's Turbo C. I guess this is the biggest issue when porting old code - calls to non-standard library functions. I missed fnsplit, a function which split file specifications into component parts. While I could have created the function myself - an excellent opportunity to practice my C - I searched more and luckily someone had created it already. Thank you Robert B. Stout. Robert granted license to use his source files to create royalty-free programs, which RLE8 is. After adding some more of Robert's code, and removing code which was not needed, RLE8 compiled and linked, even with my pedantic settings of gcc -std=c99 -pedantic -pedantic-errors -Wall -Wextra. I loved it. Witness the power of C, a 50 years old programming language, still moving forward.

Download original and modified sources together with binaries for DOS and Windows x86.

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);
  }
}