-----------------------------------------------------------------------\r
--- Metalua: $Id$\r
---\r
--- Summary: Hygienic macro facility for Metalua\r
---\r
-----------------------------------------------------------------------\r
---\r
--- Copyright (c) 2006, Fabien Fleutot <metalua@gmail.com>.\r
---\r
--- This software is released under the MIT Licence, see licence.txt\r
--- for details.\r
---\r
---------------------------------------------------------------------------------\r
---\r
--- =============\r
--- W A R N I N G\r
--- =============\r
---\r
--- THIS IS AN OLD NAIVE IMPLEMENTATION. IT'S PARATIAL (NO HYGIENE WRT OUTSIDE)\r
--- AND WRITTEN FROM SCRATCH WITH PATTERN MATCHING. MUST BE DONE WITH A WALKER.\r
---\r
--- Traditional macros carry a well-known pitfall, called variable capture:\r
--- when pasting a piece of source code A into another code B, if B bonds some\r
--- variables used by A, then the meaning of A is modified in a way probably\r
--- not intended by the user.\r
---\r
--- Example:\r
--- A = +{ n = 5 }\r
--- B = +{ local n=3; -{ A } }\r
--- \r
--- In this example, [n] in [A] will be captured by the local variable declared\r
--- by [B], and this is probably a bug.\r
--- \r
--- Notice that this also exists in C. Typical example:\r
---\r
--- #define swap (type, a, b) do { type tmp=a; a=b; b=tmp } while(0)\r
--- void f() {\r
--- int tmp=1, a=2; \r
--- swap (int, tmp, a); // won't work, [tmp] is captured in the macro\r
--- }\r
---\r
--- We can fix this by making sure that all local variables and parameters\r
--- created by [B] have fresh names. [mlp.gensym()] produces guaranteed-to-be-unique\r
--- variable names; we use it to replace all local var names declarations and \r
--- occurences in [B] by such fresh names.\r
---\r
--- Such macros which are guaranteed not to capture any variable are called\r
--- hygienic macros. By extension, an AST guaranteed not to contain capturing\r
--- variables is called an hygienic AST.\r
---\r
--- We implement here some functions which make sure that an AST is hygienic:\r
--- \r
--- - [hygienize_stat (ast)] for statement AST;\r
--- - [hygienize_stat (ast)] for statement block AST;\r
--- - [hygienize_expr (ast)] for expression AST;\r
---\r
--- This sample deconstructs AST by structural pattern matching, which is\r
--- supported by Metalua extension "match.lua"\r
---\r
---------------------------------------------------------------------------------\r
-\r
--{ extension "match" }\r
-\r
-require "std"\r
-\r
-local clone_ctx = std.shallow_copy\r
-\r
---------------------------------------------------------------------------------\r
--- Tag tables: these allow [hygienize] to decide whether an AST is\r
--- an expression, a statement, or something which isn't changed by\r
--- alpha renaming.\r
---------------------------------------------------------------------------------\r
-local stat_tags = {\r
- Do = true, Let = true,\r
- While = true, Repeat = true,\r
- If = true, Fornum = true,\r
- Forin = true, Local = true,\r
- Localrec = true, Return = true }\r
-\r
-local expr_tags = {\r
- Function = true, Table = true,\r
- Op = true, Call = true,\r
- Method = true, Index = true }\r
-\r
-local neutral_tags = {\r
- String = true, Number = true,\r
- True = true, False = true,\r
- Dots = true, Break = true,\r
- Id = true }\r
-\r
---------------------------------------------------------------------------------\r
--- Choose the relevant [hygienize_xxx()] function according to the AST's tag\r
--- and the tables above.\r
---------------------------------------------------------------------------------\r
-function hygienize (ast)\r
- if not ast.tag then hygienize_block (ast)\r
- elseif neutral_tags[ast.tag] then -- pass\r
- elseif stat_tags[ast.tag] then hygienize_stat (ast) \r
- elseif expr_tags[ast.tag] then hygienize_expr (ast) \r
- else error "Unrecognized AST" end\r
- return ast\r
-end\r
-\r
-if mlp then\r
- -- Add hygienic parsers for quotes\r
- mlp.hexpr = hygienize `o` mlp.expr\r
- mlp.hstat = hygienize `o` mlp.stat\r
- mlp.hblock = hygienize `o` mlp.block\r
-end\r
-\r
---------------------------------------------------------------------------------\r
--- Make a statement AST hygienic. The optional [ctx] parameter is a\r
--- [old_name -> new_name] map, which holds variable name substitutions\r
--- to perform.\r
---------------------------------------------------------------------------------\r
-function hygienize_stat (ast, ctx)\r
- if not ctx then ctx = { } end\r
- match ast with\r
- | { ... } if not ast.tag -> hygienize_block (ast, ctx)\r
- | `Do{ ... } -> hygienize_block (ast, clone_ctx (ctx))\r
-\r
- | `Let{ vars, vals } -> \r
- hygienize_expr_list (vars, ctx)\r
- hygienize_expr_list (vals, ctx)\r
-\r
- | `While{ cond, block } ->\r
- hygienize_expr (cond, ctx)\r
- -- use a clone of [ctx], since the block has a separate scope\r
- hygienize_block (ast, clone_ctx (ctx))\r
-\r
- | `Repeat{ block, cond } ->\r
- -- use a clone of [ctx], since the block has a separate scope.\r
- -- Notice that the condition in [repeat ... until] is evaluated\r
- -- inside the block's scope, i.e. with [inner_ctx] rather than [ctx].\r
- local inner_ctx = clone_ctx (ctx)\r
- hygienize_block (ast, inner_ctx)\r
- hygienize (cond, inner_ctx)\r
-\r
- | `If{ ... } ->\r
- for i=1, #ast-1, 2 do\r
- hygienize_expr (ast[i], ctx) -- condtion\r
- -- each block has its own scope\r
- hygienize_block (ast[i+1], clone_ctx (ctx)) -- conditional block\r
- end\r
- if #ast % 2 == 1 then \r
- hygienize_block (ast[#ast], clone_ctx (ctx)) -- else block\r
- end\r
-\r
- | `Fornum{ var, ... } ->\r
- hygienize_expr (ast[i], ctx, 2, #ast-1) -- start, finish, step? exprs\r
- local inner_ctx = clone_ctx (ctx)\r
- alpha_rename (var, inner_ctx) -- rename local var [var] in [inner_ctx]\r
- hygienize_block (ast[#ast], inner_ctx)\r
- \r
- | `Forin{ vars, vals, block } ->\r
- hygienize_expr_list (vals, ctx)\r
- local inner_ctx = clone_ctx (ctx)\r
- alpha_rename_list (vars, inner_ctx) -- rename local vars [vars] in [inner_ctx]\r
- hygienize_block (block, inner_ctx) \r
- \r
- | `Local{ vars, vals } ->\r
- -- locals only enter in scope after their values are computed\r
- -- --> parse values first, then rename vars\r
- hygienize_expr_list (vals, ctx)\r
- alpha_rename_list (vars, ctx)\r
- \r
- | `Localrec{ vars, vals } ->\r
- -- As opposed to [`Local], vars are in scope during their values' \r
- -- computation --> rename before parsing values. \r
- alpha_rename_list (vars, ctx)\r
- hygienize_expr_list (vals, ctx)\r
-\r
- | `Call{ ... } | `Method{ ... } -> \r
- -- these are actually expr, delegate to [hygienize_expr]\r
- hygienize_expr (ast, ctx)\r
-\r
- | `Return{ ... } -> hygienize_expr_list (ast, ctx)\r
- | `Break -> \r
- | _ -> error ("Unknown statement "..ast.tag)\r
- end\r
-end\r
-\r
-\r
---------------------------------------------------------------------------------\r
--- Make an expression AST hygienic. The optional [ctx] parameter is a\r
--- [old_name -> new_name] map, which holds variable name substitutions\r
--- to perform.\r
---------------------------------------------------------------------------------\r
-function hygienize_expr (ast, ctx)\r
- if not ctx then ctx = { } end\r
- match ast with\r
- | `String{ _ } | `Number{ _ } | `True | `False | `Dots -> -- nothing\r
-\r
- | `Function{ params, block } ->\r
- local inner_ctx = clone_ctx (ctx)\r
- alpha_rename_list (params, inner_ctx)\r
- hygienize_block (block, inner_ctx)\r
- \r
- | `Table{ ... } ->\r
- for _, x in ipairs (ast) do\r
- match x with\r
- | `Key{ key, val } -> \r
- hygienize_expr (key, ctx)\r
- hygienize_expr (val, ctx)\r
- | _ -> hygienize (x, ctx)\r
- end\r
- end\r
-\r
- | `Id{ x } ->\r
- -- Check for substitutions to apply:\r
- local y = ctx[x]; if y then ast[1] = y end\r
-\r
- | `Op{ op, ... } ->\r
- hygienize_expr_list (ast, ctx, 2, #ast)\r
-\r
- -- Just dispatch to sub-expressions:\r
- | `Call{ func, ... }\r
- | `Method{ obj, `String{ name }, ... }\r
- | `Index{ table, key } ->\r
- hygienize_expr_list (ast, ctx)\r
- | _ -> error ("Unknown expression "..ast.tag)\r
- end\r
-end\r
-\r
---------------------------------------------------------------------------------\r
--- Make an statements block AST hygienic. The optional [ctx] parameter is a\r
--- [old_name -> new_name] map, which holds variable name substitutions\r
--- to perform.\r
---------------------------------------------------------------------------------\r
-function hygienize_block (ast, ctx)\r
- if not ctx then ctx = { } end\r
- table.iter ((|x| hygienize(x, ctx)), ast)\r
--- for i = 1, #ast do\r
--- hygienize_stat (ast[i], ctx)\r
--- end\r
-end\r
-\r
---------------------------------------------------------------------------------\r
--- Makes a shallow copy of a table. Used to make a copy of [ctx] substitution\r
--- tables, when entering a new scope.\r
---------------------------------------------------------------------------------\r
---[[\r
-function clone_ctx (ctx)\r
- local r = { }\r
- for k, v in pairs (ctx) do r[k] = v end\r
- return r\r
-end\r
-]]\r
-\r
---------------------------------------------------------------------------------\r
--- Make every expression from index [start] to [finish], in list\r
--- [ast], hygienic. The optional [ctx] parameter is a [old_name ->\r
--- new_name] map, which holds variable name substitutions to perform.\r
--- [start] defaults to 1, [finish] defaults to the list's size.\r
---------------------------------------------------------------------------------\r
-function hygienize_expr_list (ast, ctx, start, finish)\r
- for i = start or 1, finish or #ast do \r
- hygienize_expr (ast[i], ctx)\r
- end\r
-end\r
-\r
---------------------------------------------------------------------------------\r
--- Replace the identifier [var]'s name with a fresh one generated by\r
--- [mlp.gensym()], and store the new association in [ctx], so that the\r
--- calling function will be able to substitute identifier occurences with\r
--- its new name.\r
---------------------------------------------------------------------------------\r
-function alpha_rename (var, ctx)\r
- assert (var.tag == "Id")\r
- ctx[var[1]] = mlp.gensym()[1]\r
- var[1] = ctx[var[1]]\r
-end\r
-\r
---------------------------------------------------------------------------------\r
--- runs [alpha_rename] on a list of identifiers.\r
---------------------------------------------------------------------------------\r
-function alpha_rename_list (vars, ctx)\r
- for _, v in ipairs(vars) do alpha_rename (v, ctx) end\r
-end\r
+----------------------------------------------------------------------
+-- Metalua: $Id$
+--
+-- Summary: Hygienic macro facility for Metalua
+--
+----------------------------------------------------------------------
+--
+-- Copyright (c) 2006, Fabien Fleutot <metalua@gmail.com>.
+--
+-- This software is released under the MIT Licence, see licence.txt
+-- for details.
+--
+--------------------------------------------------------------------------------
+--
+-- =============
+-- W A R N I N G
+-- =============
+--
+-- THIS IS AN OLD NAIVE IMPLEMENTATION. IT'S PARATIAL (NO HYGIENE WRT OUTSIDE)
+-- AND WRITTEN FROM SCRATCH WITH PATTERN MATCHING. MUST BE DONE WITH A WALKER.
+--
+-- Traditional macros carry a well-known pitfall, called variable capture:
+-- when pasting a piece of source code A into another code B, if B bonds some
+-- variables used by A, then the meaning of A is modified in a way probably
+-- not intended by the user.
+--
+-- Example:
+-- A = +{ n = 5 }
+-- B = +{ local n=3; -{ A } }
+--
+-- In this example, [n] in [A] will be captured by the local variable declared
+-- by [B], and this is probably a bug.
+--
+-- Notice that this also exists in C. Typical example:
+--
+-- #define swap (type, a, b) do { type tmp=a; a=b; b=tmp } while(0)
+-- void f() {
+-- int tmp=1, a=2;
+-- swap (int, tmp, a); // won't work, [tmp] is captured in the macro
+-- }
+--
+-- We can fix this by making sure that all local variables and parameters
+-- created by [B] have fresh names. [mlp.gensym()] produces guaranteed-to-be-unique
+-- variable names; we use it to replace all local var names declarations and
+-- occurences in [B] by such fresh names.
+--
+-- Such macros which are guaranteed not to capture any variable are called
+-- hygienic macros. By extension, an AST guaranteed not to contain capturing
+-- variables is called an hygienic AST.
+--
+-- We implement here some functions which make sure that an AST is hygienic:
+--
+-- - [hygienize_stat (ast)] for statement AST;
+-- - [hygienize_stat (ast)] for statement block AST;
+-- - [hygienize_expr (ast)] for expression AST;
+--
+-- This sample deconstructs AST by structural pattern matching, which is
+-- supported by Metalua extension "match.lua"
+--
+--------------------------------------------------------------------------------
+
+-{ extension "match" }
+
+require "std"
+
+local clone_ctx = std.shallow_copy
+
+--------------------------------------------------------------------------------
+-- Tag tables: these allow [hygienize] to decide whether an AST is
+-- an expression, a statement, or something which isn't changed by
+-- alpha renaming.
+--------------------------------------------------------------------------------
+local stat_tags = {
+ Do = true, Let = true,
+ While = true, Repeat = true,
+ If = true, Fornum = true,
+ Forin = true, Local = true,
+ Localrec = true, Return = true }
+
+local expr_tags = {
+ Function = true, Table = true,
+ Op = true, Call = true,
+ Method = true, Index = true }
+
+local neutral_tags = {
+ String = true, Number = true,
+ True = true, False = true,
+ Dots = true, Break = true,
+ Id = true }
+
+--------------------------------------------------------------------------------
+-- Choose the relevant [hygienize_xxx()] function according to the AST's tag
+-- and the tables above.
+--------------------------------------------------------------------------------
+function hygienize (ast)
+ if not ast.tag then hygienize_block (ast)
+ elseif neutral_tags[ast.tag] then -- pass
+ elseif stat_tags[ast.tag] then hygienize_stat (ast)
+ elseif expr_tags[ast.tag] then hygienize_expr (ast)
+ else error "Unrecognized AST" end
+ return ast
+end
+
+if mlp then
+ -- Add hygienic parsers for quotes
+ mlp.hexpr = hygienize `o` mlp.expr
+ mlp.hstat = hygienize `o` mlp.stat
+ mlp.hblock = hygienize `o` mlp.block
+end
+
+--------------------------------------------------------------------------------
+-- Make a statement AST hygienic. The optional [ctx] parameter is a
+-- [old_name -> new_name] map, which holds variable name substitutions
+-- to perform.
+--------------------------------------------------------------------------------
+function hygienize_stat (ast, ctx)
+ if not ctx then ctx = { } end
+ match ast with
+ | { ... } if not ast.tag -> hygienize_block (ast, ctx)
+ | `Do{ ... } -> hygienize_block (ast, clone_ctx (ctx))
+
+ | `Let{ vars, vals } ->
+ hygienize_expr_list (vars, ctx)
+ hygienize_expr_list (vals, ctx)
+
+ | `While{ cond, block } ->
+ hygienize_expr (cond, ctx)
+ -- use a clone of [ctx], since the block has a separate scope
+ hygienize_block (ast, clone_ctx (ctx))
+
+ | `Repeat{ block, cond } ->
+ -- use a clone of [ctx], since the block has a separate scope.
+ -- Notice that the condition in [repeat ... until] is evaluated
+ -- inside the block's scope, i.e. with [inner_ctx] rather than [ctx].
+ local inner_ctx = clone_ctx (ctx)
+ hygienize_block (ast, inner_ctx)
+ hygienize (cond, inner_ctx)
+
+ | `If{ ... } ->
+ for i=1, #ast-1, 2 do
+ hygienize_expr (ast[i], ctx) -- condtion
+ -- each block has its own scope
+ hygienize_block (ast[i+1], clone_ctx (ctx)) -- conditional block
+ end
+ if #ast % 2 == 1 then
+ hygienize_block (ast[#ast], clone_ctx (ctx)) -- else block
+ end
+
+ | `Fornum{ var, ... } ->
+ hygienize_expr (ast[i], ctx, 2, #ast-1) -- start, finish, step? exprs
+ local inner_ctx = clone_ctx (ctx)
+ alpha_rename (var, inner_ctx) -- rename local var [var] in [inner_ctx]
+ hygienize_block (ast[#ast], inner_ctx)
+
+ | `Forin{ vars, vals, block } ->
+ hygienize_expr_list (vals, ctx)
+ local inner_ctx = clone_ctx (ctx)
+ alpha_rename_list (vars, inner_ctx) -- rename local vars [vars] in [inner_ctx]
+ hygienize_block (block, inner_ctx)
+
+ | `Local{ vars, vals } ->
+ -- locals only enter in scope after their values are computed
+ -- --> parse values first, then rename vars
+ hygienize_expr_list (vals, ctx)
+ alpha_rename_list (vars, ctx)
+
+ | `Localrec{ vars, vals } ->
+ -- As opposed to [`Local], vars are in scope during their values'
+ -- computation --> rename before parsing values.
+ alpha_rename_list (vars, ctx)
+ hygienize_expr_list (vals, ctx)
+
+ | `Call{ ... } | `Method{ ... } ->
+ -- these are actually expr, delegate to [hygienize_expr]
+ hygienize_expr (ast, ctx)
+
+ | `Return{ ... } -> hygienize_expr_list (ast, ctx)
+ | `Break ->
+ | _ -> error ("Unknown statement "..ast.tag)
+ end
+end
+
+
+--------------------------------------------------------------------------------
+-- Make an expression AST hygienic. The optional [ctx] parameter is a
+-- [old_name -> new_name] map, which holds variable name substitutions
+-- to perform.
+--------------------------------------------------------------------------------
+function hygienize_expr (ast, ctx)
+ if not ctx then ctx = { } end
+ match ast with
+ | `String{ _ } | `Number{ _ } | `True | `False | `Dots -> -- nothing
+
+ | `Function{ params, block } ->
+ local inner_ctx = clone_ctx (ctx)
+ alpha_rename_list (params, inner_ctx)
+ hygienize_block (block, inner_ctx)
+
+ | `Table{ ... } ->
+ for _, x in ipairs (ast) do
+ match x with
+ | `Key{ key, val } ->
+ hygienize_expr (key, ctx)
+ hygienize_expr (val, ctx)
+ | _ -> hygienize (x, ctx)
+ end
+ end
+
+ | `Id{ x } ->
+ -- Check for substitutions to apply:
+ local y = ctx[x]; if y then ast[1] = y end
+
+ | `Op{ op, ... } ->
+ hygienize_expr_list (ast, ctx, 2, #ast)
+
+ -- Just dispatch to sub-expressions:
+ | `Call{ func, ... }
+ | `Method{ obj, `String{ name }, ... }
+ | `Index{ table, key } ->
+ hygienize_expr_list (ast, ctx)
+ | _ -> error ("Unknown expression "..ast.tag)
+ end
+end
+
+--------------------------------------------------------------------------------
+-- Make an statements block AST hygienic. The optional [ctx] parameter is a
+-- [old_name -> new_name] map, which holds variable name substitutions
+-- to perform.
+--------------------------------------------------------------------------------
+function hygienize_block (ast, ctx)
+ if not ctx then ctx = { } end
+ table.iter ((|x| hygienize(x, ctx)), ast)
+-- for i = 1, #ast do
+-- hygienize_stat (ast[i], ctx)
+-- end
+end
+
+--------------------------------------------------------------------------------
+-- Makes a shallow copy of a table. Used to make a copy of [ctx] substitution
+-- tables, when entering a new scope.
+--------------------------------------------------------------------------------
+--[[
+function clone_ctx (ctx)
+ local r = { }
+ for k, v in pairs (ctx) do r[k] = v end
+ return r
+end
+]]
+
+--------------------------------------------------------------------------------
+-- Make every expression from index [start] to [finish], in list
+-- [ast], hygienic. The optional [ctx] parameter is a [old_name ->
+-- new_name] map, which holds variable name substitutions to perform.
+-- [start] defaults to 1, [finish] defaults to the list's size.
+--------------------------------------------------------------------------------
+function hygienize_expr_list (ast, ctx, start, finish)
+ for i = start or 1, finish or #ast do
+ hygienize_expr (ast[i], ctx)
+ end
+end
+
+--------------------------------------------------------------------------------
+-- Replace the identifier [var]'s name with a fresh one generated by
+-- [mlp.gensym()], and store the new association in [ctx], so that the
+-- calling function will be able to substitute identifier occurences with
+-- its new name.
+--------------------------------------------------------------------------------
+function alpha_rename (var, ctx)
+ assert (var.tag == "Id")
+ ctx[var[1]] = mlp.gensym()[1]
+ var[1] = ctx[var[1]]
+end
+
+--------------------------------------------------------------------------------
+-- runs [alpha_rename] on a list of identifiers.
+--------------------------------------------------------------------------------
+function alpha_rename_list (vars, ctx)
+ for _, v in ipairs(vars) do alpha_rename (v, ctx) end
+end
projects / metalua.git / blobdiff