Re: [Caml-list] Symbolic derivative macro

[Bruno De Fraine <Bruno.De.Fraine@vub.ac.be>]

Hello,

On 14 Nov 2006, at 05:13, Jon Harrop wrote:
> Can someone point me to, or even knock up, a simple camlp4 macro that
> demonstrates naively but statically computing the symbolic  
> derivative of an
> OCaml expression?

Since there hasn't been an answer from anyone more knowledgeable, I'm  
willing to give it a shot.

One important part of camlp4 is the quotation system. A quotation  
allows a user function to describe how a part of the source file is  
translated into a syntax tree.

I load an ocaml toplevel with camlp4 and the standard AST quotations.  
Since every AST node is associated with a source code location, and  
the quotations can't find this out by themselves, they require the  
variable "_loc" (previously "loc") to be defined. Since I'm not  
concerned with source locations, I define a dummy value.

$ ocaml camlp4o.cma q_MLast.cmo
         Objective Caml version 3.09.2

         Camlp4 Parsing version 3.09.2

# let _loc = Token.dummy_loc ;;
val _loc : Token.flocation = ...

I can then inspect the AST of some simple OCaml expressions using the  
quotation "expr". As above, I've replaced occurrences of _loc with  
"..." to keep the output readable:

# <:expr< 1 >> ;;
- : MLast.expr =
MLast.ExInt
(...,"1")
# <:expr< x+1 >> ;;
- : MLast.expr =
MLast.ExApp
(...,
MLast.ExApp
   (...,
   MLast.ExLid
    (...,
    "+"),
   MLast.ExLid
    (...,
    "x")),
MLast.ExInt
   (...,
   "1"))

To understand this latter AST, note that the expression x+1 is  
equivalent to ((+) x) 1.

This is a good moment to mention that you can employ antiquotations  
inside quotations to specify parts that you do not want to be  
translated, but rather interpreted directly. Inside expressions you  
can antiquote e.g. expressions and literal values:

# let i = <:expr< 1 >> in <:expr< $i$ + $i$ >> ;;
- : MLast.expr =
MLast.ExApp
(...,
MLast.ExApp
   (...,
   MLast.ExLid
    (...,
    "+"),
   MLast.ExInt
    (...,
    "1")),
MLast.ExInt
   (...,
   "1"))
# <:expr< $str: Sys.ocaml_version$ >> ;;
- : MLast.expr =
MLast.ExStr
(...,"3.09.2")
# <:expr< $int: string_of_int Sys.word_size$ >> ;;
- : MLast.expr =
MLast.ExInt
(...,"32")

We can then define our core derivative function as a translation from  
one expression AST to another:
(Note that I choose to make "_loc" an explicit argument to make the  
function independent from the environment)

# let rec deriv _loc x = function
         | MLast.ExInt (_,_) -> <:expr< 0 >>
         | MLast.ExLid (_,n) ->
                 let i = if n = x then "1" else "0" in
                 <:expr< $int:i$ >>
         | MLast.ExApp (_,
                 MLast.ExApp (_,
                         MLast.ExLid (_,"+"),
                         u),
                 v) ->
                 let u' = deriv _loc x u and v' = deriv _loc x v in
                 <:expr< $u'$ + $v'$ >>
         | MLast.ExApp (_,
                 MLast.ExApp (_,
                         MLast.ExLid (_,"*"),
                         u),
                 v) ->
                 let u' = deriv _loc x u and v' = deriv _loc x v in
                 <:expr< $u'$ * $v$ + $u$ * $v'$ >>
         | _ -> failwith "Not implemented"
;;
val deriv : MLast.loc -> string -> MLast.expr -> MLast.expr = <fun>

You can see this already makes correct derivatives, although without  
algebraic simplification:

# deriv _loc "x" <:expr< x*(x+y) >> = <:expr< 1*(x+y) + x*(1+0) >> ;;
- : bool = true

I compare to the expected result in the above expression because the  
actual AST expression is hardly readable. However, with a bit of a  
workaround, it is possible to employ a printer to print an expression  
AST in a nice form. I came up with:
(note that Pcaml is a module that holds references to parsers,  
printers, etc. set by language extensions)

# #load "pr_o.cmo" ;;
# let print_expr e = !Pcaml.print_implem [MLast.StExp(_loc,e),_loc] ;;
val print_expr : MLast.expr -> unit = <fun>
# print_expr (deriv _loc "x" <:expr< x*(x+y) >>) ;;
let _ = 1 * (x + y) + x * (1 + 0)
- : unit = ()

Of course, you don't just want the AST of the derivative expression,  
you also want to evaluate it.

One way to do this would be to install the "deriv" transformation  
function as a quotation through Quotation.add. This requires the name  
of the quotation as well as how to expand from the source text to a  
expression/pattern AST:

# Quotation.add ;;
- : string -> Quotation.expander -> unit = <fun>

With file "quotation.mli" defining:

type expander =
   [ ExStr of bool -> string -> string
   | ExAst of (string -> MLast.expr * string -> MLast.patt) ]
;

A difficulty here is that our transformation requires the original  
expression as an AST while it is provided as a string. So we need to  
invoke the installed parsing functions first:

# let parse_expr s =
   Grammar.Entry.parse Pcaml.expr_eoi (Stream.of_string s) ;;
val parse_expr : string -> MLast.expr = <fun>
# Quotation.add "deriv_x" (Quotation.ExAst (
         (fun s -> deriv _loc "x" (parse_expr s)),
         (fun _ -> failwith "Not supported"))) ;;
- : unit = ()

Now we can do:

# let x = 2 and y = 3 in <:deriv_x< x*(x+y) >> ;;
- : int = 7

Alternatively, we can install our symbolic derivative transformation  
in the main grammar of the language using the syntax extension for  
defining extensions:

# #load "pa_extend.cmo" ;;
# EXTEND
     Pcaml.expr: LEVEL "expr1" [
       [ "deriv_x"; e = Pcaml.expr -> deriv _loc "x" e ]
     ];
END;;
- : unit = ()

(Note that inside of the action of the grammar rule, the variable  
"_loc" is bound to the source location of the rule; so we don't  
employ the dummy location from the environment.)

This makes deriv_x a keyword of the language and allows for it to be  
employed inside of expressions:

# let x = 2 and y = 3 in deriv_x x*(x+y) ;;
- : int = 7

EPILOGUE

When not using the toplevel, you would put the definition of function  
"deriv" as well as the EXTEND statement in a source file named  
"pa_deriv.ml" ("pa" because you influence the parsing phase). It can  
then be compiled as:

$ ocamlc -c -pp 'camlp4o q_MLast.cmo pa_extend.cmo' -I +camlp4  
pa_deriv.ml

(The -pp flag because the syntax uses AST quotations and the EXTEND  
statement; the -I flag because we refer to types and definitions from  
module MLast.)

To compile a source file that employs the deriv_x keyword, employ the  
preprocessor with our extension loaded:

$ ocamlc -c -pp 'camlp4o ./pa_deriv.cmo' example.ml

To inspect the result of preprocessing manually, you load an  
appropriate printer, e.g.:

$ camlp4o ./pa_deriv.cmo pr_o.cmo example.ml

Best regards,
Bruno De Fraine

-- 
Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, INFO - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.De.Fraine@vub.ac.be