Symbolic derivative macro

Jon Harrop
 Bruno De Fraine
 Yaron Minsky
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20061115 (12:13) 
From:  Bruno De Fraine <Bruno.De.Fraine@v...> 
Subject:  Re: [Camllist] Symbolic derivative macro 
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, B1050 Brussels tel: +32 (0)2 629 29 75 fax: +32 (0)2 629 28 70 email: Bruno.De.Fraine@vub.ac.be