Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[oleg]

Francois Berenger wrote:
> Could it be (ab)used to translate easily a whole program's OCaml source
> into C code?

In fact at one point MetaOCaml did so -- translated the generated OCaml
code to C or Fortran. This feature -- called offshoring -- was used to
generate FFT kernels. The generated C code was good enough to plug as
it was into the FFTW benchmarking and testing framework. During the
overhaul offshoring has been separated and left for clean-up and
re-writing. Now there is a place for it in the overall architecture.


> I understand that this is very interesting from a research
> perspective, but practically meta-programming is only useful as long
> as performances are the concern, for these problems when some critical
> information is not known until runtime; I can't think of another usage
> for runtime code specialisation anyway.
>
> So the question that immediately arises is then: why is metaocaml
> supporting byte code only? Is a metaocamlopt planned, envisaged,
> doable, in a galaxy not too far away?

Before discussing the plans for the native run, let me clear a
misconception. In two largish MetaOCaml projects I recall offhand,
MetaOCaml was used to generate the optimal code for FFT kernels and
for Gaussian Elimination. Gaussian Elimination is a large family of
the algorithms, parameterized by domain (integer, float, polynomial),
by the choice of pivoting, by the need to compute determinant, rank,
permutation matrix, by the layout of matrices and by a half a dozen
more aspects. Because Gaussian Elimination is often used in inner
loops, the performance matters a great deal. Therefore, all this
parameterization has to be done statically. Jacques Carette and I used
MetaOCaml to generate GE procedures for particular parameter choices.
The generated code was printed out, to be compiled in a
library -- by the native OCaml compiler. Let me emphasize: the code
generator was byte-code OCaml, but the generated code could be stored
and compiled by the native OCaml. We used the byte-code run, but only
for testing. The FFT project was similar: the generator was byte-code,
the byte-code run was used for testing, the generated code was C 
and compiled with the Intel C compiler.

The point is that the byte-code generator produces the code that can
be compiled by any suitable compiler. The mode (byte-code or native)
of the generator and of the generated code are not related. In my
experience, the existing MetaOCaml is already useful in practice --
but more could and should be done.

