Merge remote branch 'origin/master'

[metalua.git] / junk / notes.txt

=== Random personal notes ===

====================================================================
This is my persistent *scratch*. There are random notes, in random
languages, unstructured, out of date, generally unexploitable. Don't
expect anything here to make sense.
====================================================================

Readme fraft
============
This distribution of metalua tries to favor ease of install over
saving a couple of kilobytes; therefore it directly embeds pieces of
useful other free software rather than letting users fetch and
configure them, and it installs separately from a regular lua install,
instead of messing it up.

Open source code used by metalua


Metalua current sources include (possibly slightly modified versions
of) these open source projects:

- Lua, of course.

- Yueliang, a Lua compiler in written in Lua: this is
  the base of metalua's bytecode dumper.

- Rings, a part of the Kelper project, which lets handle multiple Lua
  states from within Lua.

- Editline, an interactive command line editor, very similar to GNU
  readline but with a more permissive licence.

- bitlib for bitwise manipulations (especially useful for bytecode
  dumping)

The mlc module
--------------
This module contains all of the compilation stuff. The version
available after compilation is heavily based on the pattern matching
extension, so it isn't used in the code required for bootstrapping
(which has to be in lua inter metalua. That is, then, Lua)

Libraries
---------
The mechanism of metalua libraries is exactly the same as Lua's,
except that the environment variable names ahve been changed to allow
peaceful cohabitation with Lua.

Etancheite:
===========
- shell interactif:
  * separer les niveaux
  * permettre de monter/descendre d'un niveau avec des commandes
    dediees: "+:" et "-:"

Il faut faire la part entre la synthese de l'AST et l'evaluation. La
synthese de l'AST est faite en amont de mlc.splice(). Apparemment, le
lexer est commun a tout le monde... et mlp aussi.

Hygiene:
========
les quotes peuvent etre hygieniques (HQQ) ou pas (QQ). les QQ sont
normales, ne font rien; ca permet de capturer des variables entre
morceaux. 

Les HQQ sont attachees a un contexte, dans lequel seront reversees
leurs variables libres. +{:hexpr(CTX): foo } va alpha renommer toutes
les variables libres de +{foo} et les stocker dans CTX.

Autre possibilite syntaxique: une +{hexpr: foo } retourne +{foo} et
son contexte. Le contexte permet de decider comment fusionner deux
AST. Il ne se resume pas a une substitution

->Laurie:

Your approach is to tell the user that an AST has a sense by itself:
it's an autonomous piece of data that won't interfere with its
environment. Then you re-introduce mechanisms to get some dangling
bits back, so that you can wire the various bits (QQ and splices)
together as you wish. 

Now, the point from which I'll draw my PoV: an AST is only hygienic
relative to a context. Through gensym() we're able to craft ASTs that
are hygienic in all normal contexts, but the notion of contexts
continues to exist. In particular, as soon as we want to connect bits
of AST in interesting ways, we start to need a finer-grained control
of contexts.

You offer, with $c{ } ${ } and &, ways to poke holes into contexts,
but since you try pretend to the user that there's no context, the
user is screwed when he does want to mess with it. He has to guess how
those hidden contexts work, and find ways to use the tools mentionned
above so that they have the intended effect on the stealth context.

That's a good approach when there's nothing clever to do with
contexts, and it falls down when users get out of the main use
cases. Depending on how rare it is to need such conttext hacking
capabilities, your approach might or might not be practical.

The metalua-consistent approach is the opposite one: if there's such a
thing as contexts, and it sometimes makes sense for (advanced) users
to fiddle with them, then there must be first class AST context
objects. If it can be optionally hidden in most common cases, great,
but users aren't supposed to ignore their existence.

Therefore, whenever you combine two pieces of AST, you specify how
their context must be merged. The 2 most common defaults would be
"don't touch anything" (non-hygienic macros) and "make sure there's no
interference" (full hygiene, no capture). 

In the example we just discussed, the problem is that we have 3 AST
(around, inside and usercode) and we want to splice them in a fancy
way: there's only one capturing variable between around and inside,
and it must not capture anything in usercode. You hack your way around
to build a protective shell on usercode, then toss it with the other
ASTs. I'd rather write that around and inside share the same context,
and usercode has its own. Then when combining all those, the
hygienizer will know what to do. if I wanted to combine around's and
outside's contexts so that they'd only share "q_var", I should be able
to express that as well.

