Tuesday, July 22, 2014

Backing up Nix (and Hydra) builds

One of the worst things that may happen to any computer user is that filesystems get corrupted or that storage mediums, such as hard drives, break down. As a consequence, valuable data might get lost.

Likewise, this could happen to machines storing Nix package builds, such as a Hydra continuous build machine that exposes builds through its web interface to end users.

Reproducible deployment


One of the key features of the Nix package manager and its related sub projects is reproducible deployment -- using Nix expressions (which are basically recipes that describe how components are built from source code and its dependencies), we can construct all static components of which a system consists (such as software packages and configuration files).

Moreover, Nix ensures that all dependencies are present and correct, and removes many side effects while performing a build. As a result, producing the same configuration with the same set of expressions on a different machine should yield (nearly) a bit identical configuration.

So if we keep a backup of the Nix expressions stored elsewhere, such as a remote Git repository, we should (in theory) have enough materials to reproduce a previously deployed system configuration.

However, there are still a few inconveniences if you actually have to do this:

  • It takes time to rebuild and redownload everything. Some packages and system configurations might consists of hundreds or thousands of components taking many hours to complete.
  • The source tarballs may not be available from their original download locations anymore. I have encountered these situations quite a few times when I was trying to reproduce very old configurations. Some suppliers may decide to remove old releases after a while, or to move them to different remote locations, which requires me to search for them and to adapt very old Nix expressions, which I preferably don't want to do.
  • We also have to restore state which cannot be done by the Nix package manager. For example, if the Hydra database gets lost, we have to configure all projects, jobsets, user accounts and releases from scratch again, which is tedious and time consuming.

Getting the dependencies of packages


To alleviate the first two inconveniences, we must also backup the actual Nix packages belonging to a configuration including all their dependencies.

Since all packages deployed by the Nix package manager typically reside in a single Nix store folder (typically /nix/store), that may also contain junk and irrelevant stuff, we have to somehow select the packages that we consider relevant.

Binary deployments


In Nix, there are various ways to query specific dependencies of a package. When running the following query on the Nix store path of a build result, such as a Disnix, we can fetch all its runtime dependencies:

$ nix-store --query --requisites /nix/store/sh8025fhmz1wq27663bakmq915a2pf79-disnix-0.3pre1234
/nix/store/31kl46d8l4271f64q074bzi313hjmdmv-linux-headers-3.7.1
/nix/store/94n64qy99ja0vgbkf675nyk39g9b978n-glibc-2.19
...
/nix/store/hjbzw7s8wbvrf7mjjfkm1ah6fhnmyhzw-libxml2-2.9.1
/nix/store/hk8wdzs9s52iw9gnxbi1n9npdnvvibma-libxslt-1.1.28
/nix/store/kjlv4klmrarn87ffc5sjslcjfs75ci7a-getopt-1.1.4
/nix/store/sh8025fhmz1wq27663bakmq915a2pf79-disnix-0.3pre1234

What the above command does is listing the transitive Nix store path references that a package contains. In the above example, these paths correspond to the runtime dependencies of Disnix, since they are referenced from bash scripts, as well as the RPATH fields of the ELF binaries and prevent the executables to run properly if any of them is missing.

According to the nix-store manual page, the above closure refers to a binary deployment of a package, since it contains everything required to run it.

Source deployments


We can also run the same query on a store derivation file. While evaluating Nix expressions to build packages -- including its build-time dependencies --, a store derivation file is generated each time the derivation { } function is invoked.

Every Nix expression that builds something indirectly calls this function. The purpose of a derivation is composing environments in which builds are executed.

For example, if we run the previous query on a store derivation file:

$ nix-store --query --requisites /nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234.drv
...
/nix/store/4bj56z61q6qk69657bi0iqlmia7np5vc-bootstrap-tools.cpio.bz2.drv
...
/nix/store/4hlq4yvvszqjrwsc18awdvb0ppbcv920-libxml2-2.9.1.tar.gz.drv
/nix/store/g32zn0z6cz824vbj20k00qvj7i4arqy4-setup-hook.sh
/nix/store/n3l0x63zazksbdyp11s3yqa2kdng8ipb-libxml2-2.9.1.drv
/nix/store/nqc9vd5kmgihpp93pqlb245j71yghih4-libxslt-1.1.28.tar.gz.drv
/nix/store/zmkc3jcma77gy94ndza2f1y1rw670dzh-libxslt-1.1.28.drv
...
/nix/store/614h56k0dy8wjkncp0mdk5w69qp08mdp-disnix-tarball-0.3pre1234.drv
/nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234.drv

Then all transitive references to the store derivation files are shown, which correspond to all build-time dependencies of Disnix. According to the nix-store manual page the above closure refers to a source deployment of package, since the store derivations are low-level specifications allowing someone to build a package from source including all its build time dependencies.

Cached deployments


The previous query only returns the store derivation files. These files still need to be realised in order to get a build, that may take some time. We can also query all store derivation files and their corresponding build outputs, by running:

$ nix-store --query --requisites --include-outputs \
    /nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234.drv
...
/nix/store/zmkc3jcma77gy94ndza2f1y1rw670dzh-libxslt-1.1.28.drv
...
/nix/store/hk8wdzs9s52iw9gnxbi1n9npdnvvibma-libxslt-1.1.28
...
/nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234.drv

The above command only includes the realised store paths that have been built before. By adding the --force-realise parameter to the previous command-line instruction, we can force all outputs of the derivations to be built.

According to the nix-store manual page, the above closure refers to a cached deployment of a package.

Backing up Nix components


Besides querying the relevant Nix store components that we intend to backup, we also have to store them elsewhere. In most cases, we cannot just simply copy the Nix store paths to another location and copy it back into the Nix store at some later point:

  • Some backup locations may use more primitive filesystems than Linux (and other UNIX-like systems). For example, we require filesystem features, such as symlinks and read, write and executable bits.
  • We also require necessary meta-information to allow it to be imported into the Nix store, such as the set of references to other paths.

For these reasons, it is recommendable to use nix-store --export, that serializes a collection of Nix store paths into a single file including their meta-information. For example, the following command-line instruction serializes a cached deployment closure of Disnix:

$ nix-store --export $(nix-store --query --requisites --include-outputs \
    /nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234.drv) > disnix-cached.closure

The resulting closure file (disnix-cached.closure) can easily be stored on many kinds of mediums, such as an external harddrive using a FAT32 filesystem. We can import the the closure file into another Nix store by running:

$ nix-store --import < disnix-cached.closure

The above command imports Disnix including all its dependencies into the Nix store. If any dependencies are already in the Nix store, then they are skipped. If any dependency appears to be missing, it returns an error. All these properties can be verified because the serialization contains all the required meta-information.

Storing backups of a collection of Nix components efficiently


In principle, the export and import nix-store operations should be sufficient to make reliable backups of any Nix package. However, the approach I described has two drawbacks:

  • For each package, we serialize the entire closure of dependencies. Although this approach is reliable, it is also inefficient if we want to backup multiple packages at the same time. Typically, many packages share the same common set of dependencies. As a consequence, each backup contains many redundant packages wasting a lot of precious disk space.
  • If we change a package's source code, such as Disnix, and rebuild it, we have to re-export the entire closure again, while many of the dependencies of remain the same. This makes the backup process time considerably longer than necessary.

To fix these inefficiencies, we need an approach that stores serializations of each Nix store path individually, so that we can check which paths have been backed up already and which still need to be serialized. Although we could implement such an approach ourselves, there is already a Nix utility that does something similar, namely: nix-push.

Normally, this command is used to optimize the build times of source builds by making binary substitutes available that can be downloaded instead, but it turns out to be quite practical for making backups as well.

If I run the following instruction on a collection of Nix store paths:

$ nix-push --dest /home/sander/cache /nix/store/4h4mb7lb5c0g390bd33k658dgzahkjn7-disnix-0.3pre1234

A binary cache is created in the /home/sander/cache directory from the closure of the Disnix package. The resulting binary cache has the following structure:

$ ls /home/sander/cache
03qpb8b4j4kc1w3fvwg9f8igc4skfsgj9rqb3maql9pi0nh6aj47.nar.xz
053yi53qigf113xsw7n0lg6fsvd2j1mapl6byiaf9vy80a821irk.nar.xz
05vfk68jlgj9yqd9nh1kak4rig379s09.narinfo
06sx7428fasd5bpcq5jlczx258xhfkaqqk84dx2i0z7di53j1sfa.nar.xz
...
11wcp606w07yh8afgnidqvpd1q3vyha7ns6dhgdi2354j84xysy9.nar.xz
...
4h4mb7lb5c0g390bd33k658dgzahkjn7.narinfo
...

