Quotations in F#, OCaml and Lisp

A quotation mechanism lets you embed code in your code and have the compiler transform that code from the source you provide into a data structure that represents it. For example, the following gives you a data structure representing the F# expression 1+2:

> <@ 1+2 @>;;
val it : Quotations.Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (2)])
    {CustomAttributes = [NewTuple (Value ("DebugRange"),
          NewTuple (Value ("stdin"), Value (3), Value (3), Value (3), Value (6)))];
     Raw = ...;
     Type = System.Int32;}

You can then hack on this data structure in order to apply transformations to your code, such as translating it from F# to Javascript in order to run it client side on almost any browser.

The F# quotation mechanism is extremely limited in functionality compared to the quotation mechanisms of languages like OCaml and Lisp. Moreover, although the .NET Framework and F# compiler provide everything required to compile and execute quoted code at full speed, the evaluation mechanism for quoted code is orders of magnitude slower than real F# code which, again, renders it virtually useless. Consequently, I am not familiar with any real applications of it beyond Websharper.

For example, you can only quote certain kinds of expressions in F# and not other code such as type definitions:

> <@ type t = Int of int @>;;

  <@ type t = Int of int @>;;
  ---^^^^

C:\Users\Jon\AppData\Local\Temp\stdin(4,4): error FS0010: Unexpected keyword 'type' in quotation literal

Most quotation mechanisms let you quote any valid code at all. For example, OCaml's quotation mechanism can quote the type definition that F# just barfed on:

$ ledit ocaml dynlink.cma camlp4oof.cma
        Objective Caml version 3.12.0

        Camlp4 Parsing version 3.12.0
# open Camlp4.PreCast;;
# let _loc = Loc.ghost;;
val _loc : Camlp4.PreCast.Loc.t = <abstr>
# <:expr< 1+2 >>;;
- : Camlp4.PreCast.Ast.expr =
Camlp4.PreCast.Ast.ExApp (<abstr>,
  Camlp4.PreCast.Ast.ExApp (<abstr>,
  Camlp4.PreCast.Ast.ExId (<abstr>, Camlp4.PreCast.Ast.IdLid (<abstr>, "+")),
  Camlp4.PreCast.Ast.ExInt (<abstr>, "1")),
  Camlp4.PreCast.Ast.ExInt (<abstr>, "2"))
# <:str_item< type t = Int of int >>;;
- : Camlp4.PreCast.Ast.str_item =
Camlp4.PreCast.Ast.StSem (<abstr>,
  Camlp4.PreCast.Ast.StTyp (<abstr>,
  Camlp4.PreCast.Ast.TyDcl (<abstr>, "t", [],
    Camlp4.PreCast.Ast.TySum (<abstr>,
    Camlp4.PreCast.Ast.TyOf (<abstr>,
      Camlp4.PreCast.Ast.TyId (<abstr>,
      Camlp4.PreCast.Ast.IdUid (<abstr>, "Int")),
      Camlp4.PreCast.Ast.TyId (<abstr>,
      Camlp4.PreCast.Ast.IdLid (<abstr>, "int")))),
    [])),
  Camlp4.PreCast.Ast.StNil <abstr>)

Here is an example in Common Lisp:

$ sbcl
This is SBCL 1.0.29.11.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* '(+ 1 2)
(+ 1 2)

Metaprogramming is one application where pattern matching can be extremely useful but pattern matching is a general-purpose language feature. You may appreciate the article from the Benefits of OCaml about a minimal interpreter. In particular, note how easy pattern matching makes it to act upon each of the different kinds of expression:

> let rec eval vars = function
    | EApply(func, arg) ->
        match eval vars func, eval vars arg with
        | VClosure(var, vars, body), arg -> eval ((var, arg) :: vars) body
        | _ -> invalid_arg "Attempt to apply a non-function value"
    | EAdd(e1, e2) -> VInt (int(eval vars e1) + int(eval vars e2))
    | EMul(e1, e2) -> VInt (int(eval vars e1) * int(eval vars e2))
    | EEqual(e1, e2) -> VBool (eval vars e1 = eval vars e2)
    | EIf(p, t, f) -> eval vars (if bool (eval vars p) then t else f)
    | EInt i -> VInt i
    | ELetRec(var, arg, body, rest) ->
        let rec vars = (var, VClosure(arg, vars, body)) :: vars in
        eval vars rest
    | EVar s -> List.assoc s vars;;
val eval : (string * value) list -> expr -> value = <fun>

That OCaml article was used as the basis of the F#.NET Journal article "Language-oriented programming: The Term-level Interpreter" (31st December 2007).

You can write compilers in F#. In fact, F# is derived from a family of languages that were specifically designed for metaprogramming, the so-called MetaLanguages (ML) family.

The article "Run-time code generation using System.Reflection.Emit" (31st August 2008) from the F#.NET Journal described the design and implementation of a simple compiler for a minimal language called Brainf*ck. You can extend this to implement more sophisticated languages like Scheme. Indeed, the F# compiler is mostly written in F# itself.