Tutorial on the MELT domain-specific language

Audience: You are expected to have successfully downloaded and installed GCC MELT on your machine (probably under GNU/Linux running a recent version -4.6 at least, and preferably 4.7- of GCC). You should also have read the tutorial about using GCC MELT. You are invited to test small examples of MELT, e.g. with the eval or evalfile mode. Familiarity with more than one programming language is welcome, in particular with some functional programming language, and with pattern matching. The well known SICP book is a good introduction, and it uses the Scheme programming language, which largely inspired MELT.

Nota Bene

Notice that MELT is a domain specific language designed to work in the GCC compiler. Hence, it is able to work both on MELT values and also GCC stuff (e.g. raw internal GCC represerntations like Gimple-s, Generic tree-s, and control flow representations like edges and basic blocks, and also raw long integers, etc, etc...).

This page does not focus on the various stuff handled by the MELT language (even if they are one of its main strengths), nor on the various hooks between GCC and MELT. It focus more on MELT as a programming language.
(deliberately ignoring the fact that you won't use MELT for general purpose programming tasks)
This tutorial page is still incomplete! Read also the DSL 2011 paper and the HiPEAC 2012 tutorial slides.

The distinction between MELT values and GCC stuff is essential. It is a direct consequence of GCC internal architecture. values are first class citizens and are dynamically typed (like in Scheme, Python, Javascript, ...) but stuff is statically typed (like in C, or Ocaml, ...) and require explicit code annotations.

Values are easier to work with in MELT, but GCC internals work mostly with stuff. However, you usually should prefer dealing with values. Making a value from some stuff is called boxing. Extracting the stuff inside some value is called unboxing, or taking the content of that value. Of course MELT gives you a lot of value which are not boxing some GCC stuff, but which aggregate other values, e.g. tuples, lists, homegenous hash-tables, objects, closures (or functional values), etc. The MELT runtime handle values efficiently. In particular, they are quickly allocated and garbage collected. But most stuff is directly handled by GCC (so allocating and garbage collecting them could be more costly).

MELT is a Lisp-like (or Scheme-like) language. So almost all syntactic constructs are in parenthesis. In particular (f) -usually the call of function f without arguments like f() in C- is never the same as f. Exceptions to this every composite expression is parenthesised rule are avoidable syntactic sugar, see below.

Reference material

Reference material about the MELT language is available on the [large] MELT plugin API document, which complements this page. Core language operators (like if or let etc....) are called macros, because they are all implemented by a macro-like mechanism. That MELT plugin API document also lists the documented primitives, functions, classes, iterators, matchers etc... available to the user.

MELT versus other languages

MELT is a domain specific language to easily extend GCC. Its distinctive strength is to be tightly related to GCC internals, while facilitating powerful programming paradigms. It is translated to C or C++ and you can insert some C/C++ code chunks inside your MELT code. The MELT language has several features to ease your own extensions or customizations of the GCC compiler.

MELT compared to other languages

Here are some guiding distinctions between MELT and some other programming languages. Bear in mind the essential values vs stuff difference, which distingish MELT with every other programming language.

Notice that MELT is lexically scoped. A name is bound in a well defined syntactic scope (the let expression defining it, or the rest of the source file for global defun, definstance, defclass ....).

Trivial MELT examples

You should try these examples by yourself using the eval or evalfile mode of MELT for evaluation. Some examples below looks familiar if you know Scheme, others are very MELT specific.

The quotation operator quote is so important in MELT that there is some syntactic sugar for quote: as in Scheme or Common Lisp, in MELT (quote expression) can always be written as 'expression so '23(quote 23) and '"hello"(quote "hello") and 'x(quote x)

Notice that in MELT, contrarily to Lisp or Scheme, (quote 23) which you prefer to write as '23 is not the same as 23, since '23 gives a value but 23 denotes a long stuff

The quotation of a symbol gives some MELT object value, instance of class_symbol, so 'if`IF|CLASS_SYMBOL/7023b80{}
the 7023b80 hex-digits are the hash-code of that object.

The discrim primitive gets the discriminant of some value, since each value has its discriminant. For object values, their discriminant is their class. So (discrim 'x) show with more details the class_symbol (since 'x`X|CLASS_SYMBOL/33facab6{}), i.e.

      **`DBG_OUTPUT|CLASS_SELECTOR/f9d7509{} == .?.; 
      **`DBG_OUTPUTAGAIN|CLASS_SELECTOR/23059a7{} == .?.; 
      **`NORMAL_EXP|CLASS_SELECTOR/2ffb4614{} == .?.; } 
The #20011 is the magic number inside class_symbol. The above output shows the method dictionnary for symbols, the ancestors, and the fields. Some information is hidden with .?., etc.. (because occuring too deeply).

It is possible to define your own names with define operator at top-level, the defined symbol can be used in further expressions. So (define one '1) (+iv one '12)|DISCR_CONSTANT_INTEGER#13 because +iv is the primitive adding two values and producing a new integer value (it is slower that +i because it is allocating a boxed integer value). Other defining operators exist (they all start with def), notably defun to define named functions, definstance to define named object instances, and defclass to define a named class.

In MELT local variable bindings are introduced with the let operator, followed by a sequence of bindings, followed by a body, i.e. a non-empty sequence of expressions. The binding sequence could be empty (but that is silly), and the body can be reduced to a single expression. The bindings make sense only inside the whole let expression. So (let ( (:long x 1) (y 'big) ) (if (>i x 0) y 'bang))`BIG|CLASS_SYMBOL/2072af88{} since the body (if (>i x 0) y 'bang) gets evaluated in an environment with two bindings: first the name x is bound to the long stuff 1, and then the name y is bound to the big value of class_symbol. Of course the sequence (let ( (one '1) ) (discrim one)) (if one 12 33) fails with an error unknown name; symbol is not bound - ONE because the binding of one is local to the let expression (let ( (one '1) ) (discrim one)) so is not visible from the second expression (if one 12 33)

The Hello World program in MELT

The boxed FILE* stream can be obtained with (get_field :sysdata_stdout initial_system_data) and the add2out variadic function is defined to add to some output given by its first argument (a boxed FILE* stream value, or a string buffer value), so we could code in pure MELT the following:

;; file hello-world-pure.melt
  (let ( (stdout  (get_field  :sysdata_stdout initial_system_data))
     (add2out stdout "Hello World\n"))

Notice that we don't have to define a function (like main for C). We just give an expression (the entire three-lines let expression above) to evaluate, and its evaluation has the desired side-effect (of saying Hello World to us).

However, we could also mix C code inside some MELT file, by incorporating a code chunk, with:

;; file hello-world-chunk.melt
    (code_chunk hello_chk
                #{ /* $HELLO_CHK chunk */ printf("Hello World\n");}#)
Grossly speaking, code_chunk is to MELT what the asm keyword is to C, a way to incorporate some code in the translated form (for MELT language, the translated form is in C or C++, for C, the translated form is in assembly language).

The first argument to the code_chunk, here hello_chk, should be a so-called state symbol (which usually is not bound outside of the code_chunk expression). The state symbol is expanded to some unique generated C identifier.

The second argument to the code_chunk, here
  #{ /* $HELLO_CHK chunk */ printf("Hello World\n");}#
is a macro-string. Macro-strings, inspired by the bash shell handling of $ inside double-quoted strings, start with bang left-brace #{ and are ended by the right-brace bang }# two-characters sequence. The two-characters sequences #{ and }# have been carefully choosen because they cannot appear in C code (outside of literal strings or comments, so it is always possible to avoid writing them). Macro-strings are mixing string literals and MELT symbols (when they are prefixed with a $ dollar sign). Most characters in macro-strings are taken literally.

The state symbol in a code_chunk is useful because it is uniquely expanded. So the first time some expansion occurs, hello_chk is translated as HELLO_CHK__1, the second time this expansion occurs, it is emitted as HELLO_CHK__2 etc. This is useful to obtain unique C identifiers in the generated C code. For instance, we could have counted the number of Hello World messages, repeating them randomly, using:

;; file hello-world-counted.melt
    (code_chunk hellocount_chk
                #{ /* $HELLOCOUNT_CHK chunk */ 
                     static int $HELLOCOUNT_CHK#_counter; 
                     printf ("Hello World, counted %d\n", 
                     if (random() % 4 == 0) goto $HELLOCOUNT_CHK#_lab;

A uniquely expanded state symbol is useful here to generate a unique C label.
Actually, state symbols are much more useful in other MELT constructions defining how to translate something to C code, e.g. in defciterator-s etc.

It is not uncommon to have macro-strings of a few dozen lines, or more. It is advised to emit, thu the macro-string, some distinctive C comment.

Since MELT 0.9.9, a code_chunk can contain arbitrary MELT [sub-]expressions given for their side-effects, provided their ctype is :void (you could use a progn ending with (void) for that purpose). Such expressions appearing in the code chunk macrostring are expanded, at place of their occurrence, to a C++ block.

Macro-strings are also used by expr_chunk, a syntactic construct giving an expression defined by a state symbol and a macro-string. For instance, you could get the process-id with (expr_chunk getpid_chk :long #{/* $GETPID_CHK*/ (long)getpid()}#); notice that in contrast to code_chunk-s, expr_chunk-s are strictly evaluating their sub-expressions, and are internally converted to their A-normal form like all primitive invocations, function calls, etc... in MELT.

MELT values

Example of MELT values

Every MELT value has an immutable discriminant. For a MELT object, its discriminant is its class. Discriminants (in particular classes), selectors, and fields are themselves objects and are used for message dispatching (à la Ruby or Smalltalk) using a method dictionnary (actually, an hash-table) inside discriminants. Classes are organised with single-inheritance, the top-level class is class_root, the top-level discriminant is discr_any_receiver (which is the super of class_root). The null value has discr_null_receiver as its discriminant.

value kinds

MELT values can be:

MELT values can move in memory, because of the generational copying MELT garbage collector, which may be called at any allocation.
(hence it is usually unsafe to retrieve the raw string inside a string value, store an interior pointer somewhere, etc...)

defining named values

It is possible to define names as values (but not stuff) notably:

dynamically building values

Without being exaustive, here are some common idiomatic expressions to dynamically build values:

GCC stuff in MELT

MELT needs to be able to handle raw GCC stuff. It does so by static c-type annotations (using so called Lisp keyword symbols starting with a colon :), using:

Lisp-like keyword symbols starting with a colon can also play other roles. In particular :true denote the prefered boolean true value; but unlike in Scheme, and inspired by Lisp or C, every non-null value is considered true in MELT. the leyword :rest is used in variadic formal arguments, and :else may appear in conditionals. Very often, keyword symbols represent fields inside MELT objects, like in (get_field :content_value x), but keyword symbols are not reserved in any way (you might want to use them in MELT like you would use enumaration identifiers in C).

A MELT c-type is reified as some predefined MELT object. For example, the object ctype_long describes the :long c-type, and ctype_tree describes :tree etc. Use the MELT evaluator to display some of these.

C-type annotations appear in

Stuff usually fits in a machine word, because long does, and because other stuff c-types like :tree, :gimple etc... are in fact pointers to some GCC internal data. So a :long stuff is true iff it isn't O, and a :tree stuff is true iff it isn't the null tree pointer, etc.

Beware that some GCC passes are forcibly destroying some stuff (without using Ggc, the Gcc garbage collector). So handle stuff with care, only in your passes inserted appropriately. For instance, the "expand" pass of GCC in its file gcc/cfgexpand.c is forcibly destroying some edges, so you cannot manipulate in MELT these edges (even if they have been boxed by your code) after that pass has been executed.
(this is not specific to MELT; every GCC plugin would have this issue.)

Functions in MELT

Functions are a very powerful feature of the MELT language, and are not like functions in C, but more like functional values in Ocaml, Lisp, Lua, Ruby, etc... Functions are first class values (called closures). You can define top-level named functions with defun, and dynamically build anonymous functions with lambda. The last expression in the function body usually gives the result of the function.
The defun operator is followed by the defined function name, then the list of formal arguments, then the body of the function. The lambda operator is followed by the list of formal arguments, then the body of the anonymous function.

The first argument (if given) of a MELT function should be a value but other arguments can be any things, either values or stuff. The primary result of a function should be a value. Hence you cannot code (defun badsucc (:long i) (+i i 1)) for two reasons: its first formal argument i is a long stuff, and its primary result is also a long stuff (both should be values).

A function can possibly return other secondary results which may be any things (either a value or some stuff).
The requirement that the first argument, if any, of a function is a value, and that the primary result is a value facilitates nesting of function calls, and using functions as method in the object system and in message passing, then the first arrgument is the reciever of the message.

A function can get, from some call, less arguments than what its formal arguments list requires. In that case, missing arguments are cleared. If the type of actual arguments does not match the type of formal parameters, the remaining formals are cleared.

The secondary results of a function (if any) are ignored, unless the calling site use the multicall syntax to retrieve multiple results from the call. Every function return a (primary) result value, which is the value of the last expression of the body of the function, unless a return expression is evaluated. A function can also have secondary results given by an explicit return expression (which returns both the primary value and the secondary results). For instance after a
  (defun foo (x :long n) (return (tuple x (constant_box (+i 3 n)) (*i 2 n))))
which defines foo as a function return a primary result value (some tuple) and a secondary long stuff result, the expression (multicall (y :long k) (foo 'a 5) (debug "y=" y "k=" k)) would debug-print y= same as the result of (tuple 'a '8) and k= the long stuff 10.

When a non-functional value (like a boxed number or an object) gets applied (i.e. called), nothing happens, and the call gives the null value.

Functions are first-class values and can be passed as arguments, put inside aggregate values (like objects or lists), or returned as results.

The following example is a defining a high-order function foobar which, given some (hopefully functional) value f and some other value v returns an anonymous function φ which, when later called with some value a, returns primarily the result of applying f to a tuple containing the v and the a, and secondarily the original v:

(defun foobar (f v) 
      (lambda (a) (return (f (tuple v a)) v)))
Each call to foobar above will return a different (and unique) function φ -actually a closure, so for instance if we defined (defun quad (v) (list v v v v)) -so that (quad 'a) gives the list containing four occurrences of the symbol a then ((foobar quad 'b) 'c) -that is the application of the function returned by (foobar quad 'b) to the symbol value c- would return two values, primarily the list containing four identical occurrences (in the same single value) of the 2-tuple c b, i.e. the same value as the evaluation of (let ( (tcb (tuple c b)) ) (list tcb tcb tcb tcb)), and the second result of our call ((foobar quad 'b) 'c) would be the symbol b. We could capture both results and make a reversed list of them by coding (multicall (r1 r2) ((foobar quad 'b) 'c) (list r2 r1)) which shows that multicall is followed by a formal list of results -which are locally bound by that multicall, then the called expression, then the body of the multicall. The example above shows that each returned anonymous function φ has closed the value v at the moment foobar was called. So different calls to foobar with different arguments would give different anonymous functions.

Only values can be closed in closures, e.g. those obtained as lambda functions. In particular
  (let ( (:long one 1) ) (lambda (v) (list v (make_integerbox discr_integer one)))) will be rejected, since one would be a closed stuff.

Functions are very powerful in MELT. You could code an extension in two passes, the first one would build an hash-table associating some gimple-s of the compiled program to some closures, and the second pass would choose some gimple-s and invoke appropriately the function associted to them in the first pass. This functional style enables very powerful programs.

Lexical conventions in MELT

Lexical tokenization

There are some other [obscure and deprecated] lexical conventions (see the meltgc_readval and other meltgc_read* functions in melt-runtime.c)


Macro-strings (a mix of symbols and verbatim strings) are useful to express generated C or C++ templating code pieces, used in several constructs (describing how to emit C or C++ code from MELT source).

Inside macro-strings, almost all characters (notably the backslash \, the braces { & }, the semi-colon ;, the new-line control character, etc... who are very useful in C programs) stand for themselves. But some escapes are possible.

Macro-strings starting with #{ are parsed as an s-expression, so
  #{ /* $HELLO_CHK chunk */ printf("Hello World\n");}#
is exactly parsed as
  (" /* " hello_chk " chunk */printf(\"Hello World\\n\");")
which is a 3-component s-expression starting with the 4-character string " /* ", then the hello_chk symbol, then a string containing back-slashes, double-quotes, ended by a semi-colon.

Macro-strings starting with the 3-character (bang bang left-brace) sequence ##{ which also end with the two-character sequence }# are parsed as a sequence of s-expressions.
(We could have written our entire code chunk as
(##{$code_chunk /* $HELLO_CHK chunk */ printf("Hello World\n");}#)
which is very poor taste)

All macro-strings end with the 2-character (right-brace bang) }# which is not part of the macro-string.

Mixing MELT and C/C++ code

A practically important feature of MELT is the ability to deeply mix MELT and C/C++ code. The C/C++ code is represented with macro-strings. The MELT code is given thru s-expressions.
(since MELT 0.9.9, macro-strings and s-expressions can be arbitrarily nested, so macro-strings can contain s-expressions containing themselves macro-strings etc..., and nearly arbitrary routines can be coded in MELT as hooks)

Suppose that we want to walk through a directory tree, and apply a function for every file that we find inside (giving to that function the filename and the file size). So we want to interface the ftw(3) library function call. This ftw C function wants a callback function and requires some header. We need first to include that header and declare that callback function using the cheader construction (to give some C code to be emitted in the declaration part of the C/C++ code emitted by MELT):

(cheader #{
  #include <ftw.h>
  static int 
  my_ftw_callback(const char *fpath, const struct stat *sb, int typeflag);
We need some MELT module variables (notably because the ftw API don't give any way to pass some client data to the callback): With defvar we define two module variables: varfun will hold the user given MELT function to apply on each file, and varhook will keep the hook data.

(defvar varfun)
(defvar varhook)
We now can define a hook using defhook, that is a C++ routine coded in MELT. That hook gets the file path and the file size as input arguments, it has no output arguments, and return a long flag (zero to continue the file tree traversal).
  (defhook myftwcb ;; name of the hook
        (:cstring filename :long filesize)  ;;input formals
        ()  ;;no output formals
        :long ;;ctype of result
        :var varhook   ;; put the hook data in that module variable
Our hook needs to call varfun with the boxed file name string (because the first argument given to MELT functions should be a value) and its size.
     (let ( 
         (boxedfilename (make_stringconst discr_string filename))
         (rescall (varfun boxedfilename filesize))
      (if rescall 
       (return 1) 
       (return 0))))    ;; end of hook myftwcb 
We now need to implement our my_ftw_callback function, passed as a function pointer to ftw. It just tests that the visited path is a file (not a directory) and then calls our hook. As a C++ function, our hook is called melthookproc_MYFTWCB (that name is derived from the MELT symbol myftwcb). Our my_ftw_callback glue function is plain C++ code, encapsulated in a cimplement MELT directive:
(cimplement #{
static int 
my_ftw_callback(const char *fpath, const struct stat *sb, int typeflag) {
  if (typeflag == FTW_F) { // plain file 
    long filsiz = (long) sb->st_size; // the file size
    long res = melthookproc_MYFTWCB (fpath, filsize);
    if (res) 
      return 0; // continue the file tree walk
      return 1; // abort the file tree walk
  else // not a file, skip it by returning 0
    return 0;
At last, we implement (in MELT mostly) the user function walk-file-tree which is given a closure and a string value representing some directory to scan. That function will save, set, and restore the varfun module variable (to deal with improbable recursive calls to our walk-file-tree thru its clos closure argument) containing the closure, and contains a code chunk to call the ftw C library function:
(defun walk-file-tree (clos dirpath)
  (if (and (is_closure clos) (is_string dirpath))
   (let ( (oldvarfun varfun) ;; backup & save varfun
          (:long err 0) ;; error code returned by ftw
         (setq varfun clos)
         (code_chunk callftw_chk
           #{ /* in walk-file-tree $CALLFTW_CHK */
      // copy the directory path string locally, since ... 
      // ... `dirpath' could be moved by the MELT garbage collector called inside the closure
           char pathbuf[256];
           memset (pathbuf, 0, sizeof(pathbuf));
           strncpy (pathbuf, melt_string_str($DIRPATH), sizeof(pathbuf)-1);
           // call ftw(3) with at most 40 file descriptors.
           $ERR = (long) ftw(pathbuf, my_ftw_callback, 40);
        (setq varfun oldvarfun) ;; restore varfun
        (return (if err () :true)))
   ;; else bad arguments to walk-file-tree
  (return ())
  )) ;; end of walk-file-tree

