Getting started with CirKit development

This tutorial gives an introduction into the development of CirKit. The easiest way to organize new code is by means of add-ons. We create a new add-on with a custom command that will randomly rewrite an XMG. The API of CirKit is not focus of this tutorial, but rather to understand how to get an entry point into CirKit. (Check the demo command for some demonstration of the API.)

CirKit provides utility scripts in order to create new add-ons and new files easily. The directory structure for a new add-on can be created by calling from the CirKit root directory 

./utils/make_addon.py random

Here, random is the name of the new add-on. A new directory called cirkit-addon-random is created in the directory addons. We create a file for the implementation of the new function with another script: 

./utils/make_src_file.py classical/functions/xmg_random_rewrite random

Note, that the first argument is the path to the filename without the src/ in the beginning and without an extension in the end. Two files, a header and a source file, are created. The second parameter ensures that the files are created for the correct add-on. The third parameter is optional and can have a name of the file author. If not specified, the name is fetched from the user's git configuration.

The header file in addons/cirkit-addon-random/src/classical/functions/xmg_random_rewrite.hpp contains already some skeleton code and we extend it by a function definition as follows (all comments are omitted in the code): 

// xmg_random_rewrite.hpp
#ifndef XMG_RANDOM_REWRITE_HPP
#define XMG_RANDOM_REWRITE_HPP

#include <core/properties.hpp>
#include <classical/xmg/xmg.hpp>

namespace cirkit
{

xmg_graph xmg_random_rewrite( const xmg_graph& xmg,
                              const properties::ptr& settings = properties::ptr(),
                              const properties::ptr& statistics = properties::ptr() );

}

#endif

Note that we include parameters settings and statistics into the function definition, which are very typical for algorithms in CirKit. The variable settings is used to pass optional values from the caller to the algorithm, and the variable statistics is used to return statistical information from the algorithm to the caller.

Next, we add the code to the source file. The complete code is shown at once and then described in the following paragraphs. 

// xmg_random_rewrite.cpp
#include "xmg_random_rewrite.hpp"

#include <random>

#include <core/utils/timer.hpp>
#include <classical/xmg/xmg_rewrite.hpp>

namespace cirkit
{

xmg_graph xmg_random_rewrite( const xmg_graph& xmg,
                              const properties::ptr& settings,
                              const properties::ptr& statistics )
{
  // (1) parse settings
  const auto seed                = get( settings, "seed",              51966u );
  const auto replace_probability = get( settings, "replace_prability", 10u );

  // (2) write runtime information into statistics
  properties_timer t( statistics );

  // (3) create a roll dice function
  const auto dice = [seed, replace_probability]() {
    static std::default_random_engine gen( seed );
    static std::uniform_int_distribution<unsigned> dist( 0u, 100u );

    return dist( gen ) <= replace_probability;
  };

  // (4) how to rewrite MAJ and XOR gates
  maj_rewrite_func_t on_maj = [&dice]( xmg_graph& xmg_new,
                                       const xmg_function& a,
                                       const xmg_function& b,
                                       const xmg_function& c  ) {
    return dice() ? xmg_new.get_constant( false ) : xmg_new.create_maj( a, b, c );
  };

  xor_rewrite_func_t on_xor = [&dice]( xmg_graph& xmg_new,
                                       const xmg_function& a,
                                       const xmg_function& b  ) {
    return dice() ? xmg_new.get_constant( true ) : xmg_new.create_xor( a, b );
  };

  // (5) rewrite the XMG
  const auto xmg_tmp = xmg_rewrite_top_down( xmg, on_maj, on_xor );

  // (6) strash rewritten XMG to remove dangling nodes
  return xmg_strash( xmg_tmp );
}

}
  1. There are two settings: seed contains a random seed, and replace_probililty is a percentage to control the chance for which a node is replaced by a constant.
  2. We use the class properties_timer from (core/utils/timer.hpp) to store the run-time of the code into the statistics variable.
  3. We create a function dice that when being called returns either true with a probability according to replace_probability.
  4. Two functions on_maj and on_xor are defined, which are passed to xmg_rewrite_top_down and describes how to handle an MAJ gate and a XOR gate, respectively. It behaves as normal, unless the dice returns true; in that case, the node is replaced by a constant.
  5. The XMG is then rewritten using the function xmg_rewrite_top_down using a depth-first search traversal.
  6. Since the call to xmg_rewrite_top_down can lead to dangling nodes in the graph, we clean in up using xmg_strash.

We can compile the current code by calling 

make -C build cirkit_random

from CirKit's root directory. Next, we add a command called xmgrandrw that allows us to call the code from CirKit's command line interface. For that, we generate another header and source file using the utility script: 

