Parsing Rebol Data with Lua PEG

I diverted myself from learning lua by working through the stockfetch program as I wanted to test how tricky it would be to read a Rebol data file into a Lua table using Lua's Parsing Expression Grammars (LPeg). I didn't attempt to write an actual conversion tool, just something that would give a good feeling for how difficult it would be to write such a tool.

It is necessary to understand that there really isn't such a thing as a Rebol data file. In Rebol, code is data and data is code. Any syntactically valid Rebol file can be evaluated, if a Rebol file contains functions they will be run. (The same is true of the languages descended from Rebol - Red, Boron and World.) 

Whilst functions are first class values in Lua, I don't think that variables can be treated so in Lua (though I could well be wrong). 

If I am correct, this means that it will only ever be possible to convert a subset of Rebol files to Lua tables.

For my purposes, I felt it was sufficient to confirm that both Rebol objects and blocks could be converted into Lua tables. 

When considering objects, I excluded the possibility of them containing functions or code executed as the object was loaded. For this test, a Rebol object was restricted to be akin to a keyword:value store.

Rebol blocks are ordered series of values, somewhat similar to a Lua table using integer keys.

I also applied the following restrictions for my "proof of concept":

• Words can only be a single letter - a to z
• Values can either be a block, an object or a single digit string - 0 to 9
• Blocks and Objects cannot be empty

Once I started to understand LPeg, I found writing the trial convertor to be quite straightforward. I'm happy with the solution that I came up with as it appears very readable to me (especially compared with regex). I'm sure that it could be improved by someone more familiar with Lua and LPeg than I currently am.

Here's my function:

function reboldata.import (reb)
  local bind = function (...)
    local args = {...}
    local t = {}
    for i = 1, #args, 2 do
      t[args[i]] = args[i + 1] 
    end
    return t
  end
  local End = lpeg.P(-1)
  local Space = lpeg.S(' \n\t')^0
  local OpenBlock = Space * '['
  local CloseBlock = ']' * Space
  local EndString = lpeg.S(' \n\t') + CloseBlock
  local String = Space * lpeg.C(1 - EndString)^1 * Space
  local NotCloseBlock = (1 - CloseBlock)^0
  local Word = lpeg.R('az')
  local GetWord = lpeg.C(Word) * ':' * Space
  local Value = lpeg.R('09')
  local Element = (String + lpeg.V'Block') + lpeg.V'Object'
  local GetWordValue = GetWord * 
                       ((lpeg.C(Value) + lpeg.V'Block') + lpeg.V'Object') * Space
  local ObjectContent = (GetWordValue^0 / bind) + CloseBlock
  local ParseRebol = lpeg.P{
    'PR';
    PR = lpeg.Ct(lpeg.V'BO'),
    BO = (lpeg.V'O' + lpeg.V'B') + End,
    O = (lpeg.V'Object' * lpeg.V'B') + lpeg.V'Object',
    B = lpeg.V'Block' * lpeg.V'BO',
    Object = lpeg.P('make object!' * Space * 
             OpenBlock * ObjectContent * CloseBlock),
    Block = lpeg.Ct(OpenBlock * Element^0 * CloseBlock)
  }
  return lpeg.match(ParseRebol, reb)
end

Full source and tests

Lua Patterns, Red Parse, and Regex

In my Learning Lua project, I needed to extract a four character code from a string. Many languages use a builtin Regex implementation to provide the capability to match and extract patterns from strings. I am also familiar with Red, which like Rebol before it, provides the Parse Dialect (a Domain Specific Language (DSL)) which not only has excellent string matching and extraction features but makes it easy to write further DSLs. 

I found that Lua has another approach. It has a built-in lightweight pattern language, known as Patterns. From what I understand, it was designed to be simpler than Regex both in its "grammar" and its capability. (Lua does have Regex modules available. It also has the very interesting LPeg pattern-matching library, based on Parsing Expression Grammars (PEGs).)

I thought it would be interesting to compare the three approaches, patterns, parse and regex. Here are three versions of a short function to extract the first four consecutive alphabetic characters from a string. The functions return an empty string if there is no match.

First Regex, courtesy of Ruby:

    def parse_line line

      ticker = line.match(/[A-Za-z]{4,4}/)

      if ticker then

        ticker[0]

      else

        ''

      end

    end