For each Nix store path of the closure, an xz compressed NAR file is generated (it is also possible to use bzip2 or no compression) that contains a serialization of an individual Nix store path (without meta-information) and a narinfo file that contains its corresponding meta-information. The prefix of the NAR file corresponds to its output hash while the prefix of the narinfo file corresponds to the hash component of the Nix store path. The latter file contains a reference to the former NAR file.

If, for example, we change Disnix and run the same nix-push command again, then only the paths that have not been serialized are processed while the existing ones remain untouched, saving redundant diskspace and backup time.

We can also run nix-push on a store derivation file. If a store derivation file is provided, a binary cache is generated from the cached deployment closure.

Restoring a package from a binary cache can be done as follows:

$ nix-store --option binary-caches file:///home/sander/cache \
    --realise /nix/store/3icf7dxf3inky441ps1dl22aijhimbxl-disnix-0.3pre1234

Simply realizing a Nix store path while providing the location to the binary cache as a parameter causes it to download the substitute into the Nix store, including all its dependencies.

Creating releases on Hydra for backup purposes


How can this approach be applied to Hydra builds? Since Hydra stores many generations of builds (unless they are garbage collected), I typically make a selection of the ones that I consider important enough by adding them to a release.

Releases on Hydra are created as follows. First, you have to be logged in and you must select a project from the project overview page, such as Disnix:


Clicking on a project will redirect you to a page that shows you the corresponding jobsets. By unfolding the actions tab, you can create a release for that particular project:


Then a screen will be opened that allows you define a release name and description:


After the release has been created, you can add builds to it. Builds can be added by opening the jobs page and selecting build results, such as build.x86_64-linux:


After clicking on a job, we can add it to a release by unfolding the 'Actions' tab and selecting 'Add to release':


The following dialog allows us to add the build to our recently created: disnix-0.3 release:


When we open the 'Releases' tab of the project page and we select the disnix-0.3 release, we can see that the build has been added:


Manually adding individual builds is a bit tedious if you have many them. Hydra has the ability to add all jobs of an evaluation to a release in one click. The only prerequisite is that each build must tell Hydra (through a file that resides in $out/nix-support/hydra-release-name of the build result) to which release it should belong.

For me adapting builds is a bit inconvenient and I also don't need the ability to add builds to arbitrary releases. Instead, I have created a script that adds all builds of an evaluation to a single precreated release, which does not require me to adapt anything.

For example running:

$ hydra-release-eval config.json 3 "disnix-0.3" "Disnix 0.3"

Automatically creates a release with name: disnix-0.3 and description: "Disnix 0.3", and adds all the successful builds of evaluation 3 to it.

Exporting Hydra releases


To backup Hydra releases, I have created a Perl script that takes a JSON configuration file as parameter that looks as follows:

{
  "dbiConnection": "dbi:Pg:dbname=hydra;host=localhost;user=hydra;",
  
  "outDir": "/home/sander/hydrabackup",
  
  "releases": [
    {
      "project": "Disnix",
      "name": "disnix-0.3",
      "method": "binary"
    },
  ]
}

The configuration file defines an object with three members:

  • dbiConnection contains the Perl DBI connection string that connects to Hydra's PostgreSQL database instance.
  • outDir refers to a path in which the binary cache and other backup files will be stored. This path could refer to (for example) the mount point of another partition or network drive.
  • releases is an array of objects defining which releases must be exported. The method field determines the deployment type of the closure that needs to be serialized, which can be either a binary or cache deployment.

By running the following command, I can backup the releases:

$ hydra-backup config.json

The above command creates two folders: /home/sander/hydrabackup/cache contains the binary cache generated by nix-pull using the corresponding store derivation files or outputs of each job. The /home/sander/hydrabackup/releases folder contains text files with the actual paths belonging to the closures of each release.

The backup approach (using a binary cache) also allows me to update the releases and to efficiently make new backups. For example, by changing the disnix-0.3 release and running the same command again, only new paths are being exported.

One of the things that may happen after updating releases is that some NAR and narinfo files have become obsolete. I have also created a script that takes care of removing them automatically. What it basically does is comparing the release's closure files with the contents of the binary cache and removing the files that are not defined in any of the closure files. It can be invoked as follows:

$ hydra-collect-backup-garbage config.json

Restoring Hydra releases on a different machine can be done by copying the /home/sander/hydrabackup folder to a different machine and by running:

$ hydra-restore config.json

Backing up the Hydra database


In addition to releases, we may want to keep the Hydra database so that we don't have to reconfigure all projects, jobsets, releases and user accounts after a crash. A dump of the database can be created, by running:

$ pg_dump hydra | xz > /home/sander/hydrabackup/hydra-20140722.pgsql.xz

And we can restore it by running the following command:

$ xzcat /home/sander/hydrabackup/hydra-20140722.pgsql.xz | psql hydra

Conclusion


In this blog post, I have described an approach that allows someone to fully backup Nix (and Hydra) builds. Although it may feel great to have the ability to do so, it also comes with a price -- closures consume a lot of disk space, since every closure contains all transitive dependencies that are required to run or build it. In some upgrade scenarios, none of the dependencies can be shared which is quite costly.

In many cases it would be more beneficial to only backup the Nix expressions and Hydra database, and redo the builds with the latest versions of the dependencies, unless there is really a good reason to exactly reproduce an older configuration.

Furthermore, I am not the only person who has investigated Hydra backups. The Hydra distribution includes a backup script named: hydra-s3-backup-collect-garbage that automatically stores relevant artifacts in an Amazon S3 bucket. However, I have no clue how to use it and what it's capabilities are. Moreover, I am an old fashioned guy who still wants store backups on physical mediums rather than in the cloud. :).

The scripts described in this blog post can be obtained from my Github page. If other people consider any these scripts useful, I might reserve some time to investigate whether they can be included in the Hydra distribution package.

Sunday, June 1, 2014

Porting GNU Autotools projects to Visual C++ projects (unconventional style)

Not so long ago, I have ported my IFF experiments' sub projects to SDL 2.0. Besides moving to SDL 2.0, I did some additional development work. One of the interesting things that I did was porting these sub projects to Visual C++ to make them work under Windows natively.

The main reason why I did this, is because I have received numerous feature requests for Visual C++ support in the past. Finally, I found a bit of time to actually do it. :-)

In general, the porting process was straight forward, but nonetheless I encountered a few annoyances. Moreover, since I have a research background in software deployment, I also want to make this deployment process manageable using my favourite deployment tools.

In this blog post, I will describe the porting steps I have done using my own "unconventional" style.

Generating projects


The first thing I did was turning relevant units of each package into Visual C++ projects so that they can be actually built with Visual C++. Typically, a Visual Studio project produces one single binary artifact, such as a library or executable.


Visual Studio 2013 has a very useful feature that composes solutions out of existing source directories automatically. It can be invoking by opening Visual Studio, and selecting 'File' -> 'New' -> 'Project From Existing Code...' from the menu bar.

For example, for the libiff package, I created three projects. One library project that builds libiff and two projects that produce executables: iffpp and iffjoin. To compose a project out of the src/libiff sub directory, I provided the following settings to the import wizard:

  • What type of project would you like to create? Visual C++
  • Project file location: D:\cygwin64\home\Sander\Development\libiff\src\libiff
  • Project name: libiff
  • How do you want to build the project? Use Visual Studio
  • Project type: Dynamically linked library (DLL) project

For the remaining projects (the command-line utilities), I used Console application project as a project type.

Configuring project dependencies


After generating solutions for all relevant units of each package, I have configured their dependencies so that they can be built correctly.

The first aspect is to get the dependencies right between projects in a package. For example, the libiff package builds two executables: iffpp and iffjoin which both have a common dependency on the libiff shared library. The solutions I just generated from the sub directories, have no knowledge about any of its dependencies yet.


To set the inter-project dependencies, I composed a new empty solution, through 'File' -> 'New' -> 'Project' and then by picking 'Blank Solution' under 'Other project types'. In this blank solution, I have added all the projects of the package that I have generated previously.

After adding the projects to the solution, I can configure their dependency relationships. This is done by right clicking on each project and selecting the 'Build dependencies' -> 'Project dependencies...'. I used this dialog to make libiff a project dependency of iffpp and iffjoin.

After setting up a common solution for all the package's sub projects, I can delete the individual solution files for each project, since they are no longer needed.

Configuring library dependencies


Besides getting the dependencies among projects right, executables must also be linked against dynamic libraries that are either produced by other projects in the solution or by other means (e.g. in a different solution or prebuilt). In order to configure these dependencies, we have to change the project settings:

  • To link an executable to a dynamic library, we must right click on the corresponding project, select 'Properties', and pick the option 'Configuration Properties' -> 'Linker' -> 'Input'. In the configuration screen, we must add the name of the export library (a *.LIB file) to the 'Additional Dependencies' field.
  • We must also specify where the export libraries can be found. The library search directories can be configure by selecting 'Configuration Properties' -> 'Linker' -> 'General' in the properties screen and adapting the 'Additional Library Directories' field by adding its corresponding path.
  • Projects using shared libraries typically also have to find their required header files. The paths to these files can be configured by picking the option 'Configuration Properties' -> 'C/C++' -> 'General'. The required paths must be added to the 'Additional Include Directories' property.

