Confusing about F# Quotations and Pattern Matching in Meta-programming

Question

1- I'm really confusing on applying F# Quotation & Pattern on Meta Programming, please suggest some way to approach this concept in F#.

2- Can you show me some real application of F# Quotations and Pattern in Meta Programming ?

3- Some guys said that he can even make another language like IronScheme by F#,is that right ?

Thanks.

Answer 1

1- I'm really confusing on applying F# Quotation & Pattern on Meta Programming, please suggest some way to approach this concept in F#.

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.

2- Can you show me some real application of F# Quotations and Pattern in Meta Programming ?

The F# quotation mechanism is extremely limited in functionality compared to the quotation mechanisms of languages like OCaml and Lisp, to the point where I wonder why it was ever added. 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>)

FWIW, 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 my 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).

3- Some guys said that he can even make another language like IronScheme by F#,is that right ?

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

On a related note, I just completed a project writing high-performance serialization code that used reflection to consume F# types in a project and then spit out F# code to serialize and deserialize values of those types

Answer 2

F# quotations allow you to mark some piece of F# code and get the representation of the source code. This is ued in WebSharper (see for example this tutorial) to translate F# code to JavaScript. Another example is F# support for LINQ where code marked as <@ ... @> is translated to SQL:

let res = <@ for p in db.Products 
               if p.IsVisible then yield p.Name @> |> query

Pattern matching is simply a very powerful language construct, but it is nothing more mysterious than for example if. The idea is that you can match value against patterns and program will choose the first matching branch. This is powerful because patterns can be nested and so you can use it to process various complex data structures or implement symbolc processing:

match expr with
| Multiply(Constant 0, _) | Multiply(_, Constant 0) -> 0
| Multiply(expr1, expr2) -> (eval expr1) * (eval expr2)
// (other patterns)

For example, here we're using pattern matching to evaluate some representation of numerical expression. The first pattern is an optimization that deals with cases where one argument of multiplication is 0.

Writing languages You can use F# (just like any other general purpose language) to write compilers and tools for other languages. In F#, this is easy because it comes with tools for generating lexers and parsers. See for example this introduction.