OCaml Weekly News

• ARM: Advanced RISC Machine
• BFS: Breadth First Search
• DEC: Domain Execution Context
• GC: Garbage Collector
• JSON: JavaScript Object Notation
• NUMA: Non-Uniform Memory Access
• OPAM: OCaml Package Manager
• OS: Operating System
• PR: Pull Request
• RISC-V: Reduced Instruction Set Computing - V
• SSSP: Single Source Shortest Path

The ability to transparently introduce hash-consing into a complex collection of AST types should need no argument. The ability to use "quotations" over such an AST type might need some motivation. So consider a type of s-expressions, viz

type sexp =
    Atom of string
  | Cons of sexp * sexp
  | Nil

with the obvious parsing that we're all used-to from LISP/Scheme. The hashconsed version of this type is

type sexp_node =
    Atom of string
  | Cons of sexp * sexp
  | Nil
and sexp = sexp_node hash_consed

with (from the opam package hashcons)

type +'a hash_consed = private {
  hkey : int;
  tag : int;
  node : 'a }

NOTE: there is a nuance here that I'll address at the end of ths post in the section "Appendix B: Types with and without vala".

Let's suppose we want to write the function atoms : sexp -> string list that returns the list of string (those wrapped by Atom) at the leaves of the s-expression. The code is easy enough (just rotate left-child cons-nodes to the right, until we get an atom (or Nil) and then move on to the cdr. This is a good example to consider, because it requires multi-level pattern-matching and multi-level constructor-expressions. So the introduction of meaningless bureaucracy will be palpable.

let rec atoms =
  function
    Nil -> []
  | Atom a -> [a]
  | Cons(Cons(caar, cdar), cdr) ->
      atoms (Cons(caar, Cons (cdar, cdr)))
  | Cons(Nil, cdr) -> atoms cdr
  | Cons(Atom a, cdr) -> a :: atoms cdr

and the hashconsed version is

let rec atoms =
  function
    {node = Nil} -> []
  | {node = Atom a} -> [a]
  | {node = Cons({node = Nil}, cdr)} -> atoms cdr
  | {node = Cons({node = Atom a}, cdr)} -> a :: atoms cdr
  | {node = Cons ({node = Cons (caar, cdar)}, cdr)} ->
      atoms (make_sexp (Cons (caar, (make_sexp (Cons (cdar, cdr))))))

As you can see, there are extra patterns { node = ...} and a new constructor make_sexp (to perform the actual hashtable lookup & consing). And these extra bits appear at multiple levels in both patterns and expressions.

Wouldn't it be nice, if we could write one version of this code, viz.

let rec atoms = function
    <:sexp< () >> -> []
  | <:sexp< $atom:a$ >> -> [a]
  | <:sexp< ( () . $exp:cdr$ ) >> -> atoms cdr
  | <:sexp< ( $atom:a$ . $exp:cdr$ ) >> -> a::(atoms cdr)
  | <:sexp< ( ( $exp:caar$ . $exp:cdar$ ) . $exp:cdr$ ) >> ->
    atoms <:sexp< ( $exp:caar$ . ( $exp:cdar$ . $exp:cdr$ ) ) >>

and merely by changing "<:sexp<" to "<:hcsexp<" get a version of the function that works on hashconsed s-expressions? The text within <:sexp< .... >> is called a "quotation" in Camlp5, and is similar to the same concept in ppx_metaquot and the much older LISP idea of "quasi-quotation". The contained text is parsed with a parser for s-expressions, slightly modified to have indications for where the text $...$ may appear – these are called "anti-quotations', and can contain OCaml source code (e.g. variables) albeit not quotations (so no arbitrary nesting). The "quotation expander" parses this text to AST and applies a converter to produce an OCaml expression or pattern AST that does what the quotation intends. The lovely thing is, by changing out the quotation-expander (replace "sexp" with "hcsexp") we can change the code that is generated, and if the quotation-expander is generated from the type definition, it's not actually any work for the programmer to achieve this.

