Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

17 views

Skip to first unread message

Nov 15, 2006, 7:19:20 AM11/15/06

to Jon Harrop

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.D...@vub.ac.be

_______________________________________________

Caml-list mailing list. Subscription management:

http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list

Archives: http://caml.inria.fr

Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Bug reports: http://caml.inria.fr/bin/caml-bugs

Nov 15, 2006, 7:43:41 AM11/15/06

to Jon Harrop

There is this. which is done via a functor rather than camlp4...

http://wmfarr.blogspot.com/2006/10/automatic-differentiation-in-ocaml.html

On 11/13/06, Jon Harrop <j...@ffconsultancy.com> 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?

>

> This seems like an obvious camlp4 example but I've yet to find it...

>

> --

> Dr Jon D Harrop, Flying Frog Consultancy Ltd.

> Objective CAML for Scientists

> http://www.ffconsultancy.com/products/ocaml_for_scientists

0 new messages

Search

Clear search

Close search

Google apps

Main menu