Note: 

    I'm no Regex expert, there may well  be a better way, and probably a more Rubyish way too.

Second Parse, courtesy of Red

parse-line: function [line [string!] /local ticker][

alpha: charset [#"A"-#"Z" #"a"-#"z"] parse line [to copy ticker 4 alpha] any [ticker ""] ]

Notes: 

    1. The charset allows you to efficiently define set of characters to be matched.

    2. The parse function apply the rules provided between the []s to the input.

    3. A parse rule can have any number of sub-rules.

    4. Red Parse details.

Finally Patterns, courtesy of Lua

    function stockfetch.parseLine (line)

      local match = string.match(line, '(%a%a%a%a)')

      if match then 

        return match

      else

        return ''

      end

    end

There doesn't seem much to chose between the approaches for such a simple task. The Lua pattern is very readable but you do have to know (or lookup) that %a matches an alphabetic character. The Regex is self-explanatory once you understand Regex syntax. The Red parse rule may seem a little more complicated because it also specifies to where the data are extracted (copy ticker) and has to ensure that the rules cover the whole supplied string (to end).

It will be interesting to see how the three approaches compare with more challenging requirements. Perhaps, I'll be able to add LPeg into the equation too.

Note: I am a strong supporter of and contributor to Red and am highly biased towards its Parse DSL. 

Raspberry Shoes Update

I haven't written anything about Raspberry Shoes in a while. The reason is that Raspberry Shoes still feels a long, long way away.

The route that was most attractive for me was Shoes 4 which is written for JRuby and the SWT cross-platform GUI toolkit. Last time I wrote I was quite optimistic, I had JRuby working on the Raspberry Pi. Shortly before then, the Shoes 4 team announced a pre-release Gem that would have made installing Shoes quite straightforward on Raspberry Pi. However, after installing the Gem I found that the Ruby SWT Gem upon which Shoes 4 relies only installs Intel versions of SWT. It seems there isn't an official ARM version of SWT. So, for the foreseeable future, it is unlikely that Shoes 4 will run on Raspberry Pi.

As an alternative, I installed the Green Shoes Gem. Green Shoes is a version of Shoes that uses the GTK2 GUI toolkit. It didn't work and so far I haven't spent anytime trying to figure out why. That's because Green Shoes is understandably no longer maintained in the light of Shoes 4.

One option that came to mind is that I could build Raspberry Shoes by forking Green Shoes and convert it to use GTK+3 (which, in the long term, I presume will be better supported on Raspberry Pi than GTK2). However, I very much doubt that I have the necessary skill to get it done in the time I have available. (I'm confident that I could do it if I put enough time into it.)

I even had a "if you can't beat them, join them" moment and thought that perhaps taking the easy choice, Python, would be better than trying to use Ruby. Then I saw a couple of Raspberry Pi Python code snippets. They were enough to convince me that Ruby will be much easier for a child to learn.

At the moment, I am undecided on what to do. Another language which can be even easier for beginners and in which I am more fluent than Ruby will be coming to Raspberry Pi soon. The language is Red. It is very highly influenced by Rebol. It is currently at the "alpha" stage and is expected to reach "beta" stage sometime next year. 

In the meantime, I'll try to spend a little time with Ruby and GTK+3 to see if I can come up with something for our seven year-old to follow on from Hello Ruby when it eventually arrives.

64 Bit Integer Arithmetic For Red/System

Red/System is the low-level dialect of the Red Programming Language. It is a compiled language, its datatypes and variables work like C, whereas its syntax is very similar to Red. The Red runtime is written in Red/System and the Red compiler outputs Red/System code (which is then compiled to native code).

The current version of Red/System has been written to meet those two needs and to do little more. Once Version 1.0 of Red is complete, the Red/System compiler will be re-written in Red (the current one is written in Rebol).

Using Red/System, it is very easy to write interfaces to external libraries written in C. There is a slight catch however, integers in Red/System are 32 bit integers and some libraries return 64 bit integers.

I've written a simple 64 bit integer arithmetic library for Red/System to make it easier to deal with such libraries. I expect that Red/System 2 will include built-in support for 64 bit integers so the library reflects its temporary nature.

The main functions are add, subtract, multiply, and divide. I used easy algorithms such as long multiplication and division.  There are a number of supporting functions and macros too.

You can find the library on Github.