manual update

[metalua.git] / doc / manual / walk-ref.tex

\section{{\tt walk}, the code walker}\r
\r
When you write advanced macros, or when you're analyzing some code to check for\r
some property, you often need to design a function that walks through an\r
arbitrary piece of code, and does complex stuff on it. Such a function is called\r
a code walker. Code walkers can be used for some punctual adjustments, e.g.\r
changing a function's {\tt return} statements into something else, or checking\r
that a loop performs no {\tt break}, up to pretty advanced transformations, such\r
as CPS transformation (a way to encode full continuations into a language taht\r
doesn't support them natively; see Paul Graham's On Lisp for an accessible\r
description of how it works), lazy semantics...\r
\r
Anyway, code walkers are tricky to write, can involve a lot of boilerplate code,\r
and are generally brittle. To ease things as much as possible, Metalua comes\r
with a walk library, which intends to accelerate code walker implementation.\r
Since code walking is intrinsically tricky, the lib won't magically make it\r
trivial, but at least it will save you a lot of time and code, when compared to\r
writing all walkers from scratch. Moreover, other people who took the time to\r
learn the walker generator's API will enter into your code much faster.\r
\r
\subsection{Principles}\r
\r
Code walking is about traversing a tree, first from root to leaves, then from\r
leaves back to the root. This tree is not uniform: some nodes are expressions,\r
some others statements, some others blocks; and each of these node kinds is\r
subdivided in several sub-cases (addition, numeric for loop...). The basic code\r
walker just goes from root to leaves and back to root without doing anything.\r
Then it's up to you to plug some action callbacks in that walker, so that it\r
does interesting things for you.\r
\r
Without entering into the details of AST structure, here is a simplified version\r
of the walking algorithm, pretending to work on a generic tree:\r
\r
\begin{verbatim}\r
function traverse(node)\r
   local down_result = down(node)\r
   if down_result ~= 'break' then \r
      for c in children(node) do\r
         traverse(node)\r
      end\r
   end\r
   up(node)\r
end\r
\end{verbatim}\r
\r
The algorithm behind 'walk' is almost as simple as the one above, except that\r
it's specialized for AST trees. You can essentially specialize it by providing\r
your own up() and down() functions. These visitor functions perform whatever\r
action you want on the AST; moreover, down() has the option to return 'break':\r
in that case, the sub-nodes are not traversed. It allows the user to shun parts\r
of the tree, or to provide his own special traversal method in the down()\r
visitor.\r
\r
The real walker generator is only marginally more complex than that:\r
\begin{itemize}\r
\item It lets you define your up() and down(), and down() can return 'break' to\r
  cut the tree traversal; however, these up() and down() functions are\r
  specialized by node kind: there can be separate callbacks for expr nodes, stat\r
  nodes, block nodes.\r
