16 December 2024

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..

Trackibles Prototype (licensed CC BY-SA by Rodolphe Courtier)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
Showing the strain (licensed CC BY by Brian Smithson)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 (coming soon) about compiling addons with third party dependencies.

9 December 2024

Installing Io Addons

Io is an interesting programming language. I had not planned to learn a new language in 2024. Then, in a quiet moment, I reached for Seven Languages in Seven Weeks by Bruce Tate. It is an older book, published in 2010 and I know some of the languages described there. I like studying programming languages. Playing with basic concepts without the need to finish larger tasks is relaxing. It should be an easy read.

Mustache Prototypes (licensed CC BY-NC by Bre Pettis)The Io Language
Io "is a dynamic prototype-based programming language." It seems more or less dead since 2010, basically since the book mentions it. Its site states "actively developed until 2008". While there are a few updates from last year, the latest available build for Windows dates to 4th of December 2013, more than ten years ago. Much of Io is written in C and one should be able to build it from source using cmake. While I like the retro character of plain C, similar to old Pascal, I am un-experienced in the C ecosystem. I am using Windows and building C has been proven to be a hassle due to dependencies and compiler inconsistencies. So I went with the provided Windows build.

Io is prototype based, like JavaScript and looks different than your usual C-styled languages. The core library iovm comes with a unit testing framework. The UnitTest is an old-school xUnit, e.g.
FizzBuzzTest := UnitTest clone do (

  setUp := method(
    super(setUp)
    self fizzbuzz := FizzBuzz clone
  )

  // ...

  testFizz := method(
    result := fizzbuzz single(3)
    assertEquals("Fizz", result)
  )

  // ...

  testTo5 := method(
    result := fizzbuzz upto(5)
    assertEquals(list("1", "2", "Fizz", "4", "Buzz"), result)
  )

)
The corresponding Fizz Buzz is
FizzBuzz := Object clone do (

  single := method(n,
    if (n % (3 * 5) == 0, "FizzBuzz",
      if (n % 5 == 0, "Buzz",
        if (n % 3 == 0, "Fizz",
          n asString)))
  )

  upto := method(limit,
    Range 1 to(limit) map(n, single(n))
  )
)
This could be written more concise, but such was my first Io code. I should probably do a Prime Factors, too. It seems that I am obsessed with unit tests, as it is usually the first thing I look for in a new language, e.g. Scheme or Assembly. If you want to know more about Io, read the guide or the second chapter of Seven Languages in Seven Weeks. While the language is dormant, it will change the way you see programs - exactly as Bruce promises.

Io Addons
The Io distribution contain a bunch of extensions collected under the IoLanguage GitHub organisation. Many extensions are wrappers around well tested C libraries, but these "may not be installed on your system already." And this is probably the reason why the Windows distribution only contains 28 out of the 80+ available addons. While I ignore MySQL or graphics library wrappers, basic functions like socket communication or regular expressions would be nice. There is Eerie, the Io package manager, which should be able to deal with compiling addons, but its installation fails on my system - because of a dependency that needs a missing C library (recursion ;-). Then I try to add addons manually. It is the main purpose of this post to explain how it can be done.

Let me start with some general structure of Io addons: Installed or bundled addons are located in %IO_HOME%\​lib\​io\​addons and share the same folder structure as expected by Io's AddonLoader. Assume an addon named Foo, then the following folders and files (could) exist:
  • _build: Several folders with the build results of C code, mostly empty.
  • _build\dll\libIoFoo.dll and libIoFoo.dll.a: Compiled C code, its dynamic library and GCC import library file.
  • _build\headers: Empty for bundled addons, but should contain the C headers of exported functions, i.e. the Io*.h files from source.
  • bin: Starter scripts for addons which are command line tools. e.g. Kano.
  • io\*.io: Main Io source code, i.e. new prototypes. There is at least a Foo.io.
  • samples\*.io: Optional sample code.
  • source\*.c|h: C source code, at least IoFooInit.c. The empty folder must exist.
  • tests\correctness\run.io and one or more *Test.io: Unit tests, the run.io runs all tests in the current folder.
  • tests\performance\*.io: Optional performance tests, sometimes with run.io.
  • depends file: a list of other prototypes (or addons) this addon depends on.
  • protos file: a list of all prototypes this addon provides.
Addons are activated in Io by using the prototype with the name of the addon. In an Io REPL or script, Foo will find the addon and import it making all its prototypes available. This works for all provided prototypes given the manifest (i.e. the protos file) is correct.

Io Package Management: Eerie
While working with the different types of addons, see this and the next article, I seem to have reverse engineered much of Io's build and package infrastructure ;-). Knowing about it upfront would have helped. Eerie is the package manager for Io. Unfortunately its installation failed on my system - and it seemed way too complicated for me because it created multiple environments, much like Python's virtualenv. Its documentation is "coming soon", and not helping. Some addons on GitHub are Eerie packages and miss necessary files like protos. While sometimes these files are still there - an oversight as it seems, Eerie packages contain other files:
  • package.json is the Eerie manifest. It contains the description of the package and its dependencies. This file is useful.
  • eerie.json is some kind of manifest, used in the Eerie Package Storage Database. Only two addons have it and the database is empty.
  • build.io will "rewrite AddonBuilder to represent a receipt for your package." Most addons have this and it contains information about needed native libraries and transitive dependencies.
