## BER MetaOCaml -- an OCaml dialect for multi-stage programming

BER MetaOCaml -- an OCaml dialect for multi-stage programming
Oleg Kiselyov
2010-2015-

BER MetaOCaml is a conservative extension of OCaml for writing programs that generate programs''. BER MetaOCaml adds to OCaml the type of code values (denoting program code'', or future-stage computations), and two basic constructs to build them: quoting and splicing. The generated code can be printed, stored in a file -- or compiled and linked-back to the running program, thus implementing run-time code optimization. A well-typed BER MetaOCaml program generates only well-scoped and well-typed programs: The generated code shall compile without type errors. The generated code may run in the future but it is type checked now. BER MetaOCaml is a complete re-implementation of the original MetaOCaml by Walid Taha, Cristiano Calcagno and collaborators.

Introduction to staging and MetaOCaml

The standard example of meta-programming -- the running example of A.P.Ershov's 1977 paper that begat partial evaluation -- is the power function, computing x^n. In OCaml:

let square x = x * x let rec power n x = if n = 0 then 1 else if n mod 2 = 0 then square (power (n/2) x) else x * (power (n-1) x) 

[...]

In MetaOCaml, we may also specialize the power function to a particular value n, obtaining the code which will later receive x and compute x^n. We re-write power n x annotating expressions as computed now' (when n is known) or later' (when x is given).

let rec spower n x = if n = 0 then .<1>. else if n mod 2 = 0 then .<square .~(spower (n/2) x)>. else .<.~x * .~(spower (n-1) x)>.;; 
A brief history of (BER) MetaOCaml

As MetaOCaml was being developed, new versions of the mainline OCaml were released with sometimes many fixes and improvements. The MetaOCaml team tracked new OCaml releases and merged the changes into MetaOCaml. (The MetaOCaml version number has as its base OCaml's release version.) The merge was not painless. For example, any new function in the OCaml compiler that dealt with Parsetree (AST) or Typedtree has to be modified to handle MetaOCaml extensions to these data structures. The merge process became more and more painful as the two languages diverged. For instance, native code compilation that first appeared in MetaOCaml 3.07 relied on SCaml, a large set of patches to OCaml by malc at pulsesoft.com to support dynamic linking. OCaml 3.08 brought many changes that were incompatible with SCaml. Therefore, in MetaOCaml 3.08 the native compilation mode was broken. The mode was brought back in the Summer 2005, by re-engineering the SCaml patch and implementing the needed parts of dynamic linking without any modification to the OCaml code. The revived native compilation has survived through the end.

[...]

BER MetaOCaml has been re-structured to minimize the amount of changes to the OCaml type-checker and to separate the kernel' from the user-level'. The kernel is a set of patches and additions to OCaml, responsible for producing and type-checking code values. The processing of built code values -- so-called running' -- is user-level. Currently the user-level metalib supports printing, type-checking, and byte-compiling and linking of code values. Users have added other ways of running the code, for example, compiling it to machine code, C or LLVM -- without any need to hack into (Meta)OCaml or even recompile it.

[...]

By relying on attributes, the feature of OCaml 4.02, BER N102 has become much closer integrated with OCaml. It is instructive to compare the amount of changes BER MetaOCaml makes to the OCaml distribution. The previous version (BER N101) modified 32 OCaml files. The new BER N102 modifies only 7 (that number could be further reduced to only 2; the only file with nontrivial modifications is typing/typecore.ml). It is now a distinct possibility that -- with small hooks that may be provided in the future OCaml versions -- MetaOCaml becomes just a regular library or a plug-in, rather being a fork.

## Comment viewing options

### Could it really happen?

That staging gets integrated in OCaml? I did officially ask in August 2008, but the response was underwhelming then. But now that Oleg has brought things down to so few files changed, it is looking a lot better.

### Hm

That is a good idea, I will ask.

Are you still an active user of MetaOCaml? Have you looked at the codebase itself, and would you feel ready to contribute to its maintenance?

### Active user

I was a very active user for a few years, but paused for the last two. I could easily become a very active user again.

I have delved into the code base, even wrote parts of the pretty-printer (but it then became parts of ocaml itself, so that work is hopefully obsolete already!). Of course Oleg is the person you really ought to ask about this, since he really is the author of BER-metaocaml.

If there are small maintenance tasks that need done, and Oleg doesn't mind, sure, I can do that.

### MetaOCaml integration: not yet

So I asked both the OCaml maintainers and Oleg, and Oleg answered that he thought merging MetaOCaml into OCaml would be premature for now, because there are several aspects of the design that are still evolving.

### I'm wondering if there will

I'm wondering if there will be compilation-to-native support, using ocamlopt` functionality under the hood. (instead of current approach where MetaOCaml programs and generated code always compiled to bytecode)

### If there is enough demand

AFAIK, getting this done is not a heroic task -- it just needs sufficient demand. The hardest part of the old native compiler was dynamic linking, but that seems to have been dealt with in the main compiler in the meantime.

### MetaOCaml to LLVM

MetaOCaml-LLVM, using MetaOCaml to generate LLVM code, has been
publicly described -- actually back in August 2014. MetaOCaml becomes
sort of a very powerful macro-processor for LLVM, with a good type
system. In fact, that was the title of the paper, in Japanese.
https://jssst2014.wordpress.com/program/

We did not try the dynamic linking, although it should be
possible. Our target application was generating fast numeric kernel
libraries, somthing like BLAS and above.

### Interesting. May I ask why

Interesting. May I ask why metaocamlopt was removed? What was the challenge that led to this decision?

### Native MetaOCaml

Since all of the MetaOCaml was completely re-written (except for small
bits in the parser), with new algorithms and implementations, all of
the old code was removed and new is written. The new code for
metaocamlopt was just wasn't written. The main reason is just the
lack of time. The lack of the native MetaOCaml just didn't seem to be
a big enough of a problem, especially as easy workarounds exists: just
save the generated code into a file and compile that file with
ocamlopt. BER MeteOCaml does provide a convenient function to write
code into a file.

### this isn't a workaround

especially as easy workarounds exists: just save the generated code into a file and compile that file with ocamlopt

But this isn't a workaround, because it doesn't solve the issues with dynamic linking and non-serializable CSP values(like sockets and handles).