junk/hygienic.lua

   1 ----------------------------------------------------------------------
   2 -- Metalua:  $Id$
   3 --
   4 -- Summary: Hygienic macro facility for Metalua
   5 --
   6 ----------------------------------------------------------------------
   7 --
   8 -- Copyright (c) 2006, Fabien Fleutot <metalua@gmail.com>.
   9 --
  10 -- This software is released under the MIT Licence, see licence.txt
  11 -- for details.
  12 --
  13 --------------------------------------------------------------------------------
  14 --
  15 -- =============
  16 -- W A R N I N G
  17 -- =============
  18 --
  19 -- THIS IS AN OLD NAIVE IMPLEMENTATION. IT'S PARATIAL (NO HYGIENE WRT OUTSIDE)
  20 -- AND WRITTEN FROM SCRATCH WITH PATTERN MATCHING. MUST BE DONE WITH A WALKER.
  21 --
  22 -- Traditional macros carry a well-known pitfall, called variable capture:
  23 -- when pasting a piece of source code A into another code B, if B bonds some
  24 -- variables used by A, then the meaning of A is modified in a way probably
  25 -- not intended by the user.
  26 --
  27 -- Example:
  28 -- A = +{ n = 5 }
  29 -- B = +{ local n=3; -{ A } }
  30 --
  31 -- In this example, [n] in [A] will be captured by the local variable declared
  32 -- by [B], and this is probably a bug.
  33 --
  34 -- Notice that this also exists in C. Typical example:
  35 --
  36 -- #define swap (type, a, b) do { type tmp=a; a=b; b=tmp } while(0)
  37 -- void f() {
  38 --   int tmp=1, a=2;
  39 --   swap (int, tmp, a); // won't work, [tmp] is captured in the macro
  40 -- }
  41 --
  42 -- We can fix this by making sure that all local variables and parameters
  43 -- created by [B] have fresh names. [mlp.gensym()] produces guaranteed-to-be-unique
  44 -- variable names; we use it to replace all local var names declarations and
  45 -- occurences in [B] by such fresh names.
  46 --
  47 -- Such macros which are guaranteed not to capture any variable are called
  48 -- hygienic macros. By extension, an AST guaranteed not to contain capturing
  49 -- variables is called an hygienic AST.
  50 --
  51 -- We implement here some functions which make sure that an AST is hygienic:
  52 --
  53 -- - [hygienize_stat (ast)] for statement AST;
  54 -- - [hygienize_stat (ast)] for statement block AST;
  55 -- - [hygienize_expr (ast)] for expression AST;
  56 --
  57 -- This sample deconstructs AST by structural pattern matching, which is
  58 -- supported by Metalua extension "match.lua"
  59 --
  60 --------------------------------------------------------------------------------
  61
  62 -{ extension "match" }
  63
  64 require "std"
  65
  66 local clone_ctx = std.shallow_copy
  67
  68 --------------------------------------------------------------------------------
  69 -- Tag tables: these allow [hygienize] to decide whether an AST is
  70 -- an expression, a statement, or something which isn't changed by
  71 -- alpha renaming.
  72 --------------------------------------------------------------------------------
  73 local stat_tags = {
  74    Do       = true,   Let      = true,
  75    While    = true,   Repeat   = true,
  76    If       = true,   Fornum   = true,
  77    Forin    = true,   Local    = true,
  78    Localrec = true,   Return   = true }
  79
  80 local expr_tags = {
  81    Function = true,   Table    = true,
  82    Op       = true,   Call     = true,
  83    Method   = true,   Index    = true }
  84
  85 local neutral_tags = {
  86    String = true,   Number = true,
  87    True   = true,   False  = true,
  88    Dots   = true,   Break  = true,
  89    Id     = true }
  90
  91 --------------------------------------------------------------------------------
  92 -- Choose the relevant [hygienize_xxx()] function according to the AST's tag
  93 -- and the tables above.
  94 --------------------------------------------------------------------------------
  95 function hygienize (ast)
  96    if not ast.tag           then hygienize_block (ast)
  97    elseif neutral_tags[ast.tag] then -- pass
  98    elseif stat_tags[ast.tag]    then hygienize_stat (ast)
  99    elseif expr_tags[ast.tag]    then hygienize_expr (ast)
 100    else error "Unrecognized AST" end
 101    return ast
 102 end
 103
 104 if mlp then
 105    -- Add hygienic parsers for quotes
 106    mlp.hexpr  = hygienize `o` mlp.expr
 107    mlp.hstat  = hygienize `o` mlp.stat
 108    mlp.hblock = hygienize `o` mlp.block
 109 end
 110
 111 --------------------------------------------------------------------------------
 112 -- Make a statement AST hygienic. The optional [ctx] parameter is a
 113 -- [old_name -> new_name] map, which holds variable name substitutions
 114 -- to perform.
 115 --------------------------------------------------------------------------------
 116 function hygienize_stat (ast, ctx)
 117    if not ctx then ctx = { } end
 118    match ast with
 119    | { ... } if not ast.tag -> hygienize_block (ast, ctx)
 120    | `Do{ ... } -> hygienize_block (ast, clone_ctx (ctx))
 121
 122    | `Let{ vars, vals } ->
 123       hygienize_expr_list (vars, ctx)
 124       hygienize_expr_list (vals, ctx)
 125
 126    | `While{ cond, block } ->
 127       hygienize_expr (cond, ctx)
 128       -- use a clone of [ctx], since the block has a separate scope
 129       hygienize_block (ast, clone_ctx (ctx))
 130
 131    | `Repeat{ block, cond } ->
 132       -- use a clone of [ctx], since the block has a separate scope.
 133       -- Notice that the condition in [repeat ... until] is evaluated
 134       -- inside the block's scope, i.e. with [inner_ctx] rather than [ctx].
 135       local inner_ctx = clone_ctx (ctx)
 136       hygienize_block (ast, inner_ctx)
 137       hygienize (cond, inner_ctx)
 138
 139    | `If{ ... } ->
 140       for i=1, #ast-1, 2 do
 141          hygienize_expr (ast[i], ctx) -- condtion
 142          -- each block has its own scope
 143          hygienize_block (ast[i+1], clone_ctx (ctx)) -- conditional block
 144       end
 145       if #ast % 2 == 1 then
 146          hygienize_block (ast[#ast], clone_ctx (ctx)) -- else block
 147       end
 148
 149    | `Fornum{ var, ... } ->
 150       hygienize_expr (ast[i], ctx, 2, #ast-1) -- start, finish, step? exprs
 151       local inner_ctx = clone_ctx (ctx)
 152       alpha_rename (var, inner_ctx) -- rename local var [var] in [inner_ctx]
 153       hygienize_block (ast[#ast], inner_ctx)
 154
 155    | `Forin{ vars, vals, block } ->
 156       hygienize_expr_list (vals, ctx)
 157       local inner_ctx = clone_ctx (ctx)
 158       alpha_rename_list (vars, inner_ctx) -- rename local vars [vars] in [inner_ctx]
 159       hygienize_block (block, inner_ctx)
 160
 161    | `Local{ vars, vals } ->
 162       -- locals only enter in scope after their values are computed
 163       -- --> parse values first, then rename vars
 164       hygienize_expr_list (vals, ctx)
 165       alpha_rename_list (vars, ctx)
 166
 167    | `Localrec{ vars, vals } ->
 168       -- As opposed to [`Local], vars are in scope during their values'
 169       -- computation --> rename before parsing values.
 170       alpha_rename_list (vars, ctx)
 171       hygienize_expr_list (vals, ctx)
 172
 173    | `Call{ ... } | `Method{ ... } ->
 174       -- these are actually expr, delegate to [hygienize_expr]
 175       hygienize_expr (ast, ctx)
 176
 177    | `Return{ ... } -> hygienize_expr_list (ast, ctx)
 178    | `Break ->
 179    | _ -> error ("Unknown statement "..ast.tag)
 180    end
 181 end
 182
 183
 184 --------------------------------------------------------------------------------
 185 -- Make an expression AST hygienic. The optional [ctx] parameter is a
 186 -- [old_name -> new_name] map, which holds variable name substitutions
 187 -- to perform.
 188 --------------------------------------------------------------------------------
 189 function hygienize_expr (ast, ctx)
 190    if not ctx then ctx = { } end
 191    match ast with
 192    | `String{ _ } | `Number{ _ } | `True | `False | `Dots -> -- nothing
 193
 194    | `Function{ params, block } ->
 195      local inner_ctx = clone_ctx (ctx)
 196      alpha_rename_list (params, inner_ctx)
 197      hygienize_block (block, inner_ctx)
 198
 199    | `Table{ ... } ->
 200       for _, x in ipairs (ast) do
 201          match x with
 202          | `Key{ key, val } ->
 203             hygienize_expr (key, ctx)
 204             hygienize_expr (val, ctx)
 205          | _ -> hygienize (x, ctx)
 206          end
 207       end
 208
 209    | `Id{ x } ->
 210       -- Check for substitutions to apply:
 211       local y = ctx[x]; if y then ast[1] = y end
 212
 213    | `Op{ op, ... } ->
 214       hygienize_expr_list (ast, ctx, 2, #ast)
 215
 216    -- Just dispatch to sub-expressions:
 217    | `Call{ func, ... }
 218    | `Method{ obj, `String{ name }, ... }
 219    | `Index{ table, key } ->
 220       hygienize_expr_list (ast, ctx)
 221    | _ -> error ("Unknown expression "..ast.tag)
 222    end
 223 end
 224
 225 --------------------------------------------------------------------------------
 226 -- Make an statements block AST hygienic. The optional [ctx] parameter is a
 227 -- [old_name -> new_name] map, which holds variable name substitutions
 228 -- to perform.
 229 --------------------------------------------------------------------------------
 230 function hygienize_block (ast, ctx)
 231    if not ctx then ctx = { } end
 232    table.iter ((|x| hygienize(x, ctx)), ast)
 233 --   for i = 1, #ast do
 234 --      hygienize_stat (ast[i], ctx)
 235 --   end
 236 end
 237
 238 --------------------------------------------------------------------------------
 239 -- Makes a shallow copy of a table. Used to make a copy of [ctx] substitution
 240 -- tables, when entering a new scope.
 241 --------------------------------------------------------------------------------
 242 --[[
 243 function clone_ctx (ctx)
 244    local r = { }
 245    for k, v in pairs (ctx) do r[k] = v end
 246    return r
 247 end
 248 ]]
 249
 250 --------------------------------------------------------------------------------
 251 -- Make every expression from index [start] to [finish], in list
 252 -- [ast], hygienic. The optional [ctx] parameter is a [old_name ->
 253 -- new_name] map, which holds variable name substitutions to perform.
 254 -- [start] defaults to 1, [finish] defaults to the list's size.
 255 --------------------------------------------------------------------------------
 256 function hygienize_expr_list (ast, ctx, start, finish)
 257    for i = start or 1, finish or #ast do
 258       hygienize_expr (ast[i], ctx)
 259    end
 260 end
 261
 262 --------------------------------------------------------------------------------
 263 -- Replace the identifier [var]'s name with a fresh one generated by
 264 -- [mlp.gensym()], and store the new association in [ctx], so that the
 265 -- calling function will be able to substitute identifier occurences with
 266 -- its new name.
 267 --------------------------------------------------------------------------------
 268 function alpha_rename (var, ctx)
 269    assert (var.tag == "Id")
 270    ctx[var[1]] = mlp.gensym()[1]
 271    var[1] = ctx[var[1]]
 272 end
 273
 274 --------------------------------------------------------------------------------
 275 -- runs [alpha_rename] on a list of identifiers.
 276 --------------------------------------------------------------------------------
 277 function alpha_rename_list (vars, ctx)
 278    for _, v in ipairs(vars) do alpha_rename (v, ctx) end
 279 end