Some questions recieved about MELT

[Basile Starynkevitch]

Hello All on the gcc-melt@ list....

(with blind copy to the person who sent me some questions about MELT in private)

I've got some technical questions by [private] email. Since the answer to them
should be of general interest, I dare giving my answers publicly on this public
list gcc-...@googlegroups.com; I'm somehow rephrasing the questions.


A general advice about starting on MELT is to understand some of GCC internals, and the
absolutely fondamental difference between first-class values and stuff (e.g. :gimple things)

Also, please download and use the latest MELT snapshot...




******
** rewriting GIMPLE code:

It should be possible to transform GIMPLE with MELT.
The real issue (and that may be a hard one, and the
details depend upon the use case) is to understand when to do
that transformation.

Every GCC optimization pass is transforming internal GCC representations (Gimple) into
another such representation, and you can insert arbitrary passes in MELT.
However, the GCC compiler itself has its own invariant properties about its passes.

The MELT pieces relevant for that are in files gcc/melt/xtramelt*.melt

creation of your instance of class_gcc_gimple_pass or class_gcc_simple_ipa_pass

installing that MELT pass using install_melt_gcc_pass

The difficult issue is where to install that pass.
And that depends upon what your pass want to do.

You have the basic components for making such a pass. Of course,
the pattern matching on gimple, and also the fact
that most constructs are able both to pattern match and
to construct some gimple.

For instance, you use the gimple_assign_plus in a pattern to detect simple arithmetic operations:

(match g ;; a gimple stuff
(?(gimple_assign_plus ?lhs ?rhs1 ?rhs2)
;; do something when g is an addition lhs = rsh1 + rhs2
(your_code_with lhs rhs1 rhs2)
)
(?_
;; wildcard catch-all
;; otherwise do code here
(your_other_code)
))

But you can also build such a gimple using the (gimple_assign_plus lhs rhs1 rhs2) expression.
The issue is what to do with that gimple. It depends.... (Don't forget that you always
can use code_chunk to write some C++ code mixing MELT variables with GCC function calls)

So MELT should enable you to do "aspect oriented programming" (but you need to understand
where you will insert your MELT pass in the GCC pass flow).




*****
** macros in MELT

