doc/manual/src-hints.tex

   1 \section{Digging in the sources}
   2
   3 This section is dedicated to people who want to dig into Metalua
   4 sources. It presents the main files, their current state, and where to
   5 start your exploration.
   6
   7 \subsection{gg}
   8
   9 The real core of Metalua is gg, implemented in a single file {\bf
  10   gg.ml}. Understanding it is really the key to getting the big
  11 picture. gg is written in a rather functional style, with a lot of
  12 functors and closures.
  13
  14 Gg is a restricted version of Haskell's parser combinator library
  15 parsec: parsec allows to build complex parsers by combining simpler
  16 ones with concatenation, alternative choices, etc; it allows, among
  17 others, to handle backtracking, i.e. a given parser can have several
  18 interpretations of a single sentence, and parser combinators handle
  19 this non-determinism by choosing the interpretation which allows the
  20 combined parser to yield a result.
  21
  22 Gg intentionally doesn't support backtracking: not only would it be
  23 slightly harder to read in a non-lazy language such as Lua, but it
  24 isn't required to parse Lua. More importantly, built-in backtracking
  25 would encourage people to create ambiguous syntax extensions, which is
  26 an awfully bad idea: indeed, we expect different extensions to
  27 cohabitate as smoothly as possible, and two extensions with ambiguous
  28 grammars generally cause a lot of chaos when mixed together. Finally,
  29 a lot of Lua's essence is about friendly, unsurprizing, clear
  30 syntax. We want to encourage people to respect this spirit as
  31 much as possible, so if they want to introduce chaotic syntax, Metalua
  32 won't actively prevent them to do so, but it certainly won't help by
  33 providing the tools.
  34
  35 Gg offers no atomic parsers besides keyword parser generators; it's up
  36 to the programmer to provide them. Parsers are simply functions which
  37 take a lexer as a parameter, and return an AST. Such function examples
  38 are provided for mlp in mlp\_expr.lua. Lexers are objects with a
  39 couple of mandatory methods: peek, next and is\_keyword. Lexer API
  40 shall be discussed in the part about mll.
  41
  42 \paragraph{State}
  43 Gg.lua is correctly refactored and commented, and should be readable
  44 by anyone with some notions of Lua and functional programming. Having
  45 dealt with parsec might help a bit, but is definitely not required.
  46
  47 \paragraph{Going further}
  48 From gg, there are two main leads to follow: either look down to mll,
  49 Metalua's lexer, or look up to mlp, the Metalua parser implemented on
  50 top of gg.
  51
  52 \subsection{lexer, mlp\_lexer}
  53
  54 As stated above, gg relies on a lexer respecting a certain API. We
  55 provide such a lexer for Metalua parsing, which deals with the usual
  56 lexing tasks: getting rid of spaces and comments, and discriminating
  57 between keywords, identifiers, strings, numbers etc. It's implemented
  58 in the file {\bf lexer.lua}
  59
  60 This lexer can be parameterized with a list of keywords; {\tt
  61   mlp\_lexer.lua} defines the mlp lexer, i.e. uses the generic lexer to
  62 create a derived lexer, and adds Lua keywords to it.
  63
  64 \paragraph{State}
  65 lexer.lua is somewhat extensible by someone willing to inspect its
  66 sources carfully. Among others, playing with the list lexer.extractors
  67 will let you create new lexical entities readers. However, the global
  68 architecture of the lexer still deserves a serious refactoring.
  69
  70 \subsection{mlp}
  71 Mlp is a very important part of Metalua, the one most people will
  72 actually have to deal with. Understanding it requires to understand
  73 gg. Mlp is cut into several parts:
  74
  75 \begin{itemize}
  76 \item {\bf mlp\_expr.lua} parses expressions except literal tables
  77   and quotes. It includes other constants (booleans, strings,
  78   numbers), the compound expressions built by combining them with
  79   operators, and function bodies. Most of its complexity is handled by
  80   the expression parser generator gg.expr.
  81 \item {\bf mlp\_table.lua} parses tables. Not much to say about this,
  82   this is probably the simplest subpart of mlp.
  83 \item {\bf mlp\_stat.lua} parses statements. Except for assignments,
  84   every different statement is introduced by a distinct initial
  85   keyword, and it should remain that way.
  86 \item {\bf mlp\_ext.lua} gathers the parts of the metalua syntax that
  87   aren't regular Lua: customizable assignments, short lambda syntax
  88   etc.
  89 \item {\bf mlp\_meta.lua} handles the meta-operations splicing and
  90   quoting.
  91 \item {\bf mlp\_misc.lua} contains various little bits that wouldn't
  92   fit anywhere else. In other words, it's sort of a mess.
  93 \end{itemize}
  94
  95 \subsection{Bytecode generation}
  96 Bytecode generation by metalua is a quick and dirty hack, which
  97 sort-of does the trick for now, but should eventually be largely
  98 rewritten. The current scaffolding has been hacked from Kein-Hong
  99 Man's Yueliang project (\url{http://luaforge.net/projects/yueliang}),
 100 but Yueliang design rationales don't really fit metalua's
 101 needs. Indeed, Yueliang is a translation, almost statement by
 102 statement, of the official C compiler included in Lua
 103 distribution. This has the following consequences:
 104
 105 \begin{itemize}
 106 \item it helps to understand the original compiler in C;
 107 \item it's easy to backport extensions from the C version to Yueliang
 108   (I had to do it, since Yueliang was 5.0 and I needed 5.1)
 109 \item it's rather easy to get bitwise-identical compilations, between
 110   what Yueliang produces and what the C version does. And that's good,
 111   because testing a compiler is a non-trivial problem.
 112 \item being in Lua, it's much easier to debug and extend than C.
 113 \end{itemize}
 114
 115 The big drawback is that the code is very much structured like C, and
 116 is therefore big, memory and time hungry, harder than necessary to
 117 understand and maintain, not suitable for clean and easy
 118 extensions. Two possible evolutions could be considered for metalua:
 119
 120 \begin{itemize}
 121 \item either port the bytecode producer to C, to speed up things;
 122 \item or rewrite it in ``true'' (meta)Lua\footnote{Pure Lua would
 123     probably be a much better idea: it would keep bootstrapping issues
 124     trivial.} , i.e. by leveraging all the power of tables, closures
 125   etc. This would allow the bytecode producer to be extensible, and
 126   interesting things could be done with that. Whether it's a good
 127   idea, I don't know. The drawback is, it would be much harder to keep
 128   compatibility with the next Lua VM versions.
 129 \end{itemize}
 130
 131 So, the files borrowed from Yueliang are {\bf lopcode.lua}, {\bf
 132   lcode.lua}, and {\bf ldump.lua}. They've been quickly hacked to
 133 produce 5.1 bytecode rather than 5.0. Finally, {\bf compile.lua},
 134 which uses the previous modules to convert AST to bytecode, is a
 135 grossly abused version of Yueliang's lparse.lua.
 136
 137 Notice a big current limitation: it only dumps little endian, double
 138 floats, 32 bits integers based bytecode. 64 bit and/or big endian
 139 platforms are currently not supported (although it shouldn't be hard
 140 to extend ldump.lua to handle those).
 141
 142 \subsection{The bootstrapping process}
 143
 144 FIXME