Tales of Code, Packets and Programming

LAL: Verifying magic squares

13 Apr 2016

In this post I want to informally introduce a project that I'm currently working on. From time to time I like to solve problems presented on r/dailyprogrammer on reddit. In this case the easy verification of 3x3 magic squares.

First let me post the code:

(begin
    (define-global print)
    (define-global tostring)
    (define-global table)

    (define T1 [
        3 5 7
        8 1 6
        4 9 2 ]) ; is not a magic square
    (define T2 [
        8 1 6
        3 5 7
        4 9 2 ]) ; is a magic square
    (define T3 [
        3 5 7
        8 1 6
        4 9 2 ]) ; no magic square
    (define T4 [
        2 7 6
        9 5 1
        4 3 8 ]) ; is a magic square

    (define (cell lst x y)
        (@(+ (* x 3) y) lst))

    (define (sum-direction lst start dir)
        (let ((cx (@0 start))
              (cy (@1 start))
              (sum 0))
            (for (i 0 2)
                (set! sum (+ sum (cell lst cx cy)))
                (set! cx  (+ cx (@0 dir)))
                (set! cy  (+ cy (@1 dir))))
            sum))

    (define (all-eq-to list item)
        (do-each (l list)
            (when (!= l item)
                (return #f)))
        #t)

    (define (test-all-dirs lst)
        (let ((solutions [])
              (add       (lambda (sum) (.insert table solutions sum))))
            (add (sum-direction lst [0 0] [0 1]))
            (add (sum-direction lst [1 0] [0 1]))
            (add (sum-direction lst [2 0] [0 1]))

            (add (sum-direction lst [0 0] [1 1]))
            (add (sum-direction lst [0 2] [1 -1]))

            (add (sum-direction lst [0 0] [1 0]))
            (add (sum-direction lst [0 1] [1 0]))
            (add (sum-direction lst [0 2] [1 0]))
            (all-eq-to solutions 15)))
    (print (write [
        (test-all-dirs T1)
        (test-all-dirs T2)
        (test-all-dirs T3)
        (test-all-dirs T4)
    ])))

So, lets discuss what all this is about. First, what is LAL? LAL is a Scheme inspired Lisp dialect that compiles down to Lua code. There are other projects out there, that compile down to Lua, but this one sets different requirements which I will maybe report about in a different post.

The Output of the Program is:

(#false #true #false #true)

Anyone who knows Scheme should be able to make at least a little bit of sense of the above code. Ok, there are some special forms that are not yet explained, like define-global, @, for and do-each.

define-macro is also not really explained, but it should be pretty obvious for someone with Lisp/Scheme experience. (No, LAL does not have hygienic macros). So, to look at the generated Lua code, lets define a macro:

(define-macro (print-lua-code x)
    (print (compile-to-lua x))
    x)

compile-to-lua is a special form, that compiles the value as LAL expression and returns the Lua-Code as string. Now we look at the code that defines cell:

(print-lua-code
    (define (cell lst x y)
        (@(+ (* x 3) y) lst)))

The string that is printed will be a pretty formatted piece of Lua code like this:

local cell; cell = (function (lst, x, y)
    return ((lst)[((x * 3) + y) + 1]);
end);

As you might have guessed, @ is the table/list accessing operator for numeric indices. LAL lists/arrays are zero based, unlike the Lua 1 based arrays/tables. This is one of the few things with Lua that always bugged me a bit.

The resulting code is quite readable, which is a feature that I built in for easier debugging. Sadly Lua does not have #line or #file pragmas to adjust it's error reporting. And I didn't want to make the compiler output unreadable by cramming stuff into single lines that don't belong there. It's also quite complex in this case to do that properly.

Now, lets look at the definition of sum-direction:

(define (sum-direction lst start dir)
    (let ((cx (@0 start))
          (cy (@1 start))
          (sum 0))
        (for (i 0 2)
            (set! sum (+ sum (cell lst cx cy)))
            (set! cx  (+ cx (@0 dir)))
            (set! cy  (+ cy (@1 dir))))
        sum))

Compiles to this Lua code:

local sum_direction; sum_direction = (function (lst, start, dir)
    local _lal_s1;
    do
        local cx; cx = ((start)[1]);
        local cy; cy = ((start)[2]);
        local sum; sum = 0;
        for i = 0, 2 do
            sum = (sum + cell(lst,cx,cy));
            cx = (cx + ((dir)[1]));
            cy = (cy + ((dir)[2]));
        end;
        return sum;
    end;
end);

You might notice, variable names like a-b get translated into a_b as Lua does not support - in identifiers. When writing the compiler I spent extra effort to make the output as natural as possible. The idea behind that is, that I wanted to have the same performance trade offs as I would have when writing Lua directly.

This is something that most Lisp-In-Lua interpreters or compilers completely throw away. Either they represent Lisp lists as linked lists with pairs that are made of tables with two elements. Which is of course a major performance hit, as neither the Lua GC nor the table data structure was built for this.

Other compilers usually represent any scope or expression as (function () ... end)() which is another huge performance hit and is entirely unnecessary. Those implementations also lose the proper tail call optimization that Lua provides. LAL tracks tail contexts and properly places a return f() where it belongs without any temporary variables between the call and the return. Care has also been taken to allow (return ...) in every possible place, like Scheme would allow it. You can't just translate them directly into Lua, as Lua throws errors around if you have any dead code behind a return.

LAL uses Lua tables as data structure for the code and data. Lisp is about processing lists, so why not make it naturally use Lua tables for these lists. This will come with the least performance impact and make the resulting performance more predictable for the developer. Yes, we lose the elegance of Scheme/Lisp pairs. But we gain the expressiveness of Scheme/Lisp, combined with Lisp macros with all the benefits of Lua. It's easy to embed into any C/C++ project and an adequately fast scripting language implementation while maintaining a small footprint.

At the time of this writing, LAL is still not finished enough to release it to the public. It's bound to some of the special API of the embedded Lua interpreter and I want to make LAL more portable to common Lua versions out there (LuaJIT and Lua 5.2/5.3 possibly).