It seems that Eerie's PackageInstaller extractDataFromPackageJson() method creates the protos, depends and build.io files from package.json. I will have to do this by hand. Unfortunately some package.json are incomplete and some miss important information.

Now I explain the installation of several addons with different needs and increasing difficulty using concrete examples:

Addon (licensed CC BY-NC by Giacomo)Addons without Any Native Code: Kano
There are some addons without any C source, e.g. CGI, Continued​Fraction, Rational and integrations like Bitly, Facebook, etc. All of these are included in the distribution. When looking for addons, I checked all addon repositories for ones without native code and found Docio, Eerie and Kano. I guess these were left out because they are part of Eerie. Let's look at Kano. Kano is a simple Make/​Rake inspired tool for Io. It uses a Kanofile to declare tasks. Let's get it running:
> cd "%IO_HOME%\lib\io\addons"
> git clone https://github.com/IoLanguage/kano
Cloning into 'kano'...
> io -e "Kano println"
Exception: Object does not respond to 'kano'
This is broken. io -e "<expression>" runs Io and passes the command, much like Ruby does. Passing the prototype name asks Io to load it and it is not found. By Io convention prototypes start with an uppercase letter while instances (and fields and variables) start with a lowercase one. Somewhere (in the source of Importer maybe) I read that the names must match for importing. Also this is one of only three repositories which lowercase name, i.e. docio, eerie and kano. Tip: Watch out for addon repository names matching the primary prototype.
> ren kano Kano
> io -e "Kano println"
Exception: unable to read file '...\lib\io\addons\Kano\depends'
Ah progress. It is missing the depends and protos files I mentioned earlier. It has a package.json instead:
{
  "version": 0.1,
  "author": "Josip Lisec",
  "description": "Rake-like utility for Io.",
  "readme": "README.textile",
  "category": "Utility",
  "dependencies": { },
  "protos": ["Kano", "Namespace", "Namespaces", "ObjectDescriber"]
}
No dependencies and four prototypes.
> touch Kano\depends
> echo Kano Namespace Namespaces ObjectDescriber > Kano\protos
> io -e "Kano println"
Exception: Unable to open directory ...\lib\io\addons\Kano\source
Progress again but why does Io look for C sources? In some addons, I see an empty source folder with a .gitisdumb file in it, to keep the folder in version control. Maybe it is needed.
> mkdir Kano\source
> io -e "Kano supportedFiles println"
list(make.io, Kanofile, kanofile, Kanofile.io, kanofile.io)
Nice, no error. Kano works. To be fully useable, there are a few more things to fix:
  1. Kano is a tool, it comes with bin/kano starter script. Each starter script needs a Windows version, i.e. a bin/kano.bat which calls the original starter script,
    io "%IO_HOME%\lib\io\addons\Kano\bin\kano" %*
    And both scripts need to be in the PATH. The easiest way is to copy kano.bat to %IO_HOME%\bin, which contains io.exe.

  2. Kano offers kano [-T|V|help|ns] [namespace:]taskName arg1 arg2... as help. -T lists all tasks defined in the local Kanofile and -V shows its version. At least it tries to do that. It calls Eerie to get its version. Now Eerie depends on Kano and Kano depends on Eerie, and I do not have Eerie, this is all bad. If you want everything to work, you can replace line 44 in Kano's Namespaces.io:
     V := option(
       """Prints Kano version."""
    -  version := Eerie Env named("_base") packageNamed("Kano") \
                        config at("meta") at("version")
    +  version := File thisSourceFile parentDirectory parentDirectory \
                       at("package.json") contents parseJson at("version")
       ("Kano v" .. version) println)
  3. Much later I noticed that Kano's package.json does not have a name field. This is needed for Docio to generate the documentation. Sigh. (Here is my patched Kano.)
Follow along in part two.

4 July 2024

Encapsulation vs Business Rules

Business Men (licensed CC BY-NC-ND by Andreina Schoeberlein)No Naked Primitives is a Coderetreat constraint which trains our object orientation skills. No primitive values, e.g. booleans, numbers or strings, must be visible at object boundaries, i.e. public methods. Arrays and other containers like lists or hash-tables are primitives, too. I love this constraint, as it pushes people right out of their comfort zone. ;-) (I wrote about No Naked Primitives in combination with other constraints and included it in the expert level Brutal Coding Constraints.)

