Man metalua 0.4

Fabien Fleutot
-

{

hello

}

Reading guide

• Before reading this manual: metalua is based on Lua, so you'll need a minimal level of Lua proficiency. You can probably get away without knowing much about metatables, environments or coroutines, but you need to be at ease with basic flow control, scoping rules, first-class functions, and the whole everything-is-a-table approach.
• Meta-programming in metalua: this chapter exposes the generic principles of static meta-programming: meta-levels in sources, AST representation of code, meta-operators. You need to read this carefully if you plan to write any non-trivial meta-programming code and you've never used languages like, Common Lisp, camlp4 or Converge. If you're familiar with one of these, a cursory look over this chapter might be enough for you.
• Standard meta-programming libraries: these are the tools that will allow you to manipulate code effectively; the more advanced an extension you want to write the more of these you'll want to know.
  • mlp is the dynamically extensible metalua parser. You need to know it if you want to change or extend the language's syntax
  • gg is the grammar generator, the library which lets you manipulate dynamic parsers. You need to know it in order to do anything useful with mlp.
  • match is an extension supporting structural pattern matching (which has almost nothing to do with regular expressions on strings). It's a construct taken from the ML language familly, which lets you manipulate advanced data structures in vrey powerful ways. It's extremely helpful, among others, when working with AST, i.e. for most interesting meta-programs.
  • walk is a code walker generator: smomething akin to a visitor pattern, which will help you to write code analysers or transformers. Whenever you want to find and transform all return statements in an AST, rename some conflicting local variables, check for the presence of nested for loops etc., you'll have to write a code walker, and walk will get you there much faster.
  • hygiene offers hygienic macros, i.e. protects you from accidental variable captures. As opposed to e.g. Scheme, macro writing is not limited to a term rewriting system in metalua, which lets more power to the programmer, but prevents from completely automating macro hygienization. If you wrote an extension and you want to raise it to production-quality, you'll need among others to protect its users from variable captures, and you'll need to hygienize it. If you don't feel like cluttering your code with dozens of gensym calls, you'll want to use the macro hygienizer.
  • dollar: if you wrote a macro, but don't feel the need to give it a dedicated syntax extension, this library will let you call this macro as a regular function call, except that it will be prefixed with a ``$''.
• General purpose libraries: Lua strives at staying minimalist, and does not come with batteries included; you're expected to grab them separately, currently from luaforge, and eventually from a Lua Rocks repository. Metalua needs quite some support to run, and relies on a number of imported and custom-built libraries. Most of them can be reused for many other purposes including yours.
  A whole category of metalua users, who want to use third party libraries rather than reinventing their own wheels, will be primarily interested by these.
  • metalua.runtime: extensions to Lua core libraries: base, table, string.
  • metalua.compiler: mlc offers a consistent interface to metalua compilation and code representation transformers. 'package', 'loadstring', 'dostring', 'loadfile' and 'dofile' are also updated to handle metalua source files.
  • clopts simplifies and unifies the handling of command line options for metalua programs.
  • springs brings together Lua Ring's handling of separate Lua universes with Pluto's communication capabilities.
  • clist offers an extended tables-as-list interface: lists by comprehension � la Haskell or Python, list chunks etc.
  • xglobal makes global variables declaration mandatory, for safer programming, with almost no runtime overhead, and a syntax consistant qith local variables declaration.
  • anaphoric introduces anaphoric control structures, akin to Common Lisp's aif-familly macros.
  • trycatch provides a proper exception system, with reliable finally blocks and exception catching by structural pattern matching.
  • log eases the terminal logging of variables, mainly for those from the Printf-based School of Debugging.
  • types offers dynamic type checking to metalua programs. It supports variable typing as opposed to value typing, and advanced type system features (polymorphism, dependant types etc.).
• Examples and tutorials: this chapter lists a series of tiny meta-programs whose main purpose is didactic, and walks through the detailed implementation of a couple of non-trivial extensions.

Table of Contents

