Better poly than sorry!

Extending Io to add tuple unpacking (aka destructuring bind)

NOTE: As usual, all the code is on GitHub
NOTE: You can learn more about Io from its home page and its GitHub repository.

What is Io? A quick review

Io is a programming language, obviously, created in the early 2000's by Steve Dekorte. It was featured in the original Seven Languages in Seven Weeks [1] book, which is how I learned of its existence. It's a general purpose, interpreted language, with semantics inspired by Smalltalk, Self and Lisp, and with look and feel reminiscent of TCL and Scheme.

While TCL tries to answer the question what can be done with just strings (and lists) and Scheme shows what happens when everything is a lambda (and an s‑exp), Io explores the consequences of assuming that everything is an object (and a message). They all share traits of conceptual purity and elegant minimalism of their designs and implementations. It would be a mistake, however, to think about them simply as works of art - this may come as a surprise to the uninitiated, but despite the simplicity (some would say, because of it) all these languages are mind-bendingly expressive and powerful. It's true that you need to change the way you approach problems to use their full power - but once you do, you will quickly realize that that power is over 9000!

Even though I speak about simplicity, Io is a fairly complete and usable high-level language. Its strongest superpower is probably its dynamism: nearly everything, everywhere, every time is inspectable and changeable from within the language. As for other features, from Smalltalk (and Ruby) it takes its purely object-oriented character, while Self and Lua inspired some of its object system, which is prototypal (you probably know this style of OO from JS) and with multiple inheritance. It has very simple syntax, which is customizable with incredibly powerful meta-programming tools.

Non-blocking, asynchronous Input/Output and concurrency support (with co-routines) are important parts of the language (see example on the left) - it even provides automatic deadlock detection. It has relatively simple C API for both embedding and extension and built-in CFFI for wrapping C libraries.

There are of course some disadvantages and problems: for example, Io is not very performant at this point[2] and should not be used for number-crunching (unless it can be vectorized[3]) or other performance-critical code. On the other hand, it works well even for writing bigger, complex programs which are IO-bound - all kinds of servers and (micro)services come to mind.

Another thing is that it isn't very popular currently (to put it mildly), which means the selection of ready to use libraries is narrower than with more mainstream languages. There are use-cases where it doesn't matter, though, like when embedding it as a scripting language for larger programs. It could also be used as BASH replacement for more complex scripting.

The problem, the hack and its effects

I picked Io because it seemed a good fit for one of my projects. When starting it, I considered various languages, but, taking all the requirements into consideration, only a couple were viable: LPC, Pike, Lua and Io. The process of eliminating all the other languages deserves its own post, but for now, let's focus on the winner, Io.

One way or another, my project evolved and at some point I decided that I need a ported implementation of PyParsing[5], in Io. After defining some helper methods it was an easy job, with nearly one-to-one correspondence between lines of code in both languages. This is important, because in that case it's easy to convert between the languages with a set of simple regexes ran over the lines in a file. Io incredible expressivness allowed it to emulate most of Python features used in the library - with a glaring exception of tuple unpacking, also known as destructuring bind or (a weak version of) pattern matching.

As a quick reminder, tuple unpacking is a feature of an assignment operator in Python (and many others), which is used to extract elements from a sequence and giving each of them a name. It looks like this in Python:

  def some_fun():
      some_tuple = (1, 2, 3)
      (one, two, three) = some_tuple
      assert one == 1 and two == 2 and three == 3

It's very convenient, especially if you keep most of the data in tuples of a known length, which is how most of PyParsing is written. As mentioned, it's also missing from Io, which made the translation process more tedious than it could be.