./utils/make_src_file.py classical/cli/commands/xmgrandrw random

We add the following code to the header file: 

// xmgrandrw.hpp
#ifndef CLI_XMGRANDRW_COMMAND_HPP
#define CLI_XMGRANDRW_COMMAND_HPP

#include 

namespace cirkit
{

class xmgrandrw_command : public xmg_base_command
{
public:
  xmgrandrw_command( const environment::ptr& env );

  bool execute();

private:
  unsigned seed                = 51966u;
  unsigned replace_probability = 10u;
};

}

#endif

We define a command with a special base class xmg_base_command , which is designed for commands that expect an XMG as input. It is important that the class name is xmgrandrw_command to be used in later code that makes use of macros. Two methods need to be implemented, the constructor that will set up the arguments which can be passed to the command, and execute which executes the code and calls our algorithm. More details on how to write commands can be found in the abc_cli example program.

Next we implement both these methods in the source file: 

// xmgrandrw.cpp
#include "xmgrandrw.hpp"

#include <core/utils/program_options.hpp>
#include <classical/functions/xmg_random_rewrite.hpp>

namespace cirkit
{

xmgrandrw_command::xmgrandrw_command( const environment::ptr& env )
  : xmg_base_command( env, "Rewrite XMGs randomly" )
{
  opts.add_options()
    ( "seed,s",                value_with_default( &seed ),                "random seed" )
    ( "replace_probability,p", value_with_default( &replace_probability ), "replace probability (value from 0 to 100)" )
    ;
}

bool xmgrandrw_command::execute()
{
  const auto settings = make_settings();
  settings->set( "seed", seed );
  settings->set( "replace_prabibility", replace_probability );

  xmg() = xmg_random_rewrite( xmg(), settings, statistics );

  print_runtime();

  return true;
}

}

The constructor sets up two program options --seed (which can be abbreviated -s) and --replace_probability (which can be abbreviated -p). In the function execute the values of the options are fed into a settings variable and the algorithm is called. Note that there is a statistics variable, ready to use. A utility function is used to print the runtime from the statistics variable. The function should always return true.

We are almost done. Next, we create a last file in which we register the commands and pass them to CirKit. First create header and source files with 

./utils/make_src_file.py classical/cli/commands/random_commands random

And then delete the source file with (also refresh the build directory). This step is optional, but we do not need the source file. 

rm addons/cirkit-addon-random/src/classical/cli/commands/random_commands.cpp
cmake build

The header file looks as follows, and it is very important to keep the naming convention. 

// random_commands.hpp
#ifndef RANDOM_COMMANDS_HPP
#define RANDOM_COMMANDS_HPP

#include <classical/cli/commands/xmgrandrw.hpp>

namespace cirkit
{

#define CIRKIT_RANDOM_COMMANDS     \
  cli.set_category( "Rewriting" ); \
  ADD_COMMAND( xmgrandrw );

}

#endif

The macro name must be CIRKIT_ followed by the addon name in upper case letters, followed by _COMMANDS.

Finally, we need to tell the build system, that the addon has commands by adding the following two lines into the file addons/cirkit-addon-random/CMakeLists.txt: 

add_cirkit_library(
  NAME cirkit_random
  AUTO_DIRS src
  USE
    cirkit_classical
  INCLUDE
    PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}/src
  DEFINE
    PUBLIC ADDON_RANDOM
  COMMANDS
    classical/cli/commands/random_commands.hpp
)

That's it. We rebuild CirKit with 

make -C build cirkit

and then call it to try out the new command: 

cirkit> tt --maj 11
cirkit> tt > aig
cirkit> aig > xmg
cirkit> ps -x
[i]                   ex: i/o =      11 /       1  maj =     230  xor =       0  lev =   15
cirkit> xmgrandrw
[i] run-time: 0.00 secs
cirkit> ps -x
[i]                   ex: i/o =      11 /       1  maj =      72  xor =       0  lev =   14

The complete code for this add-on can be found at this repository.

Exercises

Here are some suggestions for exercises (with a difficulty estimation from 0–50) to extend the add-on.

  1. [15] Add a validity checker to xmgrandrw_command to ensure a valid value for replace_probability.
  2. [15] Write a log function for xmgrandrw_command that logs the values of both parameters and the runtime.
  3. [25] Change the initial value of the seed variable to be based on the current time.
  4. [35] Add a new command xmgrand that creates a random XMG.
  5. [40] Make the probability distribution depend on the size of the node's cone. That is, if a node has a large cone, then it should be less likely to be replaced by a constant.