Value Objects
The usual designs to avoid naked primitives are Value Objects and First Class Collections. Value Objects, by design, expose the values they wrap with a getter because some other objects will want to use these values. What happens if I go extreme and do not allow any primitives at object boundaries? (Of course this is crazy, a clear case of Primitive Obsession Obsession. Still when Coderetreat facilitators get together to practice, things end up like that.) Let us take the Game of Life as an example. (If you do not know the Game of Life, read the description and implement it right away.) In the game, for evolving a generation, I need to count the living neighbours of each cell. The number of living neighbours is an integer and its value object in C# could look like
public class NeighbourCount {
    private int count;
    
    public NeighbourCount(int count) {
        this.count = count;
    }

    // ... code to manage the count

}
Now any code which depends on the data (i.e. the count) will have to be moved into the value object to be able to access the data. Following the rules of the game, if there are two or three living neighbours, a living cell lives on. The method Apply​Rules​OnLiving​Cell implements this rule.
public class NeighbourCount {

    // ...

    public GridSpace ApplyRulesOnLivingCell() {
        if (this.count == 2 || this.count == 3) {
            return new AliveCell();   
        }
        return new EmptySpace();
    }
}

public interface GridSpace {}
public class EmptySpace : GridSpace {}
public class AliveCell : GridSpace {}
Grouping the data (count) and the logic which is based on the data, uses or modifies it (Apply​Rules​OnLiving​Cell) together is a core principle of object orientation. Further all data is strongly encapsulated.

Polymorphism
The next method Apply​Rules​OnEmpty​Space is similar. The decision which of the two methods to call depends on the state of the cell, which is either alive or dead/non existing. This boolean state has to be encapsulated inside a class, e.g. class GridSpace. This class behaves differently for the values of the boolean state, which makes the boolean a simple type code. The object oriented way to work with type codes is to use polymorphism:
public interface GridSpace {
    public GridSpace ApplyRulesWith(NeighbourCount count);
}
public class AliveCell : GridSpace {
    public GridSpace ApplyRulesWith(NeighbourCount count) {
        return count.ApplyRulesOnLivingCell();
    }
}
public class EmptySpace : GridSpace {
    public GridSpace ApplyRulesWith(NeighbourCount count) {
        return count.ApplyRulesOnEmptySpace();
    }
}
The code looks weird and it is not my usual implementation of the game's rules. It has an issue: The rules of the game are distributed among three classes. This is Shotgun Surgery - when a single change is made to multiple classes simultaneously: If I need to change the rules, or even want to read and understand the logic of cell evolution, I have to go to three places.

Shot (licensed CC BY-NC-ND by Bart Maguire)Business Rules
On the other hand, a basic implementation of the rules using primitives (e.g. in Ruby because polyglot programming is cool),
def alive_in_next_generation(alive, living_neighbours)
  (alive and living_neighbours == 2) or 
  living_neighbours == 3
end
is one line of code and easy to understand. The game's rules - the business rules - are boolean expressions describing certain situations, which "the business" needs to act on. Typical examples of such situations are when an item is out of stock or a client qualifies for a discount. Business related conditions are called policies. (And there are predicates, which are boolean expressions, too. These have their origins in formal logic.) Boolean expression are functional in nature. So a functional design, i.e. functions operating on primitive data, could be more appropriate. Even in object oriented design there are use cases for objects containing only logic and no (mutable) data.

Conclusion
What is the point of my discussion? In the case of Game of Life, there is a tension between keeping data and its logic together versus keeping related logic together. This is particularly true for boolean expressions and code depending on them, as boolean values usually end up in conditionals. I like to keep "decisions" and the logic depending on them close together but I want to keep my business rules in one place even more. I am wondering if this is true for most design situations, besides Game of Life. Boolean logic is interesting because if allows variation in the automation. Code without any booleans is still useful, e.g. pure calculations or uniform transformations in a pipeline style of operations.

Taking it further?
While boolean is a primitive, it is different from other primitives. What happens if I do not allow any primitives besides boolean at object boundaries? The data of class NeighbourCount would still be encapsulated when I add relevant queries (in Python because I love programming languages):
class NeighbourCount:

  def __init__(self, count):
    self._count = count

  # ... code to manage the count

  def isTwoOrThree(self):
    return self._count == 2 or self._count == 3

  def isThree(self):
    return self._count == 3
Using these small methods, I get a concise implementation of the rules,
class Rules:
  def cellInNextGeneration(self, cell, count):
    if (cell.isAlive() and count.isTwoOrThree()) or count.isThree():
      return AliveCell()
    return EmptySpace()
Is this better? I am not sure. At least the (business) rules of the Game of Life are in one place now. They could be replaced with different rules if needed, making the design extensible. At the same time different rules would most likely require different queries in NeighbourCount. For example in Hex Life, I need a weighted sum of first and second tier living neighbours to decide the state of the next generation. This is not possible without adding new queries to NeighbourCount. The Open Closed Principle is not satisfied. (Then maybe Hex Life is too much of a change for any design to "survive".) My rules logic keeps calling into the encapsulated value object repeatedly, which looks much like Feature Envy. I feel like I am going in circles here ;-)

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

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...