Chapter 1  Meta-programming in metalua

1.1  Concepts

Lua

• a conventional syntax (similar to Pascal's or Ruby's);
• the associative table as basic datatype instead of the list;
• no full continuations (although coroutines are actually one-shot semi-continuations);
• no macro system.

Metalua

Metaprogramming

• The reference manual: http://www.lua.org/manual/5.1
• The first edition of PiL, kindly put online by its author at http://www.lua.org/pil
• A compact reference sheet (grammar and standard libraries) by Enrico Colombini: http://lua-users.org/wiki/LuaShortReference
• Generally speaking, the Lua community wiki (http://lua-users.org/wiki) is invaluable.
• The mailing list (http://www.lua.org/lua-l.html) and the IRC channel (irc://irc.freenode.net/#lua) are populated with a very helpful community.
• You will also find a lot of useful programs and libraries for Lua hosted at http://luaforge.net: various protocol parsers, bindings to 2D/3D native/portable GUI, sound, database drivers...
• A compilation of the community's wisdom will eventually be plubished as ``Lua Gems''; you can already check its ToC at http://www.lua.org/gems

• The couple of syntax extensions offered by Metalua over Lua;
• The two CTMP magic constructs +{...} and -{...};
• The libraries which support CTMP (mainly for syntax extension).

Metalua design philosophy

• Lisp offers a lot of flexibility, at the price of macro-friendly syntax, rather than user-friendly. Besides the overrated problem of getting used to those lots of parentheses, it's all too tempting to mix macros and normal code in Lisp, in a way that doesn't visually stand out; this really doesn't encourage the writing of reusable, mutually compatible libraries. As a result of this extreme flexibility, large scale collaboration doesn't seem to happen, and Lisps lack a de facto comprehensive set of standard libs, besides those included in Common Lisp's specification. Comparisons have been drawn between getting Lispers to work together and herding cats...
  
  
• Macro-systems bolted on existing languages (Template Haskell⁴, CamlP5⁵, MetaML⁶...) tend to be hard to use: the syntax and semantics of these target languages are complex, and make macro writing much harder than necessary. Moreover, for some reason, most of these projects target statically typed languages: although static inference type systems � la Hindley-Milner are extremely powerful tools in many contexts, my intuition is that static types are more of a burden than a help for many macro-friendly problems.
  
  
• Languages built from scratch, such as converge⁷ or Logix⁸, have to bear with the very long (often decade) maturing time required by a programming language. Moreover, they lack the existing libraries and developpers that come with an already succesful language.

• Its compact, clear, orthogonal, powerful semantics, and its approach of giving powerful generic tools rather than ready-made closed features to its users.
• Its excellent supports for runtime metaprogramming.
• Its syntax, despite (or due to its) being very readable and easy to learn, is also extremely simple to parse. This means no extra technology gets in the way of handling syntax (no BNF-like specialized language, no byzantine rules and exceptions). Even more importantly, provided that developers respect a couple of common-sense rules, cohabitation of multiple syntax extensions in a single project is made surprizingly easy.

• Simple things should be easy and look clean: writing simple macros shouldn't require an advanced knowledge of the language's internals. And since we spend 95% of our time not writing macros, the syntax should be optimized for regular code rather than for code generation.
• Good coding practices should be encouraged. Among others, separation between meta-levels must be obvious, so that it stands out when something interesting is going on. Ideally, good code must look clean, and messy code should look ugly.
• However, the language must be an enabler, not handcuffs: it should ensure that users know what they're doing, but it must provide them with all the power they're willing to handle.

1.2  Metalua syntax extensions over Lua

1.2.1  Anonymous functions

1.2.2  Functions as infix operators

1.2.3  Algebraic datataypes

1.2.4  Metalevel shifters

1.3  Data structures

1.3.1  Algebraic Datatypes (ADT)

• a tag (a string, stored in the table field named ``tag'')
• some children, which are either sub-trees, or atomic values (generally strings, numbers or booleans). These children are stored in the array-part⁹ of the table, i.e. with consecutive integers as keys.

Example 1

{ tag="Cons", 1, 
  { tag="Cons", 2, 
    { tag="Cons", 3, 
      { tag="Nil" } } } }

Example 2

• litteral numbers, represented as integers;
• symbolic variables, represented by the string of their symbol;
• formulae, i.e. numbers, variables an/or sub-formulae combined by operators. Such a formula is represented by the symbol of its operator, and the sub-formulae / numbers / variables it operates on.

{ tag="Formula", "Addition", 
  { tag="Formula", "Exponent", 
    { tag="Variable", "e" },
    { tag="Formula", "Multiplication", 
      { tag="Variable", "i" },
      { tag="Variable", "pi" } } },
  { tag="Number", 1 } }

Syntax

• The tag can be put in front of the table, prefixed with a backquote. For instance, { tag = "Cons", car, cdr } can be abbreviated as `Cons{ car, cdr }.
• If the table contains nothing but a tag, the braces can be omitted. Therefore, { tag = "Nil" } can be abbreviated as `Nil (although `Nil{ } is also legal).
• If there is only one element in the table besides the tag, and this element is a literal number or a literal string, braces can be omitted. Therefore { tag = "Foo", "Bar" } can be abbreviated as `Foo "bar".

`Formula{ "Addition", 
   `Formula"{ "Exponent", 
      `Variable "e",
      `Formula{ "Multiplication", 
                `Variable "i",
                `Variable "pi" } },
   `Number 1 }

`Op{ "add", `Number 1,
     `Op{ "pow", `Id "e", 
          `Op{ "mul", `Id "i", `Id "pi" } } }

1.3.2  Abstract Syntax Trees (AST)

Example

1.3.3  AST �� Lua source translation

Expressions

Number constants

String constants

Variable names

Other atomic values

• nil is encoded as `Nil¹¹;
• false is encoded as `False;
• true is encoded as `True;
• ... is encoded as `Dots.

Table constructors

• the AST of an expression, for array-part entries without an explicit associated key;
• a pair of expression AST, tagged with Pair: the first expression AST represents a key, and the second represents the value associated to this key.

Examples

• The empty table { } is represented as `Table{ };
  
  
• {1, 2, "a"} is represented as:
  `Table{ `Number 1, `Number 2, `String "a" };
  
  
• {x=1, y=2} is syntax sugar for {["x"]=1, ["y"]=2}, and is represented by `Table{ `Pair{ `String "x", `Number 1 }, `Pair{ `String "y", `Number 2} };
  
  
• indexed and non-indexed entries can be mixed: { 1, [100]="foo", 3} is represented as `Table{ `Number 1, `Pair{ `Number 100, `String "foo"}, `Number 3 };

Binary Operators

Examples

• 2+2 is represented as `Op{ 'add', `Number 2, `Number 2 };
• 1+2*3 is represented as:
  

  `Op{ 'add', `Number 1, 
       `Op{ 'mul', `Number 2, `Number 3 } }
  

• (1+2)*3 is represented as:
  

  `Op{ 'mul, `Op{ 'add', `Number 1, `Number 2 },
       `Number 3 } }
  

  `Op{ 'mul', `Op{ 'add', `Number 1, `Number 2 }, `Number 3 }
• x>=1 and x<42 is represented as:
  

  `Op{ 'and', `Op{ 'le', `Number  1, `Id "x" },
              `Op{ 'lt', `Id "x", `Number 42 } }
  
  

Unary Operators

Examples

• -x is represented as `Op{ `Sub, `Id "x" };
• -(1+2) is represented as:
  `Op{ `Sub, `Op{ `Add, `Number 1, `Number 2 } }
