Extending Io to add tuple unpacking (aka destructuring bind) ¶
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
book, which is how I learned of its existence. It's a general purpose,
interpreted language, with semantics inspired
look and feel reminiscent of TCL
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!
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 and should not be used for number-crunching (unless it can be vectorized) 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. Incredible expressive power and ease of DSL creation allows you to express business logic with minimal ceremony and with the just right level of verbosity, so it can also be a good tool for configuring larger systems (which you'd do with XML or YAML otherwise).
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 - it starts up quickly enough.
The problem, the hack and its effects
I picked Io up 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, 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 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:
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, which 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:
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:
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
Now, to explain the rest of the example, we just need to know what
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,
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 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
call message argumentsand you can access individual arguments with shortcut methods
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, see below) of the
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
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.
call, then, represents a (parsed) message send coupled with an
environment (a context) in which the message send is being evaluated. It is
accessible (via interpreter magic) in
method bodies, not
call is an object of
type (ie. with a prototype set
sender (context) and
target attributes. Further,
message is an object of
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 thanks to this.
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:
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
in Iois used for arithmetic operators, string
concatenation operators and so on, but it's also used for faking statements,
Parse transforms of assign operators
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.
OperatorTable object, and then the call is
transformed like this:
It should now be easy to see why my attempt at writing
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 Garbage Collector, low-level co-routines implementation and an interpreter.
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
file. Main definitions there are
Io C source 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
Messages, the method which does the actual shuffling of operators is
Levels_attach, with the following signature:
IoMessage objects contain an
IoMessage* next field, which makes them a
low-level implementation of a linked list (not to be confused with
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
expressions list. The
IoMessage_opShuffle function (defined
549-573), which calls
Levels_attach, does so in a loop and repeats
until there are no messages to process:
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
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:
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 and later nobody wanted (or needed) to touch it. 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 (which is rather common for
internal APIs) and second, most functions which implement "methods", are
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 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 is defined as shown at
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. It goes like this:
Let's start with lines 13-16
setSlotName here is a
Symbol struct pointer (aka. object instance),
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 an empty list. Then, 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
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.
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 (coupled with my lack of experience) 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
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
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
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.
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 Manifestoif only
polyglotwas more of a thing... ↵
- It could get much better with JIT compilation, but it's not implemented currently. ↵
- Io has built-in support for vectorized operations, somewhat similar to NumPy, but lower-level. ↵
- Python PEG library; I wanted to use it for parsing user commands. ↵
- The method is called "destructure", because it has a potential to cover more cases than just sequence unpacking: it could, for example, allow extracting values from dicts and other containers and support wildcards. The code for this is not shown, but it would be very similar. ↵
- To be honest, my wife made it for me - I'm hilariously incompetent in the graphics department. Thanks, honey! ↵
- Implemented in
page on Wiki for more info on the whole
mark and sweepbusiness. ↵
- Implemented partially in assembly, in libs/coroutine/source. There's also a Wiki page about co-routines. ↵
- It's implemented as a virtual machine and lives in libs/iovm/source. ↵
- BTW, I took some liberties with formatting to reduce the height and width of the examples, hope you don't mind. ↵
- The "clean up this method" comment suggests as much. ↵
- Honestly, I think I simply don't fully understand the IoMessage intended semantics - it should be possible to get away with just clones, I just didn't manage to find out how. ↵
- Let me know if you'd like to start hacking! You can find my email in contact page. ↵