Camlp4 is a software system for writing extensible parsers for programming languages. It provides a set of Objective Caml libraries that are used to define grammars as well as loadable syntax extensions of such grammars. Camlp4 stands for Caml Preprocessor and Pretty-Printer and one of its most important applications is the definition of domain-specific extensions of the syntax of OCaml. Objective Caml (OCaml) is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ... CAML may mean: Categorical_Abstract_Machine_Language, a version of ML Collaborative Application Markup Language, an XML-Based markup language used with the Microsoft SharePoint collaborative portal application. ... In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. ... To prettyprint (or pretty-print) is to make something, commonly some printed material, appear more appealing to the human eye. ... Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...

Camlp4 is part of the official OCaml distribution which is developed at the INRIA. Its original author is Daniel de Rauglaudre. OCaml version 3.10.0, released in May 2007, introduced a significantly modified and backwards incompatible version of Camlp4. All of the examples below are for the previous version of Camlp4 (versions 3.09 and prior). The Institut national de recherche en informatique et en automatique (INRIA) is a French national research institution focusing on computer science, control theory and applied mathematics. ... In technology (especially computing), backward compatibility has several related but differing meanings: A system is backward compatible if it is compatible with earlier versions of itself, or sometimes other earlier systems, particularly systems it intends to supplant. ...

Concrete and abstract syntax

A Camlp4 preprocessor operates by loading a collection of compiled modules which define a parser as well as a pretty-printer: the parser converts an input program into an internal representation. This internal representation constitutes the abstract syntax tree (AST). It can be output in a binary form, e.g. it can be passed directly to one of the OCaml compilers, or it can be converted back into a clear text program. The notion of concrete syntax refers to the format in which the abstract syntax is represented. A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. ... To prettyprint (or pretty-print) is to make something, commonly some printed material, appear more appealing to the human eye. ... A computer program is a collection of instructions that describe a task, or set of tasks, to be carried out by a computer. ... In computer science, an abstract syntax tree (AST) is a finite, labeled, directed tree, where the internal nodes are labeled by operators, and the leaf nodes represent the operands of the node operators. ... This article is about the computing term. ...

For instance, the OCaml expression (1 + 2) can also be written ((+) 1 2) or (((+) 1) 2). The difference is only at the level of the concrete syntax, since these three versions are equivalent representations of the same abstract syntax tree. As demonstrated by the definition of a revised syntax for OCaml, the same programming language can use different concrete syntaxes. They would all converge to an abstract syntax tree in a unique format that a compiler can handle. An expression in a programming language is a combination of values and functions or procedures, interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then returns another value. ...

The abstract syntax tree is at the center of the syntax extensions, which are in fact OCaml programs. Although the definition of grammars must be done in OCaml, the parser that is being defined or extended is not necessarily related to OCaml, in which case the syntax tree that is being manipulated is not the one of OCaml. Several libraries are provided which facilitate the specific manipulation of OCaml syntax trees.

Fields of application

Domain-specific languages are a major application of Camlp4. Since OCaml is a multi-paradigm language, with an interactive toplevel and a native code compiler, it can be used as a backend for any kind of original language. The only thing that the developer has to do is write a Camlp4 grammar which converts the domain-specific language in question into a regular OCaml program. Other target languages can also be used, such as C. C is a general-purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

If the target language is OCaml, simple syntax add-ons or syntactic sugar can be defined, in order to provide an expressivity which is not easy to achieve using the standard features of the OCaml language. A syntax extension is defined by a compiled OCaml module, which is passed to the camlp4o executable along with the program to process. Syntactic sugar is a term coined by Peter J. Landin for additions to the syntax of a computer language that do not affect its expressiveness but make it sweeter for humans to use. ...

Interestingly, Camlp4 includes a domain-specific language as it provides syntax extensions which ease the development of syntax extensions. These extensions allow a compact definition of grammars (EXTEND statements) and quotations such as <:expr< 1 + 1 >>, i.e. deconstructing and constructing abstract syntax trees in concrete syntax. A domain-specific language (DSL) is a programming language designed to be useful for a specific set of tasks, in contrast to general-purpose programming languages. ...

Example

The following example defines a syntax extension of OCaml. It provides a new keyword, memo, which can be used as a replacement for function and provides automatic memoization of functions with pattern matching. Memoization consists in storing the results of previous computations in a table so that the actual computation of the function for each possible argument occurs at most once. In computer science, a keyword is an identifier which indicates a specific command. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ... Pattern matching is the act of checking for the presence of the constituents of a given pattern. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ... Look up computation in Wiktionary, the free dictionary. ...

This is pa_memo.ml, the file which defines the syntax extension:

 let unique = let n = ref 0 in fun () -> incr n; "__pa_memo" ^ string_of_int !n EXTEND GLOBAL: Pcaml.expr; Pcaml.expr: LEVEL "expr1" [ [ "memo"; OPT "|"; pel = LIST1 match_case SEP "|" -> let tbl = unique () in let x = unique () in let result = unique () in <:expr< let $lid:tbl$ = Hashtbl.create 100 in fun $lid:x$ -> try Hashtbl.find $lid:tbl$ $lid:x$ with [ Not_found -> let $lid:result$ = match $lid:x$ with [ $list:pel$ ] in do { Hashtbl.replace $lid:tbl$ $lid:x$ $lid:result$; $lid:result$ } ] >> ] ]; match_case: [ [ p = Pcaml.patt; w = OPT [ "when"; e = Pcaml.expr -> e ]; "->"; e = Pcaml.expr -> (p, w, e) ] ]; END 

Example of program using this syntax extension:

 let counter = ref 0 (* global counter of multiplications *) (* factorial with memoization *) let rec fac = memo 0 -> 1 | n when n > 0 -> (incr counter; n * fac (n - 1)) | _ -> invalid_arg "fac" let run n = let result = fac n in let count = !counter in Printf.printf "%i! = %i number of multiplications so far = %in" n result count let _ = List.iter run [5; 4; 6] 

The output of the program is as follows, showing that the fac function (factorial) only computes products that were not computed previously:

 5! = 120 number of multiplications so far = 5 4! = 24 number of multiplications so far = 5 6! = 720 number of multiplications so far = 6 

See also

• Objective Caml

Objective Caml (OCaml) is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...

External links

• Camlp4 reference manual
• Camlp4 tutorial
• Camlp4 undocumented features
• How to customize the syntax of OCaml, using Camlp4 - Everything you always wanted to know, but were afraid to ask
• One-Day Compilers or How I learned to stop worrying and love metaprogramming