\item There's also a binder() visitor for identifier binders. Binders are\r
  variables which declare a new local variable; you'll find them in nodes\r
  `Local, `Localrec, `Forin, `Fornum, `Function. The binders are visited just\r
  before the variable's scope begins, i.e. before traversing a loop or a\r
  function's body, after traversing a `Local's right-hand side, before\r
  traversing a `Localrec's right-hand side. \\ \r
  Notice that separate up() and down() visitors wouldn't make sense for\r
  binders, since they're leave nodes.\r
\item Visitor functions don't only take the visited node as parameter: they also\r
  take the list of all expr, stat and block nodes above it, up to the AST's\r
  root. This allows a child node to act on its parent nodes.\r
\end{itemize}\r
\r
\subsection{API}\r
There are 3 main tree walkers: {\tt walk.expr()}, {\tt walk.stat()} and {\tt\r
  walk.block()}, to walk through the corresponding kinds of ASTs. Each of these\r
walker take as parameters a table {\tt cfg} containing the various visitor\r
functions, and the AST to walk throuhg. the configuration table {\tt cfg} can\r
contain fields:\r
\begin{itemize}\r
\item {\tt cfg.stat.down(node, parent, grandparent...)}, which applies when\r
  traversing a statement down, i.e. before its children nodes are parsed, and\r
  can modify the tree, and return {\tt nil} or {\tt'break'}. The way children\r
  are traversed is decided {\em after} the {\tt down()} visitor has been run:\r
  this point matters when the visitor modifies its children nodes.\r
\item {\tt cfg.stat.up(node, parent, grandparent...)}, which is applies on the\r
  way back up. It is applied even if {\tt cfg.stat.down()} returned\r
  {\tt'break'}, but in that case, the children have not been (and will not be)\r
  traversed. \r
\item {\tt cfg.expr.down()} and {\tt cfg.expr.up()}, which work just as their\r
  {\tt stat} equivalent, but apply to expression nodes.\\\r
  Notice that in Lua, function calls and method invocations can be used as\r
  statements as well as as espressions: in such cases, they are visited only by\r
  the statement visitor, not by the expression visitor.\r
\item {\tt cfg.block.down()} and {\tt cfg.block.up()} do the same for statements\r
  blocks: loops, conditional and function bodies.\r
\item {\tt cfg.binder(identifier, id\_parent, id\_grandparent...)}: this\r
  is run on identifiers which create a new local variable, jsut before that\r
  variable's scope begins.\r
\end{itemize}\r
\r
Moreover, there is a {\tt walk.guess(cfg, ast)} walker which tries to guess the\r
type of the AST it receives, and applies the appropriate walker. When an AST can\r
be either an expression or a statement (nodes {\tt`Call} and {\tt`Invoke}), it\r
is interpreted as an expression.\r
\r
\subsection{Examples}\r
\r
A bit of practice now. Let's build the simplest walker possible, that does\r
nothing:\r
\r
\begin{verbatim}\r
cfg = { }\r
walker = |ast| walk.block(cfg, ast)\r
\end{verbatim}\r
\r
Now, let's say we want to catch and remove all statement calls to function\r
assert(). This can be done by removing its tag and content: an empty list is\r
simply ignored in an AST. So we're only interested by `Call nodes, and within\r
these nodes, we want the function to be `Id 'assert'. All of this is only\r
relevant to stat nodes:\r
\r
\begin{verbatim}\r
function cfg.stat.down (x)\r
   match x with\r
   | `Call{ `Id 'assert', ... } -> x.tag=nil; x <- { }\r
   | _ -> -- not interested by this node, do nothing\r
   end\r
end\r
\end{verbatim}\r
\r
You'll almost always want to use the 'match' extension to implement visitors.\r
The imperative table overrider ({\tt x <- y} a.k.a. {\tt table.override(x, y)}\r
also often comes handy to modify an AST.\r
\r
We'll now remove {\tt assert()} calls in non-statement; we cannot replace an\r
expression by nothing, so we'll replace these nodes by these will simply be\r
replaced by {\tt nil}:\r
\r
\begin{verbatim}\r
function cfg.expr.down (x)\r
   match x with\r
   | `Call{ `Id 'assert', ... } -> x <- `Nil\r
   | _ -> -- not interested by this node, do nothing\r
   end\r
end\r
\end{verbatim}\r
\r
\r
Here's a remark for functional programmers: this API is very imperative; you\r
might cringe at seeing the `Call nodes transformed in-place. Well, I tend to\r
agree but it's generally counter-productive to work against the grain of the\r
wood: Lua is imperative at heart, and design attempts at doing this functionally\r
sucked more than approaches that embraced imperativeness. \r
\r
\paragraph{Cuts}\r
By making down() return 'break', you can prevent the traversal to go further\r
down. This might be either because you're not interested by the subtrees, or\r
because you want to traverse them in a special way. In that later case, just do\r
the traversal by yourself in the down() function, and cut the walking by\r
returning 'break', so that nodes aren't re-traversed by the default walking\r
algorithm. We'll see that in the next, more complex example, listing of free\r
variables.\r
\r
This example is exclusively there for demonstration purposes. For actual work on\r
identifiers that require awareness of an identifier's binder of freedom, there\r
is a dedicated {\tt walk.id} library.\r
\r
We'll progressively build a walker that gathers all global variables used in a\r
given AST. This involves keeping, at all times, a set of the identifiers\r
currently bound by a "local" declaration, by function parameters, as for loop\r
variables etc. Then, every time an identifier is found in the AST, its presence\r
is checked in the current set of bound variables. If it isn't in it, then it's a\r
free (global) identifier.\r
\r
The first thing we'll need is a scope handling system: something that keeps\r
track of what identifiers are currently in scope. It must also allow to save the\r
current scope (e.g. before we enter a new block) and restore it afterwards (e.g.\r
after we leave the block). This is quite straightforward and unrelated to code\r
walking; here is the code:\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
require 'std'\r
require 'walk'\r
\r
-{ extension 'match' }\r
\r
--------------------------------------------------------------------------------\r
-- Scope handling: ':push()' saves the current scope, ':pop()'\r
-- restores the previously saved one. ':add(identifiers_list)' adds\r
-- identifiers to the current scope. Current scope is stored in\r
-- '.current', as a string->boolean hashtable.\r
--------------------------------------------------------------------------------\r
\r
local scope = { }\r
scope.__index = scope\r
\r
function scope:new()\r
   local ret = { current = { } }\r
   ret.stack = { ret.current }\r
   setmetatable (ret, self)\r
   return ret\r
end\r
\r
function scope:push()\r
   table.insert (self.stack, table.shallow_copy (self.current))\r
end\r
\r
function scope:pop()\r
   self.current = table.remove (self.stack)\r
end\r
\r
function scope:add (vars)\r
   for id in values (vars) do\r
      match id with `Id{ x } -> self.current[x] = true end\r
   end\r
end\r
\end{Verbatim}\r
\r
(There is an improved version of that class in library {\tt walk.scope}; cf.\r
its documentation for details).\r
\r
Now let's start designing the walker. We'll keep a scope object up to date, as\r
well as a set of found free identifiers, gathered every time we find an `Id{ }\r
node. To slightly simplify matter, we'll consider that the AST represent a\r
block.\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
local function fv (term)\r
   local freevars = { }\r
   local scope    = scope:new()\r
   local cfg      = { expr  = { } }\r
\r
   function cfg.expr.down(x)\r
      match x with\r
      | `Id{ name } -> if not scope.current[name] then freevars[name] = true end\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   walk.guess(cfg, term)\r
   return freevars\r
end\r
\end{Verbatim}\r
\r
Since we don't ever add any identifier to the scope, this will just list all the\r
identifiers used in the AST, bound or not. Now let's start doing more\r
interesting things:\r
\r
\begin{itemize}\r
\item We'll save the scope's state before entering a new block, and restore it\r
  when we leave it. That will be done by providing functions {\tt cfg.block.down()}\r
  and {\tt cfg.block.up()}. Saving and restoring will be performed by methods\r
  {\tt :push()} and {\tt :pop()}.\r
\item Whenever we find a {\tt local} declaration, we'll add the list of\r
  identifiers to the current scope, so that they won't be gathered when parsing\r
  the {\tt `Id} expression nodes. Notice that the identifiers declared by the\r
  'local' statement only start being valid after the statement, so we'll add\r
  them in the {\tt cfg.stat.up()} function rather than {\tt cfg.stat.down()}.\r
\end{itemize}\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
local cfg = { expr  = { },\r
              stat  = { },\r
              block = { } }\r
   [...]\r
   function cfg.stat.up(x)\r
      match x with\r
      | `Local{ vars, ... } -> scope:add(vars)\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   -----------------------------------------------------------------------------\r
   -- Create a separate scope for each block, close it when leaving.\r
   -----------------------------------------------------------------------------\r
   function cfg.block.down() scope:push() end\r
   function cfg.block.up()   scope:pop()  end  \r
\end{Verbatim}\r
\r
This starts to be useful. We can also easily add the case for `Localrec{ } nodes\r
(the ones generated by {\tt "local function foo() ... end"}), where the variable\r
is already bound in the {\tt`Localrec} statement's right-hand side; so we do the\r
same as for {\tt`Local}, but we do it in the {\tt down()} function rather than\r
in the up() one.\r
\r
We'll also take care of {\tt`Function}, {\tt`Forin} and {\tt`Fornum} nodes,\r
which introduce new bound identifiers as function parameters or loop variables.\r
This is quite straightforward; the only thing to take care of is to save the\r
scope before entering the function/loop body (in {\tt down()}), and restore it\r
when leaving (in {\tt up()}). The code becomes:\r
\r
  \r
\begin{Verbatim}[fontsize=\scriptsize]\r
local function fv (term)\r
   local freevars = { }\r
   local scope    = scope:new()\r
   local cfg      = { expr  = { },\r
                      stat  = { },\r
                      block = { } }\r
\r
   -----------------------------------------------------------------------------\r
   -- Check identifiers; add functions parameters to newly created scope.\r
   -----------------------------------------------------------------------------\r
   function cfg.expr.down(x)\r
      match x with\r
      | `Id{ name } -> if not scope.current[name] then freevars[name] = true end\r
      | `Function{ params, _ } -> scope:push(); scope:add (params)\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   -----------------------------------------------------------------------------\r
   -- Close the function scope opened by 'down()'.\r
   -----------------------------------------------------------------------------\r
   function cfg.expr.up(x)  \r
      match x with\r
      | `Function{ ... } -> scope:pop()\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   -----------------------------------------------------------------------------\r
   -- Create a new scope and register loop variable[s] in it\r
   -----------------------------------------------------------------------------\r
   function cfg.stat.down(x)\r
      match x with\r
      | `Forin{ vars, ... }    -> scope:push(); scope:add(vars)\r
      | `Fornum{ var, ... }    -> scope:push(); scope:add{var}\r
      | `Localrec{ vars, ... } -> scope:add(vars)\r
      | `Local{ ... }          -> -- pass\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   -----------------------------------------------------------------------------\r
   -- Close the scopes opened by 'up()'\r
   -----------------------------------------------------------------------------\r
   function cfg.stat.up(x)\r
      match x with\r
      | `Forin{ ... } | `Fornum{ ... } -> scope:pop()\r
      | `Local{ vars, ... }            -> scope:add(vars)\r
      | _ -> -- pass\r
      end\r
   end\r
\r
   -----------------------------------------------------------------------------\r
   -- Create a separate scope for each block, close it when leaving.\r
   -----------------------------------------------------------------------------\r
   function cfg.block.down() scope:push() end\r
   function cfg.block.up()   scope:pop()  end\r
\r
   walk.guess(cfg, term)\r
   return freevars\r
end\r
\end{Verbatim}\r
\r
This is almost correct now. There's one last tricky point of Lua's semantics\r
that we need to address: in {\tt repeat foo until bar} loops, "bar" is included\r
in "foo"'s scope. For instance, if we write {\tt repeat local x=foo() until\r
  x>3}, the "x" in the condition is the local variable "x" declared inside the\r
body. This violates our way of handling block scopes: the scope must be kept\r
alive after the block is finished. We'll fix this by providing a custom walking\r
for the block inside `Repeat, and preventing the normal walking to happen by\r
returning 'break':\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
   -----------------------------------------------------------------------------\r
   -- Create a new scope and register loop variable[s] in it\r
   -----------------------------------------------------------------------------\r
   function cfg.stat.down(x)\r
      match x with\r
      | `Forin{ vars, ... }    -> scope:push(); scope:add(vars)\r
      | `Fornum{ var, ... }    -> scope:push(); scope:add{var}\r
      | `Localrec{ vars, ... } -> scope:add(vars)\r
      | `Local{ ... }          -> -- pass\r
      | `Repeat{ block, cond } -> -- 'cond' is in the scope of 'block'\r
         scope:push()\r
         for s in values (block) do walk.stat(cfg)(s) end -- no new scope\r
         walk.expr(cfg)(cond)\r
         scope:pop()\r
         return 'break' -- No automatic walking of subparts 'cond' and 'body'\r
      | _ -> -- pass\r
      end\r
   end\r
\end{Verbatim}\r
\r
That's it, we've now got a full free variables lister, and have demonstrated\r
most APIs offered by the basic 'walk' library. If you want to walk through\r
identifiers in a scope-aware way, though, you'll want to look at the {\tt\r
  walk.id} library.\r
\r
\subsection{Library {\tt walk.id}, the scope-aware walker}\r
\r
This library walks AST to gather information about the identifiers in it. It\r
call distinct visitor functions depending on whether an identifier is bound or\r
free; moreover, when an identifier is bound, the visitor also receives its\r
binder node as a parameter. For instance, in {\tt +\{function(x) print(x)\r
  end\}}, the bound identifier walker will be called on the \verb|+{x}| in the\r
\verb|print| call, and the visitor's second parameter will be the {\tt`Function}\r
node which created the local variable {\tt x}.\r
\r
\paragraph{API}\r
The library is loaded with \verb|require 'walk.id'|. The walkers provided are:\r
\begin{itemize}\r
\item {\tt walk\_id.expr()};\r
\item {\tt walk\_id.stat()};\r
\item {\tt walk\_id.block()};\r
\item {\tt walk\_id.guess()}.\r
\end{itemize}\r
\r
They take the same config tables as regular walkers, except that they also\r
recognize the following entries:\r
\begin{itemize}\r
\item {\tt cfg.id.free(identifier, parent, grandparent...)}, which is run on\r
  free variables;\r
\item {\tt cfg.id.bound(identifier, binder, parent, grandparent...)}, which is\r
  run on bound variables. The statement or expression which created this bound\r
  veriable's scope is passed as a second parameter, before the parent nodes.\r
\end{itemize}\r
\r
\paragraph{Examples}\r
Let's rewrite the free variables walker above, with the id walker:\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
function fv (term)\r
   local cfg = { id = { } }\r
   local freevars = { }\r
   function cfg.id.free(id)\r
      local id_name = id[1]\r
      freevars[id_name] = true\r
   end\r
   walk_id.guess (cfg, term)\r
   return freevars\r
end\r
\end{Verbatim}\r
\r
Now, let's $\alpha$-rename all bound variables in a term. This is slightly\r
trickier than one could think: we need to first walk the whole tree, then\r
perform all the replacement. If we renamed binders as we went, they would stop\r
binding their variables, and something messy would happen. For instance, if we\r
took {\tt +\{function(x) print(x) end\}} and renamed the binder {\tt x} into\r
{\tt foo}, we'd then start walking the function body on the tree {\tt\r
  +\{function(foo) print(x) end\}}, where {\tt x} isn't bound anymore.\r
