POLYGLOT PROGRAMMING

Better poly than sorry!

ffipf - jump to file in a project quickly (PoC)

Using Emacs loadable modules and native Nim code to speed up the file search

Last updated on:

NOTE: As usual, source code is on Github

ffi... what?

The name stands for Fuzzy Find in Project Fast, thanks for asking. Believe me, I tried to come up with a better name for the project... and failed miserably. Sorry. I'd be forever grateful for better name suggestions.

The project is in a proof-of-concept stage and my main reason for this writeup is to see if there's any interest in something like this. I'm happy with the functionality it has, but it's nowhere near polished enough for other people to easily reuse.

So what is it?

ffipf is a backend for fuzzy matching file paths. It's scoring and sorting algorithm is better suited for matching paths compared to more general fuzzy matching implementations, like Helm and Ivy. It's written in Nim and compiled to native code, which makes it faster and more memory-efficient than other solutions. The compiled DLL is a proper Emacs module and can be loaded as if it was Elisp.

Let's go over the features in a bit more detail next.

Better matching and sorting algorithm

The matching algorithm is designed specifically for patterns targeting paths. It matches each section of the pattern, delimited by /, fuzzily, but then matches each segment in sequence. The sorting is done based on how well the path conforms to the pattern, with the path most closely resembling the pattern at the top. The algorithm is said to be close to the one used by TextMate[1] by its author, whose code I ported to Nim from the Ruby original[2].

In practice, this means that you can skip large parts of the path and input very few characters, yet still arrive at the correct file. You can use it to also quickly list files within a set of similar directories, or files matching some pattern no matter where they are in the hierarchy.

Some examples of patterns I'd use to search for some files and results for them. Examples are from my .emacs.d directory, and the output is shortened (you can easily change how many candidates are returned).

  -▶ ./ffip
  > fo/mag/mag.el                       # wanted: magit.el
  .emacs.d/plugins-forked/magit/lisp/magit.el
  .emacs.d/plugins-forked/magit/lisp/magit-tag.el
  .emacs.d/plugins-forked/magit/lisp/magit-wip.el
  .emacs.d/plugins-forked/magit/lisp/magit-git.el
  .emacs.d/plugins-forked/magit/lisp/magit-log.el
  .emacs.d/plugins-forked/magit/lisp/magit-pkg.el
  .emacs.d/plugins-forked/magit/t/magit-tests.el
  .emacs.d/plugins-forked/magit/lisp/magit-core.el
  .emacs.d/plugins-forked/magit/lisp/magit-stash.el

  > stg/                                # wanted: all files in plugins-staging/
  .emacs.d/plugins-staging/f3/.gitignore
  .emacs.d/plugins-staging/f3/LICENSE
  .emacs.d/plugins-staging/f3/README.md
  .emacs.d/plugins-staging/f3/create-markdown.coffee
  .emacs.d/plugins-staging/f3/f3.el
  .emacs.d/plugins-staging/f3/package-lock.json
  .emacs.d/plugins-staging/f3/package.json
  .emacs.d/plugins-staging/f3/update-commentary.el
  .emacs.d/plugins-staging/ecb/ecb-advice-test.el

  > stg/.el                             # wanted: all Elisp files in plugins-staging/
  .emacs.d/plugins-staging/f3/f3.el
  .emacs.d/plugins-staging/ecb/ecb.el
  .emacs.d/plugins-staging/elx/elx.el
  .emacs.d/plugins-staging/esup/esup.el
  .emacs.d/plugins-staging/doom/init.el
  .emacs.d/plugins-staging/doom/core/autoload/ui.el
  .emacs.d/plugins-staging/unfill/test.el
  .emacs.d/plugins-staging/doom/core/cli/env.el
  .emacs.d/plugins-staging/ecb/ecb2/test.el
  .emacs.d/plugins-staging/doom/core/core.el

  > plu/REA                             # wanted: all plugin READMEs
  .emacs.d/plugins-forked/xr/README
  .emacs.d/plugins-staging/ecb/README
  .emacs.d/plugins-forked/muse/README
  .emacs.d/plugins-forked/distel/README
  .emacs.d/plugins-forked/lua-mode/README
  .emacs.d/plugins-forked/yaml-mode/README
  .emacs.d/plugins-forked/s/README.md
  .emacs.d/plugins-forked/f/README.md
  .emacs.d/plugins-forked/a/README.md
  .emacs.d/plugins-forked/ht/README.md
  .emacs.d/plugins-forked/gh/README.md

  > co/mini/h                          # wanted: my config file for Helm
  .emacs.d/config/interface/minibuffer/my-helm-config.el

  > co/mini/                           # wanted: all config files related to minibuffer
  .emacs.d/config/interface/minibuffer/my-helm-overrides.el
  .emacs.d/config/interface/minibuffer/my-ido-config.el
  .emacs.d/config/interface/minibuffer/my-selectrum-config.el
  .emacs.d/config/interface/minibuffer/my-helm-config.el
  .emacs.d/config/interface/minibuffer/my-yes-or-no-prompt.el
  .emacs.d/config/interface/minibuffer/my-ivy-config.el
  .emacs.d/plugins-forked/selectrum-group/marginalia/.gitignore
  .emacs.d/plugins-forked/selectrum-group/marginalia/LICENSE
  .emacs.d/plugins-forked/selectrum-group/marginalia/README.md