The example above demonstrates that MELT has now (since MELT 0.9.9) the ability to interface to arbitrary C or C++ libraries, including those requiring some function pointers of an arbitrary signature (thanks to hooks). Please publish, if possible, any such small glue code to your favorite C++ library.

Main syntax of MELT

We use some EBNF-like syntax: lower-case name-like-this is a non-terminal, lower-cases names like if (and others) are terminals, parenthesis like ( and ) are meta-linguistic, brackets like [ and ] are around optional items, the postfix star * denotes optional repetition of 0, 1, or more, and the postfix plus + denotes mandatory repetition of 1 or more. The vertical bar | is for linguistic conjunction. The assigment := sign is for definition of the left-handed non-terminal. We don't claim to be complete (and advanced MELT users could extend the grammar thru their own macros), so this is an incomplete grammar.

Syntactic sugar

Some syntactic sugar is possible for brevity, but could always be avoided. The ≡ sign means here is read the same as:

Some of the special characters above are possible in symbols, after letters. The above syntactic sugar is implemented in the MELT reader.

Formal parameters

Formal parameters list or formals are given in parenthesis and contain formal name symbols (e.g. x or perhaps p-1) and c-type keyword symbol annotations like :long or :tree or :gimple or :value which apply to the following formals. The last :rest annotation is for variadic functions.