Regarding native MetaOCaml. As far as generating code is concerned, it
can be done already. (I should try to make optmetaocamlc -- it should
just work). The generated code can be stored on file, compiled any way
we wish -- and linked back using dynlink. What is needed currently is
to make this process automatic and convenient. The refactoring of 
MetaOCaml should help. The functions to run the code are now `user
level'. That is, to change them or to add new ones, one does not have
to re-compile MetaOCaml. Adding a new run function is as simple as
adding a new library function -- just making sure the compiler
can find your *.cmi and *.cmo/*.cmx files.

I too want the end result quicker. Yet basics have to be done
first. At the very least we need to get the codebase that one can work
with and understand, and to be able to add features without breaking
anything.  I think basics is mostly done.

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[Francois Berenger]

On 02/01/2013 03:53 PM, oleg@okmij.org wrote:
> Francois Berenger wrote:
>> Could it be (ab)used to translate easily a whole program's OCaml source
>> into C code?
>
> In fact at one point MetaOCaml did so -- translated the generated OCaml
> code to C or Fortran. This feature -- called offshoring -- was used to
> generate FFT kernels. The generated C code was good enough to plug as
> it was into the FFTW benchmarking and testing framework. During the
> overhaul offshoring has been separated and left for clean-up and
> re-writing. Now there is a place for it in the overall architecture.

Amazing.
At some point, if MetaOcaml can be made available as an OPAM switch,
people will be able to give it a try very easily.

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[Anil Madhavapeddy]

On 1 Feb 2013, at 07:53, Francois Berenger <berenger@riken.jp> wrote:

> On 02/01/2013 03:53 PM, oleg@okmij.org wrote:
>> Francois Berenger wrote:
>>> Could it be (ab)used to translate easily a whole program's OCaml source
>>> into C code?
>> 
>> In fact at one point MetaOCaml did so -- translated the generated OCaml
>> code to C or Fortran. This feature -- called offshoring -- was used to
>> generate FFT kernels. The generated C code was good enough to plug as
>> it was into the FFTW benchmarking and testing framework. During the
>> overhaul offshoring has been separated and left for clean-up and
>> re-writing. Now there is a place for it in the overall architecture.
> 
> Amazing.
> At some point, if MetaOcaml can be made available as an OPAM switch,
> people will be able to give it a try very easily.

Thanks to Cedric Cellier packaging it up and sending us a pull request [1],
you can try our MetaOCaml BER straight from OPAM via:

$ opam update
$ opam switch 4.00.1+BER
$ eval `opam config env`
$ ocaml...

-anil

[1] https://github.com/OCamlPro/opam-repository/pull/461

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[bob zhang]

[-- Attachment #1: Type: text/plain, Size: 1811 bytes --]

Hi Jacques,
  metaocamlmktop works well, thanks!

On Tue, Feb 19, 2013 at 8:51 PM, Jacques Carette <carette@mcmaster.ca>wrote:

> You need to use 'metaocamlmktop' to make a custom top-level which supports
> metaocaml.  I have tested this, and it works.
>
> I will let Oleg answer the other queries.
>
> Jacques
>
>
> On 13-02-18 10:37 PM, bob zhang wrote:
>
>> Dear Oleg,
>>    After reading the patch of BER MetaOCaml today, I found that it is not
>> too hard to port camlp4/Fan to support metaocaml.
>>    I tried to compile and install metaocaml with the patches you provided:
>>
>>    I get an install error
>> ./build/partial-install.sh: line 25: config/config.sh: No such file or
>> directory
>> make: *** [install] Error 1
>>
>>    After I ignore the error message, the metaocaml toplevel works
>> perfectly well.
>>
>>    But if I customized my own toplevel (I used my toplevel as 'ocamlmktop
>> -custom -o mocaml')
>>    mocaml is bundled with compiler-libs, the toplevel does not work, I
>> get the following
>>    error message:
>>    # let spower7 = .! spower7_code;;
>>    Error: Reference to undefined global `Runcode'
>>
>>   Currently metaocaml does not support native code, but it seems that the
>> patch only installs ocamlc, is it possible to get ocamlc.opt installed as
>> well? (not the ocamlopt.opt) ocamlbuild is not installed either. It would
>> be even nicer that ocamlopt.opt could be installed without supporting
>> metaocaml, otherwise I have to switch between different compilers from time
>> to time.
>>
>>    Would you mind get the ocamlbuild, ocamlc.opt also works? I would be
>> happy to port Fan/Camlp4 to support metaoaml, and it would be really cool
>> to get compile-time and run-time metaprogramming work together
>>
>>    Thank you in advance!
>>
>
>


-- 
Regards
-- Bob

