dabbling with metacompilers

Lately, I've been reading about metacompilers, and I have to say it's a really impressive piece of technology.  A compiler that can read high level descriptions of grammars to generate other compilers, and it can generate itself. And once you have a description of itself, you can keep tweaking both syntax and semantics using a two step compilation.

It all started in this page when I saw what seemed a fine tutorial with some lua code as example.  I read the code a few times and the amusement was bigger the more I understood what was all that about.  There are very few resources on this technique on the web, so the chances of having to understand everything by myself were big. Btw, the original paper from Schorre is here

Big plans

 While practicing with it I tried to write a parser for lua, because , as you know, lua syntax is quite simple. The first problem was that most syntax descriptions out there are in ebnf... So I thought I should use metaII to write a stepping stone compiler that would undesrtand ebnf, and then feed it the lua syntax. And then I would be happy and have my utterly useless lua parser.

Problems 

MetaII has its own problems, like no backtracking, and really poor error handling. so your parsing either fails or succeeds, but you have notmuch info where or why....

The no backtracking issue is a big one, as ebnf syntax is difficult to convert to a dfa-like grammar. I kept falling into infinite left recursions and dying out of 'stack limit reached'.

Slow Start

So I wiped everything and went back to the basics and started by doing really stupid changes to the metaII syntax. For now I've added comments to it. And I still have the ebnf branch 'alive', so we'll see if I can manage to do something with it.


It's nice I only had to add support for .line, comment and accept comment in place of a rule. It's worth noting that the syntax approach of the compiler makes it easy to have comments in place of full rules, but it would be more complex to have 'line oriented' parsing rules instead of syntax ones. Btw, the only change in the runtime is to add

 local function parseCMT() return read(match("^[^\n]*")) end

More reading

Since I started this adventure, I've read Alessandro Warth Phd about Ometa (I heard about it many many times, but now finally I understand it), and read this metacompilers tutorial on and off. So even with the not-so-much-success situation, the learning is there :)

The end?

Probably no, but I wanted just to write some of the progress in case anyone wants to join me in the quest.

TIL: ediff-revision

When editing a file in some git branch I often want to take a quick look at the same file in other branch (usually master).  I always did it by

 git diff HEAD master -- file.rb 

but today I discovered there's an emacs way to do it.

 M-x ediff-revision

. it asks you for a file (defaults to the current one), and two branches. And that's it!

entr: a suckless inotify-tools

Another little tool I'm going to accomodate in ~/bin.

Entr  just runs commands when a file changes.  Dead simple, and the usage is like:

ls -d * | entr make

It runs on Mac, Linux and BSDs , and it's 500 lines of C.  Simple tools that do just one thing.

+1

Continuations as accumulators

Some months ago I read The Little Schemer, an amazing book that guides through many functional programming concepts in a very different way to other books.

To me, by far the most challenging part of the book whas that exercise in page 137 which uses a continuation as an accumulator. I remember being hours staring at it thinking "WTF?". In fact I also remembered that in SICP there was a code example (in the compiler chapter IIRC) that used this style of programming, and also got me puzzled, and I ended up letting it go, and continuing reading (after some time staring at it also).

Months after TLS and years after SICP, I'm reading Concepts, Techniques, and Models of Computer Programming (CTM), and at some point it talks about recursion, and accumulators. At the point it starts explaining multiple accumulators, I had an 'aha' moment, closing the multirember&co problem. In fact CTM doesn't talk about CPS (at least in that part). But somehow intuitively they're talking about the same concept.

def odd_even_part(l, &block)
  if l.empty?
    yield([], [])
  elsif l[0].even?
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds, evens + [l[0]])
    end
  else
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds + [l[0]], evens)
    end
  end
end

odd_even_part([1,2,3,4]) do |odds, evens|
  puts "odds => #{odds}"
  puts "evens => #{evens}"
end

I decided to reimplement a variant of it in ruby. Now that I look at it, it's super simple... I guess some things just need time to settle.

Here are some related links, talking about the technique or explanations of the original problem.

Linting guix packages

Guix is getting more mature every day (It's probably going to beta soonish).  One of the commands it got 'recently' is guix lint.

Once you write a package definition you want to know if it complies with guix standards. Let's try guix lint.

1. Write package definition.
2. Put the definition into a guix checkout (not your running guix).
3. run 'guix environment guix'.
4. cd to the checkout directory.
5. ./bootstrap && ./configure --localstatedir=/var --prefix= && make
6. ./pre-inst-env guix lint my-package
7.  If you get an 'ERROR: missing interface for module (gnutls)', means that you need to install gnutls. 'guix package -i gnutls'
8. After that, you can finally run 'guix lint my-package', and it'll tell you if you have any obvious failures or warnings in your definition.

dash docset for nginx lua

Here's a quick hack I wrote to fetch the reference doc for nginx lua module and convert it to a dash docset. Which I view using our beloved helm-dash.

Quick, and kinda easy.  It's totally hackish in the way that I'm parsing HTML with regexps. Not even recursive regexps.....

But the thing is that this html is generated by markdown, and as it's fetching for a very concrete type of lines, they are all formatted the same way.

Another option (less hackish but for this concrete case, equally fragile) is using xmlstarlet. The code is also in the import.sh file (for reference).

So here's the kidd/HttpLuaModule.docset repo.

Improving Lua support in etags

It seems it's Lua time again!

So for my new project I'm starting in openresty+lua, I needed some kind of support for tags. Lua is a very simple language syntaxwise (it's whole grammar fits in a screen of code).

Etags support is quite poor, in fact, if you read the emacs-devel message when it got added, you'll see how basic is it.

+ * Lua tag functions
+ *  look for function, local function.
+ */
+
+static void
+Lua_functions (inf)
+     FILE *inf;
+{
+  register char *bp;
+
+  LOOP_ON_INPUT_LINES (inf, lb, bp)
+    {
+      if (bp[0] != 'f' && bp[0] != 'l')
+       continue;
+
+      LOOKING_AT (bp, "local");
+
+      if (LOOKING_AT (bp, "function"))
+       get_tag (bp, NULL);
     }
 }

The regex version of this would be:   /^(local)?\s+function\s+(\w)/ .

So I wanted to add support for lines not in the beginning, and also to add support for things like

local foo = function (p1, p2) .... end

So it turned out to not be very difficult to augment etags to do that.

tags:
 etags --language=lua --regex='/.*\([^. \t]\)*[ \t]*=[ \t]*function/\1/' \
 --regex='/.*\(local\|\)[ \t][ \t]*function[ \t]\([^ \t(]*\)[ \t]*(/\2/'  **/*lua

Just adding this to the Makefile allows me to catch the other forms of lua functions. Again, regex to the rescue! :)