formal parameters
formals := ( ( ctype? name+ ) * :rest? )
ctype := :long for long stuff
  | :cstring for raw constant c-string stuff
  | :tree for GCC tree stuff
  | :gimple for GCC gimple stuff
  | :gimple_seq for GCC gimple_seq (sequence of gimple-s) stuff
  | :basic_block for GCC basic_block stuff
  | :edge for GCC edge-s [between basic blocks] stuff
  | :loop for GCC loop-s stuff
  | :value for MELT first-class values
  | :void cannot be used in formals;
annotate lack of data like void in C
etc etc....

Conventionally, formal names are short and only made of letters, perhaps followed by digit. We avoid underscore _ and minus sign - in formals.

There are some restrictions on formals: in particular, the formals of a function should start with a value formal (if any). And variadic formals (ending with :rest) are only permitted for functions (not for primitives). The implicit initial ctype annotation is :value.

Main expression operators

The expression operators have often a greedy evaluation of their operands. But some expressions are lazily evaluated (for their arguments), like if etc... The MELT translator decides if an expression is a function application, a primitive invocation, a message sending, a hook call, etc ... according to the binding related to the operator name.
Expressions with a non-name operator (e.g. a complex sub-expression, like a conditional or an application, etc...) in operator position are always function applications..

expression operators
expr :=
 | ( exprop   expr * ) function application
