Relit: Typed Literal Macros for Reason

Reason is an increasingly popular alternative syntax for OCaml designed by engineers at Facebook to make OCaml more notationally comfortable for contemporary programmers. However, Reason, following OCaml, builds in literal notation for only a few common data structures, e.g. list literals like

[x, y, z]

[|x, y, z|]

In our ICFP 2018 paper (.bib, video, slides), we address this problem by introducing typed literal macros (TLMs) into Reason. TLMs allow the programmer to define new literal notation, of nearly arbitrary design, for expressions and patterns of any type at all.

Tutorial: Regex Notation

For example, say that we have defined a recursive datatype

Regex.t

reason
  module Regex = {
    type t =
      | Empty
      | AnyChar
      | Str(string)
      | Seq(t, t)
      | Or(t, t)
      | Star(t);
  };

Applying these constructors directly is notationally costly, so let's define a TLM named

$regex

$regex

Regex_notation

reason
module Regex_notation = {
  notation $regex at Regex.t { /* ... full definition given under "TLM Definitions" below ... */ }
};

The client programmer can apply

Regex_notation.$regex

Regex.t

reason
let r = Regex_notation.$regex `(a*bb(b|a)b)`;

a*bb(b|a)b

`(

)`

reason
Regex.(Seq(Star(Str("a")), Seq(Str("b"), Seq(Str("b"), Seq(Or(Str("b"), Str("a")), Str("b")))))

Abbreviations

To make TLM applications even more concise, we can

open Regex_notation

$regex

reason
open Regex_notation;
let r = $regex `(a*bb(b|a)b)`;

$r

Regex_notation.$regex

reason
notation $r = Regex_notation.$regex;
let r = $r `(a*bb(b|a)b)`;

or implicitly apply

Regex_notation.$regex

open notation

reason
open notation Regex_notation.$regex;
let r = `(a*bb(b|a)b)`;

open notation

reason
let r = Regex_notation.$regex.( `(a*bb(b|a)b)` )

Splicing

Sometimes we want to construct a regex value compositionally, i.e. by "splicing together" other values. To support this,

$regex

$(e)

$$(e)

e

e

DNA.any_base

bisI

open notation Regex_notation.$regex;
module DNA = {
  let any_base = `(A|T|G|C)`;
};
let bisI = `(GC$(DNA.any_base)GC)`;

Each TLM decides for itself how it recognizes spliced expressions.

Keep in mind that the literal body is expanded at compile-time, so using TLMs together with composite representations of data structures like regexes and SQL queries can help programmers avoid string injection attacks without giving up the notational benefits of string representations.

Splicing is also sometimes called interpolation because it generalizes string interpolation as featured in many languages. Splicing is also sometimes called unquotation or antiquotation because it generalizes the unquotation forms in code quotation systems, like those in various Lisp dialects and many other languages.

Typing, Hygiene and Segmentation

User-defined notation is great when you are familiar with it, but what about when you encounter an unfamiliar notation? TLMs were carefully designed to be uniquely reasonable in this situation. In particular, you do not need to peek at the generated expansion or the details of the parser to reason about types and binding in a program that uses TLMs. Instead, the system maintains the following important abstract reasoning principles:

• Expansion Typing: Each notation definition specifies a type annotation—

  at Regex.t

  on

  $regex

  above—that determines the type of the generated expansion.
• Context Independence: The expansion is guaranteed to be context independent, meaning that it does not make any assumptions about which variables (including module variables) are in scope at the application site. Therefore, clients can rename variables and manage imports without thinking about the expansion's dependencies. For example, the

  Regex

  module can be shadowed, or even out of scope entirely, when applying

  $regex

  , even though the expansion uses the constructors defined in the

  Regex

  module (see below for more on how dependencies are managed).

• Capture Avoidance: Spliced expressions are capture avoiding, meaning that any variables that appear in a spliced expression cannot capture bindings internal to the expansion. Consider the following example:

   let tmp = DNA.any_base;
   let bisI = $regex `(GC$(tmp)GC)`
  

  Even if the expansion generated by the TLM above happens to bind a variable named

  tmp

  for internal use, the system ensures that the reference to

  tmp

  in the spliced expression will always refer to the binding of

  tmp

  on the first line.

  The context independence and capture avoidance principles together are referred to as the hygiene principles. Relit is strictly hygienic—there is no way for a TLM to opt out of these restrictions.

• Segmentation: Spliced expressions must be separated by at least one character. This ensures that there is always a unique segmentation of every literal body into spliced expressions and characters parsed in some other way by the TLM.

• Segment Typing: Each spliced expression is also labeled with an expected type by the applied TLM. This information is currently used when reporting type errors. In the future, we expect to convey the segmentation and segment typing information interactively within the program editor.

The ICFP paper investigates these reasoning principles in formal detail (i.e. with a typed lambda calculus and proofs).

TLM Definitions

Let us now consider the full definition of

Regex_notation.$regex

module Regex_notation = {
  notation $regex at Regex.t {
    lexer Regex_parser.Lexer
    parser Regex_parser.Parser.start
    in package regex_parser;
    dependencies = {
      module Regex = Regex;
    };
  };
};

Scoping

A TLM definition can appear anywhere a module definition can appear, and TLM definitions follow the same scoping rules as modules (internally, they are implemented as modules with singleton signatures; see the paper).

Lexing and Parsing

Each TLM must specify a lexer, here

Regex_parser.Lexer

Regex_parser.Parser.start

start

in package regex_parser

The lexer must be generated by (or satisfy the same interface as lexers generated by) ocamllex and the parser must be generated by (or satisfy the same interface as parsers generated by) Menhir, which is a modernized derivative of ocamlyacc. These are the most popular and mature lexer and parser generators within the OCaml ecosystem, and notably, Reason itself is implemented using these same generators. Chapter 16 of Real World OCaml nicely introduces both.

We will not detail the regex lexer and parser definitions here, but the ICFP paper (Sec. 2.2) does cover them. The full definitions can be found alongside the rest of the definitions above in the

example_tlms/regex_example

Relit.Segment.read_to

relit_helper

metaquot

Dependencies

Each TLM definition also provides a listing of expansion dependencies, i.e. types and modules from the definition site that expansions generated by the parser might need access to (other than

Pervasives

Regex

Regex

Regex

The paper further motivates this design decision, but briefly, explicit dependencies serve to ensure that renamings need not propagate into the parse trees constructed in the parser (where variables are represented using strings), and it also serves to maintain the abstraction discipline of the OCaml module system (making all bindings at the definition site implicitly available at application sites would require violating abstraction).

More Examples and Tests

We've got an

examples_tlms

To see some simple uses of these examples, look under

simple_tests

make {simple_example,spliced_ocaml,splice_in_splice,my_first_timeline}

Run

make

test/test.ml

There is also a standlone repository that defines a TLM for lists and can be used as a project template for TLM providers.

Installation

Requirements

Make sure you have opam and OCaml 4.07.x by running

opam switch

via

opam

Run

opam update && opam install ppx_relit

via

git

An alternative way to install Relit is via

git

git clone https://github.com/cyrus-/relit
cd relit
make deps
make install
make test

Usage

To use Relit in your own project, you just have to include the Relit ppx,

ppx_relit

(preprocess (staged_pps ppx_relit))

simple_tests/dune

staged_pps

What about OCaml??

Relit does not support OCaml at the moment. There's nothing particularly Reason-specific, aside from the fact that we have only forked the Reason parser and not the OCaml one. We're planning to add OCaml support sometime soon. :smile:

How It Works

The ppx execution starts in

ppx_relit/ppx_relit.ml

relit_expansion_pass

There's also a four page talk proposal and slides that cover the implementation in a little more detail. We're happy to discuss the implementation with anyone who wants to work on it or implement TLMs in another language!

Debug Mode

Relit does provide a way to peek at the underlying expansion of macros when the need arises.

Setting the environment variable

RELIT_DEBUG=true

open Regex_example;

let regex = Regex_notation.$regex (a|b|c);
let () = print_endline(Regex.show(regex));

will cause the Relit PPX to print out the following (comments added here for clarity):

open Regex_example;

/* type annotation (moved to the let binding by the pretty-printer) ensures
   that the expansion is of the expected type /
let regex: Regex_notation.RelitInternalDefn_regex.t =
  (
    / open this first to avoid edge case where path to TLM is through a 
       shadowed module in Pervasives /
    [@warning "-33"] / suppresses warnings when a dependency is not used /
    Regex_notation.RelitInternalDefn_regex.( 
      [@warning "-33"]
      Pervasives.(
        [@warning "-33"]
        Dependencies.( / open the dependencies /
          () => / no spliced expressions, so this is an empty argument list /
            / the generated expansion itself */
            Regex.Or(
              Regex.Or(Regex.Str("a"), Regex.Str("b")),
              Regex.Str("c"),
            )
        )
      )
    )
  )();
let () = print_endline(Regex.show(regex));

This ends up showing a lot of the implementation details of Relit. Relit is designed to ensure that TLM readers and users should rarely have to look at the expansion of a TLM application. Debug mode is mainly targeted towards authors of TLM definitions: it allows TLM writers to debug their parsers easily.

Current Limitations

• Relit does not yet implement pattern TLMs.
• Relit does not yet implement parametric TLMs. As a somewhat awkward workaround, you can use parameterized modules (functors), e.g. see this example of a TLM for lists.
• Relit doesn't work within the toploop/rtop/utop.

• The following warning will come up a lot:

    [WARNING] Interface topdirs.cmi occurs in several directories: /home/cyrus/.opam/4.06.1/lib/ocaml/compiler-libs, /home/cyrus/.opam/4.06.1/lib/ocaml
  

It is harmless. It is due to a bug in OCaml.

Contributors

• Charles Chamberlain
• Cyrus Omar