\r
\begin{Verbatim}[fontsize=\scriptsize]\r
--------------------------------------------------------------------------------\r
-- bound_vars keeps a binder node -> old_name -> new_name dictionary.\r
-- It allows to associate all instances of an identifier together,\r
-- with the binder that created them\r
--------------------------------------------------------------------------------\r
local bound_vars    = { }\r
\r
--------------------------------------------------------------------------------\r
-- local_renames will keep all identifier nodes to rename as keys,\r
-- and their new name as values. The renaming must happen after \r
-- the whole tree has been visited, in order to avoid breaking captures.\r
--------------------------------------------------------------------------------\r
local local_renames = { }\r
\r
--------------------------------------------------------------------------------\r
-- Associate a new name in bound_vars when a local variable is created.\r
--------------------------------------------------------------------------------\r
function cfg.binder (id, binder)\r
   local old_name         = id[1]\r
   local binder_table     = bound_vars[binder]\r
   if not binder_table then\r
      -- Create a new entry for this binder:\r
      binder_table        = { }\r
      bound_vars[binder]  = binder_table\r
   end\r
   local new_name         = mlp.gensym(old_name)[1] -- generate a new name\r
   binder_table[old_name] = new_name -- remember name for next instances\r
   local_renames[id]      = new_name -- add to the rename todo-list\r
end\r
\r
--------------------------------------------------------------------------------\r
-- Add a bound variable the the rename todo-list\r
--------------------------------------------------------------------------------\r
function cfg.id.bound (id, binder)\r
   local old_name    = id[1]\r
   local new_name    = bound_vars[binder][old_name]\r
   local_renames[id] = new_name\r
end\r
\r
-- walk the tree and fill laocal_renames:\r
walk_id.guess(cfg, ast)\r
\r
-- perform the renaming actions:\r
for id, new_name in pairs(local_renames) do id[1] = new_name end\r
\end{Verbatim}\r
\r
\subsection{Library {\tt walk.scope}, the scope helper}\r
This library allows to easily store data, in an AST walking function, in a scope\r
aware way. Cf. comments in the sources for details.\r