MELT does not support (today, april 2013)
yet macros as easily as Scheme or Common Lisp do, e.g.
(defmacro addone (a) `(+i ,a 1))
because the backquote and comma syntax macros are not yet implemented.
However, the reader is parsing them. Implementing backquote & comma is on my TODO list
(it would require using TRANSLATE_RUN_MELT_EXPRESSIONS, which is nearly our EVAL, but internally generates some *.c file, compile it into some *.so, and dlopen that, and run some
dlsym-ed function inside...).

However, there is some crude way to do macros today. And actually,
most of MELT implementation is using macros already.... So let me explain a bit more...

First, an "s-expr" in MELT is actually an instance of CLASS_SEXPR with two fields, the first
giving (if known) the source location, and the second giving the list of components
in that s-expr. So the s-expr (+i 2 3) supposedly at line 3 column 4 of foo.melt
is parsed by the MELT reader coded in C as an instance of CLASS_SEXPR a bit like

(instance class_sexpr
:loca_location (the_location_at "foo.melt" 3 4)
:sexp_content (list '+i 2 3))

[[but I have no the_location_at primitive, it is here to explain you what the MELT reader do]]


Then, the MELT translator indeed do some macro-expansion on every MELT s-expression.
The macro expansion of any s-expr is supposed to give an instance of some sub-class of
CLASS_SOURCE. Actually, the macro-expansion of the above s-expr is something similar to
the result of

(instance class_source_primitive
:loca_location (the_location_at "foo.melt" 3 4)
:sprim_oper the_+i_primitive
:sargop_args (tuple 2 3))

Of course, the_+i_primitive is something complex
an instance of class_primitive which probably is the value of the +i symbol


Now, you may have macros: they should expand some instance of CLASS_SEXPR
into some instance of a subclass of CLASS_SOURCE. Every macro expander
is a function (a closure) recieving as arguments:

1. the s-expr, instance of CLASS_SEXPR, to expand

2. the environment in which you are expanding

3. the macro-expander to be used to recursively macro-expand
components of your s-expr.

4. a module generation context, instance of CLASS_MODULE_CONTEXT

and that macro-expander should return an instance of some subclass of CLASS_SOURCE
or perhaps some "atomic" value like a symbol or a boxed integer.
Later, that value -often some CLASS_SOURCE indirect instance- will be normalized.

Once you have your macro-expander function mexpand_foo,
you can install it for your macro foo with
(export_macro foo mexpand_foo)
then further MELT modules (but not the current one) are able to use the FOO macro....

I invite you to look at the code of mexpand_unless
in file melt/warmelt-macro.melt perhaps near line 4470
as a simple example of macro.

So the macro ADDONE might be coded as perhaps the following,
which build the temporary sexpression (+i ARG 1) and macroexpands it.

;; untested code, could be wrong
(defun mexpand_addone (sexpr env mexpander modctx)
(let (
(cont (get_field :sexp_contents sexpr))
(loc (get_field :loca_location sexpr))
(contup (list_to_multiple cont discr_multiple))
)
;; we have 2 components in our sexpr, the first being ADDONE
(when (!=i (multiple_length contup) 2)
(error_plain loc "(ADDONE <expr>) wants a single argument)
(return))
(let ( (macarg (multiple_nth contup 1))
(sexplus (instance class_sexpr
:loca_location loc
:sexp_contents (list '+i macarg 1)))
(res (mexpand sexplus env mexpander modctx))
)
res)))

Notice that we are making a temporary instance sexplus of CLASS_SEXPR and expanding it.
This is not the most clever, we could macroexpand only macarg and create
the appropriate instance of class_source_primitive

Later in the same MELT source code we do

(export_macro addone mexpand_addone)

Then any further MELT module (but not the current one!) can use addone.
So you would define your macros in a foomacro.melt file,
and have your GCC extension in another fooana.melt file.




By the way, you could even extend your MELT language even further:
you could perhaps add your own subclasses of CLASS_SOURCE, and then
add their normalization method, etc... You could even have your own
subclasses of CLASS_NREP -representing normalized forms- etc etc...
So an adventurous MELT user could extend a lot the MELT language,
without having to patch a single line of the current MELT implementation
(the melt/warmelt*.melt files)





*****
** Can MELT load other code

Of course yes, using the same syntax (LOAD "somesource.melt") as most other lisps
Look at the code of mexpand_load near line 3830 of melt/warmelt-macro.melt to see
how it is implemented....

However, you may want to use several modules. LOAD is just a macro mechanism.



*****
** Does MELT have a read-eval-print-loop [REPL] able to do simple arithmetic.

In principle, yes. Use the repl mode, i.e. pass -fplugin-arg-melt-mode=repl to your gcc
and pass some empty C file to have cc1 started!

The REPL is reading a sequence of expressions ended by two -not one, but two- newlines.
Then, it is compiling that sequence to a C code, forking a make to build a *.so, dlopen-ing that, etc... Notice that the REPL wants a sequence of one or more s-expressions
ended by two newlines.

However, the arithmetic has not the same syntax as most Scheme or Lisp.
First, arithmetic operators have fixed arity. So addition requires two arguments.
Then, an important [mis-]feature in MELT is the essential value vs stuff distinction.
(I won't explain it here again, there are a lot of material explaning that already).
That distinction is mandated by the GCC compiler (and its memory management).

Recall that in MELT (contrarily to Scheme or Common Lisp) 1 is a stuff
-raw unboxed :long thing, exactly a long data in the generated C++ code-
and '1 is a value, a boxed integer of discriminant discr_constant_integer,
which you could get with (make_integerbox discr_constant_integer 1) and that
primitive may trigger the garbage collector since it is allocating a value...

Actually, you have several additions in MELT code, all are binary operations:

+i takes two :long stuff and gives a :long result; so (+i 2 3) is the :long stuff 5

+iv takes two values, and if both are boxed integers give the sum of their
boxed numbers as a boxed integer, else nil. So (+iv '2 '3) evaluate to
something like '5 but gives a value at a new address

+ivi takes a value and a raw :long stuff, e.g. (+ivi '2 3) and produced a boxed value
if the first argument is a boxed integer value, or else nil


So you cannot code (+ 1 2 3) in MELT, you need to code
(+i 1 (+i 2 3)) which gives a long stuff
or (+iv '1 (+iv '2 '3)) or (+iv '1 (+i 2 3)) which gives a boxed value.

****
* Evaluation mode

That question was not asked, but you can evaluate a single sequence of MELT
expressions, for example

gcc -c -fplugin=melt -fplugin-arg-melt-mode=eval \
-fplugin-arg-melt-arg="(parent_module_environment)" \
empty.c

I invite you to type that command, you'll understand more what MELT environments are.
You could even try with "(current_module_environment_container)"

In practice, adding a lot of (DEBUG ....) expressions in your MELT code don't hurt.
Use the translatequickly or runfile modes...



****
* Extending MELT with your C or C++ code.

Of course that is possible. You want to read about CODE_CHUNK CHEADER and USE_PACKAGE_FROM_PKG_CONFIG -and perhaps DEFPRIMITIVE DEFCMATCHER
DEFCITERATOR etc... macros in http://gcc-melt.org/meltpluginapi.html
Notice that USE_PACKAGE_FROM_PKG_CONFIG enables you to use any package
known by pkg-config and that is very handy, e.g. libpcre for
Perl compatible regular expressions. Adding a *.pc file for software not
packaged yet by pkg-config (like MySQL) is quite simple.


****
* embedding the REPL inside a GUI

This is also in my TODO list (for the probe or something better). But
you could also consider using REGISTER_INPUT_CHANNEL_HANDLER if you have
your own textual asynchronous protocol between some of your GUI interface
and MELT. Look inside xtramelt-probe.melt for an example.


Hope this helps.

Cheers
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

[Sanel Zukan]

Hi,

Sorry for a bit late reply... Looks like you were faster and pasted my
mail here before I did :)

> It should be possible to transform GIMPLE with MELT.
> The real issue (and that may be a hard one, and the
> details depend upon the use case) is to understand when to do
> that transformation.

I quickly scanned your presentations and found how gcc could done more
than 200 passes :S AFAIK, there is example how to print passes from
MELT. But, in my case, I would be happy to do it as early as possible.

> The difficult issue is where to install that pass.
> And that depends upon what your pass want to do.

For example let we have this:

--------------------------
static void __placeholder() {}

int main() {
  __placeholder();

  /* rest of the code */

  return 0;
}
--------------------------

Now, depending on some cases I would like to fill __placeholder() body
with some content (or replace it), and in some cases just remove it or
leave it to optimizer for removal. But, after further reading your
presentations and reading the code, I found this shouldn't be hard.

However, the second use case: is it possible to influence or install
pass before syntax check pass? Let say I would like to add operator
'<-' that behaves just like '=', so the code can look like:

 a <- foo(1,2)

and after MELT pass, it will be rewritten to:

 a = foo(1,2);

leaving the rest to gcc. Can this be done?

> MELT does not support (today, april 2013)
> yet macros as easily as Scheme or Common Lisp do, e.g.

> ...

> However, there is some crude way to do macros today. And actually,
> most of MELT implementation is using macros already....

I scanned 'warmelt-macro.melt' a little bit and it looks quite
interesting.  However, what is the reason behind this macro design and
approach? Additional pass that will perform standard macro expansion
like is done in other lisps sounds to me much simpler approach...

> Of course yes, using the same syntax (LOAD "somesource.melt") as
> most other lisps

> ...
> However, you may want to use several modules. LOAD is just a macro
> mechanism.

Excellent!

> But you could also consider using REGISTER_INPUT_CHANNEL_HANDLER if
> you have your own textual asynchronous protocol between some of your
> GUI interface and MELT. Look inside xtramelt-probe.melt for an
> example.

Cool, I'll inspect this.

Thanks for detail reply.

Best,
Sanel

[Basile Starynkevitch]

On Mon, Apr 15, 2013 at 05:18:44AM -0700, Sanel Zukan wrote:
> Hi,
>
> Sorry for a bit late reply... Looks like you were faster and pasted my
> mail here before I did :)
>
> > It should be possible to transform GIMPLE with MELT.
> > The real issue (and that may be a hard one, and the
> > details depend upon the use case) is to understand when to do
> > that transformation.
>
> I quickly scanned your presentations and found how gcc could done more
> than 200 passes :S AFAIK, there is example how to print passes from
> MELT. But, in my case, I would be happy to do it as early as possible.

Be careful to not do it too early. If you do your transformations at
a very early stage, GCC has not yet computed enough internal representations
(for instance, you probably want its CFG= control flow graph information).

>
> > The difficult issue is where to install that pass.
> > And that depends upon what your pass want to do.
>
> For example let we have this:
>
> --------------------------
> static void __placeholder() {}
>
> int main() {
> __placeholder();
>
> /* rest of the code */
>
> return 0;
> }
> --------------------------
>
> Now, depending on some cases I would like to fill __placeholder() body
> with some content (or replace it), and in some cases just remove it or
> leave it to optimizer for removal. But, after further reading your
> presentations and reading the code, I found this shouldn't be hard.

You might make __placeholder a GCC builtin if that helps.
(I don't understand who is adding the call to __placeholder. Do you expect
your user to write that explicitly in his main.c file?)

Alternatively, you could have a pass which handles specifically the main function
(which GCC recognizes somehow) and insert automagically inside its body,
just at the start of the relevant basic block, a call to your placeholder.

>
> However, the second use case: is it possible to influence or install
> pass before syntax check pass? Let say I would like to add operator
> '<-' that behaves just like '=', so the code can look like:
>
> a <- foo(1,2)
>
> and after MELT pass, it will be rewritten to:
>
> a = foo(1,2);

This is simply not possible by using current GCC plugin technology
(i.e. both with MELT, and thru your own C++ hand-written GCC plugin).
The reason is that GCC parsing offers no plugin hooks. So by the time
any plugin code is reached (and that includes MELT and your MELT extensions)
the abstract syntax tree has already been parsed. BTW, a <- foo(1,2) is
parsed in C or C++ as a less-than operator followed by a minus unary operator:
a < (- (foo(1,2))) ...

>
> > MELT does not support (today, april 2013)
> > yet macros as easily as Scheme or Common Lisp do, e.g.
> > ...
> > However, there is some crude way to do macros today. And actually,
> > most of MELT implementation is using macros already....
>
> I scanned 'warmelt-macro.melt' a little bit and it looks quite
> interesting. However, what is the reason behind this macro design and
> approach? Additional pass that will perform standard macro expansion
> like is done in other lisps sounds to me much simpler approach...

There are several reasons. Please understand that MELT was incrementally designed & implemented, and that compatibility with GCC internals was always a driving principle.
I was also greatly inspired by C.Queinnec's Lisp in Small Pieces book.

Many reasons are somehow explained in my DSL2011 paper
http://gcc-melt.org/MELT-Starynkevitch-DSL2011.pdf

First, I wanted to keep source location of every MELT s-expr. This is important notably
because MELT is emitting a big lot of #line directives. So if something bad happens
(e.g. a core dump) you should get an understandable backtrace (even in gdb)
So a MELT s-expr cannot be just a list, it has to contain its source location,
and that source location will appear in emitted #line directives.
And you can also experiment with MELT and add somewhere in your code a false assert e.g.

(assert_msg "some message")

When you reach that MELT expression (translated in translatequickly mode,
or using eval, or repl, or runfile modes) you'll see a rather nice MELT
backtrace, please try. In other words, you often don't need gdb to debug MELT code,
you can just use debug & assert_msg expressions (and pass -fmelt-plugin-arg-debug).
Actually, I almost never use gdb to debug MELT.

Then, the MELT language was itself incrementally designed. And the MELT runtime
requires normalization (because of the precise copying garbage collector for
MELT values), so (f (g x) y) is actually transformed into some internal equivalent of
(let ( (tmp (g x)) ) (f tmp y)) this can be pedantically called
http://en.wikipedia.org/wiki/A-normal_form

So inside MELT,

the reader coded in C inside melt-runtime.c is parsing s-exprs (of class_sexpr)

s-expr (of class_sexpr) are transformed into source forms (of class_source) by the
macro expansion phase (file melt/warmelt-macro.melt)

source form expressions are transformed into normal expressions (of class_nrep)
by the normalization phase (file melt/warmelt-normal.melt); the pattern matching
normalization is complex enough to be handled by a separate file melt/warmelt-normatch.melt

normal expressions are transformed into C generated object forms (of class_objvalue for
"expression" like objects and of class_objinstr for "instruction" like objects)
this "generation" happens in melt/warmelt-genobj.melt

object forms are emitted as C or C++ code in file melt/warmelt-outobj.melt

and the picture is actually more complex: in addition of emitting one C or C++ function
for every MELT "procedure" (i.e. a function defined by defun or lambda) we also emit
code to mark each MELT call frame and be nice both with MELT copying garbage collector
& with Ggc (the GCC marking GC). Also every initial data is filled inside the initialization
routine (there is no data outside of C code, so even closures have
to filled at initialization time). So the initialization routine
is conceptually huge (and in practice divided in many smaller chunks,
to make the GCC compiling the MELT generated C/C++ code happy.).

Actually, some of MELT implementation is a bit messy (but I don't have much resources to
re-implement MELT in a cleaner way). However it works.


The advantage of such a design is to stay compatible with GCC runtime,
while still being able to incrementally add additional linguistic
features to MELT.

In particular, an advanced MELT user is in principle able to add new
language trait to MELT without editing the existing MELT implementation
code: the design is "modular" enough to make that possible, since you
can add your own MELT macros, your own subclasses of class_source,
implement the required methods & functions for macro expansions and
for normalization and compilation to object forms, add your own subclasses
of clas_nrep, your own subclasses of class_objvalue & class_objinstr, etc....)


By the way, every existing MELT syntactic construct, including defun,
defprimitive, let, letrec, lambda, setq, if, cond, .... is implemented
as a macro.

If you happen to be interested in extending the MELT core language
(e.g. adding defmacro, comma, backquote...) be sure to contact me and more
importantly to start the http://gcc.gnu.org/contribute.html legal prerequisites
because I cannot accept any patch to GCC MELT from your part without
you being officially recognized as a GCC maintainer (because MELT
is copyrighted by FSF as any GCC branch).

Thanks for your interest.

BTW, do you have a repository (github, elsewhere?) of your MELT experimentations?