Bottom line is: I'd rather have 1st class context than implicit ones,
which will be a hassle to interact with when I have to. KISS
engineering at its best :)



Restent a faire:
================
- reflechir a l'addition automatique des mots-clef par les parsers qui
  vont bien. Peut-etre qu'ils sont attaches optionnellement a un lexer,
  et que cet attachement est transmis par defaut qd on insere un
  parser ds un autre
- notation pour la generation auto de sous-tables
- verifier le runtime error handling patch d'EVE
- anaphoric macros should bind 'it' to a function when it appears directly in
  it. it would allow anonymous recursive functions. However, anaphoric
  structures tend to capture each other very fast; maybe Arc has insightful
  ideas about this? (e.g. different captured names for function and other
  structs)


Bugs a verifier:
================
- reentrance de in_a_quote dans mlp_meta.lua
- refuser les flags autres qu'expr dans les splices in_a_quote

il faudra encore fournir une boucle interactive, celle de lua n'est
pas patchable. Idem pour le compilo.

metalua compiler/interpreter short usage manual
===============================================

Allows to compile and/or run metalua programs, and to use interactive
loop.

--compile
--run
--interactive
--output
--load-library <name>[@metalevel]
--print-ast

By default, parameters are passed to all running chunks. However, if
there is are parameters and no running chunk, the first parameter is
taken as the running chunk.

metalua --compile foo.mlua 

if there is an --output, all run and compiled files will be saved in
it.

- compile all files.
- displays ASTs depending on --print-ast
- run all files if --run
- run loop after compile and run if -i or if no file
- if no -a and no -o, -x is implied
- if -x and no file, first param is a file

2nd attempt
===========

Compile and/or execute metalua programs. Parameters passed to the
compiler should be prefixed with an option flag, hinting what must be
done with them: take tham as file names to compile, as library names
to load, as parameters passed to the running program... When option
flags lack, metalua tries to adopt a "Do What I Mean" approach:

- if no code (no library, no literal expression and no file) is
  specified, the first flag-less parameter is taken as a file name to
  load.

- if no code and no parameter is passed, an interactive loop is
  started.

- if a target file is specified with --output, the program is not
  executed by default, unless a --run flag forces it to. Conversely,
  if no --output target is specified, the code is run unless ++run
  forbids it.

When does it compile, when does it execute?
------------------------------------------- 
The result of the compilation is saved if there is a --output
specifying a destination file. If not, the result is run. If both
--output and --run are specified, the result is both saved and run. If
the compilation must be saved, it is mandatory to have at least one
file or library. 

How to load chunks to compile/run
---------------------------------
Files can be passed, with their relative paths, with --file. Libraries
can be loaded, from standard paths, with --library. Litteral blocks of
code can be passed with --literal.

When does it launch an interactive loop?
----------------------------------------
When --interactive is specified, or when no chunk is loaded.




Macro hygiene
=============

alpha should go at the top of the chunk *where the quote is used*,
which is generally not the same as where it's defined. Ideally, it
should go where the extension using the quote is called. So what I
really need is an improved 'extension' statement, which handles quotes
anhoring.

A serious problem is that most quotes are inside functions and
therefore not always evaluated in the extension() call.

Let's consider two instants:
- when the QQ is formally created for compilation (1)
- when it's returned by a function, presumably to be spliced (2)


 If alpha-conv
happens at QQ creation, then I lose the


So, alpha
conversion must happen at CT


Extension
=========
The current extension() function automatically loads a runtime, even
when empty. More control should be given. Both RT and CT parts should
go in the same directory. Finally, RT should probably handle macro
hygiene in a standardized way.

==> extension() should be like a require(), except that it:
- prepends 'extension.' to the module name
- returns nil when require() returns true

From there, macro alphas could be handled as follows:
- create a common alpha at the opening of the extension. As an empty list.
- push in in H() so that it'll be shared by all hygienizations
- return it if there' no runtime, or return it with a require()
  statement for the RT lib.

