Tuesday, January 22, 2008

A 'simple' extension with a catch

UPDATE: The extension sample presented in this post has been completed, debugged and included in metalua 0.4 There are a variety of preprocessor projects targeting Lua, and some people don't easily get the point of metalua, when there are some simpler tools that seem to addresss similar issues. I'm not going to explain again what's meta-programming, why it's an intrinsically complex job, and why although not so simple, metalua is IMO the simplest design that allows to write *usable* extensions. Instead, I'll walk through the design of a seemingly simple extension, and show where hides that intrinsic complexity. One of the most current thing you'll want to do, when you have a Lua preprocessor, is to build a decent exception catching syntax. Lua, as usual, has the underlying meta-mechanism, a function pcall(f, args...) which will try to evaluate f(args), and return either 'true' with f's results on success, or 'false' with an error message. Since error messages are not limited to strings in Lua, you have everything it takes to build an exception handling system, except a decent syntax. However, my final try-catch extension takes 70 lines of code, which is a lot for such a trivial syntax sugar issue. Why? At first, it really seems trivial. We want the following transformation:
-- Syntax sugar:
catch $X ->

-- Developped version:
  local status, $x = pcall(function() $FOOBAR end)
  if not status then $EXCEPTION_HANDLING

-- Metalua macro doing this:
function trycatch_builder(x)
  local try_block, exn_name, catch_block = unpack(x)
  return +{ stat: do
     local status, -{exn_name} = pcall(function() -{try_block} end)
     if not status then -{catch_block} end
  end }

mlp.lexer:add{ "try", "catch", "end" }     -- new keywords.
mlp.stat:add{ "try", mlp.block, "catch", mlp.id, "->", mlp.block, "end",
             builder = trycatch_builder } -- new statement.
This almost works, which is worse than not working at all. Metalua extensions are first-class, i.e. there's nothing that distinguishes them from regular language constructs. This means that if the extensions aren't as robust as the rest of the language, the whole language is deemed unreliable, and since people can't rely on it, they go back to Perl or COBOL: you really want to trust your compiler when you're doing bugs on your own. (MS-Windows, although having its fair share of own bugs, faces an issue similar to poor macros ruining the compiler's reputation: it is often accused of instabilities actually caused by poorly written third party device drivers). With the macro above, what happens if the user puts a return statement in the block? Try to expand the following:
function f()
     return 42
  catch x -> print("An error occured: "..x) end
"return 42" will return from the pcalled function, not from f() has the user clearly intended. No erro will be detected, but 42 is lost (in the variable exn_name actually), and f won't return despite what the user expected. So already in this very simple macro, we need:
  • either to detect the presence of some return statements in the try-block, and refuse to compile if we find one;
  • or, if we want the macro to be usable, to catch them and change them into something smarter.
We'll adopt the latter approach, of course. That's the point of having a meta-programming system which groks the code it manipulates. Here we go, with the "walk" library, applying our code transformation to all return statements in the try-block. If we do that, however, we're screwed another way: if there's a local function in the try-block which has some returns of its own, we must not touch these. So what we're looking for are the return statements that are in the try-block, but not in a `Function{ } sub-node. The walk library lets us do that:
local function d(x)
  match x with
  | `Return{...}   -> transform_return_statement(x); return 'break'
  | `Function{...} -> return 'break'
  | _ -> -- pass
replace_returns = |x| walk.block({stat={down=d}, expr={down=d}}, x)
Now, this could work. We're moving on to an essential feature of a proper error handling construct: the "finally" block. This block of code must be executed no matter what: if there's an error, if there isn't, if a return prematurely ends the execution... The hard job is already done, since we already catch errors and returns. It's just easy meta-programming. An trap we might still fall in, though, is that the code in the "catch" part of the statement can also fail, and that it wouldn't be an excuse not to run the finally-block. So we pcall() the catch-block, parse it to transform rogue returns in it go through the finally-block no matter what, then re-throw any error that might have been caught in the catch-block. The transformation will now look like this:
-- Syntactical version:
catch $EXN_NAME ->

-- Transformed version
  local returned_values = nil
  local try_success, $EXN_NAME =
     pcall(function() $TRY_BLOCK_WITH_PARSED_RETURNS end)
  local catch_success, catch_error
  if not user_success then
     catch_success, catch_error =
        pcall(function() $CATCH_BLOCK_WITH_PARSED_RETURNS end)
  if not user_success and not catch_success then
     error (catch_error)
  if returned_values then
     return unpack(returned_values)

-- In the code above, _PARSED_RETURNS means that "return $RESULTS"
-- is replaced with "returned_values = { $RESULTS }; return"
This code almost works; but in the transformed version above, I've introduced four local variables that might capture user variables, so if the system doesn't support hygienic macros, I'm going to have to splice plenty of gensym()s in the (already complex) developped code quasi-quote. Moreover, this code expects standard functions pcall(), error() and unpack() to be accessible. If the user calls the macro in a place where they're shadowed by homonym local variables, it will barf at runtime in hard to predict (and understand) ways. Finally, a last irritatingly missing feature of this macro is that I've got only one catch-block per macro, which catches every errors. I want to be able to choose which errors I catch and which I let go through. Since I've got better things to do than reinventing the wheel, and since there's a 'match' extension which does a good job of selecting actions to execute depending on some term's structure, I'll just reuse its code to match against the error caught. I authorize several catch cases (by directly reusing match's parser), and if none of them catches the error, then the finally-block is run and the error is re-thrown. I'm not going to describe the detail of the required changes, but the code is in the repository:

Trycatch extension Usage samples

Now to come back to preprocessors: for the extension described above, here's the whole parser extension code:
mlp.lexer:add{ 'try', 'catch', 'finally', '->' }
mlp.block.terminators:add{ 'catch', 'finally' }
table.insert(match_cases_list_parser.terminators, 'finally')

  gg.onkeyword{ 'catch', match_cases_list_parser },
  gg.onkeyword{ 'finally', mlp.block },
  builder = trycatch_builder }
That's it, the syntax-tweaking part of the extension represent 10 lines of code, all the rest is about really describing what the macro must do. You might count another 10 lines for match_cases_list_parser(), defined in the 'match' extension. So, granted, you need to know the basics of mlp (the metalua parser), and some of the half-dozen functions in gg API (the grammar generator); but if you think that's a significant part of the macro writing issues, you've probably overlooked amny other, far more complex difficulties.