Tutorial on the MELT domain-specific language

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.

• Common Lisp (with Scheme, see below) inspired MELT. Lexical conventions are quite similar. Named functions are defined like in Common Lisp with defun. The cond, if, progn, and, or, let, lambda, syntax looks familiar. In contrast to Common Lisp, MELT has only one name space, and no packages. return is used to return from a function. Unlike in Lisp or Scheme, MELT lists are not exactly pairs: a list knows its first and its last pair. Unlike in Scheme or Common Lisp, (quote 2) [same as '2 as in all Lisp dialects] is not the same as 2 : the expression (quote 2) evaluates to a boxed value containing 2, but the literal 2 evaluates to the raw unboxed long stuff 2. Most primitives operations are spelled different in MELT than in Lisp or Scheme; MELT does not know car, cdr, + but provides equivalent functionality.
• Scheme inspired MELT a lot, and many constructs are common to both MELT and Scheme. However, MELT does not provide the tail recursion required by Scheme's definition, there are no tail calls in MELT; every recursive call eats a stack frame. Hence, MELT provide some iterative constructs (e.g. forever and exit, and iterators). Scheme programmers should notice that let in MELT is like let* in Scheme (introducing a sequence of bindings), and that let bindings can define a stuff local variable. Some syntactic constructs are spelled differently.
• The Python scripting language is syntactically very different from MELT, but has a quite similar notion of value.
• The Ruby scripting language has inspired (like Smalltalk) the object model of MELT.
• The Lua language's tables (but not its meta-tables) are vaguely similar to MELT hash-tables
• The Javascript language is prototyped based, unlike MELT.
• The C programming language (and also C++) is useful to know, because occasionally you may want to mix C or C++ code chunks inside your MELT code. Notice that C, C++, Javascript, D language and Go language all separate instructions from expressions, but MELT knows (like Scheme or Ocaml, ....) only expressions.
• The Ocaml language (and also Haskell) demonstrates the power of pattern matching and functional programming, but both are statically typed.
  (there is not type inference in MELT)

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.

• Evaluation of a literal integer e.g. 1 gets a warning (since that integer is a stuff, not a value), and give the auto-boxed value containing that integer:

        cc1: warning: MELT WARNING MSG [#0]::: 
        runtime expressions ending with a non-value expression, auto-boxing it.
        - CTYPE_LONG [enabled by default]
  ;;; result of eval mode of 1 expression[s] is ...
  |DISCR_CONSTANT_INTEGER#1
  

• Addition of long stuff is given thru the +i binary primitive operation: (+i 1 2) → |DISCR_CONSTANT_INTEGER#3 with auto-boxing warning
• long stuff test for less-than is <i, and if gives a conditional expression (like ?: in C, or if in Scheme or Lisp or Ocaml), so (if (<i 3 0) -1 2) → |DISCR_CONSTANT_INTEGER#2 (with auto-boxing) because the condition (<i 3 0) is false.
• To enter boxed integer values, use the quote operator, like (quote 42) → |DISCR_CONSTANT_INTEGER#42 without auto-boxing;
• To enter boxed string values, use likewise (quote "some string") → "some string" (which is how string values are displayed).
• The null value is represented as ()

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.

`CLASS_SYMBOL|CLASS_CLASS/5e17eaa#20011{ DISC_METHODICT= |DISCR_METHOD_MAP{/3
      **`DBG_OUTPUT|CLASS_SELECTOR/f9d7509{} == .?.; 
      **`DBG_OUTPUTAGAIN|CLASS_SELECTOR/23059a7{} == .?.; 
      **`NORMAL_EXP|CLASS_SELECTOR/2ffb4614{} == .?.; } 
   DISC_SUPER=^^`CLASS_NAMED|CLASS_CLASS/3016a208  CLASS_ANCESTORS= |DISCR_CLASS_SEQUENCE*3[..] 
   CLASS_FIELDS= |DISCR_FIELD_SEQUENCE*3[..] }

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");}#)

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; 
                     $HELLOCOUNT_CHK#_counter++;
                   $HELLOCOUNT_CHK#_lab:
                     printf ("Hello World, counted %d\n", 
                             $HELLOCOUNT_CHK#_counter);
                     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.

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:

• the nil value, noted () in MELT; nil is represented by the NULL pointer, but its discrimant is conventionally discr_null_receiver; nil is the only false value; all other values are considered true (when used as tested conditions).
• boxed values with a discriminant and some stuff content, e.g.
  • boxed longs, with a raw long integer content; when their discriminant is discr_constant_integer the content cannot change; for other discriminants, such as discr_integer, the content can be changed.
  • boxed gimple-s, with a raw gimple content (a pointer to some gimple instruction), usually of discriminant discr_gimple
  • boxed tree-s, with a raw tree content (a pointer to some tree node representing a constant, a variable, a type inside GCC, some other Generic), usually of discriminant discr_tree
  • etc...; any GCC stuff (except raw c-strings) can be boxed as a value
  The discriminant of a boxed value defines the static type of its content.
• string values (often with discr_string discriminant) know their constant length, and the constant string -e.g. a zero-terminated sequence of bytes
• string buffers (of discr_strbuf) contain a growing mutable buffer of characters, and can be used to incrementally fill a buffer of characters (e.g. to later output it, or make a string value from it)
• pairs, with a discriminant (often discr_pair), a head value, and a tail pair (or nil);
• lists, with a discriminant (often discr_list), the first and last pair values
  (hence prepending or popping a first value, or appending a last value, are quick operations);
• tuples, with a discriminant (often discr_multiple), the (constant) number of components, and the sequence of component values;
• closures (or functional values), with a discriminant (often discr_closure), the routine, the sequence of closed values; they are typically created with lambda (for anonymous functions) or defun (for defined functions).
• MELT objects, with their class as the discriminant, a constant random hash-code, a short magic number, the constant number of fields, and the field values;
  (the magic number is initially 0 and can be set only once; in discriminants it is used to dynamically type the discriminated value)
• homogeneous hash-tables are associating keys to non-null values. They are homogeneous: all the keys have the same type. So
  • string hash-tables (of discr_map_strings) associate non-empty strings to values, so are some kind of dictionnary.
  • object hash-tables (of discr_map_objects) associate MELT objects to values.
  • tree hash-tables map raw non-null GCC tree-s to non-null values
  • gimple hash-tables map raw non-null GCC gimple-s to non-null values
  • etc....; most GCC stuff have corresponding hash-tables.
  Each hash-table carries an auxiliary value (initially null) which can be retrieved and set to an arbitrary MELT value.
  Hash-tables associating GCC stuff (like gimple-s, edge-s, basic_block-s, ....) are practically useful because GCC representations cannot be extended and don't carry client data. So your additional GCC passes have to associate some values to some gimple-s or tree-s outside.
• etc...   (MELT has other useful kinds of values, notably boxed FILE* stdio streams)

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:

• with define you can name any value given its expression, e.g. (define three (+iv '1 '2)).
• Use definstance to define a named instance, of some given class, filling its fields (those not given are cleared to the null value), e.g. (define refj class_reference :reference_value '"John Doe"); the class_reference has only one field, reference_value, and is useful to keep a mutable reference to some value.
• Use defun to define a named function (with the name, then the formal parameter lists, ending with the body of the function). So the familiar factorial recursive function working on boxed integers and producing a boxed integer value is coded as:

        (defun fact (nv) 
          (if (<=ivi nv 1)
             nv
             (*iv nv (fact (-ivi nv 1)))))
  

• defprimitive can be used to define new primitive operators by giving, thru a macro-string (without state symbol), their expansion in C or C++. For instance you could define your squarei primitive (returning the long stuff which is the square of its sole formal long stuff) with:

  (defprimitive squarei (:long i) :long #{/*squarei*/ ($I) * ($I)}#)
  

  (the first :long is qualifying the i formal argument. The second :long is typing the result of the defined primitive)
• defmacro is used to define a macro (often using quasi-quotation, i.e. backquote)
• defvar (new in MELT 0.9.9) can be used to define a module variable (which is a value kept in some static C/C++ variable managed by MELT and GCC garbage collectors). Module variables can be assigned with setq but cannot be exported.

  When a variable is an argument to a function or primitive application, its value may be fetched before evaluation of other arguments; so don't depend on the order of argument evaluation.

• defhook (new in MELT 0.9.9) can be used to define hooks, which are translated to [nearly] arbitrary C/C++ routines (callable by C or C++ code e.g. in some code_chunk or otherwise). Notice that if your hook is used outside of MELT code, you probably should trigger an explicit minor garbage collection (by calling minor_garbcoll just before returning from the hook).
• other definitions are possible, notably with defcmatcher to define C-matchers (constructs for pattern matchings), defunmatcher to define matchers in MELT, defciterator to define iterative constructs in C or C++ with macro-strings for their expansions, etc... $

dynamically building values

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

• build a constant or mutable boxed number value from some given long stuff (given by a variable or an expression) ι :
  (make_integerbox discr_constant integer ι) or simply (constant_box ι) (to box an integer stuff into a constant immutable value)
    or (make_integerbox discr_integer ι) or simply (box ι) - (to box an integer stuff into a mutable value);
  N.B. box and constant_box are new in MELT 0.9.8
• build a tuple out of its element values (given by variables or expressions) v₁ and v₂ and v₃ :
  (tuple v1 v2 v3)
  to make a null-filled tuple of variable length (some long stuff expression or variable) ln use (make_multiple discr_multiple ln) then use multiple_put_nth to change components inside.
• build a list from values (given by variables or expressions) a, b, c use
  (list a b c)
• dynamically build a functional value or closure with lambda, so (lambda (v) (f (get_field :named_name v))) is the anonymous function which applies some f to the field :named_name (defined in the standard class_named) of its formal argument v; notice that f is a closed variable (or already bound variable), provided by the environment, e.g. because it is bound by some enclosing let expression. Functional values are tremendously useful in MELT.
• build an object value with the instance construct, followed by a class name, then the fields initialization; each initialized field is given by a keyword symbol starting with a colon : e.g.
  (instance class_gcc_gimple_pass :named_name '"foo_pass" :gccpass_exec foo_exec)) is building a new instance of class_gcc_gimple_pass with the named_name field (inherited from the ancestor class class_named) initialized to the "foo_pass" boxed string, and the gccpass_exec field (defined in the parent class class_gcc_pass) initialized to the function foo_exec.
• A big lot of primitives are building new values, for example:
  • make_integerbox to build a boxed integer, like (make_integerbox discr_integer (+i 3 1)) to build a boxed 4 integer;
  • make_tree to build a boxed GCC tree, like (make_tree discr_tree t)
  • make_mapobject to build an hash-map keyed by MELT object values, like (make_mapobject discr_map_objects 120) where 120 is an initial estimate of the hash-table size (which will grow as needed)
  • make_mapgimple to build an hash-map keyed by GCC Gimple stuff, like (make_mapgimple discr_map_gimples 400)
  • make_bucketlong to build a sorted bucket associating arbitrary long stuff to non-nil values, like (make_bucketlong discr_bucket_longs 100); contrarily to hash-maps, buckets don't automatically grow, but the bucketlong_put primitive may return a new bucket bigger than the original one.
  • etc...; there are many other value-building primitives!
  Notice that most building primitives take a discriminant as their first argument (the discriminant of the newly built value). If that discriminant is inappropriate for the primitive, e.g. (make_maptree discr_integer 10) this primitive gives nil (here make_maptree wants discr_map_trees, not discr_integer!).

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:

• :long to annotate raw long integers
  (the C translation from MELT uses the long C type.)
• :tree to annotate raw GCC tree-s (for Generic Trees), e.g. variables and declarations and operands of the GCC compiled code;
• :gimple to annotate raw GCC gimple-s (internal representation of simple elementary instructions, like assignment, arithmetic [e.g. a = b - c;], calls, conditional jumps, etc...);
• :basic_block to annotate raw GCC basic blocks;
• many other stuff such as :edge, :loop, etc....;
• (sometimes useful) :value to annotate MELT values (which is the default c-type)
• :cstring to annotate constant raw strings in read-only memory. The only safe stuff of that :cstring c-type are constant literal strings like "hello"; you should not (and cannot) compute a stuff of that c-type (e.g. extracting a :cstring from a string value will crash MELT).
• occasionally :void annote something which does not carry any data. The expression of that c-type is (void)
• The :auto annotation (new in MELT 0.9.8!) within let bindings means that the let-bound variable takes its type from the expression defining it.

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

• formal parameters list; the c-type affects all following formals; so the formal parameters (x :long i j :value v) represents 4 formals, x being a value formal, i & j being raw long stuff formals, and v being a value formal
• local binding; so the binding (:long i 1) binds the raw long stuff 1 to the symbol name i; but the binding (one '1) which is same as (one (quote 1)) or even (:value one (quote 1)) binds the symbol name one to the boxed value 1 of dicriminant discr_constant_integer
• typing the sole result of a primitive

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 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)))

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 tokenization

• indentation does not matter in MELT (like in Scheme or Lisp or C), but is very useful for readability. Use a good Lisp friendly mode in your favorite editor, e.g. emacs or vim.
• comments start with a semi-colon, and goes up to the end-of-line; so the first line in MELT source files is often ;; -*- Lisp -*- to make emacs happy (multi-line comments starting with #| and ending with |# are possible but not recommended);
• symbols (called identifiers in some other langages) may contain some punctuation characters (and letters, and non-initial digits), notably any of * / + - < > = _  and some others. In particular, a+b is a single symbol of 3 characters, and is not the same as a + b (a sequence of 3 symbols which does not represent the sum of a and b!).
  Parsed symbols are interned by the reader, as (shared) instances of class_symbol.
• case is not significant in symbols so If is the same as if or iF; conventionally lower-cases are prefered
• So called keyword symbols are symbols starting with a colon sign : like :else or :foo, and are parsed as (shared) instances of class_keyword; keyword symbols are "self-evaluating" and cannot be explicitly bound (e.g. by some let). Notice that keyword symbols in MELT are not like keyword identifiers (e.g. for) in C.
  keyword symbols are parsed and interned by the reader, as (shared) instances of class_keyword, a sub-class of class_symbol.
• in principle, there are no reserved symbols in MELT (like the keyword identifiers such as while in C), but in practice and, assert_msg, cond, debug, defciterator, defclass, defcmatcher, define, definstance, defprimitive, defun, defunmatcher, exclaim, exit, export_class, export_macro, export_values, forever, if, instance, lambda, let, letrec, match, multicall, or, progn, question, quote, return, setq, when, are so important that you don't want to use them outside of their pre-established MELT meaning, and you should not redefine them.
• symbols containing melt should be avoided, since they are implementation reserved
• integer literals may start with an optional + or - sign, and follow C conventions: 10 or +10 or 0xa or +0xa or 012 is ten, with 0x prefix for hexadecimal, and 0 prefix for octal notation. An integer literal constant should fit in a long.
• character constants starts with bang backslash e.g. with #\ followed by a printable character, e.g. #\a and they are considered as integer literals, so #\a is the same as 97 (because 97 or 0x61 is the ASCII encoding of the a letter). Multi-byte UTF-8 encoding is not yet supported. Some control characters can be conveniently input, e.g. #\nul or #\alarm or #\backspace or #\tab or \#linefeed or \#vtab or \#page or \#return or \#space or \#esc. But character constants are integer literals (so represent stuff of :long c-type).
• string literals start and stop with a double-quote " and have the same escapes (e.g. \\, \", \a, \b, \n, \r, \t, \v, \x0a ...) as in C, so "ab\nd" is a four-character string literal whose third is the newline. They represent stuff of :cstring c-type.
• macro-strings start with #{ and end with }#. See below for more.
• S-expressions or s-exprs start with an opening parenthesis ( and terminate with a balanced closed parenthesis ). They are read as unique instances of class_sexpr which have their :loca_location field set, when possible, to the source location of the s-expr and their :sexp_contents field set to the list of components, i.e. the sub-expressions, of that s-expr. Syntactic sugar (see below) enables some few s-exprs to be read without starting with a left parenthesis.

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

Macro-strings

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.

• a dollar $ followed by letters (or non-initial digits, or underscores _, i.e. all valid characters iside C identifiers) represent the MELT symbol of that same name. So $HELLO_CHK represents the hello_chk symbol in our example. If the symbol is immediately followed by a bang #, that character is skipped.
• a dollar followed by a dot $. is skipped
• a double-dollar $$ represents a single dollar character.
• a dollar followed by a bang $# is read as a single bang # character
• Since MELT 0.9.9 a macro-string can contain nested sub-expressions. They start with a dollar followed by a left parenthesis $(, and end with the matching right parenthesis ). Within code_chunk, sub-expressions should be of :void c-type and are useful only for their side-effects.
• etc... (there are some other conventions starting with a dollar sign $)
• The right-brace bang }# is ending the macro-string an is not part of it.

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.

Syntactic sugar

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

• 'ε ≡ (quote ε) and is used for quotations. So (quote 2) is the same as '2 and refers to the quoted integer value 2.
• ?π ≡ (question π) and is used for patterns with match. In particular ?_ represents the catch-all wildcard pattern. (in Ocaml the wildcard pattern is written _ in matches.)
• !ρ ≡ (exclaim ρ) is used for dereference, and is understood like (get_field :reference_value ρ).
  (the ! notation is inspired by Ocaml and it should be followed by a letter, or a space, or a parenthesis)
• `ε ≡ (backquote ε) to build s-expressions by quasi-quotation.
• ,ε ≡ (comma ε) is to insert something in a backquote-ed s-expression.
• @ε ≡ (at ε) is reserved for future use.

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.

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..

• Function application starts with the function, then the evaluated arguments. The function may itself be given by a complex expression. The first argument (if any) should be a value, and the primary result of the application is a value. Notice that only functions (but not e.g. hooks or primitives or message selectors) can be applied when the operator is a complex expression (e.g. a conditional expression, or the result of some computation). If the operator of an application does not evaluate to a closure, nil is returned by the application.
• If the named operator of an expression is statically bound to a primitive (previously defined with defprimitive), it is a primitive invocation with a fixed signature (known number and c-type of arguments and result). Often, expression operators are just MELT primitives and there are a big lot of them. Beware that ((if somecond +i -i) 2 3) won't work as you want : since the operator is a complex sub-expression (if somecond +i -i), it is assumed to be a function application, but you want that to be a primitive invocation.
• If the named operator of an expression is statically bound to a hook (previously defined with defhook), it is a hook call.
• If the named operator of an expression is statically bound to a selector (previously defined with defselector), it is a message sending. The first argument (evaluated to a value) is required and is the reciever of the message.
• If the named operator of an expression is statically bound to a macro (previously defined with defmacro or export-macro etc...), it is a macro invocation. Most MELT syntax is defined by macros : actually, if, lambda, let, defun, quote etc... -and most operators described here- are all predefined macros.
• The quote operator does not evaluate its sole argument, and gives a constant value.
  • For an integer literal, its gives a boxed value of discr_constant_integer, so (quote 2), often given as '2 gives the same as (make_integerbox discr_constant_integer 2), except that the boxing happens only once (the boxed integer value is constructed at initialization time).
  • The quotation of a string literal gives a boxed string.
  • The quotation of a symbol gives the instance of class_symbol which is the interned (shared, unique) instance of the symbol.
  • The quotation of an s-expr builds dynamically that s-expr so gives an instance of class_sexpr.
• The backquote operator is used for quasi-quotations to dynamically build s-expressions, often with the comma operator. For example (let ( (one 1) (ab (list 'a 'b)) ) (backquote (+ (comma one) (comma ab)))) which can be written (let ( (one 1) (ab (list 'a 'b)) ) `(+ ,one ,ab)) expands to an s-expr like (+ 1 a b) built at runtime (since ab is a sequence, it is expanded to its constituents).
• The debug operator is useful for debugging. It accepts any number of arguments of any kind (stuff or things), e.g. (debug "here x=" x "and g=" (gimple_content gv)). When you run MELT with the -fplugin-arg-melt-debug or -fplugin-arg-melt-debugging=all program option, some debugging output happens, mentionning the source location of that debug expression. But MELT modules of optimized flavor do not show any debugging output.
• The box operator (new in MELT 0.9.8!) is taking a stuff operator and gives a mutable value boxing it. So (box (+i 2 3)) gives the same as (make_integerbox discr_integer 5).
• The constant_box operator (new in MELT 0.9.8!) is taking a stuff operator and gives a constant value boxing it. So (constant_box (+i 2 3)) gives the same as (make_integerbox discr_constant_integer 5).
• The unbox operator (new in MELT 0.9.8!) is taking a c-type [of the result of the unboxing] and some value. It safely unboxes that value, returning its content or else a cleared stuff. So (unbox :tree v) is nearly the same as (tree_content v) and delivers the raw tree content of v if it is a boxed tree, or else the null tree.
• The lambda operator is for making anonymous functional values or closures (it is a constructive expression).
• The tuple operator builds tuple values of discr_multiple discriminant (it is a constructive expression). For example, (tuple '2 'x) evaluates to a 2-sized tuple whose first component is a boxed constant integer 2.
• The list operator builds list values and implicitly the contained pair values (it is a constructive expression). For example (list (tuple 'a) '2) is a list of two pairs, the first of which having a 1-tuple as its head. Notice that -contrarily to Scheme or Common Lisp- in MELT the expression (list) does not evaluate to nil (but to an empty list without pairs). Remember that lists know their first and last pairs.
• The exclaim operator (e.g. (exclaim x) which is the same as !x in MELT) is for dereferencing.
• The instance operator dynamically builds an object, of a given class, with appropriate field initializations. Each field has a globally unique name, and is a keyword symbol so starts with a colon, like :reference_value; for example (instance class_reference :reference_value 'a)
• The get_field operator safely retrieves some given field from an object value. If the value is not an instance of the class defining that field, nil is given. For instance (get_field :reference_value r) is the same as !r
• The put_fields operator safely mutates an object value with some given fields. If the value is not an instance of the class defining that fields, no harm is done. For instance (put_fields pass :gccpass_exec somefun :gccpass_data somedata) won't touch pass if it is not an instance of class_gcc_pass (or some sub-class of it) which defines the :gccpass_exec and :gccpass_data fields.
• The code_chunk operator enables the embedding of a chunk of C code (or in the subset of C++ acceptable inside GCC). It is only useful for its side-effects. It is quite useful in practice. Sub-expressions appearing in the macro-string should be of :void c-type and are expanded at place of occurrence.
• The expr_chunk operator (new in MELT 0.9.9) permits embedding some C/C++ expression in MELT. Sub-expressions appearing in the macro-string are always strictly evaluated (like arguments to primitives or to function calls) before the computation of the expression chunk. Hence, an expr_chunk of :void c-type is not the same as the equivalent code_chunk.
• The parent_module_environment operator produces the parent environment, that is the environment which is extended by the current module. Use with care, and avoid modifying the parent environment.
• The current_module_environment_reference operator gives a reference to the current module environment. Use with care, and avoid modifying the referenced current module environment yourself.
• The variadic arithmetic operators (new in MELT 0.9.9) i.e. +, -, *, / are expanded to left-nested invocations of binary primitives +i, -i, *i, /i. Notice that no variadic comparator exist, so use the binary >i, ==i (on long stuff), == (to test identity of values), etc... etc...

Main control operators

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

• The familiar if operator is the conditional ternary operator (like if in Ocaml or Scheme, or the ternary ?: operator of C, etc...), if the condition expr_test is evaluated as true, the second operand, i.e. the expr_then is evaluated and gives the result of the whole if expression. Otherwise, the optional third operand expr_else is evaluated, and if missing, a cleared value or stuff is given.
• The when operator is a syntactic sugar, with test expression and body sub-expressions (it is transformed to a progn as the then exression of an if without else part). When the test is true, the sub-expressions are evaluated in sequence, and the last one gives the result of the when expression.
• The Lisp inspired cond operator is the multi-conditional expression, with conditional clauses. Each conditional clause starts with a test expression followed by sub-expressions which gets evaluated in sequence if their condition was true, but the last clause may start with :else. The result of the entire cond expression is the last expression of the first true conditional clause.
• The and operator is a lazy and-then conditional (similar to && in C). Sub-expressions are evaluated in sequence till a false (nil or 0, ...) result is obtained.
• The or operator is a lazy or-else conditional (similar to || in C). Sub-expressions are evaluated in sequence till a true result is obtained.
• The progn construct is for sequential evaluation of sub-expressions, only the last sub-expression gives the result of the entire progn expression and all but the last sub-expressions are evaluated only for their side-effects. Hence it is similar to the begin operator of Scheme, to the progn construct of Lisp, to the comma operator , of C and to the semi-colon ; operator of Ocaml
• The return construct is returning a primary value (or nil if none is given) with secondary results, if given. So (return) just returns the nil value from the enclosing function, and (return v 1 !r) returns v as the primary value result, and the long stuff 1 with the value inside the reference r as the secondary results. Secondary results can be captured with the multicall binding construct in the caller code.
• The forever construct is for endless loops. It is followed by the name of the loop. These loops can be exited with exit (and also with return) expressions. The result of the forever expression is the last expression in the internal exit sub-expression exiting that loop. Notice that the exited forever loop should be in the same function as the exit expression.
• The exit construct is a local jump outside of a forever loop. The exit is followed by the name of the loop to be exited, then some expressions, the last of which gives the result of the exited loop.
• The iterators (or iterative expressions) start with a c-iterator name, then a sequence of input expressions, then a sequence of local formals, then the body of the iteration; while most c-iterators are actually looping, we consider them as binding expressions, since they have formals. For example the familiar  for(i = 2; i <= 6; i++) debugprintf("i=%d", i);  loop of C would be
  (foreach_long_upto (2 6) (:long i) (debug "i=" i)), where (:long i) is the local formals of the iteration (so i is bound only inside the iteration body). The foreach_long_upto c-iterator is defined with defciterator in the MELT standard library which also defines many other c-iterators, such as foreach_in_multiple to iterate on the components of tuple values, and foreach_argument_of_gimple_call to iterate on the arguments of a Gimple call instruction. A c-iterator is defined by providing macro-strings to be expanded before and after its body. Some c-iterators loop only once, e.g. with_cfun_decl to get the current C function declaration in a pass. As MELT expressions, iterations are of void c-type and don't give any result. They are only used for side-effects (and bindings of the local formals within their body).
• The matching expressions start with match, then a matched expression, then a sequence of matching clauses. Each matching clause starts with a pattern.

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:

• the let operator is followed by a sequence of bindings and has body sub-expressions. It is similar to the let* of Scheme, because the bindings are done sequentially, and a previous binding can be used in the expression of some following binding. Each let-binding starts optionally by a c-type annotation or by :auto [which is the default], then the newly and locally bound symbol, then the expression defining that symbol. If a real c-type annotation is given (e.g. :long or :tree), then the binding expression should be of that c-type. If no c-type annotation is given, or if :auto is given, then the binding expression's type is used to determinate the c-type of the newly bound variable, e.g. in
  (let ( (:auto i 1) (:value v 'xx) (t (tuple v (box i))) ) (debug "t=" t) t)   the c-type of i is :long (given by 1) and the c-type of t is :value (given by tuple). The result of that entire let is a tuple value, and the debug sub-expression is for its side-effects only.
• The letrec operator is for co-recursively defined constructive bindings. Each constructive binding has a locally bound variable and a constructive expression (.e.g. lambda, tuple, instance etc....), so binds a value to the defined name. You can use letrec to build circular data structures e.g.
  (letrec ( (ipse (instance class_reference :reference_value ipse)) ) ipse) which defines a silly reference pointing to itself.
  But letrec is often used to define local recursive functions with lambda. Remember that recursive calls are always truely recursive (no tail-calls in MELT).
• The multicall operator captures the primary and the secondary results of a call (or a message sending). It is inspired by Lisp's call-with-values. It is followed by a formals list (to be bound to the results), then the function application or message sending expression, then the body sub-expressions. The first formal should be a value name, since it gets the primary result. The other formals get the secondary results.
• The iterations with some c-iterator as the operator are also locally binding the local formals.
• The patterns in matching clauses are also locally binding their pattern variables.
• the variadic expressions can appear only in variadic functions (whose formal parameters end with :rest). A variadic-clause gets evaluated if the current variadic arguments fit in the formals of the clause.

Patterns

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
              ?(tree_identifier 
                ?(cstring_same "mcfr_varptr"))
              ?(tree_array_type ?telemtype 
                                ?(tree_integer_type_bounded ?tindextype
                                                            ?(tree_integer_cst 0)
                                                            ?(tree_integer_cst ?lmax) 
                                                            ?tsize)))
             (debug "meltframe_exec telemtype=" telemtype
                    " tindextype=" tindextype 
                    " tsize=" tsize
                    " lmax=" lmax)
             (setq tmeltframvarptr tcurfield)
             (setq nbvarptr lmax)
             )
          (?_ 
           (void)))

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

• Constant expressions, often litterals (or some locally bound MELT variable). So The pattern 2 matches the long stuff 2. Constant patterns are tested using the identity test == in the generated C/C++ code (so never write "some string literal" as a pattern but code ?(cstring_same "some string literal") which gets translated to a test calling strcmp, because two same string literals are not identical in C code).
• The catch-all wildcard pattern ?_ has its matching always successful. (so the underscore _ is not a valid pattern variable name)
• a pattern variable like ?v (with the name v conventionally starting with a letter like ?tr); if the pattern variable v is not pattern-bound in the current matching clause, [pattern-]bind it to the matched data and succeed the matching; if it is pattern-bound to some data (by a previous occurrence of the same pattern variable in the current matching clause), test for identity (with == in the generated C or C++ code) of the matching data to the pattern variable's data.
• a composite pattern possibly involving sub-expressions [with an "input" role] and sub-patterns [with an "output" role], in particular:
  • pattern starting with a matcher name. A matcher defines a basic pattern, either in c-matchers defined with defcmatcher by macro-strings describing the C/C++ code to test the pattern and to fill, for sub-patterns, the extracted data, or in fun-matchers defined with defunmatcher by a MELT function -returning a true value on successful match- whose secondary results are the extracted data. The standard MELT library provides a big lot of useful matchers.
  • patterns starting with ?(tuple ... ) match a tuple value, and whose components match the corresponding sub-pattern.
  • patterns starting with ?(list ... ) match a list value, whose elements match the corresponding sub-pattern.
  • patterns starting with ?(instance name_class ... ) match a MELT object value, instance (directly or thru subclasses) of the given class name_class, whose fields match the corresponding sub-patterns.
• a conjunctive pattern ?(and ...) matches if and only if all the conjunct sub-patterns match; side-effect, notably pattern variable bindings, are transmitted betwen conjunct sub-patterns which are lazily processed in order.
• a disjunctive pattern ?(or ...) matches as soon as one disjunct sub-pattern matches; sub-patterns are lazily processed in order (so further disjunct sub-patterns are not matched when a previous disjunct did match)
• etc...; expert MELT users could define their pattern constructions by defining their own pat-macros