Shipping 0.4
============
- remove autotable: I don't use it and it isn't polished enough to be
  useful yet.

- remove machine and fsm_test; or at least, put it in samples

- remove mandatory platform from makefile call

- H loads extension/H-runtime.mlua?



README.TXT
==========
For installation matters, cf. INSTALL.TXT

Metalua 0.4
===========
Metalua is a static metaprogramming system for Lua: a set of tools
that let you alter the compilation process in arbitrary, powerful and
maintainable ways. For the potential first-time users of such a
system, a descripition of these tools, as implemented by metalua,
follows.

Dynamic Parsers
---------------
One of these tools is dynamic parser: a source file can change the
syntax recognized by the parser while it's being parsed. Taken alone,
this feature lets you make superficial syntax tweaks on the
language. The parser is based on a parser combinator called 'gg'. You
should know the half dozen functions in gg API to do advanced things,
but it means you can use and define functions that transform parsers:

- There are a couple of very simple combinators like gg.list,
  gg.sequence, qq.multisequence, gg.optkeyword etc. that offer a level
  of expressiveness comparable to Yacc-like parsers. For instance, if
  mlp.expr parses Lua expressions, gg.list{ mlp.expr } creates a
  parser which handles lists of Lua expressions.

- Since you can create all the combinators you can think of, there
  also are combinators specialized for typical language tasks. In
  Yacc-like systems, the language definition quickly becomes
  unreadable, because all non-native features have to be encoded in
  clumsy and brittle ways; so if your parser won't natively let you
  specify infix operator precedence and associativity easily, tough
  luck for you and your code maintainers. With combinators, this is
  abstracted away in a regular function, so you just write:

  > mlp.expr.infix:add{ "xor", prec=40, assoc='left', builder=xor_builder }

  Moreover, combinators tend to produce usable error messages when fed
  with syntactically incorrect inputs. It matters, because clearly
  explaining why an invalid input is invalid is almost as important as
  compiling a valid one, for a use=able compiler.

Yacc-like systems might seem simpler to adopt than combinators, as
long as they're used on extremely simple problems. However, if if you
either try to write something non trivial, or to write a simple macro
in a robust way, you'll need to use lots of messy tricks and hacks,
and spend much more time getting them (seemingly) ritght than that 1/2
hour required to master most of gg.


Real meta-programming
---------------------
If you plan to go beyond trivial keyword-for-keyword syntax tweaks,
what will limit you is the ability to manipulate source code
conveniently: without the proper tools and abstractions, even the
simplest tasks will turn into a dirty hacks fest, then either into a
nightmare, or most often into abandonware. Providing an empowering
framework is metalua's whole purpose.  The core principle is that
programs prefer to manipulate code as trees (whereas most developers
prefer ASCII sources). The make-or-break deal is then:

- To easily let users see sources as trees, as sources, or as
  combination thereof, and switch representations seamlessly.

- To offer the proper libraries, that won't force you to reinvent a
  square wheel, will take care of the most common pitfalls, won't
  force you to resort to brittle hacks.

On the former point, Lisps are at a huge advantage, their user syntax
already being trees. But languages with casual syntax can also offer
interchangeable tree/source views; metalua has some quoting +{ ... }
and anti-quoting -{ ... } operators which let you switch between both
representations at will: internally it works on trees, but you always
have the option to see them as quoted sources. Metalua also supports a
slightly improved syntax for syntax trees, to improve their
readability.

Library-wise, metalua offers a set of syntax tree manipulation tools:

- Structural pattern matching, a feature traditionally found in
  compiler-writing specialized languages (and which has nothing to do
  with string regular expressions BTW), which lets you express
  advanced tree analysis operations in a compact, readable and
  efficient way.  If you regularly have to work with advanced data
  structures and you try it, you'll never go back.

- The walker library allows you to perform transformations on big
  portions of programs. It lets you easily express things like:
  "replace all return statements which aren't in a nested function by
  error statements", "rename all local variables and their instances
  into unique fresh names", "list the variables which escape this
  chunk's scope", "insert a type-checking instruction into every
  assignments to variable X", etc. You can't write many non-trivial
  macros without needing to do some of those global code
  transformations.