It is a bit tricky to specify some of these paths in a "portable" way. Fortunately, there were a couple very useful macros that I was able to use, such as: $(OutDir) to refer to the output directory of the solution.

To refer to external libraries that do not reside in the solution (such as SDL 2.0), I defined my own custom properties and manually added them to the Visual C++ project files. For example, to allow a project to find SDL 2.0, I added the following lines to SDL_ILBM's project file:

<PropertyGroup>
  <SDL2IncludePath>..\..\..\SDL2-2.0.3\include</SDL2IncludePath>
  <SDL2LibPath>..\..\..\SDL2-2.0.3\lib\x86</SDL2LibPath>
</PropertyGroup>

I can refer to the properties with the following macros: $(SDL2IncludePath), $(SDL2LibPath) from the 'Additional Includes' and 'Additional Library Directories' fields. Moreover, these properties can also be overridden by the build infrastructure, which is very useful as we will see later.

Building export libraries


Another thing I observed is that in Visual C++, you need export libraries (*.LIB files) in order to be able to link a dynamic library to something else. However, if no exports are defined in a library project, then this file is not generated.

The most common way to export functions is probably by annotating headers and class definitions, but I don't find this very elegant for my project, since it requires me to adapt the source code and add non-standard pieces to it.

Another way is creating a Module-Definition File (*.DEF file) and adding it to the project that builds a library. A module definition file can be added to a project by right clicking on it, picking 'Add new item...', and selecting 'Visual C++' -> 'Code' -> 'Module-Defintion File (.def)'.


Creating this module definition file is straight forward. I investigated all headers files of the library to see what functions need to be accessible. Then I created a module definition file that looks as follows:

LIBRARY    libiff
EXPORTS
    IFF_readFd  @1
    IFF_read    @2
    IFF_writeFd @3
    IFF_write   @4
    IFF_free    @5
    IFF_check   @6
    IFF_print   @7
    IFF_compare @8

The above file basically lists the names of all publically accessible functions with a unique numeric id. These steps were enough for me to get an export library built.

Porting the command-line interfaces


Another porting issue was getting the command-line interfaces to work. This is actually the only "non-standard" piece of code of the IFF sub projects and depends on getopt() or getopt_long(), which is not part of Visual C++'s standard runtime. Furthermore, getopt-style parameters are a bit weird for Windows command line utilities.

I have decided to create a replacement command-line interface for Windows, that follows Windows console application conventions for command line parameters. For example on Unix-like platforms we can request the help text of iffpp as follows:

$ iffpp -h

On windows the same option can be requested as follows:

$ iffpp /?

As can be observed, we use Windows-style command-line parameters.

Automating build processes


The last aspect I had to take care of is getting the entire build process of all the sub projects automated. People who know me, know that I have a preference for Nix-related tools, for various reasons (check the link for the exact reasons).

Like .NET software, Visual C++ projects can be built from the command-line with MSBuild. Fortunately, I have already created a Nix function that invokes MSBuild to compile C# projects some time ago.

I have not used Nix on Cygwin for a while, and Nix's Cygwin support seemed to be broken, so I had to revive it. Fortunately, the changes were relatively minor. Moreover, the .NET build function still seemed to work after reviving Cygwin support.

To support building Visual C++ projects, I basically had to make two changes to the function that I have used for Visual C# projects. First, I had to set the following environment variable:

$ export SYSTEMDRIVE="C:"

Without this environment variable set, the compiler complains that paths are not well formed.

The second thing is to make the parameters to MSBuild configurable through an environment variable named msBuildOpts:

$ MSBuild.exe ... $msBuildOpts

The reason why I have added this feature, is because I want to make the properties that refer to external libraries (such as SDL 2.0 through the $(SDL2IncludePath) and $(SDL2LibPath) macros) configurable so that they can refer to dependencies that reside in the Nix store.

With these changes, I can write a Nix expression for any IFF file format experiment project. I used the following partial expression to build SDL_ILBM with Visual C++:

with import <nixpkgs> {};

let
  SDL2devel = stdenv.mkDerivation {
    name = "SDL2-devel-2.0.3";
    src = fetchurl {
      url = http://www.libsdl.org/release/SDL2-devel-2.0.3-VC.zip;
      sha256 = "0q6fs678i59xycjlw7blp949dl0p2f1y914prpbs1cspz98x3pld";
    };
    buildInputs = [ unzip ];
    installPhase = ''
      mkdir -p $out
      mv * $out
    '';
    dontStrip = true;
  }; 
in
dotnetenv.buildSolution {
  name = "SDL_ILBM";
  src = ./.;
  baseDir = "src";
  slnFile = "SDL_ILBM.sln";
  preBuild = ''
    ...
    export msBuildOpts="$msBuildOpts /p:SDL2IncludePath=\"$(cygpath --windows ${SDL2devel}/include)\""
    export msBuildOpts="$msBuildOpts /p:SDL2LibPath=\"$(cygpath --windows ${SDL2devel}/lib/x86)\""
  '';
}

The above expression builds the SDL_ILBM solution that resides in the src/ folder of the package. It uses the msBuildOpts variable to pass the override the properties that we have defined earlier to pass the paths of the external projects to the build, such as SDL 2.0. It uses the cygpath command to translate UNIX paths to Windows paths so that they can be used with MSBuild.

By running the following command-line instruction:

$ nix-build sdlilbm.nix

SDL_ILBM including all its dependencies are automatically downloaded and built by Nix and stored in the Nix store.

Conclusion


By performing all the steps described in the blog post, I was able to port all my IFF file format experiment sub projects to Visual C++, which I can also automatically build with the Nix package manager to make the deployment process convenient and repeatable.

The following screenshots may show some interesting results to you:


Availability


The updated IFF projects can be obtained from my GitHub page. Moreover, if you want to use Nix to build Visual C++ projects on Cygwin, then you need to use my personal forks of Nix and Nixpkgs, which contain Cygwin specific fixes. I may push these changes upstream if others are interested in it and I consider them stable enough.

Sunday, May 18, 2014

Rendering 8-bit palettized surfaces in SDL 2.0 applications

Recently, I have ported SDL_ILBM to SDL 2.0, since it's out there for a while now. SDL 2.0 has many improvements over SDL 1.2 and is typically a better fit for modern hardware.

The majority of the porting activities were quite straight forward, thanks to the SDL 1.2 to 2.0 migration guide. What impacted SDL_ILBM were the following:

  • SDL 2.0 supports multiple windows, so we have to create (and discard) them in a slightly different way in the viewer app.
  • There is a more advanced graphics rendering pipeline in SDL 2.0 that uses hardware acceleration (e.g. through OpenGL or Direct3D) where possible.

Properly supporting the latter aspect puzzled me a bit, because the migration guide did not clearly describe what the best way is to continuously render 8-bit palettized surfaces for every frame.

SDL_ILBM generates these kind of surfaces for the majority of ILBM images by default (images using the HAM viewport mode are notable exceptions, because they typically contain more than 256 distinct colors). I need to update these surfaces for every frame to support animated cycle ranges.

In this blog post, I will describe what I did to support this, because I couldn't find any hands on information about this elsewhere and I think this information might be helpful to others as well.

Rendering surfaces using SDL 1.2


In the old implementation using SDL 1.2, the viewer application basically did the following: It first parses an IFF file, then extracts the ILBM images from it and finally composes SDL_Surface instances from the ILBM images that are shown to the user. Then the application enters a main loop which responds to user's input and continuously updates what is being displayed in the window.

Expressing this in very simplified code, it looks as follows. First, we obtain an SDL_Surface that contains the represents an ILBM image that we want to display:

SDL_Surface *pictureSurface;

When using the default options, it produces a 8-bit palettized surface, unless you try to open an image using the HAM viewport setting.

Then we construct a window that displays the image. One of the options of the viewer is to make the dimensions of the window equal to the dimensions of the image:

SDL_Surface *windowSurface = SDL_SetVideoMode(pictureSurface->w,
    pictureSurface->h,
    32,
    SDL_HWSURFACE | SDL_DOUBLEBUF);

Besides constructing a window, SDL_SetVideoMode() also returns an SDL surface representing the graphics that are displayed in the window. The SDL_HWSURFACE parameter is used to tell SDL that the pixel data should reside in hardware memory (video RAM) instead of software memory (ordinary RAM), which the picture surface uses.

Eventually we reach the main loop of the program that responds to user events (e.g. keyboard presses), updates the pixels in the picture surface when cycling mode is turned on and flips the logical and physical screen buffers so that the changes become visible:

