* Re: [Caml-list] Symbolic derivative macro
2006-11-14 4:13 Symbolic derivative macro Jon Harrop
@ 2006-11-15 12:13 ` Bruno De Fraine
2006-11-15 12:37 ` Yaron Minsky
1 sibling, 0 replies; 3+ messages in thread
From: Bruno De Fraine @ 2006-11-15 12:13 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 3+ messages in thread