- Macro hygiene, although not perfect yet in metalua, is required if
  you want to make macro writing reasonably usable (and contrary to a
  popular belief, renaming local variables into fresh names only
  address the easiest part of the hygiene issue; cf. changelog below
  for more details).

- The existing extensions are progressively refactored in more modular
  ways, so that their features can be effectively reused in other
  extensions.


Notworthy changes since 0.3
===========================

- A significantly bigger code base, mostly due to more libraries:
  about 2.5KLoC for libs, 4KLoC for the compiler. However, this remains
  tiny in today's desktop computers standards. You don't have to know
  all of the system to do useful stuff with it, and since compiled
  files are Lua 5.1 compatible, you can keep the "big" system on a
  development platform, and keep a lightweight runtime for embedded or
  otherwise underpowered targets.


- The compiler/interpreter front-end is completely rewritten. The new
  program, aptly named 'metalua', supports proper passing of arguments
  to programs, and is generally speaking much more user friendly than
  the mlc from the previous version.


- Metalua source libraries are looked for in environmemt variable
  LUA_MPATH, distinct from LUA_PATH. This way, in an application
  that's part Lua part Metalua, you keep a natural access to the
  native Lua compiler.

  By convention, metalua source files should have extension .mlua. By
  default, bytecode and plain lua files are preferred to metalua
  sources, which lets you easily precompile your libraries.