while(TRUE)
{
    /* Process events */

    /* Modify the pixels of pictureSurface */

    /* Blit picture surface on the window */
    SDL_BlitSurface(pictureSurface, NULL, windowSurface, NULL);

    /* Update the screen */
    SDL_Flip(windowSurface);
}

After changing the palette and/or the pixels in the picture surface, we can simply use SDL_BlitSurface() to make the modified surface visible in the window surface. This function also converts the pixels into the format of the target surface automatically, which means that it should work for both 8-bit palettized surfaces as well as RGBA surfaces.

Rendering surfaces using SDL 2.0


Since SDL 2.0 has a more advanced graphics rendering pipeline, there are more steps that we need to perform. Constructing the same window with the same dimensions in SDL 2.0 must be done as follows:

SDL_Window *sdlWindow = SDL_CreateWindow("ILBM picture",
    SDL_WINDOWPOS_UNDEFINED,
    SDL_WINDOWPOS_UNDEFINED,
    pictureSurface->w, pictureSurface->h,
    0);

Besides a window, we must also construct a renderer instance, that renders textures on the window:

SDL_Renderer *renderer = SDL_CreateRenderer(sdlWindow, -1, 0);

The renderer is capable of automatically scaling a texture to the window's dimensions if needed. The following instructions configure the renderer's dimensions and instruct it to use linear scaling:

SDL_SetHint(SDL_HINT_RENDER_SCALE_QUALITY, "linear");
SDL_RenderSetLogicalSize(sdlRenderer,
    pictureSurface->w, pictureSurface->h);

In SDL 2.0, a texture is basically a pixel surface that resides in hardware memory while an 'ordinary' surface resides in software memory. In SDL 1.2 both were SDL surfaces with a different flag parameter.

The previous steps were quite easy. However, while I was trying to port the main loop to SDL 2.0 I was a bit puzzled. In order to show something in the window, we must ensure that the pixels are in hardware memory (i.e. in the texture). However, we do not have direct access to a texture's pixels. One of the solutions that the migration guide suggests is to convert a surface (that resides in software memory) to a texture:

SDL_Texture *texture = SDL_CreateTextureFromSurface(renderer, surface);

The above function invocation creates a texture out of the surface and performs all necessary steps to do it, such as allocating memory for the texture and converting chunky pixels to RGBA pixels.

Although this function seems to do everything we need, it has two drawbacks. It allocates memory for the texture which we have to free ourselves over and over again, while we know that the texture always has the same size. Second, the resulting texture is a static texture and its pixels can only be modified through SDL_UpdateTexture(), which is also a slow operation. Therefore, it is not recommended to run it to render every frame.

A faster alternative (according to the migration guide) is to use a streaming texture:

SDL_Texture *texture = SDL_CreateTexture(renderer,
    SDL_PIXELFORMAT_RGBA8888,
    SDL_TEXTUREACCESS_STREAMING,
    pictureSurface->w,
    pictureSurface->h);

However, we cannot construct textures that store its pixels in chunky format, so we have to convert them from the surface's format to the texture's format. After studying the SDL documentation a bit, I stumbled upon SDL_ConvertPixels(), but that did not seem to work with the picture surface, because the function cannot convert surfaces with an indexed palette.

I ended up implementing the main loop as follows:

/* Construct a surface that's in a format close to the texture */
SDL_Surface *windowSurface = SDL_CreateRGBSurface(0,
    pictureSurface->w, pictureSurface->h,
    32, 0, 0, 0, 0);

void *pixels;
int pitch;

while(TRUE)
{
    /* Process events */

    /* Modify the pixels of pictureSurface */

    /*
     * Blit 8-bit palette surface onto the window surface that's
     * closer to the texture's format
     */
    SDL_BlitSurface(pictureSurface, NULL, windowSurface, NULL);

    /* Modify the texture's pixels */
    SDL_LockTexture(texture, NULL, &pixels, &pitch);
    SDL_ConvertPixels(windowSurface->w, windowSurface->h,
        windowSurface->format->format,
        windowSurface->pixels, windowSurface->pitch,
        SDL_PIXELFORMAT_RGBA8888,
        pixels, pitch);
    SDL_UnlockTexture(texture);
    
    /* Make the modified texture visible by rendering it */
    SDL_RenderCopy(renderer, texture, NULL, NULL);
}

I introduced another SDL surface (windowSurface) that uses a format closer to the texture's format (RGBA pixels) so that we can do the actual conversion with SDL_ConvertPixels(). After modifying the pixels in the 8-bit palettized surface (pictureSurface), we blit it to the window surface, which automatically converts the pixels to RGBA format. Then we use the window surface to convert the pixels to the texture's format, and finally we render the texture to make it visible to end users.

This seems to do the trick for me and this is the result:


Moreover, if I enable cycling mode the bird and bunny also seem to animate smoothly.

Conclusion


In this blog post I have described my challenges of porting SDL_ILBM from SDL 1.2 to SDL 2.0. To be able to modify the pixels and the palette of an 8-bit palettized surface for every frame, I used a second surface that has a format closer to the texture's format, allowing me to easily convert and transfer those pixels to a streaming texture.

This approach may also be useful for porting classic 8-bit graphics games to SDL 2.0.

Moreover, besides SDL_ILBM, I also ported SDL_8SVX to SDL 2.0, which did not require any modifications in the code. Both packages can be obtained from my GitHub page.

Tuesday, April 1, 2014

Asynchronous package management with NiJS

Last week, I have implemented some additional features in NiJS: an internal DSL for Nix in JavaScript. One of its new features is an alternative formalism to write package specifications and some use cases.

Synchronous package definitions


Traditionally, a package in NiJS can be specified in JavaScript as follows:

var nijs = require('nijs');

exports.pkg = function(args) {
  return args.stdenv().mkDerivation ({
    name : "file-5.11",
    
    src : args.fetchurl()({
      url : new nijs.NixURL("ftp://ftp.astron.com/pub/file/file-5.11.tar.gz"),
      sha256 : "c70ae29a28c0585f541d5916fc3248c3e91baa481f63d7ccec53d1534cbcc9b7"
    }),
    
    buildInputs : [ args.zlib() ],
    
    meta : {
      description : "A program that shows the type of files",
      homepage : new nijs.NixURL("http://darwinsys.com/file")
    }
  });
};

The above CommonJS module exports a function which specifies a build recipe for a package named file, that uses zlib as a dependency and executes the standard GNU Autotools build procedure (i.e. ./configure; make; make install) to build it.

The above module specifies how to build a package, but not which versions or variants of the dependencies that should be used. The following CommonJS module specifies how to compose packages:

var pkgs = {

  stdenv : function() {
    return require('./pkgs/stdenv.js').pkg;
  },

  fetchurl : function() {
    return require('./pkgs/fetchurl').pkg({
      stdenv : pkgs.stdenv
    });
  },

  zlib : function() {
    return require('./pkgs/zlib.js').pkg({
      stdenv : pkgs.stdenv,
      fetchurl : pkgs.fetchurl
    });
  },
  
  file : function() {
    return require('./pkgs/file.js').pkg({
      stdenv : pkgs.stdenv,
      fetchurl : pkgs.fetchurl,
      zlib : pkgs.zlib
    });
  }
}

export.pkgs = pkgs;

As can be seen, the above module includes the previous package specification and provides all its required parameters (such as a variant of the zlib library that we need). Moreover, all its dependencies are composed in the above module as well.

Asynchronous package definitions


The previous modules are synchronous package definitions, meaning that once they are being evaluated nothing else can be done. In the latest version of NiJS, we can also write asynchronous package definitions:

var nijs = require('nijs');
var slasp = require('slasp');

exports.pkg = function(args, callback) {
  var src;
  
  slasp.sequence([
    function(callback) {
      args.fetchurl()({
        url : new nijs.NixURL("ftp://ftp.astron.com/pub/file/file-5.11.tar.gz"),
        sha256 : "c70ae29a28c0585f541d5916fc3248c3e91baa481f63d7ccec53d1534cbcc9b7"
      }, callback);
    },
    
    function(callback, _src) {
      src = _src;
      args.zlib(callback);
    },
    
    function(callback, zlib) {
      args.stdenv().mkDerivation ({
        name : "file-5.11",
        src : src,
        buildInputs : [ zlib ],
    
        meta : {
          description : "A program that shows the type of files",
          homepage : new nijs.NixURL("http://darwinsys.com/file")
        }
      }, callback);
    }
  ], callback);
};

The above module defines exactly the same package as shown earlier, but defines it asynchronously. For example, it does not return, but uses a callback function to pass the evaluation result back to the caller. I have used the slasp library to flatten its structure to make it better readable and maintainable.