The details of the scoring algorithm are a bit more complex, but the effects are very satisfactory in my opinion.

Native module and execution speed

The main functionality is implemented in Nim and compiled to native code. Nim is a high-level language with a Pythonesque syntax, but its performance is closer to C or C++. Thanks to Yuuta Yamada[3] work it's possible to write Emacs extension modules easily in Nim.

My .emacs.d has nearly 40000 files under it. This is a lot, and simply traversing the directory hierarchy takes time; when you add the time needed to process the list of files in Emacs Lisp, the invocation of (for example) counsel-file-jump can take close to 2 seconds to initialize. Further, filtering can also feel sluggish during the input of the first few characters (it gets better when the pattern gets longer).

Traversing the whole hierarchy, or initializing the search, takes just 0.3 of a second with the Nim implementation. Moreover, the feedback - displaying candidates as you type - is always instantaneous.

There are downsides to the usage of native code. For example, it's possible for the module to crash Emacs as a whole in case there's a segfault triggered in the code. However, Nim makes it significantly harder to shoot yourself in the foot like that. Almost all of the module is written in a "safe" subset of Nim, and the only place where a crash is possible is in the parts which interact with Emacs module API. Fortunately, after wrapping the raw API calls with helper procedures, the chance of triggering unrecoverable error also goes down drastically.

Another downside is that you need to compile the module first in order to use it. Fortunately, Nim is much easier to compile than C, and it's available for all major platforms. After installing Nim you're just one make or nimble build command away from a working module. It's also possible to distribute binaries in case you don't want to install Nim, but that's something for the future (I have no way of cross-compiling for non-Linux OSes currently).

Displaying candidates

Currently, I use Ivy for displaying candidates and a built-in project.el for finding the root directory of the current project. The interface is very basic, for example it doesn't highlight the parts which were matched, but it does the trick.

That being said, my main focus is on the backend, the Nim-based dynamic module. It should be easy to write a Helm source for it or interface with it through Selectrum, IDo, or any other completion framework.

The main question

Before I start working on making the implementation bulletproof and usable for others I need to know if there's any interest towards a module like this. The code is currently nearly there in terms of features that I want it to have, and if it's for my personal use only, I can slowly improve only the parts I need. On the other hand, if there's any interest, I would need to clean up the code, remove all the assumptions specific to my setup, and add configuration options at the very least. For example, the directory blacklist (list of dirs that should not be traversed) is currently hardcoded on the Nim side, which doesn't bother me, while it could be a problem for others.

So here's the question: would you be interested in a blazing fast fuzzy file finder for your Emacs?

Comments

Clojure-like lambda expressions in Emacs Lisp

If it's this easy, why isn't it implemented?

Last updated on:

Anonymous function syntax

In Clojure[1] there are two syntaxes for anonymous functions. The first one is equivalent to lambda expressions in Emacs Lisp; they look like this:

  (fn [arg1] body)
  (lambda (arg1) body)

The other syntax, which is shorter and built into the reader, has no equivalent in Emacs Lisp. It looks like this:

  #(expr %1 %2)

This is equivalent to the following lambda expression:

  (fn [%1 %2] (expr %1 %2))

The shorter syntax is convenient and works really well with map/mapcar and other higher-order functions. It is, however, absent in Emacs Lisp.

Some time ago I found an implementation of short lambda syntax for Emacs Lisp. It's a simple macro which expands to lambda expression. You can test it like this:

  (funcall (short-lambda (cons 1 %1)) 2)  ; => (1 . 2)

The implementation, however, is incomplete. In the words of the author:

This assumes that there is a reader macro in the Emacs C code that translates #(STRUCTURE) to (short-lambda STRUCTURE), in the same way as for the backquote macro.

Indeed, as it is, it's even longer than normal lambda - clearly there's something missing. Namely: a support for the short lambda in the reader, which is implemented in C.

Implementing the missing part

How hard would it be to add the missing support to the reader? When I was thinking about this, I noticed that there is already something similar in Elisp, namely - hash-table syntax. It looks like this:

  (make-hash-table)
  ;; ⇒ #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8125 data ())

The #s(...) syntax is supported by the reader, ie. hash tables can be read with the same syntax they are printed in.

Wouldn't it be easy to create a short lambda syntax by changing #s to #f? Turns out - yes, it is easy. It took me an afternoon or two to figure it out, with no prior experience with Emacs C codebase. The whole implementation is less than 5 lines of code.

Changing the reader

First, I located the hash-table reader code in lread.c, which is where the reader lives. There's a function called read1, where the hash-table support is implemented. It looks like this (reformatted for brevity):