(operator exprop should be evaluated to a closure;
first argument, if any, should be a value)
 | ( nameprimitive   expr * ) primitive invocation
 | ( namemacro   expr * ) macro invocation
 | ( nameselector   exprreciever expr * ) message sending
 | (quote literal-or-name ) quotation, often with ' syntactic sugar
 | (backquote  expr  ) quasi-quotation building an s-expr, often with ` syntactic sugar
 | (comma  expr ) insertion inside quasi-quotation, often with , syntactic sugar
 | (debug  expr * ) debug printing
 | (box  expr  ) mutable value boxing
 | (constant_box  expr  ) constant value boxing
 | (unbox  c-type expr  ) safe value unboxing,
producing some stuff of appropriate c-type
 | (exclaim  expr  ) dereferencing, often with ! syntactic sugar
 | (tuple  expr * ) tuple constructor
 | (list  expr * ) list constructor
 | (lambda  formals exprbody+ ) anonymous functional value
 | (instance  nameclass ( :namefield   expr ) *   ) dynamic instance creation.
The field names are keyword symbols, so start with a colon :.
 | (get_field  :namefield expr). safely retrieve a field from an object value.
Field keyword names start with a colon :
nil is given if expr is not a value of the appropriate class defining the field.
 | (put_fields  exprobj ( :namefield   expr ) *   ) safe object mutation.
The field names are keyword symbols, so start with a colon :.
Nothing happens if exprobj is not a value of the appropriate class defining all the fields.
 | (code_chunk  namestate macro-string ) Embed some C/C++ code, for side effects.
 | (expr_chunk  namestate c-type macro-string ) Embed some C/C++ expression.
 | (parent_module_environment)  Gives the parent environment extended by the current module.
 | (current_module_environment_reference)  Gives a reference to the current module environment.

Main control operators

The control operators are mostly familiar to Scheme or Common Lisp developers:

control operators
expr :=
 | (if exprtest   exprthen   exprelse? ) conditional expression
 | (when exprtest   exprbody+ ) syntactic sugar, same as
  (if exprtest (progn exprbody+))
if the test is true, the body sub-expressions are evaluated in sequence,
the last giving the result of the when; otherwise false is given.
 | (cond conditional-clause*  else-clause? ) multiple conditional expression
 | (and expr+ ) sequential lazy and-then conjonction.
evaluated left-to-right till a false result is given.
The last evaluated conjunct is the result of the whole and.
 | (or expr+ ) sequential lazy or-else disjonction.
evaluated left-to-right till a true result is given.
The first evaluated true disjunct is the result of the whole or.
 | (progn expr+ ) sequential evaluation
last expression gives result, previous for side effects only!
 | (return expr* ) return from function.
first expression (if present) should give a value, the primary result.
Remaining expressions give secondary results. See also multicall.
 | (forever nameloop  expr * ) infinite loop with internal exit
 | (exit nameloop  expr * ) exit enclosing loop;
last expression gives result of enclosing forever loop.
 | (match exprmatched  matching-clause+ ) pattern matching;
the matched matching-clause gives the result.
 | (nameiterator   ( exprinput* ) formalslocal exprbody* ) iteration.
conditional-clause := (exprcond exprbody+ ) if the condition is true, the body sub-expressions are evaluated,
the last giving the result of the enclosing cond.
else-clause := (:else exprbody+ ) if all previous conditions are false, the body sub-expressions are evaluated,
the last giving the result of the enclosing cond.
matching-clause := ( pattern exprbody+ ) If the matched thing is matching the pattern, the body sub-expressions are evaluated
with pattern-variables locally bound
the last body sub-expression giving the result of the enclosing match.

Notice that in some conditional expressions, the then and else part should be of same c-type; it could be useful to force one of them to be void with (void); likewise for matching clauses.

Main binding operators

Binding operators introduce new lexically scoped local bindings, and the locally bound variables are not visible outside of the whole binding expression:

Notice that let and letrec are always followed by an opening left parenthesis which starts the sequence of bindings. The result of the entire let or letrec expression is given by the last sub-expression of its body, evaluated in an environment augmented by the local bindings defined in the let or letrec.

binding operators
expr :=
 | (let  ( binding * ) expr+  ) local bindings; the variables are bound in sequence.
the body sub-expressions are evaluated with these bindings.
The last body sub-expression gives the result of the whole let expression.
 | (letrec  ( binding * ) expr+  ) recursive constructive bindings;
each binding should be with a constructive expression (lambda, tuple, instance etc...).
the body sub-expressions are evaluated with these bindings.
The last body sub-expression gives the result of the whole letrec expression.
 | (multicall formals   exprapply-or-send   exprbody+ ) call with multiple results.
The first formal capture the primary result value;
the following formals capture the secondary results.
The first expression should be a function application or a message sending.
The last body sub-expression gives the result of the entire multicall expression.
 | expriteration [see iteration as a control operator]
 | (variadic variadic-clause+ else-clause? ) within variadic functions, capture some variadic formals
binding :=   ( ( ctype | :auto )?   name   expr ) Locally bind the given name to expr.
If :auto or no c-type is given, it is guessed from the expr.
variadic-clause :=   ( formals expr+ ) Inside variadic when the actual variadic parameters match the given formals, evaluate the sequence of expr


Pattern matching (thru (match .... ) expressions) is one of the main strengths of the MELT programming language. It practically enables very powerful, expressive and concise coding. For instance, the following code (extracted from a MELT pass checking the coding style of the MELT runtime) is matching a tcurfield variable (some :tree stuff) to find if it is a field declaration of a field named mcfr_varptr which is an array whose size should go into tsize pattern variable.

   (match tcurfield
          ( ?(tree_field_decl
                ?(cstring_same "mcfr_varptr"))
              ?(tree_array_type ?telemtype 
                                ?(tree_integer_type_bounded ?tindextype
                                                            ?(tree_integer_cst 0)
                                                            ?(tree_integer_cst ?lmax) 
             (debug "meltframe_exec telemtype=" telemtype
                    " tindextype=" tindextype 
                    " tsize=" tsize
                    " lmax=" lmax)
             (setq tmeltframvarptr tcurfield)
             (setq nbvarptr lmax)

Patterns appear only within matching expressions (i.e. match operations) as the first syntactic element of matching clauses. Patterns use the question syntax, often thru its syntactic sugar ?π for (question π). The pattern of a given matching clause may introduce new pattern variables which are local to the matching clause and initially cleared (so set to the null value if it is a value pattern variable, set to 0 if it is a long stuff pattern variable, set to the null tree if it is a tree stuff pattern variable, etc...). Pattern variables may be bound by matching, and they can be used in the body expressions of their matching clause.
A pattern can be

Notice that pattern syntax is mimicking expression syntax on purpose. Quite often, you can use a pattern with a code quite similar to the MELT expression constructing the matched data.

pattern matching
pattern :=
  expr some "constant" expression,
often a literal or a local variable bound in an enclosing let
 | ?_ the catch-all wildcard pattern always match
 | ?namevar pattern variables
If not pattern-bound, bind the variable to the matched data;
if previously pattern-bound, test for identity == to the pattern-variable's bound data
Side effect: pattern-bind that namevar to the matched data.
 | ?(namematcher exprin* patternout* ) The namematcher of the matcher defines the number and roles of [input] sub-expressions exprin and [output] sub-patterns patternout
 | ?(tuple pattern* ) Match a tuple value of given sub-pattern-s
 | ?(list pattern* ) Match a list value of given sub-pattern-s
 | ?(instance nameclass
  ( :namefield pattern)* )
Match an value of given class (or some subclass) and fields
 | ?(and pattern+ ) conjunctive pattern, all sub-patterns should match;
sub-patterns are lazily matched in order till match failure
 | ?(or pattern+ ) disjunction pattern, some sub-pattern should match;
sub-patterns are lazily matched in order till match success

to be completed