Moreover, because packages implement an asynchronous function interface, we also have to define the composition module in a slightly different way:

var pkgs = {

  stdenv : function(callback) {
    return require('./pkgs-async/stdenv.js').pkg;
  },
   
  fetchurl : function(callback) {
    return require('./pkgs-async/fetchurl').pkg({
      stdenv : pkgs.stdenv
    }, callback);
  },
  
  zlib : function(callback) {
    return require('./pkgs-async/zlib.js').pkg({
      stdenv : pkgs.stdenv,
      fetchurl : pkgs.fetchurl
    }, callback);
  },
  
  file : function(callback) {
    return require('./pkgs-async/file.js').pkg({
      stdenv : pkgs.stdenv,
      fetchurl : pkgs.fetchurl,
      zlib : pkgs.zlib
    }, callback);
  }
}

exports.pkgs = pkgs;

Again, this composition module has the same meaning as the one showed earlier, but each object member implements an asynchronous function interface having a callback.

So why are these asynchronous package specifications useful? In NiJS, there are two use cases for them. The first use case is to compile them to Nix expressions and build them with the Nix package manager (which can also be done with synchronous package definitions):

$ nijs-build pkgs-async.js -A file --async
/nix/store/c7zy6w6ls3mfmr9mvzz3jjaarikrwwrz-file-5.11

The only minor difference is that in order to use asynchronous package definitions, we have to pass the --async parameter to the nijs-build command so that they are properly recognized.

The second (and new!) use case is to execute the functions directly with NiJS. For example, we can also use the same composition module to do the following:

$ nijs-execute pkgs-async.js -A file
/home/sander/.nijs/store/file-5.11

When executing the above command, the Nix package manager is not used at all. Instead, NiJS directly executes the build function implementing the corresponding package and all its dependencies. All resulting artifacts are stored in a so-called NiJS store, which resides in the user's home directory, e.g.: /home/sander/.nijs/store.

The latter command does not depend on Nix at all making it possible for NiJS to act as an independent package manager, yet having the most important features that Nix also has.

Implementation


The implementation of nijs-execute is straight forward. Every package directly or indirectly invokes the same function that actually executes a build operation: args.stdenv().mkDerivation(args, callback).

The original implementation for nijs-build (that compiles a JavaScript composition module to a Nix expression) looks as follows:

var nijs = require('nijs');

exports.pkg = {
  mkDerivation : function(args, callback) {
    callback(null, new nijs.NixExpression("pkgs.stdenv.mkDerivation "
        +nijs.jsToNix(args)));
  }
};

To make nijs-execute work, we can simply replace the above implementation with the following:

var nijs = require('nijs');

exports.pkg = {
  mkDerivation : function(args, callback) {
      nijs.evaluateDerivation(args, callback);
  }
};

We replace the generated Nix expression that invokes Nixpkgs' stdenv.mkDerivation {} by a direct invocation to nijs.evaluateDerivation() that executes a build directly.

The evaluateDerivation() translates the first parameter object (representing build parameters) to environment variables. Each key corresponds to an environment variable and each value is translated as follows:

  • A null value is translated to an empty string
  • true translates to "1" and false translates to an empty string.
  • A string, number, or xml object are translated to strings literally.
  • Objects that are instances of the NixFile and NixURL prototypes are also translated to strings literally.
  • Objects instances of the NixInlineJS prototype are converted into a separate builder script, which gets executed by the default builder.
  • Objects instances of the NixRecursiveAttrSet prototype and arbitrary objects are considered derivations that need to be evaluated separately.

Furthermore, evaluateDerivation() invokes a generic builder script with similar features as the one in Nixpkgs:

  • All environment variables are cleared or set to dummy values, such as HOME=/homeless-shelter.
  • It supports the execution of phases. By default, it runs the following phases: unpack, patch, configure, build, install and can be extended with custom ones.
  • By default, it executes a GNU Autotools build procedure: ./configure; make; make install with configurable settings (that have a default fallback value).
  • It can also take custom build commands so that a custom build procedure can be performed
  • It supports build hooks so that the appropriate environment variables are set when providing a buildInputs parameter. By default, the builder automatically sets PATH, C_INCLUDE_PATH and LIBRARY_PATH environment variables. Build hooks can be used to support other languages and environments' settings, such as Python (e.g. PYTHONPATH) and Node.js (e.g. NODE_PATH)

Discussion


Now that NiJS has the ability to act as an independent package manager in addition to serving the purpose of an internal DSL, means that we can deprecate Nix and its sub projects soon and use Nix (for the time being) as a fallback for things that are not supported by NiJS yet.

NiJS has the following advantages over Nix and its sub projects:

  • I have discovered that the Nix expression language is complicated and difficult to learn. Like Haskell, it has a solid theoretical foundation and powerful features (such as laziness), but it's too hard to learn by developers without an academic background.

    Moreover, I had some difficulties accepting JavaScript in the past, but after discovering how to deal with prototypes and asynchronous programming, I started to appreciate it and really love it now.

    JavaScript has all the functional programming abilities that we need, so why should we implement our own language to accomplish the same? Furthermore, many people have proven that JavaScript is the future and we can attract more users if we use a language that more people are familiar with.
  • NiJS also prevents some confusion with a future Linux distribution that is going to be built around it. For most people, it is too hard to make a distinction between Nix and NixOS.

    With NiJS this is not a problem -- NiJS is supposed to be pronounced in Dutch as: "Nice". The future Linux distribution that will be built around it will be called: "NiJSOS", which should be pronounced as "Nice O-S" in Dutch. This is much easier to remember.
  • Same thing holds for Disnix -- Nix sounds like "Nothing" in Dutch and Disnix sounds like: "This is nothing!". This strange similarity has prevented me to properly spread the word to the masses. However "DisniJS" sounds like "This is nice!" which (obviously) sounds much better and is much easier to remember.
  • NiJS also makes continuous integration more scalable than Nix. We can finally get rid of all the annoying Perl code (and the Template Toolkit) in Hydra and reimplement it in Node.js using all its powerful frameworks. Since in Node.js all I/O operations are non-blocking, we can make Hydra even more faster and more scalable.

Conclusion


In this blog post, I have shown that we can also specify packages asynchronously in NiJS. Asynchronous package specifications can be built directly with NiJS, without requiring them to be compiled to Nix expressions that must be built with Nix.

Since NiJS has become an independent package manager and JavaScript is the future, we can deprecate Nix (and its sub projects) soon, since NiJS has significant advantages over Nix.

NiJS can be downloaded from my GitHub page and from NPM. NiJS can also bootstrap itself :-)

Moreover, soon I will create a website, set up mailing lists, create an IRC channel, and define the other sub projects that can be built on top of it.

Follow up


UPDATE: It seems that this blog post has attracted quite a bit of attention today. For example, there has been some discussion about it on the Nix mailing list as well as the GNU Guix mailing list. Apparently, I also made a few people upset :-)

Moreover, a lot readers probably did not notice the publishing date! So let me make it clear:

IT'S APRIL FOOLS' DAY!!!!!!!!!!!!!!!

The second thing you may probably wonder is: what exactly is this "joke" supposed to mean?

In fact, NiJS is not a fake package -- it actually does exists, can be installed through Nix and NPM, and is really capable of doing the stuff described in this blog post (as well the two previous ones).

However, the intention to make NiJS a replacement for Nix was a joke! As a matter of fact, I am a proponent of external DSLs and Nix already does what I need!

Furthermore, only 1% of NiJS' features are actually used by me. For the rest, the whole package is just simply a toy, which I created to explore the abilities of internal DSLs and to explore some "what if" scenarios, no matter how silly they would look :-)

Although NiJS can build packages without reliance on Nix, its mechanisms are extremely primitive! The new feature described in this blog post was basically a silly experiment to develop a JavaScript specification that can be both compiled (to Nix) and interpreted (executed by NiJS directly)!

Moreover, the last few years I have heard a lot of funny, silly, and stupid things, about all kinds of aspects related to Nix, NixOS, Disnix and Node.js which I kept in mind. I (sort of) integrated these things into a story and used a bit of sarcasm as a glue! What these things exactly are is an open exercise for the reader :-).

Tuesday, March 25, 2014

Structured asynchronous programming (Asynchronous programming with JavaScript part 3)

A while ago, I explained that JavaScript execution environments, such as a web browser or Node.js, do not support multitasking. Such environments have a single event loop and when JavaScript code is being executed, nothing else can be done. As a result, it might (temporarily or indefinitely) block the browser or prevent a server from handling incoming connections.

In order to execute multiple tasks concurrently, typically events are generated (such as ticks or timeouts), the execution of the program is stopped so that the event loop can process events, and eventually execution is resumed by invoking the callback function attached to an event. This model works as long as implementers properly "cooperate".