- Compilation of files are separated in different Lua Rings: this
  prevents unwanted side-effects when several files are compiled
  (This can be turned off, but shouldn't be IMO).


- Metalua features are accessible programmatically. Library
  'metalua.runtime' loads only the libraries necessary to run an
  already compiled file; 'metalua.compile' loads everything useful at
  compile-time.

  Transformation functions are available in a library 'mlc' that
  contains all meaningful transformation functions in the form
  'mlc.destformat_of_sourceformat()', such as 'mlc.luacfile_of_ast()',
  'mlc.function_of_luastring()' etc. This library has been
  significantly completed and rewritten (in metalua) since v0.3.


- Helper libraries have been added. For now they're in the
  distribution, at some point they should be luarocked in. These
  include:
  - Lua Rings and Pluto, duct-taped together into Springs, an improved
    Rings that lets states exchange arbitrary data instead of just
    scalars and strings.
  - Lua bits for bytecode dumping.
  - As always, very large amounts of code borrowed from Yueliang.
  - As a commodity, I've also packaged Lua sources in.


- Builds on Linux, OSX, Microsoft Visual Studio. Might build on mingw
  (not tested recently). It's easily ported to all systems with a full
  support for lua.

  The MS-windows building is hackish: it's driven by a batch script,
  and Pluto can't compile as a win32 DLL, so it's linked in the Lua
  VM. If you want to run your own VM, either link pluto in statically,
  or disabled separate compilation by setting environment variable
  LUA_MFAST at true. In the later case, expect puzzling behaviors when
  you load several sources containing compile-time code (==>
  precompile everything).

  Notice that bits of the compiler itself are now written in metalua,
  which means that its building now goes through a bootstrapping
  stage.


- Structural pattern matching:
  - now also handles string regular expressions: 'someregexp'/pattern
    will match if the tested term is a string accepted by the regexp,
    and on success, the list of captures done by the regexp is matched
    against pattern.
  - Matching of multiple values has been optimized
  - the default behavior when no case match is no to raise an error,
    it's the most commonly expected case in practice. Trivial to
    cancel with a final catch-all pattern.
  - generated calls to type() are now hygienic (it's been the cause of
    a puzzling bug report; again, hygiene is hard).


- AST grammar overhaul: 
  The whole point of being alpha is to fix APIs with a more relaxed
  attitude towards backward compatibility. I think and hope it's the
  last AST revision, so here is it:
  - `Let{...} is now called `Set{...} 
    (Functional programmers would expect 'Let' to introduce an
    immutable binding, and assignment isn't immutable in Lua)
  - `Key{ key, value } in table literals is now written `Pair{ key, value }
    (it contained a key *and* its associated value; besides, 'Pair' is
    consistent with the name of the for-loop iterator)
  - `Method{...} is now `Invoke{...}
    (because it's a method invocation, not a method declaration)
  - `One{...} is now `Paren{...} and is properly documented
    (it's the node representing parentheses: it's necessary, since
    parentheses are sometimes meaningful in Lua)
  - Operator are simplified: `Op{ 'add', +{2}, +{2} } instead of
    `Op{ `Add, +{2}, +{2} }. Operator names match the corresponding
    metatable entries, without the leading double-underscore.
  - The operators which haven't a metatable counterpart are
    deprecated: 'ne', 'ge', 'gt'.

 
- Overhaul of the code walking library:
  - the API has been simplified: the fancy predicates proved more
    cumbersome to use than a bit pattern matching in the visitors
  - binding identifiers are handled as a distinct AST class
  - walk.id is scope-aware, handles free and bound variables in a
    sensible way.
  - the currified API proved useless and sometimes cumbersome, it's
    been removed.


- Hygiene: I originally planned to release a full-featured hygienic
  macro system with v0.4, but what exists remains a work in
  progress. Lua is a Lisp-1, which means unhygienic macros are very
  dangerous, and hygiene a la Scheme pretty much limits macro writing
  to a term rewriting subset of the language, which is crippling to
  use. 

  Note: inside hygiene, i.e. local variables created by the macro
  which might capture user's variable instances, is trivial to address
  by alpha conversion. The trickier part is outside hygiene, when
  user's binders capture globals required by the macro-generated
  code. That's the cause of pretty puzzling and hard to find bugs. And
  the *really* tricky part, which is still unsolved in metalua, is
  when you have several levels of nesting between user code and macro
  code. For now this case has to be hygienized by hand.

  Note 2: Converge has a pretty powerful approach of hygienic macros
  in a Lisp-1 language; for long and boringly technical reasons, I
  don't think its approch would be the best suited to metalua.

  Note 3: Redittors must have read that Paul Graham has released Arc,
  which is also a Lisp-1 with Common Lisp style macros; I expect this
  to create a bit of buzz, out of which might emerge proper solutions
  the macro hygiene problem.


- No more need to create custom syntax for macros when you don't want
  to. Extension 'dollar' will let you declare macros in the dollar
  table, as in +{block: function dollar.MYMACRO(a, b, c) ... end},
  and use it as $MYMACRO(1, 2, 3) in your code.

  With this extension, you can write macros without knowing anything
  about the metalua parser. Together with quasi-quotes and automatic
  hygiene, this will probably be the closest we can go to "macros for
  dummies" without creating an unmaintainable mess generator.


- Lexers can be switched on the fly. This lets you change the set of
  keywords temporarily, with the new gg.with_lexer() functor, or
  handle radically different syntaxes in a single file (think
  multiple-languages systems such as LuaTeX, or programs+goo as PHP).


- Incorporation of the bugs listed on the mailing list and the blog.


- New samples and extensions, in various states of completion:

  - lists by comprehension, a la python/haskell. It includes lists
    chunking, e.g. mylist[1 ... 3, 5 ... 7]

  - anaphoric macros for 'if' and 'while' statements: with this
    extension, the condition of the 'if'/'while' is bound to variable
    'it' in the body; it lets you write things like:
    while file:read '*l' do print(it) end.
    No runtime overhead when 'it' isn't used in the body. An anaphoric
    variable should also be made accessible for functions, to let
    easily write anonymous recursive functions.

  - continue statement, logging facility, ternary "?:" choice operator

  - Try ... catch ... finally extension.

  - with ... do extension: it uses try/finally to make sure that
    resources will be properly closed. The only constraint on
    resources is that they have to sport a :close() releasing method.
    For instance, he following code guarantees that file1 and file2
    will be closed, even if a return or an error occurs in the body.

    with file1, file2 = io.open "f1.txt", io.open "f2.txt" do
       contents = file1:read'*a' .. file2:read ;*a'
    end


Credits
=======
I'd like to thank the people who wrote the open source code which
makes metalua run: the Lua team, the authors of Yueliang, Pluto, Lua
Rings, Bitlib; the people whose bug reports, patches and insightful
discussions dramatically improved the global design, including
Laurence Tratt, Viacheslav Egorov, David Manura, John Belmonte, Eric
Raible...