It was a surprising omission on Io part, considering that the language already gives you ways of defining custom operators, including assignment operators. To simplify the porting of Python code (and for fun, obviously!), I decided to try defining a <- operator, that would implement the semantics of destructuring bind. In more specific terms, I wanted to extend Io so that the following code is valid and gives expected results:

  someMethod := method(object,
      object := Object clone
      object [one, two, three] <- [1, 2, 3]
      assert(object one = 1, object two = 2, object three = 3)

It should be possible to do this, thanks to the mentioned features of Io: its extensible parser, which allows you to define new operators, and the lazy, on-demand, evaluation of method arguments. Actually, the code for doing so is hilariously simple, just a couple of lines of code[6]:

  Object destructure := method(
      # target [a, b] <- list(9,8) becomes: target a := 9; target b := 8
      msg := call argAt(0)
      lst := call evalArgAt(1)
      target := call target
      msg arguments foreach(i, x,
          target setSlot(x name, lst at(i))
  # inform the parser about our new operator
  OperatorTable addAssignOperator("<-", "destructure")

It should have worked! - but it didn't ☹. Why? Also, what's perhaps more important to you right now (if you don't know Io), how was it supposed to work in the first place, anyway? And then, finally, is it even possible to make it work? (hint: yes!)

Relevant Io semantics explained

One trick to reading the above code is to realize that whitespace between words is not a separator, but attribute access operator. In other languages, attribute access is very often written with a dot (.) - so the literal translation to JavaScript (for example), would look like this:

  Object.destructure = function () {
      let msg = call.argAt(0)
      let lst = call.evalArgAt(1)
      let target = call.target
      msg.arguments.foreach( (i,x) =>
        target.setSlot(x.name, lst.at(i))
      return target

Now, to explain the rest of the example, we just need to know what call object is, what attributes it has and what it does. It's really simple (in a monad-like kind of way...): the call is just a runtime representation of a message send! (Just a Monoid in the category of endofunctors, right?)

Joking aside, what is a message send? Known as a method call in other languages, the message send is simply another name for a syntactic construct describing an invocation of a method with given arguments on some object.

I prepared a little diagram[7] illustrating the concept:

Some additional description:

  • message arguments - any expression is allowed, not just simple variables or literals. Expressions passed as arguments are only evaluated on demand. It's a very important feature, which means that you can pass unquoted (but still syntactically correct) code as an argument and it won't be evaluated unless the body of a method explicitly extracts and evaluates them. You can access a list of unevaluated argument expressions via call message arguments and you can access individual arguments with shortcut methods call argAt(n) and call evalArgAt(n).
  • target - an object whose method is going to get called. Target may be a variable name in the simplest case, but in general it is an arbitrary expression, which is evaluated to obtain a reference to an object. If Io interpreter encounters a message send without a target, it is by default set to the sender (aka. context) of the call.
  • context - a dynamic environment in which the message send is going to be evaluated. Is has no representation during compile-time, it only exists during runtime, and it's simply a mapping from variable names to object references, like what you get out of locals() function in Python. It is resolved on runtime. It's accessible via call sender attribute.

Io has no other syntax than a message send, which means that message sends and expressions are the same thing. Io doesn't have statements (in imperative sense) at all, which in turn means that the message send is the whole syntax of Io. As is normal for expressions, message sends return a value when evaluated.

A call, then, represents a (parsed) message send coupled with an environment (a context) in which the message send is evaluated this time. It is accessible (via interpreter magic) in block and method bodies, not unlike the arguments object in JavaScript. Such call is an object of type (ie. with a prototype set to) Call, which has message, sender (context) and target attributes. Further, message is an object of type Message, which has name and arguments attributes.

That's it - it's almost complete description of Io syntax. As you can see, Io is conceptually very simple and consistent. It manages to stay very expressive despite of this.

Defining operators

One of the missing pieces in the above description is the syntactic sugar which Io offers to enable operators. In Io, operators are simply messages which do not need to have their arguments parenthesized. The parser maintains a special object, called OperatorTable, which contains names of all the operators along with their corresponding precedence. It then automatically inserts parentheses around values to the right of an operator, taking precedence into account. For example:

  1 + 2 * 2
  # is converted (while parsing) to:
  1 +(2 *(2))
  # ==> 5

There are languages, such as Smalltalk, where this isn't the case: they use strict left-to-right evaluation order, only alterable by explicit parentheses. This parentheses inference is used for arithmetic operators, string concatenation operators and so on, but it's also used for faking statements, like return, break or yield.

Assign operators parse transform

Operators of a special kind, called assign operators, are parsed in yet another way. In this case, operator name (eg. :=) is first mapped to a method name (eg. setSlot) via OperatorTable object, and then the call is transformed like this:

  someObject someName := someExpression
  # is converted (while parsing) to:
  someObject setSlot("someName", someExpression)

It should now be easy to see why my attempt at writing destructure (as shown above) operator failed. The parse transform assumes the first argument to the assign operator to always be a simple name. It then puts quotes around that name and passes resulting string as the first argument to the method implementing the operator. If that assumption is broken (by eg. operating on a more complex expression), the conversion to a quoted string fails and the whole thing errors out.

This is enforced during parsing, before any Io code has a chance to run, so it's impossible to change it from within the language. If you take a second to think about it, that restriction (to simple names only) doesn't make any sense and is not present anywhere else in the language. To fix it, however, I had to delve deeper, into the C code of Io interpreter.

Deep dive into Io interpreter

Io is implemented in C, with implementation consisting of a custom, tri-color mark and sweep[8] Garbage Collector, low-level co-routines[9] implementation and an interpreter[10].

It took me more time than I'm comfortable admitting to find the relevant code. While the documentation for Io exists, it's not very extensive - there's little information about the internals of the interpreter and its overall design. However, the bigger problem was wrestling with CMake and my own lack of knowledge about typical C tooling. It's slightly embarassing, since I worked with C and later C++ for years (although it was decades ago at this point). Once I brushed up on my skills in this area, locating the place to fix and developing patch wasn't that hard, fortunately.

The IoMessage_opShuffle.c module

As mentioned above, operators in Io are implemented as a parse transform. Most of it is implemented in IoMessage_opShuffle.c file. Main definitions there are Level and Levels structs:

  enum LevelType {ATTACH, ARG, NEW, UNUSED};

  typedef struct {
      IoMessage *message;
      enum LevelType type;
      int precedence;
  } Level;

  typedef struct {
      Level pool[IO_OP_MAX_LEVEL];
      int currentLevel;

      List *stack;
      IoMap *operatorTable;
      IoMap *assignOperatorTable;
  } Levels;

Io C source[11] is written in an object-oriented style, with C struct types being treated as classes and structs instances as objects. Following this style, function names are prefixed with class name on which instances they are supposed to operate; they also always take a pointer to a structure as their first argument (most often called self, like in Python).

Ignoring the boilerplate code for constructing the Levels objects out of raw Messages, the method which does the actual shuffling of operators is called Levels_attach, with the following signature:

  void Levels_attach(Levels *self, IoMessage *msg, List *expressions)

IoMessage objects contain a IoMessage* next field, which makes them a low-level implementation of a linked list (not to be confused with the List type). Despite the singular form of msg, it represents both a single message and a list of messages (just like char * represents both a string and a pointer to first character). The function takes the message, transforms it (warning: in-place!) and appends the following (next) message to expressions list. The IoMessage_opShuffle function (defined in lines 549-573), which calls Levels_attach, does so in a loop and repeats until there are no messages to process:

  List *expressions = List_new();

  List_push_(expressions, self);

  while (List_size(expressions) >= 1) {
      IoMessage *n = List_pop(expressions);

      do {
          Levels_attach(levels, n, expressions);
          List_appendSeq_(expressions, DATA(n)->args);
      } while ((n = DATA(n)->next));


The Levels_attach function has to handle at least two cases: that of normal and assign operators. We're currently not interested in normal operators - what we need is to locate the code which handles messages of the form:

  optionalTarget msg(name1, name2) assignOp(arg1, arg2) nextMsg

Fortunately, it was easy to find it - there's even a comment showing our exact case next to the code, in lines 396-400. The problem is that this case is apparently considered an error and is handled as follows:

  if (IoMessage_argCount(attaching) > 0) { // a(1,2,3) := b ;
      state, msg,
      "compile error: The symbol to the left of %s cannot have arguments.",

Right, but Steve, why?! I'd like to know why that restriction was put in place; my intuition tells me that this code was written relatively early in language development, wasn't thought through completely and later nobody wanted to touch it[12]. Well, it at least explains why my initial attempt failed.

The patch - proper handling of our case

Well, at this point I at least knew exactly, where to put my code for handling this! After checking out the source and setting up a build environment, I started implementing the code. It wasn't as easy as I'd like: first, internal APIs are mostly undocumented and second, most functions which implement "methods", are defined using IO_METHOD macro, which my "Go to definition" plugin didn't like☹. Other than this, the mutable nature of IoMessage objects and the need to deep copy (not just clone) them[13] were a bit of a PITA.

Still, after a bit of tinkering, putting a lot of printfs here and there and a fair share of segfaults, I managed to produce a working implementation. Actually, I'm still surprised that it works... but it does! Let me show you (assuming the destructure operator to be defined):

  o := Object clone
  o [wa, wb, x] <- list(3, 123)
  o println

  # prints:
  #  Object_0x19bcb60:
  #  wa               = 3
  #  wb               = 123
  #  x                = nil

As you can see, it works and returns desired results! The patch to Levels_attach is not too long (about 20 LOC) and not very complicated, which was a pleasant surprise. Let's explain what happens in it, line by line.

  Level *currentLevel = Levels_currentLevel(self);
  IoMessage *attaching = currentLevel->message;
  IoSymbol *setSlotName;

  /* ... */

  if (IoMessage_argCount(attaching) > 0) { // a(1,2,3) := b ;
    // Expression: target msgName(v1, v1, v3) assignOp   v4   ; rest
    //                    ^^^^^^^^^^^^^^^^^^^ ^^^^^^^^  ^^^^  ^^^^^^^
    //                      slotNameMessage     msg      val    rest
    // becomes:    target assignOpName(msgName(v1, v2, v3), v4) ; rest

    IoSymbol *tmp = IoSeq_newSymbolWithCString_(state, "");
    setSlotName = Levels_nameForAssignOperator(
      self, state, messageSymbol, tmp, msg

    IoMessage *slotNameMessageCopy = IoMessage_deepCopyOf_(attaching);

    IoMessage *slotNameMessage = attaching;
    DATA(slotNameMessage)->name = setSlotName;
    DATA(slotNameMessage)->args = List_new();

    IoMessage_rawSetNext_(slotNameMessageCopy, NULL);
    IoMessage_addArg_(slotNameMessage, slotNameMessageCopy);

    IoMessage *value = IoMessage_deepCopyOf_(DATA(msg)->next);
    IoMessage_rawSetNext_(value, NULL);
    IoMessage_addArg_(slotNameMessage, value);

    IoMessage *rest = IoMessage_deepCopyOf_(DATA(DATA(msg)->next)->next);
    IoMessage_rawSetNext_(slotNameMessage, rest);


In lines 13-16, setSlotName is a Symbol struct pointer, containing a string extracted from OperatorTable, which we know as the second argument in the call to OperatorTable addAssignOperator. In other words, it's a name of the method which implements given operator. Once we have the name, in lines 18-22, we create a copy of current slotNameMessage message, and start modifying the original. We set its name to the one obtained above, and we set its argument list to empty list.

In lines 24-25, we mutate the slotNameMessageCopy by cutting off its tail (as mentioned, every message carries a pointer to the following messages) and put it as the first argument to the original slotNameMessage. This is the most important change to the logic of Levels_attach: without it, the destructure operator wouldn't work.

Further, in lines 27-29, we get the first message to the right of the original operator (the one before conversion to method name, <- in our case) - in other words, the value that we want to destructure - and put it as a second argument to the operator method. Again, we need to cut off its tail, otherwise we'd put the following messages inside the argument list as well.

Finally, in lines 31-32, we attach the first of the rest of the messages as a tail of slotNameMessage. This completes the transformation.

That's it!

To be honest, the whole thing took me nearly a year to finish (including writing this post). I could work on it only once in a while, and I hit a few roadblocks which took many sessions to work around. I mentioned it briefly before, but getting Io code to compile was one such roadblock - I've never used CMake before, for one, and then some add-ons refused to compile on my system. It took me a while to sort all that out, and I couldn't start hacking without this.

With that done, I realized that I have no idea about what is where in the codebase. I had a rough idea of the architecture, as it is mentioned in the docs, but it was on a level high enough as to be mostly useless. I spent many an evening just reading the C sources, trying to familiarize myself with its style and design.

Once I felt vaguely comfortable with my knowledge, I started poking here and there with printfs. It's not that easy to print Io objects from C side - there's a bit of a ceremony involved. For example, to display the slotNameMessage I'd do:

  printf("slotNameMessage: %s\n",
         CSTRING(IoObject_asString_(slotNameMessage, msg)));

Memory management wasn't that big of an issue - Io objects are garbage collected, and I didn't need to allocate memory on the heap from C at all. Understanding how the GC works, and how different structs are to be interpreted as classes in a class hierarchy was a real challange, though.

Once I understood most of the IoMessage_opShuffle.c and implemented my fix, I realized that many parts of the interpreter could really use a serious refactoring. My first reflex was to put const qualifier almost everywhere - which backfired, because mutable state is everywhere and it's hard to say which argument to the function will be modified and which will be left alone. Some functions use multiple return statements, each in a surprising place; all these returns return nothing, basically acting as goto to the end of a function.

The internal APIs for manipulating objects are underdocumented (yes, I know I said it already) and incomplete. Working at the C level is made awkward because of that, as it's never clear if you should call a method or a helper function. Methods are also defined incosistently, either with IO_METHOD macro or without. It took me awhile to understand the DATA macro and why is it redefined for every Io object. There's a lot of commented out code and some areas of the code are simply a mess.

Despite all this, it was an interesting, if a bit long, journey. I learned a lot, which was my main goal anyway, and also managed to make the desired feature work, which was a nice by-product.

The End

If you reached this point - thanks for reading. I hope it wasn't too boring a write-up. I'd be incredibly happy if this post inspired you to take a closer look at Io, to try to use it, or perhaps even to try developing it.

Despite some messy parts, Io codebase is relatively short and simple, and Io as a language has a couple of features that make it a viable alternative to other languages in certain circumstances. With Io, you get Lisp-level meta-programming support without being tied to s-exp syntax. The ability to add your own syntax to the language, coupled with its incredible reflection support makes molding the language to closer fit your problem domain a breeze. Unlike Scheme, Io is based on a familiar, object-oriented metaphor, which makes it easier to read and learn by most programmers.

The slowness of Io - and I'm not even sure how big it is, I didn't measure - only means that there probably are many low-hanging optimizations to be done in its source. After reading the code I get the feeling that the authors wanted the language more than they wanted the implementation, which means they chose to add features instead of polishing existing ones. It's actually a good strategy early in language development and it's usually left to the 1.0 release preparation work to clean the code and make it efficient. It's just that Io died before the effort to make it 1.0-grade software even started.

I think it's still not too late, that Io still has potential and that it could, with time, be made into a serious competitor for Lua in some cases.

  • More precisely, "Seven Languages in Seven Weeks: A Pragmatic Guide to Learning Programming Languages", a book which could serve as a Polyglot Manifesto if only polyglot was more of a thing...
  • It could get much better with JIT compilation, but it's not implemented currently.
  • Io has built-in support for these.
  • A descendant language of -->