One of its undesired side effects is that code is much harder to structure due to the extensive use of callback functions. Many solutions have been developed to cope with this. In my previous blog posts I have covered the async library and promises as possible solutions.

However, after reading a few articles on the web, some discussion, and some thinking, I came to the observation that asynchronous programming, that is: programming in environments in which executions have to be voluntarily interrupted and resumed between statements and -- as a consequence -- cannot immediately deliver their results within the same code block, is an entirely different programming world.

To me, one of the most challenging parts of programming (regardless of what languages and tools are being used) is being able to decompose and translate problems into units that can be programmed using concepts of a programming language.

In an asynchronous programming world, you have unlearn most of the concepts that are common in the synchronous programming world (to which JavaScript essentially belongs in my opinion) and replace them by different ones.

Are callbacks our new generation's "GOTO statement"?


When I think about unlearning programming language concepts: A classic (and very famous) example that comes into my mind is the "GOTO statement". In fact, a few other programmers using JavaScript claim that the usage of callbacks in JavaScript (and other programming languages as well) are our new generation's "GOTO statement".

Edsger Dijkstra said in his famous essay titled: "A case against the GO TO statement" (published as "Go To Statement Considered Harmful" in the March 1968 issue of the "Communications of the ACM") the following about it:

I become convinced that the go to statement should be abolished from all "higher level" programming languages (i.e. everything except -perhaps- plain machine code)

As a consequence, nearly every modern programming language used these days, lack the GOTO statement and people generally consider it a bad practice to use it. But I have the impression that most of us seem to have forgotten why.

To re-explain Dijkstra's essay a bit in my own words: it was mainly about getting programs correctly implemented by construction. He briefly refers to three mental aids programmers can use (which he explains in more detail in his manuscript titled: "Notes on Structured Programming") namely: enumeration, mathematical induction, and abstraction:

  • The first mental aid: enumeration, is useful to determine the correctness of a code block executing sequential and conditional (e.g. if-then-else or switch) statements.

    Basically, it is about stepping through each statement sequentially and reason whether for each step whether some invariant holds. You could address each step independently with what he describes: "a single textual index".
  • The second mental aid: mathematical induction, comes in handy when working with (recursive) procedures and loops (e.g. while and doWhile loops).

    In his manuscript, he shows that validity of a particular invariant can be proved by looking at the basis (first step of an iteration) first and then generalize the proof to all successive steps.

    For these kinds of proofs, a single textual index no longer suffices to address each step. However, using an additional dynamic index that represents each successive procedure call or iteration step still allows one to uniquely address them. The previous index and this second (dynamic) index constitutes something that he calls "an independent coordinate system".
  • Finally, abstraction (i.e. encapsulating common operations into a procedure) is useful in many ways to me. One of the things Dijkstra said about this is that somebody basically just have to think about "what it does", disregarding "how it works".

The advantage of "an independent coordinate system" is that the value of a variable can be interpreted only with respect to the progress of the process. According to Dijkstra, using the "GOTO statement" makes it quite hard (though not impossible) to define a set of meaningful set of such coordinates, making it harder to reason about correctness and not to make your program a mess.

So what are these coordinates really about you may wonder? Initially, they sound a bit abstract to me, but after some thinking, I have noticed that the way execution/error traces are presented in commonly used programming language these days (e.g. when capturing an exception or using a debugger) use a coordinate system like that IMHO.

These traces have coordinates with two dimensions -- the first dimension is the name of the text file and the corresponding line number that we are currently at (assuming that each line contains a single statement). The second dimension is the stack of function invocations, each showing their corresponding location in the corresponding text files. It also makes sense to me that adding the effects of GOTOs (even when marking each of them with an individual number) to such traces is not helpful, because there could be so many of them that these traces become unreadable.

However, when using structured programming concepts (as described in his manuscript), such as the sequential decomposition, alteration (e.g. if-then-else and switch), and repetition (e.g. while-do, and repeat-until) the first two mental aids can be effectively used to proof validity, mainly because the structure of the program at runtime stays quite close to its static representation.

JavaScript language constructs


Like many other conventional programming languages that are in use these days, the JavaScript programming language supports structured programming language concepts, as well as a couple of other concepts, such as functional programming and object oriented programming through prototypes. Moreover, JavaScript lacks the goto statement.

JavaScript has been originally "designed" to work in a synchronous world, which makes we wonder: what are the effects of using JavaScript's language concepts in an asynchronous world? And are the implications of these effects similar to the effects of using GOTO statements?

Function definitions


The most basic thing one can do in a language such as JavaScript is executing statements, such as variable assignments or function invocations. This is already something that changes when moving from a synchronous world to an asynchronous world. For example, take the following trivial synchronous function definition that simply prints some text on the console:

function printOnConsole(value) {
    console.log(value);
}

When moving to an asynchronous world, we may want to interrupt the execution of the function (yes I know it is not a very meaningful example for this particular case, but anyway):

function printOnConsole(value, callback) {
    process.nextTick(function() {
        console.log(value);
        callback();
    });
}

Because we generate a tick event first when calling the function and then stop the execution, the function returns immediately without doing its work. The callback, that is invoked later, will do it instead.

As a consequence, we do not know when the execution is finished by merely looking when a function returns. Instead, a callback function (provided as a function parameter) can be used, that gets invoked once the work has been done. This is the reason why JavaScript functions in an asynchronous world use callbacks.

As a sidenote: I have seen some people claiming that merely changing the function interface to have a callback, makes their code asynchronous. This is absolutely not true. Code becomes asynchronous if it interrupts and resumes its execution. The callback interface is simply a consequence of providing an equivalent for the return statement that has lost its relevance in an asynchronous world.

Same thing holds for functions that return values, such as the following that translates one numerical digit into a word:

function generateWord(num) {
    var words = [ "zero", "one", "two", "three", "four",
        "five", "six", "seven", "eight", "nine" ];
    return words[num];
}

In asynchronous world, we have to use a callback to pass its result to the caller:

function generateWord(digit, callback) {
    var words;
    process.nextTick(function() {
        words = [ "zero", "one", "two", "three", "four", "five",
            "six", "seven", "eight", "nine" ];
        callback(words[num]);
    });
}

Sequential decomposition


The fact that function interfaces have become different and function invocations have to be done differently, affects all other programming language concepts in JavaScript.

Let's take the simplest structured programming concept: the sequence. Consider the following synchronous code fragment executing a collection of statements in sequential order:

var a = 1;
var b = a + 1;
var number = generateWord(b);
printOnConsole(number); // two

To me it looks straight forward to use enumerative reasoning to conclude that the output shown in the console will be "two".

As explained earlier, in an asynchronous world, we have to pass callback functions as parameters to know when they return. As a consequence, each successive statement has to be executed within the corresponding callback. If we do this in a dumb way, we probably end up writing:

var a = 1;
var b = a + 1;

generateWord(b, function(result) {
    var number = result;
    printOnConsole(number, function() {
        
    }); // two
});

As can be observed in the above code fragment, we end up one indentation level deeper every time we invoke a function, turning the code fragment into pyramid code.

Pyramid code is nasty in many ways. For example, it affects maintenance, because it has become harder to change the order of two statements. It has also become hard to add a statement, say, in the beginning of the code block, because it requires us to refactor all the successive statements. It also becomes a bit harder to read the code because of the nesting and indentation.

However, it also makes me wonder this whether pyramid code is a "new GOTO"? I would say no, because I think we still have not lost our ability to address statements through a "single textual index" and the ability to use enumerative reasoning.

We could also say that the fact that we invoke callback functions for each function invocation introduces the second dynamic index, but on the other hand, we know that a given callback is only called by the same caller, so we can discard that second index because of that.

My conclusion is that we still have enumerative reasoning abilities when implementing a sequence. However, the overhead of each enumeration step is (in my opinion) bigger because we have to keep the indentation and callback nesting into account.

Fortunately, I can create an abstraction to clean up this pyramid code:

function runStatement(stmts, index, callback, result) {
    if(index >= stmts.length) {
        if(typeof callback == "function")
            callback(result);
    } else {
        stmts[index](function(result) {
            runStatement(stmts, index + 1, callback, result);
        }, result);
    }
}

function sequence(stmts, callback) {
    runStatement(stmts, 0, callback, undefined);
}

The above function: sequence() takes an array of functions each requiring a callback as parameter. Each function represents a statement. Moreover, since the abstraction is an asynchronous function itself, we also have to use a callback parameter to notify the caller when it has finished. I can refactor the earlier asynchronous code fragment into the following:

var a;
var b;
var number;

slasp.sequence([
    function(callback) {
        a = 1;
        callback();
    },

    function(callback) {
        b = a + 1;
        callback();
    },
    
    function(callback) {
        generateWord(b, callback);
    },
    
    function(callback, result) {
        number = result;
        printOnConsole(number); // two
    }
]);