NOTE: Unlike with ppx_metaquot, the antiquotations can be placed in nearly-arbitrary positions in the parse-tree (hence, in the AST): there is no requirement that they correspond to variable-names or identifiers in the OCaml AST: indeed, our running example will not be the OCaml AST, even though all of this machinery has been applied-to the OCaml AST successfully.

In this post I'll walk you thru how to achieve this goal: building up the machinery, step-by-step, to allow one to write basically arbitrary expressions in your AST's surface syntax, and automatically get either "normal' (no hash-consing) or "hashconsed" patterns & expressions.

A while back in the "Future of PPX" post ( https://discuss.ocaml.org/t/the-future-of-ppx/3766 ) there was some discussion of hash-consing for ASTs, and the complexities of achieving it. I wrote a reply post "Hashconsing an AST via PPX" ( https://discuss.ocaml.org/t/hashconsing-an-ast-via-ppx/5558 ) where I showed how one could use a PPX rewriter to automate the task of "re-sharing" an AST when writing a top-down/bottom-up rewriter for an AST. (That is, you're walking an AST, making small modifications, but most of it stays the same; so in principle, at a node Add(Mul(e1,e2), e3) when rewriting e3 actually changes it visibly, but Mul(e1,e2) doesn't, we might want the output value's first subtree to be pointer-equal to the input's first subtree.) I called this "rehashcons"ing (admittedly not a great name). The idea being, rehashcons is not trying to hash-cons, but only to restore whatever sharing was there originally, to whatever extent that's possible.

But this is neither sufficient in all cases, nor real hash-consing. The problem with hash-consing is::

A. If you start with an AST type that doesn't have the various bits needed for hash-consing (at a minimum, a type 'a node = { it : 'a ; hashcode : int } and its use at each spot where we want to hash-cons) then you have to first produce a new AST type with those bits inserted. Let's call these the "normal" and "hashconsed" ASTs.

B. You have to write tons of boilerplate code: first, to map to-and-from these two type-families, and second to implement the hash-consing (special constructors, (ephemeral) hashtables here-and-there, etc). Then perhaps you'd like to memoize functions over these hash-consed ASTs, and that's more boilerplate.

C. And then, when it comes to writing expressions and patterns over this new AST type, you have to remember where the "special bits" go – where to insert the special constructors, and where to add {it=....} to patterns.

It's all a bit of a tedious bother, when what we want is to just manipulate the hashconsed data-type as if it were the "normal" type, and have the messy bits filled-in for us.

This post is about how to achieve that.

Let's first map out the plan of attack:

1. Start with an AST type (or types) for our language, and a parser (in this case, written using Camlp5's grammar machinery).
2. Add to the AST type some indications for where antiquotations may go, and modify the parser to parse these antiquotations. We'll call this the "normal" AST type. Note that this is the version with antiquotation markers.
3. pa_ppx_hashcons Generate a hashconsed version of the AST type from the "normal" AST type.
4. pa_ppx_migrate Generate functions back-and-forth between "normal" and "hashconsed" versions of the AST type. So we're hashconsing the version with antiquotation markers. We could hashcons the version without antiquotation markers, and everything here would still work out … but it would be more complicated to explain.
5. pa_ppx_q_ast From each of the "normal" and "hashconsed" AST types, generate functions that can take values of the type and generate OCaml code for patterns and expressions that correspond to those values.

6. pa_ppx.deriving_plugins.params In implementing the above, we're describing complex tasks, so it's possible that when not automatically inferrable from types, the "hints" we might need to give will be complex. It would be nice if there were a way to automatically generate code to parse such specifications. If we were writing some other application, we might want to use ppx_deriving.yojson (or our equivalent, pa_ppx.deriving_plugins.yojson) and write our specification in JSON. But since we're writing a PPX rewriter, the specification will come in the payload of a PPX attribute/extension. Since our "hints" might need to contain types and expressions, we'd probably like the payload to be real expressions and types. So what we need is a type-driven mapping from expression-ASTs, to expressions.

   Then, when implementing a PPX rewriter, we can write down the type of its "params", and from that generate the function that will convert expression-ASTs to that type.

The implementation of all of the above, is what I will describe in the rest of this note. I've applied it to

• (simple) s-expressions
• (simple) deBruijn lambda-terms
• (simple) named-variable lambda-terms
• (complex and comprehensive) the entire OCaml AST in Camlp5.

In this section, I'll work thru how to apply the ideas above, step-by-step, to s-expressions. Everything described here is working code, documented and tested in camlp5/pa_ppx_q_ast/tests/{sexp_example,eg_sexp_example}.

I've also applied this same methodology to the entire OCaml AST in Camlp5 (for which there is a parser, as part of Camlp5) and verified that the quotations thus generated pass the same tests as the hand-implemented quotations provided as part of Camlp5.

The quotations of Camlp5 are substantial, and cover almost all of the OCaml language. I believe that this means it is possible to both provide full hash-consing support for a very complex AST type, and full quotation support both for the AST type, and for its automatically-generated hashconsed variant.

I've shown three different PPX rewriters (migrate, hashcons, and q_ast) and in some of their invocations, there are nontrivial OCaml expressions to supply as options. Writing the code that converts these options (OCaml expressions) into values of meaningful types (for the rewriter code) is unutterably boring, time-consuming, and error-prone: it is effectively a demarshalling problem. So I wrote a PPX rewriter, that automates this task, and in fact that is what is used to generate the demarshallers used in these PPX rewriters. Here is an example: the params PPX rewriter as used by pa_ppx_migrate to generate its options demarshaller:

type tyarg_t =
  { srctype : ctyp;
    dsttype : ctyp;
    raw_dstmodule : longid option
      [@name dstmodule];
    dstmodule : longid option
      [@computed longid_of_dstmodule dsttype raw_dstmodule];
    inherit_code : expr option;
    code : expr option;
    custom_branches_code : expr option;
    custom_branches : (lident, case_branch) alist
      [@computed extract_case_branches custom_branches_code];
    custom_fields_code : (lident, expr) alist [@default []];
    skip_fields : lident list [@default []];
    subs : (ctyp * ctyp) list [@default []];
    type_vars : string list
      [@computed compute_type_vars srctype dsttype subs];
    subs_types : ctyp list
      [@computed compute_subs_types loc subs]
}
[@@deriving params]

type default_dispatcher_t =
  { srcmod : longid;
    dstmod : longid;
    types : lident list;
    inherit_code : (lident, expr) alist[@default []]
  }
[@@deriving params]

type t =
  { optional : bool
  ; plugin_name : string
  ; inherit_type : ctyp option;
    dispatch_type_name : lident[@name dispatch_type];
    dispatch_table_constructor : lident;
    declared_dispatchers : (lident, Dispatch1.tyarg_t) alist
      [@default []] [@name dispatchers];
    default_dispatchers : default_dispatcher_t list[@default []];
    dispatchers : (lident, Dispatch1.tyarg_t) alist
      [@computed compute_dispatchers loc type_decls declared_dispatchers default_dispatchers];
    type_decls : (string * MLast.type_decl) list
      [@computed type_decls];
    pretty_rewrites : (string * Prettify.t) list
      [@computed Prettify.mk_from_type_decls type_decls] }
[@@deriving params {formal_args = {t = [type_decls]}}]

This generates a function params : (string * MLast.type_decl) list -> MLast.expr -> t that performs the entire demarshalling task. At a couple of points, we supply functions to handle custom demarshalling operations, but the vast majority of the code (and work) is handled automatically. This is liberating: it means that there is no cost to being precise in describing the data one needs as input, and no need to "encode" arguments into easy-to-parse form. A good comparison is with the "@with" syntax of the ppx_import PPX rewriter, where it's clear that they're shoe-horning types into expression syntax, for want of a nicer syntax that is still easily to manipulate.

In the "Motivation" section, I introduced a type of sexp, and then the hashconsed version of the type. Neither type had vala markings in it. The mechanism described in this post can equally well work to produce quotation-expanders that work over types without vala. The only difficulty, is that the parser still needs to be defined over a version of the type with vala, because it will be used to parse quotations (which must necessarily contain antiquotations). But everything else works, and in camlp5/pa_ppx_q_ast/tests/{sexp_example,eg_sexp_example} you will find the definition and use of "sexpnovala", a quotation expander for the first sexp type we defined in this post. I didn't bother building the quotation expander for "hcsexpnovala", but it's a straightforward exercise.

In short, the choice of whether your AST type needs to have vala markings in it, is independent of hash-consing. You only need to supply a version of your AST type with vala, along with a parser, for the quotation machinery.

Consider that sexp type

type sexp =
    Atom of string
  | Cons of sexp * sexp
  | Nil

If we want to provide a ppx_metaquot-like facility for this type, perhaps we can overload the meaning of the strings in atoms. So the s-expression

( _A . foo )

that expands to

Cons(Atom "_A", Atom "foo")

could mean an s-expression with a single meta-variable, _A. But this meta-variable is necessarily a variable that can only denote an s-expression, and not a string. More generally, in an AST type if metavariables are merely overloaded variables, anyplace that a variable cannot appear, cannot be subject to meta-variable-based pattern-matching/substitution. So it's not possible to match on the list of types or expressions in a tuple type/expression, nor the list of branches in a match-with. And on and on. This is why the version of the sexp type with antiquotation markers

type sexp =
    Atom of (string vala)
  | Cons of (sexp vala) * (sexp vala)
  | Nil

includes Atom of (string vala). This allows us to write a pattern with a metavariable that matches an s-expression, e.g.

Cons (VaVal x, VaVal (Atom (VaVal "foo")))

(in quotation syntax, <:sexp< ( $exp:x$ . bar ) >>) or a metavariable that matches the string in an Atom, e.g.

Cons
  (VaVal (Atom (VaVal x)),
   VaVal (Atom (VaVal "foo")))

And this is a general issue in all (meta-)quotation support, not merely for the OCaml AST. If we want high-quality quotation support for our data-types, we need to build high-quality suppot for antiquotations.

WARNING: Some web browsers like Chrome will claim that the temporary site name is misleading and too close to forge.ocamlcore.org and it is a potential phishing attempt, but this should be safe.

Here are the actions you can take now:

• Project admins can get back the dump of project data (see the FAQ)
• Project admins can send PR to indicate the new project homepage (see the FAQ)
• Members can send PR to indicate their new homepage (see the the FAQ)

The whole process is still a bit undefined, because I need proof that the people sending PR were admins of the project. I still need to figure out a good way to get these proofs, so I will experiment a bit at the beginning (see the FAQ for the current state).

You can already check what the website will look like on https://forge-ocamlcore-org.netlify.app/

2020-10-11 -> 2020-10-18:

• Members can still browse the website and recover what will not be part of the project dump.

Any changes to the website made during this time, will be discarded.

2020-10-18:

• I will archive a whole copy of the website VM (encrypted)
• https://forge.ocamlcore.org will become a static website only containing “anonymous” data (see prototype)
• All file downloads will use https://downloads.ocamlcore.org (this is already the case)
• All mailing lists will be shut down
• Source control will not be accessible anymore (this is already the case)
• All domains *.forge.ocamlcore.org will point to the matching project page or to the FAQ.

2021-04-18:

• Last time for admins to get back the dump of project data (see the FAQ)
• Last time for members and admins to update their page on the static website
• I will destroy the copy of the website VM

Past this point, I will still have the dumps of the project data and will still accept PR for the Github repository, but this will be a “best effort” SLO.