• #x is represented as `Op{ `Len, `Id "x" }

Indexed access

Examples

• x[3] is represented as `Index{ `Id "x", `Number 3 };
• x[3][5] is represented as:
  `Index{ `Index{ `Id "x", `Number 3 }, `Number 5 }
• x.y is syntax sugar for x["y"], and is represented as:
  `Index{ `Id "x", `String "y" }

Function call

Examples

• f() is represented as `Call{ `Id "f" };
• f(x, 1) is represented as `Call{ `Id "f", `Id "x", `Number 1 };
• f(x, ...) is represented as `Call{ `Id "f", `Id "x", `Dots }.

Method invocation

Examples

• o:f() is represented as `Invoke{ `Id "o", String "f" };
• o:f(x, 1) is represented as:
  `Invoke{ `Id "o", `String "f", `Id "x", `Number 1 };
• o:f(x, ...) is represented as:
  `Invoke{ `Id "o", `String "f", `Id "x", `Dots };

Function definition

Examples

• function (x) return x end is represented as:
  `Function{ { `Id x } { `Return{ `Id "x" } } };
  
  
• function (x, y) foo(x); bar(y) end is represented as:

  `Function{ { `Id x, `Id y } 
             { `Call{ `Id "foo", `Id "x" },
               `Call{ `Id "bar", `Id "y" } } }
  

• function (fmt, ...) print (string.format (fmt, ...)) end is represented as:

  `Function{ { `Id "fmt", `Dots } 
             { `Call{ `Id "print",
                      `Call{ `Index{ `Id "string",
                                     `String "format" }, 
                             `Id "fmt", 
                             `Dots } } } }
  

  
  
  
• function f (x) return x end is not an expression, but a statement: it is actually syntax sugar for the assignment f = function (x) return x end, and as such, is represented as:

  `Let{ { `Id "f" }, 
        { `Function{ {`Id 'x'} {`Return{`Id 'x'} } } } }
  

  (see assignment in the statements subsection for more details);

Parentheses

{ `Localrec{ { `Id "f" },  
             { `Function{ { },
                          `Return{ `Number 1,
                                   `Number 2,
                                   `Number 3 } } } },
  `Return{ `Table{ `Paren{ `Call{ `Id "f" } } } } }

Statements

Assignment

Examples

• x[1]=2 is represented as:
  `Set{ { `Index{ `Id "x", `Number 1 } }, { `Number 2 } };
  
  
• a, b = 1, 2 is represented as:
  `Set{ { `Id "a",`Id "b" }, { `Number 1, `Number 2 } };
  
  
• a = 1, 2, 3 is represented as:
  `Set{ { `Id "a" }, { `Number 1, `Number 2, `Number 3 } };
  
  
• function f(x) return x end is syntax sugar for:
  f = function (x) return x end. As such, is represented as:
  

  `Set{ { `Id "f" }, 
        { `Function{ {`Id 'x'}  {`Return{ `Id "x" } } } } }
  

  
  
  
• function o:m(x) return x end is syntax sugar for:
  o["f"] = function (self, x) return x end, and as such, is represented as:
  

  `Set{ { `Index{ `Id "o", `String "f" } }, 
        { `Function{ { `Id "self, "`Id x } 
                     { `Return{ `Id "x" } } } } }
  

Local declaration

Examples

• local x=2 is represented as:
  `Local{ { `Id "x" }, { `Number 2 } };
  
  
• local a, b is represented as:
  `Local{ { `Id "a",`Id "b" }, { } };

Recursive local declaration

`Localrec{ { `Id "f" }, 
           { `Function{ { `Id x } 
                        { `Call{ `Id "f", `Id "x" } } } } }

Function calls and method invocations

Blocks and pseudo-statements

Example

{ `Call{ `Id "foo", `Id "x" },
  `Call{ `Id "bar", `Id "y" },
  `Return{ `Id "x", `Id "y" } }

Do statement

Example

`Do{ `Call{ `Id "foo", `Id "x" },
     `Call{ `Id "bar", `Id "y" },
     `Return{ `Id "x", `Id "y" } }

While statement

Repeat statement

For statements

for x1, x2... in e1, e2... do
  <foo>;
  <bar>;
  ...
end

If statements

Examples

• if <foo> then <bar>; <baz> end is represented as:
  `If{ <foo>, { <bar>, <baz> } };
  
  
• if <foo> then <bar1> else <bar2>; <baz2> end is represented as: `If{ <foo>, { <bar1> }, { <bar2>, <baz2> } };
  
  
• if <foo1> then <bar1>; <baz1> elseif <foo2> then <bar2>; <baz2> end
  is represented as:
  `If{ <foo1>, { <bar1>, <baz1> }, <foo2>,{ <bar2>, <baz2> } };
  
  

• if     <foo1> then <bar1>; <baz1> 
  elseif <foo2> then <bar2>; <baz2> 
  else               <bar3>; <baz3> end+ 
  

  is represented as:

  `If{ <foo1>, { <bar1>, <baz1> }, 
       <foo2>, { <bar2>, <baz2> },
               { <bar3>, <baz3> } }
  

Breaks and returns

Example

Extensions with no syntax

Goto and Labels

Statements in expressions

1.4  Splicing and quoting

1.4.1  Quasi-quoting

X = +{ 2 + 2 }
Y = +{ four = -{ X } }

-- As a single quote:
Y = +{stat: four = 2+2 }
-- Without any quote, directly as an AST:
Y = `Let{ { `Id "four" }, { `Op{ `Add, `Number 2, `Number 2 } } }
-- Various mixes of direct AST and quotes:
X = +{ 2+2 };                          Y = +{stat: four = -{ X } }
X = `Op{ `Add, +{2}, +{2} };           Y = +{stat: four = -{ X } }
X = `Op{ `Add, `Number 2, `Number 2 }; Y = +{stat: four = -{ X } }
Y = +{stat: four = -{ `Op{ `Add, `Number 2, `Number 2 } } }
Y = +{stat: four = -{ +{ 2+2 } } }
Y = `Let{ { `Id "four" }, { +{ 2+2 } } }
-- Nested quotes and splices cancel each other:
Y = +{stat: four = -{ +{ -{ +{ -{ +{ -{ +{ 2+2 } } } } } } } } }

Y = +{stat: four = -{ block: 
                      local two=`Number 2
                      return `Op{ 'add', two, two } } }

1.4.2  Splicing

                  ______               ________
+-----------+    /      \    +---+    /        \    +--------+
|SOURCE FILE|-->< Parser >-->|AST|-->< Compiler >-->|BYTECODE|  
+-----------+    \______/    +---+    \________/    +--------+

                                                     +--------+
                  ______               ________   +->|BYTECODE|  
+-----------+    /      \    +---+    /        \  |  +--------+
|SOURCE FILE|-->< Parser >-->|AST|-->< Compiler >-+
+-----------+    \______/    +-^-+    \________/  |  +--------+
                              /|\      ________   +->|BYTECODE|  
                               |      /        \     +---+----+
                               +-----<   Eval   ><-------+
                                      \________/

fabien@macfabien$ cat sample.mlua
-{block: print "META HELLO"
         return +{ print "GENERATED HELLO" } }
print "NORMAL HELLO"

fabien@macfabien$ metalua -v sample.mlua -o sample.luac
[ Param "sample.mlua" considered as a source file ]
[ Compiling `File "sample.mlua" ]
META HELLO
[ Saving to file "sample.luac" ]
[ Done ]
fabien@macfabien$ lua sample.luac
GENERATED HELLO
NORMAL HELLO
fabien@macfabien$ _

• The code inside the splice is parsed and compiled separately;
• it is executed: the call to print "META HELLO" is performed, and the AST representing
  print "GENERATED HELLO" is generated and returned;
• in the AST generated from the source code, the splice is replaced by the AST representing
  print "GENERATED HELLO". Therefore, what is passed to the compiler is the AST representing
  print "GENERATED HELLO"; print "NORMAL HELLO".

1.4.3  A couple of simple concrete examples

ternary choice operator