By using the sequence() function, we have eliminated all pyramid code, because we can indent the statements on the same level. Moreover, we can also maintain it better, because we do not have to fix the indentation and callback nesting each time we insert or move a statement.

Alteration


The usage of alteration constructs is also slightly different in an asynchronous world. Consider the following example that basically checks whether some variable contains my first name and lets the user know whether this is the case or not:

function checkMe(name) {
    return name == "Sander"
}
    
var name = "Sander";
    
if(checkMe(name)) {
    printOnConsole("It's me!");
    printOnConsole("Isn't it awesome?");
} else {
    printOnConsole("It's someone else!");
}

(As you may probably notice, I intentionally captured the conditional expression in a function, soon it will become clear why).

Again, I think that it will be straight forward to use enumerative reasoning to conclude that the output will be:

It's me!
Isn't it awesome?

When moving to an asynchronous world (which changes the signature of the checkMe() to have a callback) things become a bit more complicated:

function checkMe(name, callback) {
    process.nextTick(function() {
        callback(name == "Sander");
    });
}

var name = "Sander";

checkMe(name, function(result) {
    if(result) {
        printOnConsole("It's me!", function() {
            printOnConsole("Isn't it awesome?");
        });
    } else {
        printOnConsole("It's someone else!");
    }
});

We can no longer evaluate the conditional expression within the if-clause. Instead, we have to evaluate it earlier, then use the callback to retrieve the result and use that to evaluate the if conditional expression.

Although it is a bit inconvenient not being able to directly evaluate a conditional expression, again I still do not think this affect the ability to use enumeration for similar reasons as the sequential decomposition. The above code fragment basically just adds an additional sequential step, nothing more. So in my opinion, we still have not encountered a new GOTO.

Fortunately, I can also create an abstraction for the above pattern:

function when(conditionFun, thenFun, elseFun, callback) {
    sequence([
        function(callback) {
            conditionFun(callback);
        },
        
        function(callback, result) {
            if(result) {
                thenFun(callback);
            } else {
                if(typeof elseFun == "function")
                    elseFun(callback);
                else
                    callback();
            }
        }
    ], callback);
}

and use this function to express the if-statement as follows:

slasp.when(function(callback) {
    checkMe(name, callback);
}, function(callback) {
    slasp.sequence([
        function(callback) {
            printOnConsole("It's me!", callback);
        },
        
        function(callback) {
            printOnConsole("Isn't it awesome?", callback);
        }
    ], callback);
}, function(callback) {
    printOnConsole("It's someone else!", callback);
});

Now I can embed a conditional expression in my artificial when statement.

Same thing applies to the other alteration construct in JavaScript: the switch statement -- you also cannot evaluate a conditional expression directly if it invokes an asynchronous function invocation. However, I can also make an abstraction (which I have called circuit) to cope with that.

Repetition


How are the repetition constructs (e.g. while and do-while) affected in an asynchronous world? Consider the following example implementing a while loop:

function checkTreshold() {
    return (approx.toString().substring(0, 7) != "3.14159");
}

var approx = 0;
var denominator = 1;
var sign = 1;

while(checkTreshold()) {
    approx += 4 * sign / denominator;
    printOnConsole("Current approximation is: "+approx);
        
    denominator += 2;
    sign *= -1;
}

The synchronous code fragment shown above implements the Gregory-Leibniz formula to approximate pi up to 5 decimal places. To reason about its correctness, we have to use both enumeration and mathematical induction. First, we reason that the first two components of the series are correct, then we can use induction to reason that each successive component of the series is correct, e.g. they have an alternating sign, and a denominator increases with 2 for each successive step.

If we move to an asynchronous world, we have a couple of problems, beyond those that are described earlier. First, repetition blocks the event loop for an unknown amount of time so we must interrupt it. Second, if we interrupt a loop, we cannot resume it with a callback. Therefore, we must write our asynchronous equivalent of the previous code as follows:

function checkTreshold(callback) {
    process.nextTick(function() {
        callback(approx.toString().substring(0, 7) != "3.14159");
    });
}

var approx = 0;
var denominator = 1;
var sign = 1;

(function iteration(callback) {
    checkTreshold(function(result) {
        if(result) {
            approx += 4 * sign / denominator;
            printOnConsole("Current approximation is: "+approx, function() {
                denominator += 2;
                sign *= -1;
                setImmediate(function() {
                    iteration(callback);
                });
            });
        }
    });
})();

In the above code fragment, I have refactored the code into a recursive algorithm. Moreover, for each iteration step, I use setImmediate() to generate an event (I cannot use process.nextTick() in Node.js because it skips processing certain kinds of events) and I suspend the execution. The corresponding callback starts the next iteration step.

So is this implication the new GOTO? I would still say no! Even though we were forced to discard the while construct and use recursion instead, we can still use mathematical induction to reason about its correctness, although certain statements are wrapped in callbacks that make things a bit uglier and harder to maintain.

Luckily, I can also capture the above pattern in an abstraction:

function whilst(conditionFun, statementFun, callback) {
    when(conditionFun, function() {
        sequence([
            statementFun,
            
            function() {
                setImmediate(function() {
                    whilst(conditionFun, statementFun, callback);
                });
            }
        ], callback);
    }, callback);
}

The above function (called: whilst) takes three functions as parameters: the first parameter takes a function returning (through a callback) a boolean that represents the conditional expression, the second parameter takes a function that has to be executed for each iteration, and the third parameter is a callback that gets invoked if the repetition has finished.

Using the whilst() function, I can rewrite the earlier example as follows:

var approx = 0;
var denominator = 1;
var sign = 1;

slasp.whilst(checkTreshold, function(callback) {
    slasp.sequence([
        function(callback) {
            approx += 4 * sign / denominator;
            callback();
        },
        
        function(callback) {
            printOnConsole("Current approximation is: "+approx, callback);
        },
        
        function(callback) {
            denominator += 2;
            callback();
        },
        
        function(callback) {
            sign *= -1;
            callback();
        }
    ], callback);
});

The same thing that we have encountered also holds for the other repetition constructs in JavaScript. doWhile is almost the same, but we have to evaluate the conditional expression at the end of each iteration step. We can refactor a for and for-in loop as a while loop, thus the same applies to these constructs as well. For all these constructs I have developed corresponding asynchronous abstractions: doWhilst, from and fromEach.

Exceptions


With all the work done so far, I could already conclude that moving from a synchronous to an asynchronous world (using callbacks) results in a couple of nasty issues, but these issues are definitely not the new GOTO. However, a common extension to structured programming is the use of exceptions, which JavaScript also supports.

What if we expand our earlier example with the generateWord() function to throw an exception if a parameter is given that is not a single positive digit?

function generateWord(num) {
    if(num < 0 || num > 9) {
        throw "Cannot convert "+num+" into a word";
    } else {
        var words = [ "zero", "one", "two", "three", "four", "five",
            "six", "seven", "eight", "nine" ];
        return words[num];
    }
}

try {
    var word = generateWord(1);
    printOnConsole("We have a: "+word);
    word = generateWord(10);
    printOnConsole("We have a: "+word);
} catch(err) {
    printOnConsole("Some exception occurred: "+err);
} finally {
    printOnConsole("Bye bye!");
}

The above code also captures a possible exception and always prints "Bye bye!" on the console regardless of the outcome.

The problem with exceptions in an asynchronous world is basically the same as with the return statement. We cannot just catch an exception because it may not have been thrown yet. So instead of throwing and catching exception, we must simulate them. This is commonly done in Node.js by a introducing another callback parameter called err (that is the first parameter of callback) that is not null if some error has been thrown.

Changing the above function definition to throw errors using this callback parameter is straight forward:

function generateWord(num, callback) {
    var words;
    process.nextTick(function() {
        if(num < 0 || num > 9) {
            callback("Cannot convert "+num+" into a word");
        } else {
            words = [ "zero", "one", "two", "three", "four", "five",
                "six", "seven", "eight", "nine" ];
            callback(null, words[num]);
        }
    });
}