[-- Attachment #2: Type: text/html, Size: 2390 bytes --]

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[Jacques Carette]

You need to use 'metaocamlmktop' to make a custom top-level which 
supports metaocaml.  I have tested this, and it works.

I will let Oleg answer the other queries.

Jacques

On 13-02-18 10:37 PM, bob zhang wrote:
> Dear Oleg,
>    After reading the patch of BER MetaOCaml today, I found that it is 
> not too hard to port camlp4/Fan to support metaocaml.
>    I tried to compile and install metaocaml with the patches you provided:
>
>    I get an install error
> ./build/partial-install.sh: line 25: config/config.sh: No such file or 
> directory
> make: *** [install] Error 1
>
>    After I ignore the error message, the metaocaml toplevel works 
> perfectly well.
>
>    But if I customized my own toplevel (I used my toplevel as 
> 'ocamlmktop -custom -o mocaml')
>    mocaml is bundled with compiler-libs, the toplevel does not work, I 
> get the following
>    error message:
>    # let spower7 = .! spower7_code;;
>    Error: Reference to undefined global `Runcode'
>
>   Currently metaocaml does not support native code, but it seems that 
> the patch only installs ocamlc, is it possible to get ocamlc.opt 
> installed as well? (not the ocamlopt.opt) ocamlbuild is not installed 
> either. It would be even nicer that ocamlopt.opt could be installed 
> without supporting metaocaml, otherwise I have to switch between 
> different compilers from time to time.
>
>    Would you mind get the ocamlbuild, ocamlc.opt also works? I would 
> be happy to port Fan/Camlp4 to support metaoaml, and it would be 
> really cool to get compile-time and run-time metaprogramming work together
>
>    Thank you in advance!

[Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[bob zhang]

[-- Attachment #1: Type: text/plain, Size: 1333 bytes --]

Dear Oleg,
   After reading the patch of BER MetaOCaml today, I found that it is not
too hard to port camlp4/Fan to support metaocaml.
   I tried to compile and install metaocaml with the patches you provided:

   I get an install error
./build/partial-install.sh: line 25: config/config.sh: No such file or
directory
make: *** [install] Error 1

   After I ignore the error message, the metaocaml toplevel works perfectly
well.

   But if I customized my own toplevel (I used my toplevel as 'ocamlmktop
-custom -o mocaml')
   mocaml is bundled with compiler-libs, the toplevel does not work, I get
the following
   error message:

   # let spower7 = .! spower7_code;;
   Error: Reference to undefined global `Runcode'

  Currently metaocaml does not support native code, but it seems that the
patch only installs ocamlc, is it possible to get ocamlc.opt installed as
well? (not the ocamlopt.opt) ocamlbuild is not installed either. It would
be even nicer that ocamlopt.opt could be installed without supporting
metaocaml, otherwise I have to switch between different compilers from time
to time.

   Would you mind get the ocamlbuild, ocamlc.opt also works? I would be
happy to port Fan/Camlp4 to support metaoaml, and it would be really cool
to get compile-time and run-time metaprogramming work together

   Thank you in advance!

[-- Attachment #2: Type: text/html, Size: 1604 bytes --]

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[Francois Berenger]

Hello,

Could it be (ab)used to translate easily a whole program's OCaml source
into C code?
I have no need for this right now but I'm just curious.

I wonder if it would be one way to obtain optimized binaries
on architectures for which there is no optimizing compiler.

Regards,
F.

On 01/31/2013 04:49 PM, oleg@okmij.org wrote:
> BER MetaOCaml N100 is now available. It is a strict superset of OCaml
> 4.00.1, extending it with staging annotations to construct and run
> typed code values. BER MetaOCaml has been completely re-implemented
> and thus caught up with OCaml. For those who don't know what staging
> or MetaOCaml is, a short introduction follows the news summary.
 > [...]

Re: [Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[rixed]

Once disabled Tk (--no-tk) everything compiled and installed as documented.
Thank you.

I understand that this is very interesting from a research perspective, but
practically meta-programming is only useful as long as performances are the
concern, for these problems when some critical information is not known until
runtime; I can't think of another usage for runtime code specialisation anyway.

So the question that immediately arises is then: why is metaocaml supporting
byte code only? Is a metaocamlopt planned, envisaged, doable, in a galaxy
not too far away?


For the record, I encounter a surprising lot number of occasions, both in pet
projects and at work, where meta-programming is a fruitful approach.  Probably
it's such a technique that once you used it once you suddenly discover how hard
you missed it until then. If so then it could be a killer feature for OCaml.

Only recently I've used it from scheme to specialize scheme, from scheme to
specialize C, from python to specialize C, from C to specialize C, from OCaml
to specialize assembly and from OCaml to specialize OCaml (yes, with Printf and
Dynlink). The only 'natural' language for doing such things is of course
Lisp/Scheme, but even in Lisp you don't have many guaranties that the generated
code is safe - you just know that your code fragment is a valid s-expression;
not much that what you got from the printf+compile+dlopen approach). MetaOCaml
looks so much more interesting from a practical point of view!

[Caml-list] ANN: Brand-new BER MetaOCaml for OCaml 4.00.1

[oleg]

BER MetaOCaml N100 is now available. It is a strict superset of OCaml
4.00.1, extending it with staging annotations to construct and run
typed code values. BER MetaOCaml has been completely re-implemented
and thus caught up with OCaml. For those who don't know what staging
or MetaOCaml is, a short introduction follows the news summary.

BER MetaOCaml is in the spirit of the original MetaOCaml by Taha and
Calcagno, but has been completely re-written using different
algorithms and techniques. BER MetaOCaml has been re-structured to
minimize the number of the changes to the OCaml type-checker and to
separate the `kernel' (type-checking and constructing code values)
from the `user-level'. Various ways of running the code -- compiling
to byte-code or machine instructions and executing them, or
translating code values to C or LLVM, or printing them -- can be done
in `user-level' libraries, without any need to hack into (Meta)OCaml.
(Printing and byte-code execution are included in BER N100.)  This
release of BER MetaOCaml is meant to incite future research into
type-safe meta-programming. 

To the user, the two major differences of BER N100 from the old
MetaOCaml are:

 -- constructor restriction: all data constructors and record labels 
 used within brackets must come from the types that are declared in 
 separately compiled modules.

 -- scope extrusion check: attempting to build code values with
 unbound or mistakenly bound variables (which is possible with
 mutation or other effects) is caught early, raising an exception
 with good diagnostics.

Both are explained after the short introduction to staging.  Smaller
visible differences are better printing of cross-stage persistent
values and the full support for labeled arguments. A long-standing
problem with records with polymorphic fields has fixed itself. The BER
N100 code is now extensively commented, and has a regression test
suite. BER N100 is much less invasive into OCaml: compare the size of
the patch to the main OCaml type-checker typing/typecore.ml, which
contains the bulk of the changes for type checking the staging
constructs. In the previous version BER N004, the patch had 564 lines
of additions, deletions and context; now, only 328 lines.
(The core MetaOCaml kernel is trx.ml, with 1800 lines.)


BER MetaOCaml N100 is available:

-- as a set of patches to the OCaml 4.00.1 distribution. 
        http://okmij.org/ftp/ML/ber-metaocaml-100.tar.gz
See the INSTALL document in that archive. You need the source
distribution of OCaml 4.00.1, see the following URL for details.
        http://ocaml.org/install.html

-- as a GIT bundle containing the changes relative to OCaml 4.00.1
        http://okmij.org/ftp/ML/metaocaml.bundle
First, you have to obtain the base
       git clone https://github.com/ocaml/ocaml.git -b 4.00 ometa4
then switch to tag 4.00.1 and then apply the bundle.

Jacques Carette has extensively re-written the printing of code
values, and is currently maintaining this part. I'm grateful to him
for encouragement and discussions.


Introduction to staging and MetaOCaml

The standard example of meta-programming -- the running example of
A.P.Ershov's 1977 paper that begat meta-programming -- 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)
    (* val power : int -> int -> int = <fun> *)

Suppose our program has to compute x^7 many times. We may define
    let power7 x = power 7 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 becomes known) and `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)>.
    (* val spower : int -> ('cl, int) code -> ('cl, int) code = <fun> *)

The two annotations, or staging constructs, are brackets .< e >. and
escape .~e . Brackets .< e >. `quasi-quote' the expression e,
annotating it as computed later. Escape .~e, which must be used within
brackets, tells that e is computed now but produces the result for
later. That result, the code, is spliced-in the containing bracket. 
The inferred type of spower is different. The result is no longer an
int, but ('cl, int) code -- the code of expressions that compute an int.
The first type argument to 'code', often named 'cl, is a so-called
environment classifier and can be skipped on first reading. The type
of spower spells out which argument is received now, and which
later. To specialize spower to 7, we define

    let spower7_code = .<fun x -> .~(spower 7 .<x>.)>.;;
(*
    val spower7_code : ('cl, int -> int) code = .<
      fun x_1 ->
       (x_1 *
         (((* cross-stage persistent value (id: square) *))
           (x_1 * (((* cross-stage persistent value (id: square) *)) (x_1 * 1)))))>.
*)
and obtain the code of a function that will receive x and return
x^7. Code, even of functions, can be printed, which is what MetaOCaml
toplevel did. The print-out contains so-called cross-stage persistent
values, or CSP, which `quote' present-stage values such as square to
be used later. One may think of CSP as references to `external
libraries' -- only in our case the program acts as a library for the
code it generates.

If we want to use thus specialized x^7 now, in our code, we should
compile spower7_code and link it back to our program. This is called
`running the code'

    let spower7 = .! spower7_code
    (*
    val spower7 : int -> int = <fun>
    *)

The specialized spower7 has the same type as the partially applied
power7 above. They behave identically. However, power7 x will do
recursion on n, checking n's parity, etc. In contrast, specialized
spower7 has no recursion (as can be seen from spower7_code). All
operations on n have been done when the spower7_code was computed,
producing the straight-lined code spower7 that operates only on x.

MetaOCaml supports arbitrary number of later stages, letting us write
not only code generators but also generators of code generators, etc.


Data constructor restriction

BER MetaOCaml N100 imposes the restriction that all data constructors
and record labels used within brackets must come from the types that 
are declared in separately compiled modules. For example, the
following all work:

    .<true>.;;
    .<raise Not_found>.;;
    .<Some [1]>.;;
    .<{Complex.re = 1.0; im = 2.0}>.;;
    let open Complex in .<{re = 1.0; im = 2.0}>.;;
    .<let open Complex in {re = 1.0; im = 2.0}>.;;

because data types bool, option, list, Complex are either Pervasive or
defined in the (separately compiled) standard library. However, the
following are not allowed and flagged as compile-time error:

       type foo = Bar;;
       .<Bar>.

       module Foo = struct exception E end;;
      .<raise Foo.E>.

The type declaration foo or the module declaration Foo must be moved
into a separate file. The corresponding .cmi file must also be
available at run-time: either placed into the same directory as the
executable, or somewhere within the OCaml library search path.

Scope extrusion test

Although MetaOCaml permits manipulation and splicing of open code, its
type system statically ensures that only closed code can be printed or
run: We can't run the code we haven't finished constructing. For example,
     .<fun x -> .~(let y = .! .<x>. in .<y>.)>.;;
gives a type error since .<x>. is obviously open code.

This static guarantee holds only for pure code. Effects such as
storing code values in mutable cells void the guarantee. Here is the
example using the _old_ MetaOCaml from 2006 (version 3.09.1 alpha
030).  (The problem can be illustrated simpler, but the following
example is more realistic and devious.)

    let c =
     let r = ref .<fun z->z>. in 
     let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in 
     .<fun x -> .~f (.~(!r) 1)>. ;;
    (*
    val c : ('a, '_b -> int) code =
      .<fun x_4 -> ((fun x_2 -> 0) ((fun y_3 -> x_2) 1))>.
    *)

One must look hard to see that x_2 is actually unbound in the resulting
code. The problem is revealed when we attempt to run that code:

    .! c;;
    (*
    Characters 77-78:
      Unbound value x_2

    Exception: Trx.TypeCheckingError.
    *)

Since we get the error anyway (without much diagnostics though), one
may discount the problem. Alas, sometimes scope extrusion results in
no error -- just in wrong results.

    let c1 =
     let r = ref .<fun z->z>. in 
     let _ = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in 
     !r;;
    (*
    val c1 : ('a, '_b -> '_b) code = .<fun y_3 -> x_2>.
    *)

we then use c1 to construct the code c2:

    let c2 = .<fun y -> fun x -> .~c1>.;;
    (*
    val c2 : ('a, 'b -> 'c -> '_d -> '_d) code =
      .<fun y_1 -> fun x_2 -> fun y_3 -> x_2>.
    *)

which contains no unbound variables and can be run without problems.

    (.! c2) 1 2 3;;
    (* - : int = 2 *)

It is most likely that the user did not intend for 'fun x ->' in c2 to
bind x in c1. This is the blatant violation of lexical scope. And yet we
get no error or other overt indication that something went wrong.

BER MetaOCaml N100 has none of this. Although the type system still
permits code values with escaped variables, attempting to use such
code in any way -- splice, print or run -- immediately raises an
exception. For example, entering the expression c in the top-level BER
MetaOCaml N100 gives

Exception: Failure
Scope extrusion at Characters 89-99:
       let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in 
                                    ^^^^^^^^^^
 for the identifier x_7 bound at Characters 74-75:
       let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in 
                     ^
The exception message tells which variable got away, where it was
bound and where it eloped.


The file NOTES.txt in the BER MetaOCaml distribution describes the
features of BER MetaOCaml in more detail and outlines directions for
further development. Hopefully the release of BER MetaOCaml N100 would
stimulate using and researching typed meta-programming.