static Lisp_Object read1(Lisp_Object readcharfun, int *pch, bool first_in_list) {
  int c;
  // ... more variables here ...
retry:

  c = READCHAR_REPORT_MULTIBYTE (&multibyte);
  if (c < 0) end_of_file_error ();

  switch (c) {
    case '(': return read_list (0, readcharfun);
    case '[': return read_vector (readcharfun, 0);
    case ')':
    case ']': {
      *pch = c;
      return Qnil;
    }
    case '#':
      c = READCHAR;
      if (c == 's') {
        // ... lots of code specific to hash-tables ...

The only thing needed to add support for short lambda is to change the line 19 to this:

1
2
3
4
5
  if (c == 'f') {
    return list2(Qfn, read0(readcharfun));
  }
  else if (c == 's') {
    // ... lots of code specific to hash-tables ...

The list2 function creates a list of two elements, where the first one is a symbol, defined (that's the second, and last, change to C code) like this at the end of lread.c (fn is and alias for short-lambda):

  DEFSYM (Qfn, "fn");

The second element of the list is whatever can be read after the opening paren.

The whole diff looks like this:

diff --git a/src/lread.c b/src/lread.c
index 015bcc2e11..42fc4050ae 100644
--- a/src/lread.c
+++ b/src/lread.c
@@ -2880,7 +2880,10 @@ read1 (Lisp_Object readcharfun, int *pch, bool first_in_list)

     case '#':
       c = READCHAR;
-      if (c == 's')
+      if (c == 'f') {
+        return list2(Qfn, read0(readcharfun));
+      }
+      else if (c == 's')
        {
          c = READCHAR;
          if (c == '(')
@@ -5168,6 +5171,7 @@ syms_of_lread (void)
   DEFSYM (Qload_force_doc_strings, "load-force-doc-strings");

   DEFSYM (Qbackquote, "`");
+  DEFSYM (Qfn, "fn");
   DEFSYM (Qcomma, ",");
   DEFSYM (Qcomma_at, ",@");

When is it useful?

As mentioned, the shortened syntax works well with higher-order functions. It's not essential, but it is convenient. Especially if you use libraries like dash.el, which give you a lot of such functions.

Just yesterday I was writing a bit of code to replace literal characters with HTML entities. I fetched the list of entities from the gist published by Christian Tietze (blog post, the gist), and started coding. I had to parse the list of entities and needed to break each line into components, entity, entity name, and description. The whole code looks like this:

(defconst html-entity-list
  '("char: \" entity: &quot;    text: quotation mark (APL quote)"
    "char: & entity: &amp;      text: ampersand"
    "char: ' entity: &apos;     text: apostrophe (apostrophe-quote); see below"
    ;; ....
)
(require 's)
(require 'dash)
(require 'short-lambda)

(defconst html-entities-lookup-table
  (-> (-juxt
       #f(second (s-match "char: \\(.\\) " %))
       #f(second (s-match "entity: \\(&.+;\\) " %))
       #f(second (s-match "text: \\(.+\\)" %)))
    (-map html-entity-list)))

(defun my-html-replace-entity (p)
  (interactive "d")
  (let*
      ((ch (buffer-substring-no-properties p (1+ p)))
       (rep (-find #f(equal ch (car %))
                   html-entities-lookup-table)))
    (delete-char 1)
    (insert (second rep))))

There are 4 lambdas in the code - were it not for the short lambda, I would probably write this code differently. Using them, though, the code ended up being short and readable, without the need for any of the heavier abstractions.

That's it, so... why?

That's really everything you need to add short lambda support Emacs Lisp. I have this implemented in my Emacs since a few years back and I use the #f() syntax regularly. It's convenient. It's easy to implement. I wonder from time to time - why isn't it still implemented in Emacs?

Please let me know if you know the reason!

EDIT: so, um, yeah, one reason may be that nobody suggested this as a feature yet. I'm stupid, it totally slipped my mind. I assumed it was proposed already, for sure, given that the short-lambda.el repo[2] is 6 years old at this point. But I didn't check. My bad!

Comments

Merging ZSH history files from different hosts with Scala

Learning Scala - along with Groovy, Java and JVM ecosystem - was fun!

Last updated on:

NOTE: As usual, all the code is in a GitHub repository.

Motivation

For the past two years I've been dabbling in DIY home automation. I ended up with a bunch of Raspberry PIs[1] all over the house, all running under Linux and connected via WiFi. They service some sensors and cameras, and show current date and time (among other dashboard-y things, like calendar or weather forecast) on a few displays around the house.

I have a few Ansible[2] playbooks set up for running things like package- and system updates, but I still often ssh to the PIs for one-off tasks (in the beginning they all look like one-offs...) To do this comfortably, I installed ZSH[3] - my shell of choice - on the PIs, using the same .zshrc config everywhere. Just a handful of ifs was enough to make my config portable, which was a pleasant surprise.

One of the CLI tools I have set up in my .zshrc is fzf[4], which I use as a history search mechanism, replacing the default one under Control + r. It's incredibly useful, as it lets you narrow down the search incrementally and interactively, with fuzzy matching, which makes arriving at the intended command much faster than with the built-in search. You could say I got addicted to the ease of both browsing and searching through the shell history in an interactive manner. However, no matter what search method you use, if something's not there, you won't find it! That sounds trivial, but it connects to the topic of this post: how to merge ZSH history files.

The use case should be clear by this point: very often, whatever I did on one PI, I would need to do, sooner or later, on one or two others. In such cases I, reflexively, tried to search for the needed command in the history of the current shell, which never saw that command... Obviously, I couldn't find it.

Going through a few minutes of frustration a couple times was enough for me to start thinking about an automatic solution. How nice would it be if something gathered the histories from all the hosts and merged them into a single one, I thought.

Why Scala? Groovy? JVM?

As usual: by accident. It just so happened that I was learning Scala (and JVM in general) at the time for work, so I decided to use the urge to automate as a material for practice. As many of us do all the time, I thought, how hard could it be? and started setting up a project, which you can see on GitHub. In this post, I want to highlight nice things about Scala that I learned in the process.

Project setup using Gradle

I'm not against the use of Scala build tool, sbt. I chose Gradle[5] simply because I had some prior experience with it, from my previous JVM project. That project had parts written in Java, Groovy, and Scala, and Gradle was the first tool we found which handled this case without tons of boilerplate code. Gradle has plugins for nearly everything, lightweight config syntax, and good performance. When starting the current project, I simply copy-pasted the build.gradle from the previous one, which was the fastest way to get started. The file looks roughly like this (click to unfold):

plugins {
  id 'application'
  id 'scala'
}

application { mainClassName 'zsh.history.Main' }

sourceSets {
  main {
    scala { srcDirs = ['src/scala/'] }
  }
}

repositories { jcenter() }

dependencies {
  implementation 'com.github.pathikrit:better-files_2.13:3.8.0'
  implementation 'com.github.nscala-time:nscala-time_2.13:2.22.0'
  implementation 'org.scala-lang:scala-dist:2.13.1'
  implementation 'org.scala-lang.modules:scala-parser-combinators_2.13:1.1.2'
  implementation 'org.scala-lang.modules:scala-parallel-collections_2.13:0.2.0'
}

You execute tasks configured in build.gradle with gradle command, which works kind of like make (or gulp, or mix, etc.). For example, the plugin called 'application' defines a task called 'installDist' which compiles and packages the project, giving you a script which starts your application. To compile and run the project in one go, I ended up with a following script, run.sh:

1
2
3
4
5
6
#! /usr/bin/env bash

set -e

gradle installDist
./build/install/zsh-merge-hist/bin/zsh-merge-hist

It's worth noting that you can define your own tasks in build.gradle, using the full Groovy[6] language. Here's an example which creates scripts for running REPLs with the whole project on the CLASSPATH:

File mkfile(obj) { obj instanceof File ? obj : new File(obj.toString()) }
task makeScripts(type: DefaultTask) {
    String shebang = "#! /usr/bin/env sh\n"
    String root = projectDir.absolutePath
    String pre = ""
    File outFile

    String classpath = sourceSets.main.runtimeClasspath.toList()*.toString().join(":")
    try {
        String opts = mkfile(root + "/.java").text.split("\n").join(" ")
        pre += "\nexport JAVA_OPTS='$opts'\n\n"
    }
    catch(_){}

    outFile = mkfile("-scala")
    outFile.write shebang + pre + "scala -classpath ${classpath}\n"
    outFile.setExecutable(true, true)

    outFile = mkfile("-amm")
    outFile.write shebang + pre + "java -cp ${classpath}:/usr/local/bin/amm ammonite.Main\n"
    outFile.setExecutable(true, true)

    ArrayList<String> jshell_cp = classpath.split(":").findAll({
        // TODO: filter out all nonexistent dirs, not just the blacklisted ones
        !(it.contains("build/classes/java/main") ||
          it.contains("build/resources/main"))
    })
    outFile = mkfile("-jshell")
    outFile.write shebang + pre + "jshell --class-path ${jshell_cp.join(':')}\n"
    outFile.setExecutable(true, true)
}

Interactive shell is always nice to have, and one of the three, called Ammonite[7], is a Scala equivalent of IPython[8], and is a pleasure to work with - I used it extensively to experiment with unfamiliar libraries, for example.

At this point the setup is done. Let's start examining the implementation.

Fetching history files with SCP & Scala external commands

Recounting the problem: I have a number of hosts on the network, where I tend to log in via ssh - which means I have authorized_keys properly configured already. I would like the shell history, which is a plain text file, to be synchronized among all the hosts. To do this, I need to fetch the history files from the network, process them somehow and put the merged file back on the hosts.

In this situation, using scp[9] command seemed the easiest way of copying files across my network. It's not Scala-specific, but there's no need to reinvent the wheel and write custom networking code for something this simple. Fortunately, Scala has a simple DSL for running external programs built-in, in the sys.process namespace (see the docs.)

While the DSL is powerful - even chaining I/O of a sequence of programs (like what the | operator does in most shells) is possible - what I really needed was just a return code. If it's equal to 0, we know the transfer finished successfully; anything else signifies an error. To execute a command and get the exit code, you use ! method, implicitly added to Strings and Seqs:

object Transfer {
  import scala.sys.process._
  import better.files.File
  import Configuration.config

  type DownloadInfo = (String, File)
  type DownloadResult = Either[DownloadInfo, DownloadInfo]

  def downloadSingleFileFrom(host: String): DownloadResult = {
    val (from, path) = config.connectionData(host)
    val localHistFile = File(path)

    println(s"Transfer $from to $path")
    val returnCode = s"scp $from $path".!  // could be: Seq("scp", from, path).!
    if (returnCode != 0 || !localHistFile.exists) {
      // clear the empty or partial file, don't throw if it doesn't exist at all
      localHistFile.delete(swallowIOExceptions=true)
      Left((from, localHistFile))
    }
    else {
      Right((from, localHistFile))
    }
  }
  // ...
}

Downloading multiple files at a time with parallel collections

Most of my PIs are connected via WiFi, some of the older ones even use the 2.5Ghz network. The transfer is not slow enough to be irritating, but that's only if you need something from a single host. If you try downloading many files in sequence, the latency will add up to the level where it's noticeable.

Scala provides a wonderful, high-level construct for parallelizing processing: parallel collections. Basically, whenever you have code which maps (or folds) a function over a collection, you can transform said collection into a parallel one. Parallel collections implement map method which executes given function on a pool of threads. The result is another parallel collection, which you can transform back into a normal one, which will have the results of computations, in the correct order. The toList method which does this blocks and waits for all the items in all the threads to finish being processed. It looks like this:

  // ...
  def downloadHistoryFiles(allowMissing: Switch = Switch.T): List[File] = {
    require(config.hosts.length > 0)
    config.createDownloadDirectory()

    val downloads = config.hosts.par.map(downloadSingleFileFrom _).toList
    val (failures, successes) = downloads.partition(_.isLeft)
    if (!allowMissing && failures.nonEmpty) {
      throw new TransferError(failures map unwrapFailure)
    }
    successes.map(_.toOption.map(_._2).get)
  }
  // ...

The interesting part is in this expression:

    hosts.par.map(downloadSingleFileFrom _).toList

Which is roughly equivalent to the following Python code:

import os
from concurrent.futures import ThreadPoolExecutor

hosts = [ ... ]
futures = []
results = []

with ThreadPoolExecutor(max_workers=os.cpu_count()) as executor:
    for host in hosts:
        futures.append(executor.submit(downloadSingleFileFrom, host))
    for future in futures:
        results.append(future.result())

Parallel collections take care of all the bookkeeping behind the scenes, so that you can have a "scatter & gather"[10] concurrency and parallelism without having to do any scattering or gathering yourself.

One thing worth considering is if our use of parallel collections is safe. The question arises because calling external processes is very clearly a side-effect, and side-effects are generally bad fit for concurrency. In this case, however, we know that each application of downloadSingleFileFrom gets a file from a different server and saves that file under a path different from all the other calls. As there is nothing shared between calls, they are safe to execute concurrently.

Parsing ZSH history file format

ZSH has two formats of history files: simple and extended. The extended one, which I use, looks like this:

1
2
3
: 1538336195:0;history 1
: 1538336321:0;cat mix.exs
: 1538336321:0;find . -iname rye

Each history entry (note: not "each line", because entries can span multiple lines) starts with a colon and space - : - which is followed by the timestamp in typical UNIX format, then by time taken by the command to execute, and finally the command itself.

Commands spanning multiple lines are problematic - we can't just split the file contents on newlines to get the list of commands. Other than that, the format is not very complex and it can be parsed with a few regexes.

Personally, though, whenever I think about a few regexes - not just one or two - I tend to go for a more powerful and structured parsing tool. Scala provides a parser combinator library[11] with a DSL for defining the structure of the text to be parsed. Parser combinators are a functional way of encoding recursive descent parsing, and so are able to parse both contex-free and context-sensitive grammars; we don't need its full power here, but it's good to know we can deal with more complex formats with the same tool.

The parser is defined as an object which extends Parsers subclass, RegexParsers:

  import scala.util.parsing.combinator.RegexParsers

  type ResultData = List[(Long, Int, String)]
  type ParseResult = SimpleParser.ParseResult[ResultData]

  object SimpleParser extends RegexParsers {
    override def skipWhitespace = false

    def nl = "\n"
    def semi = ";"
    def colon = ":"
    def digits = "[0-9]+".r
    def noNewLine = "[^\n]+".r

    def start = nl ~ colon
    def elapsed = digits <~ semi
    def timestamp = start ~> " " ~> digits <~ colon
    def command = ( noNewLine | (not(start) ~> nl) ).+ <~ guard(start)

    def line = timestamp ~ elapsed ~ command ^^ {
      case ts ~ el ~ cmd => (ts.toLong, el.toInt, cmd.mkString.trim)
    }

    def lines = line.+
  }

The parser is an object which defines a series of methods returning Parser instances. There are implicit conversions defined for Strings and Regexex that convert them into Parsers - which is why the nl to noNewLine definitions work. The parsers themselves are defined as functions which take a stream as input and return a result along with the rest of the stream (to be parsed by following parsers.)

After defining the basic building blocks of the syntax, we define the grammar using parser combinators: methods ~>, <~, and ~. They all express sequencing, ie. the parser created by parser1 ~ parser2 will match whatever parser1 matches, then will try to match parser2. The difference between the three methods has to do with the results of parsing: the basic ~ operator means combine the results of both parsers into one, while ~> means discard results of the first parser, return whatever the second returns. The <~ operator discards the results of the second parser instead.

There is an alternative operator, spelled parser1 | parser2 - the same way as in regexps - which parses whatever either parser1 parses, or whatever parser2 parses. Another important combinator is parser.+, which parses repetitions of whatever parser parses. It puts the results in a List. Finally, we have guard(parser) combinator, which parses whatever parser parses, but doesn't advance the position in the input stream. This is known as lookahead assertion in regexes.

The last operator, parser ^^ fun, applies fun to the results of parser. Whatever fun returns becomes the new parsing result. Quoting the docs: If you've done yacc parsing, the left hand side of the ^^ corresponds to the grammar rule and the right hand side corresponds to the code generated by the rule. This is used for cleaning up and structuring parsing results, as you can see in the example, where the combined results of three parsers are pattern matched on and transformed into a single 3-tuple (lines 20-22).

To actually use the parser, you do something like this:

1
2
3
4
5
6
7
8
  def parseHistory(input: java.io.InputStream): Either[String, ResultData] = {
    val reader = new java.io.InputStreamReader(input, "UTF-8")
    SimpleParser.parse(SimpleParser.lines, reader) match {
      case SimpleParser.Success(lines, _) => Right(lines)
      case SimpleParser.Failure(msg, _) => Left(msg)
      case SimpleParser.Error(msg, _) => Left(msg)
    }
  }

As you can see, there are two failure modes: Failure and Error. Because I don't care about the distinction, I transform the result into Either, with Right meaning success. The ignored part of the patterns, _, is the mentioned rest of the input, which should be empty.

This would normally work, but the parseHistory, as it is, fails on some history files. What is happenning, and why?

(Un)Metafying ZSH history

Turns out ZSH escapes some characters in a special way when writing and reading history files. As far as I can tell, this mechanism is there to make sure characters special to the shell, like $, !, ~, etc., are not interpreted/executed by accident. It unfortunately causes a problem with string encoding; in Java this means you get the following exception when you try reading the file:

    jshell> var p = java.nio.file.FileSystems.getDefault().getPath("/home/cji/mgmnt/zsh_history")
    p ==> /home/cji/mgmnt/zsh_history
    jshell> var cs = java.nio.charset.StandardCharsets.UTF_8
    cs ==> UTF-8
    jshell> java.nio.file.Files.readAllLines(p,cs)
    |  Exception java.nio.charset.MalformedInputException: Input length = 1
    |        at CoderResult.throwException (CoderResult.java:274)
    |        at StreamDecoder.implRead (StreamDecoder.java:339)
    |        at StreamDecoder.read (StreamDecoder.java:178)
    |        at InputStreamReader.read (InputStreamReader.java:185)
    |        at BufferedReader.fill (BufferedReader.java:161)
    |        at BufferedReader.readLine (BufferedReader.java:326)
    |        at BufferedReader.readLine (BufferedReader.java:392)
    |        at Files.readAllLines (Files.java:3330)
    |        at (#3:1)

Now, ZSH mostly can handle UTF-8 text. Or rather, UTF is defined in such a way that it's mostly backward compatible: as long as a program doesn't do anything special with character codes above 127, it should be able to handle UTF-8 transparently. ZSH escaping, however, uses codes above 0x83 (that is 131 in decimal, 0b10000011 in binary) to encode its special characters. It does this without accounting for a variable-width encoding of UTF-8, breaking the encoding in the process.

The history file is written in the metafied - meaning escaped - format. To make it UTF8-clean, we need to reverse the escaping. In ZSH source, there's a function called unmetafy, which looks like this:

#define Meta 0x83

mod_export char *
unmetafy(char *s, int *len)
{
    char *p, *t;

    for (p = s; *p && *p != Meta; p++);
    for (t = p; (*t = *p++);)
	if (*t++ == Meta && *p)
	    t[-1] = *p++ ^ 32;
    if (len)
	*len = t - s;
    return s;
}

The metafication inserts a special character, Meta, before special character, which is then XORed with 32. As XOR is its own inverse, unmetafying simply removes every Meta character encountered, and XORs the following character with 32 again. The code is terse and efficient, as it does this in-place - no new string is allocated. My reimplementation in Scala is less efficient, as it creates a copy of the input string, but it's not really an issue, given the amount of RAM available vs. the lenght of the history file. For reference, currently my history file is 2.4Mb, while my computer has 32Gb of RAM... Anyway, in Scala it looks like this:

object Unmetafy {
  val Meta = 0x83.toByte  // On the JVM bytes can only be signed, so numbers
                          // above 127 need to be be converted
  def unmetafy(file: File): String = unmetafy(file.byteArray)

  def unmetafy(bytes: Array[Byte]): String = {
    val it = bytes.iterator
    val out = new ArrayBuffer[Byte](bytes.length)
    while (it.hasNext) {
      val byte = it.next()
      if (byte == Meta)
        out.addOne((it.next() ^ 32).toByte)
      else
        out.addOne(byte)
    }
    new String(out.toArray, "UTF-8")
  }
}

One curious thing I learned, which is visible in this example, is that on the JVM there is no unsigned byte type. What it means is that values above 127 are interpreted as negative; this is known as two's complement, where the highest bit encodes a sign. What's important to note is that the value - ie. the bits set - stays the same, it's just the interpretation that changes. This means we can write the Array of Bytes back into a file without doing anything special - we only need to convert values over 127 to Byte to satisfy the type checker.

Dumping merged history back into a file

After parsing, we have a number of Lists of tuples. Many - almost all, actually - of the tuples are duplicates, which we need to remove. I do this by joining all the lists, then sorting by timestamp (first element of a tuple), then removing duplicates, and finally removing repeating commands (third element of tuples) from the list. It looks like this:

object Transform {
  import better.files.File
  import Parsing.ResultData
  import Configuration.config

  def removeDuplicates(lines: ResultData): ResultData =
    lines.sortBy(_._1).distinct

  def removeRepeatedCommands(lines: ResultData): ResultData =
    lines.reverse.distinctBy(_._3).reverse

  def processHistoryFiles(): ResultData =
    processHistoryPaths(config.hosts.map(config.getPathForHost))

  def processHistoryFiles(files: List[File]): ResultData = {
    val parsedFiles =
      files.par.map({ dest =>
        println(s"Parsing ${dest}...")
        val inputString = Unmetafy.unmetafy(dest)
        val Right(parsed) = Parsing.parseHistory(inputString): @unchecked
        parsed
      })
    removeRepeatedCommands(removeDuplicates(List.concat(parsedFiles.toList: _*)))
  }
}

As you can see, parsing also happens in parallel, thanks to parallel collections. The main function, processHistoryFiles, returns Parsing.ResultData, which is an alias for a list of triples: List[(Long, Int, String)].

What's left is just dumping the results back into a file:

object Dumping {
  import better.files._
  import Parsing.ResultData
  import Configuration.config

  def renderLine(ts: Long, rt: Int, cmd: String) =
    s": $ts:$rt;$cmd\n"

  def dumpResultsToFile(res: ResultData): Unit =
    dumpResultsToFile(res, config.getPathForHost("merged"))

  def dumpResultsToFile(res: ResultData, path: String): Unit = {
    println(s"Dumping parsed data to ${path}")
    dumpResults(res, File(path).newOutputStream)
  }

  def dumpResults(res: ResultData, out: java.io.OutputStream = System.out): Unit = {
    Using.resource(out) { out =>
      for( (ts, elapsed, command) <- res ) {
        out.write(renderLine(ts, elapsed, command).getBytes("UTF-8"))
      }
    }
  }
}

The code here is straightforward, one thing worth noting is line 18 - the Using.resource() construct[12]. Scala doesn't have try-with-resources[13] which is used to always free, or close, a resource, when control exits from a block - both normally and via exception. In Python, you would use with statement; Scala defines a higher-order function which does the same.

Configuration and reading JSON data

Instead of hardcoding a list of hosts, I decided to create a configuration file, .mergerc. It is a JSON file - mostly because I wanted to try using JSON with Scala. The configuration format looks like this:

1
2
3
4
5
{
  "hosts": ["vps1", "kuro", "shiro", "midori", "sora", "..."],
  "tempDir": "./tmp",
  "sourcePath": "mgmnt/zsh_history"
}

To read the configuration, I first created a case class, imaginatively named Configuration, which has the fields corresponding to JSON attributes:

1
2
3
4
5
6
7
case class Configuration(
  val hosts: List[String],
  val tempDir: String = "./tmp/",
  val sourcePath: String = "~/.zsh_history",
) {
  // ...
}

The class defines some helper methods which are not essential, so I elided them here. Then, there's a companion object, also called Configuration, which handles loading the JSON data and mapping them into Configuration instance. It looks like this:

import com.fasterxml.jackson.databind._
import com.fasterxml.jackson.module.scala.DefaultScalaModule

object Configuration {
  import better.files.File
  import org.joda.time.Instant

  val settingsFile = (File.home / ".mergerc")

  val mapper = new ObjectMapper()
  mapper.registerModule(DefaultScalaModule)

  def loadConfig = mapper.readValue(
    settingsFile.toJava,
    classOf[Configuration]
  )

  if (!settingsFile.exists)
    throw new RuntimeException("No configuration file found!")

  val config = loadConfig()
}

Well, it's still longer and more verbose than a simple JSON.parse() in JavaScript would be, but I have to say - it's not bad, given the statically typed nature of Scala. The magic apparently happens in the ObjectMapper object, which is customized for Scala with the .registerModule(DefaultScalaModule) call. I have no idea how that works - probably via reflection, but I don't know Scala meta-programming well enough to say for sure. Still, all you have to do is define a class with fields of correct types, and you get an instance of that class with correctly parsed values automatically. Not bad.

That's it!

That's basically all the code in the project - there are some additional utilities here and there, but I covered all the essential parts of the project. I use it regularly to merge ZSH history on a number of hosts, currently 8, and it works without a hitch. A single run takes around 30 seconds, while subsequent runs take around 7-8 seconds. Most of the time is spent downloading and uploading files, with parsing, sorting, and dumping merged history taking less than a second. This is for 9 hosts and a history file(s) of around 2.5Mb - not bad I think.

Above all else, though, I learned a lot, about Scala and the JVM, and string encodings on top of that. There were frustrating moments, but overall it was a pleasant and fun journey. I hope you enjoyed reading about it - let me know what you think about the post in the comments.

That's it - thanks for reading!

Comments

Awesome WM and an animated 3x3 grid of virtual desktops

Last updated on:

My new window manager is Awesome

I wrote a few posts in the past about my window manager - I was using StumpWM, which is a WM written in Common Lisp. It's great, and I used it for a long time, but had to switch. Unfortunately, I got a 4k laptop from work, and Stump couldn't handle that - at least not without a lot of work. The fact that Stump draws everything with X APIs (XCB) doesn't make it any easier, too.

So, reluctantly, I was forced to switch to GNOME. It's a surprisingly solid environment, as long as you install a few add-ons and disable most "user friendly" features (I wonder who ever thought the "reversed scroll direction" is "natural"!!)

Unfortunately, GNOME is not an interactively extendable piece of software. It is scriptable with JavaScript (and probably other languages), but it doesn't offer a REPL where you could explore the system from the inside, access and modify all global state, and add or edit functions on the fly. These are important tools, which help customize the software to your needs - a lot faster than without them.

I started looking for a solution. I wanted a reasonably stable, maintained window manager with a (or even built around) REPL - a simple requirement, but it filtered out 99% of the candidates, leaving just three:

Sawfish is scriptable with "a Lisp variant", described as a "mix of Emacs Lisp and Scheme", though I'm not sure how exactly that's supposed to look like. Unfortunately, it looked the least maintained of the bunch, so I decided to pass on it.

XMonad uses Haskell for scripting, which is an interesting choice. I don't know Haskell - I just skimmed a few books on it and played in the REPL, but that's not the level of "knowing" a language - but I could learn. After taking note of this, I went to examine the third option.

As already said in the title, I ultimately chose Awesome WM. My main reason (besides the name) was that it is built around a library of lightweight widgets, which render using Cairo lib, not the antiquated X widgets (like in StumpWM). Furthermore, it was scripted in Lua, a language which I know, and which is also a target for the transpiler I happened to be interested in. The reasonably complete documentation helped, though you can see a few lacking areas.

I will write the rest - how I set up Awesome, explored its library (called "awful"...), re-learned Lua from the ground up, or how I ended up forking the mentioned language, you know, the uninteresting details - in the follow-up posts, so now I just want to share a minor success of coding a complete widget by myself!

3x3 virtual desktop grid

Right, its about virtual desktops. All modern OSes offer the functionality where you can switch to another "desktop" with its own set of windows, then switch back. In some cases changing the desktop is accompanied with an animation (eg. sliding vertically or horizontally), and there's often a "zoomed out" mode for viewing windows from all desktops at once. In most popular implementations, the desktops are chained in a straight line, even without a wraparound.

Awesome's of course has virtual desktops, though it calls them tags: switching to a desktop number 3 makes only the windows tagged with "3" to become visible. The default configuration has ten tags configured, users can change it however they wish. With the larger number of desktops, though, comes another problem: how do you remember what window is on which desktop?

My solution to that problem was, since my early Linux experiences with Enlightenment 0.16, arranging the desktops in a grid. I'm not sure what it is, but there's something about path-finding and spacial metaphor that our brains seem to like a lot... Anyway, Awesome sadly lacked the ability to display a grid of my desktops - the "taglist" is a single row of labels (often numerical), like here:

So the first thing I want to share is that, after a long while, I managed to display a three by three, free floating taglist in Awesome! It was much more troublesome than I expected, due to the dual (schizophrenic) nature of the widget system (X / Cairo) and lack of good docs on Awesome architecture. Well, after a lot of tinkering, I made it! See the screenshot below (on the right).

Well, it was almost perfect, but unfortunately, no matter where I placed it or how I played with opacity, there was always a moment where it displayed over some important details, requiring manual intervention. I understood that, to be fully ideal, it would need to hide and show itself at just the correct moments: show after desktop change (or after key shortcut, or mouse-over), then hide a few seconds later or immediately if clicked on.

This time it was a bit easier, mostly because I already learned most of the API, but also thanks to Lua coroutines. Awesome has no direct support for animations, doesn't use them for anything (that I'm aware of) and apparently is not very interested in them. Fortunately, Awesome implements a timer: a piece of code which can call the callback function after some time, then repeat (or not). That is enough to allow users to implement their own stepping logic. Thanks to Lua coroutines, you can describe your animations as simple functions, wrap them with coroutine and plug straight into a timer. Here's the result of my efforts in action:

The code for this is in the repo on Github (as usual), but if you'd like to use it, ping me first - it's my personal config and I didn't bother with too much cleanup, but I can do it if it's going to be useful to someone.

Comments

Extending Io to add tuple unpacking (aka destructuring bind)

Last updated on:

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 talk 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, including the syntax. 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 JavaScript) and with multiple inheritance. It has very simple syntax, which enables its incredibly powerful and sophisticated 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. 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[4], 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:

1
2
3
4
  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 left-arrow (<-) 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:

1
2
3
4
5
  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[5]:

  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))
      )
      target
  )
  # 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:

1
2
3
4
5
6
7
8
9
  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[6] 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, see below) 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 being evaluated. 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 thanks to 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
3
4
  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 in Iois used for arithmetic operators, string concatenation operators and so on, but it's also used for faking statements, like return, break or yield.

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. setSlot) via OperatorTable object, and then the call is transformed like this:

1
2
3
  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[7] Garbage Collector, low-level co-routines[8] implementation and an interpreter[9].

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[10] 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 an 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));

      Levels_nextMessage(levels);
  }

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:

1
2
3
4
5
6
7
8
  if (IoMessage_argCount(attaching) > 0) { // a(1,2,3) := b ;
    IoState_error_(
      state, msg,
      "compile error: The symbol to the left of %s cannot have arguments.",
      messageName
    );
    return;
  }

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[11]. 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 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[12] 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 the begining):

1
2
3
4
5
6
7
8
9
  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. It goes like this:

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

    return;
  }

Let's start with lines 13-16

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

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:

1
2
3
4
5
    IoMessage *slotNameMessageCopy = IoMessage_deepCopyOf_(attaching);

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

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:

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

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:

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

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:

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

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 (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 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 [13].

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 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 libs/garbagecollector/source. See GC page on Wiki for more info on the whole mark and sweep business.
  • 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.
Comments