However simulating the effects of a throw, and the catch and finally clauses is not straight forward. I am not going to much into the details (and it's probably best to just just briefly skim over the next code fragment), but this is what I basically what I ended up writing (which is still partially incomplete):

generateWord(1, function(err, result) {
    if(err) {
        printOnConsole("Some exception occured: "+err, function(err) {
            if(err) {
                // ...
            } else {
                printOnConsole("Bye bye!");
            }
        });
    } else {
        var word = result;
        printOnConsole("We have a: "+word, function(err) {
            if(err) {
                printOnConsole("Some exception occurred: "+err, function(err) {
                    if(err) {
                        // ...
                    } else {
                        printOnConsole("Bye bye!");
                    }
                });
            } else {
                generateWord(10, function(err, result) {
                    if(err) {
                        printOnConsole("Some exception occurred: "+err, function(err) {
                            if(err) {
                                // ...
                            } else {
                                printOnConsole("Bye bye!");
                            }
                        });
                    } else {
                        word = result;
                        printOnConsole("We have a: "+word, function(err) {
                            if(err) {
                                printOnConsole("Some exception occurred: "+err, function(err) {
                                    if(err) {
                                        // ...
                                    } else {
                                        printOnConsole("Bye bye!");
                                    }
                                });
                            } else {
                                // ...
                            }
                        });
                     }
                });
            }
        });
    }
});

As you may notice, now the code clearly blows up and you also see lots of repetition because of the fact that we need to simulate the effects of the throw and finally clauses.

To create an abstraction to cope with exceptions, we must adapt all the abstraction functions that I have shown previously to evaluate the err callback parameters. If the err parameter is set to something, we must stop the execution and propagate the err parameter to its callback.

Moreover, I can also define a function abstraction named: attempt, to simulate a try-catch-finally block:

function attempt(statementFun, captureFun, lastlyFun) {
    statementFun(function(err) {
        if(err) {
            if(typeof lastlyFun != "function")
                lastlyFun = function() {};
                    
            captureFun(err, lastlyFun);
        } else {
            if(typeof lastlyFun == "function")
                lastlyFun();
        }
    });
}

and I can rewrite the mess shown earlier as follows:

slasp.attempt(function(callback) {
    slasp.sequence([
        function(callback) {
            generateWord(1, callback);
        },
        
        function(callback, result) {
            word = result;
            printOnConsole("We have a: "+word, callback);
        },
        
        function(callback) {
            generateWord(10, callback);
        },
        
        function(callback, result) {
            word = result;
            printOnConsole("We have a: "+word);
        }
        
    ], callback);
}, function(err, callback) {
    printOnConsole("Some exception occured: "+err, callback);
}, function() {
    printOnConsole("Bye bye!");
});

Objects


Another extension in JavaScript is the ability to construct objects having prototypes. In JavaScript constructors are functions as well as object methods. I think the same applies to these kind of functions just as regular ones -- they cannot return values immediately because they may not have finished their execution yet.

Consider the following example:

function Rectangle(width, height) {
    this.width = width;
    this.height = height;
}

Rectangle.prototype.calculateArea = function() {
    return this.width * this.height;
};

var r = new Rectangle(2, 2);

printOnConsole("Area is: "+r.calculateArea());

The above code fragment simulates a Rectangle class, constructs a rectangle having a width and height of 2, and calculates and displays its area.

When moving to an asynchronous world, we have to take into account all things we did previously. I ended up writing:

function Rectangle(self, width, height, callback) {
    process.nextTick(function() {
        self.width = width;
        self.height = height;
        callback(null);
    });
}

Rectangle.prototype.calculateArea = function(callback) {
    var self = this;
    process.nextTick(function() {
        callback(null, self.width * self.height);
    });
};

function RectangleCons(width, height, callback) {
    function F() {};
    F.prototype = Rectangle.prototype;
    var self = new F();
    Rectangle(self, width, height, function(err) {
        if(err)
            callback(err);
        else
            callback(null, self);
    });
}

RectangleCons(2, 2, function(err, result) {
    var r = result;
    r.calculateArea(function(err, result) {
        printOnConsole("Area is: "+result);
    });
});

As can be observed, all functions -- except for the constructor -- have an interface including a callback.

The reason that I had to do something different for the constructor is that functions that are called in conjunction with new cannot propagate this back to the caller without including weird internal properties. Therefore, I had to create a "constructor wrapper" (named: RectangleCons) that first constructs an empty object with the right prototype. After the empty object has been constructed, I invoke the real constructor doing the initialisation work.

Furthermore, the this keyword only works properly within the scope of the constructor function. Therefore, I had to use a helper variable called self to make the properties of this available in the scope of the callbacks.

Writing a "wrapper constructor" is something we ideally do not want to write ourselves. Therefore, I created an abstraction for this:

function novel() {
    var args = Array.prototype.slice.call(arguments, 0);
    
    var constructorFun = args.shift();
    function F() {};
    F.prototype = constructorFun.prototype;
    F.prototype.constructor = constructorFun;
    
    var self = new F();
    args.unshift(self);
    
    var callback = args[args.length - 1];
    args[args.length - 1] = function(err, result) {
        if(err)
            callback(err);
        else
            callback(null, self);
        };
    
        constructorFun.apply(null, args);
    }
}

And using this abstraction, I can rewrite the code as follows:

function Rectangle(self, width, height, callback) {
    process.nextTick(function() {
        self.width = width;
        self.height = height;
        callback(null);
    });
}

Rectangle.prototype.calculateArea = function(callback) {
    var self = this;
    process.nextTick(function() {
        callback(null, self.width * self.height);
    });
};

slasp.novel(Rectangle, 2, 2, function(err, result) {
    var r = result;
    r.calculateArea(function(err, result) {
        printOnConsole("Area is: "+result);
    });
});

When using novel() instead of new, we can conveniently construct objects asynchronously.

As a sidenote: if you want to use simulated class inheritance, you can still use my inherit() function that takes two constructor functions as parameters described in an earlier blog post. They should also work with "asynchronous" constructors.

Discussion


In this blog post, I have shown that in an asynchronous world, functions have to be defined and used differently. As a consequence, most of JavaScript's language constructs are either unusable or have to be used in a different way. So basically, we have to forget about most common concepts that we normally intend to use in a synchronous world, and learn different ones.

The following table summarizes the synchronous programming language concepts and their asynchronous counterparts for which I have directly and indirectly derived patterns or abstractions:

Concept Synchronous Asynchronous
Function interface
function f(a) { ... }
function f(a, callback) { ... }
Return statement
return val;
callback(null, val);
Sequence
a; b; ...
slasp.sequence([
    function(callback) {
        a(callback);
    },
    
    function(callback) {
        b(callback);
    }
    ...
]);
if-then-else
if(condFun())
    thenFun();
else
    elseFun();
slasp.when(condFun,
    thenFun,
    elseFun);
switch
switch(condFun()) {
    case "a":
        funA();
        break;
    case "b":
        funB();
        break;
    ...
}
slasp.circuit(condFun,
    function(result, callback) {
        switch(result) {
            case "a":
                funA(callback);
                break;
            case "b":
                funB(callback);
                break;
            ...
        }
    });
Recursion
function fun() { fun(); }
function fun(callback) {
    setImmediate(function() {
        fun(callback); 
    });
}
while
while(condFun()) {
    stmtFun();
}
slasp.whilst(condFun, stmtFun);
doWhile
do {
    stmtFun();
} while(condFun());
slasp.doWhilst(stmtFun, condFun);
for
for(startFun();
    condFun();
    stepFun()
) {
    stmtFun();
} 
slasp.from(startFun,
    condFun,
    stepFun,
    stmtFun);
for-in
for(var a in arrFun()) {
    stmtFun();
} 
slasp.fromEach(arrFun,
    function(a, callback) {
        stmtFun(callback);
    });
throw
throw err;
callback(err);
try-catch-finally
try {
    funA();
} catch(err) {
    funErr();
} finally {
    funFinally();
}
slasp.attempt(funA,
    function(err, callback) {
        funErr(callback);
    },
    funFinally);
constructor
function Cons(a) {
    this.a = a;
}
function Cons(self, a, callback) {
    self.a = a;
    callback(null);
}
new
new Cons(a);
slasp.novel(Cons, a, callback);

To answer the question whether callbacks are the new GOTO: my conclusion is that they are not the new GOTO. Although they have drawbacks, such as the fact that it becomes harder to read, maintain and adapt code, it does not affect our ability to use enumeration or mathematical induction.

However, if we start using exceptions, then things become way more difficult. Then developing abstractions is unavoidable, but this has nothing to do with callbacks. Simulating exception behaviour in general makes things complicated, which is fueled by the nasty side effects of callbacks.

Another funny observation is that it has become quite common to use JavaScript for asynchronous programming. Since it has been developed for synchronous programming, means that most its constructs are useless. Fortunately, we can cope with that by implementing useful abstractions ourselves (or through third party libraries), but it would be better IMHO that a programming language has the all relevant facilities that are suitable for the domain in which it is going to be used.

Conclusion


In this blog post, I have explained that when moving from a synchronous to an asynchronous world requires forgetting certain programming language concepts and use different asynchronous equivalents.

I have made a JavaScript library out of the abstractions in this blog post (yep, that is yet another abstraction library!), because I think they might come in handy at some point. It is named slasp (SugarLess Asynchronous Structured Programming), because it implements abstractions that are close to the bare bones of JavaScript. It provides no sugar, such as borrowing abstractions from functional programming languages and so on, which most other libraries do.

The library can be obtained from my GitHub page and through NPM and used under the terms and conditions of the MIT license.