package yuujinchou

  1. Overview
  2. Docs

Yuujinchou is an OCaml package of name patterns. It was motivated by the "import" or "include" statements present in almost all programming languages. Here are a few examples:

open import M -- Agda
import foo # Python

The ability to import content from other files helps organize code. However, it also poses a new challenge: how could programmers prevent imported content from shadowing existing content? For example, if we already have a function test in the current scope, maybe we do not wish to import another function also named test. To address this, many programming languages allow programmers to selectively hide or rename part of the imported content:

open import M renaming (a to b) public
-- (Agda) renaming a to b, and then re-exporting the content

Another way to address this is to place the imported content under some namespace. For example, in Python,

import math # Python: the sqrt function is available as  `math.sqrt`.

The goal of the Yuujinchou library is to provide a calculus of these modifications. If we view the collection of hierarchical names as a trie, then these name modifiers are trie transformers, and they should be composable. Currently, it supports renaming, scopes, sequencing, unions, and custom hooks for more advanced patterns.

Notes on Namespaces

This package intends to treat a namespace as the prefix of a group of names; there is no namespace a, but a group of unrelated names that happen to have the prefix a. This is different from many other designs which attempt to group a collection of bindings as a module. It is possible that such a design is unnecessarily limited unless one wishes to implement parametric signature polymorphism (without row polymorphism).

Modules in this Package

The code is split into three parts:

module Trie : module type of Trie

The Trie module implements a data structure that maps paths to values and supports efficient subtree operations.

module Pattern : sig ... end

The Pattern module defines the patterns.

module Action : sig ... end

The Action module implements the engine running the patterns.

Example Code

open Yuujinchou

module Data =
struct
  type t = int
  let equal n1 n2 = n1 = n2
  let merge ~rev_path x y =
    if equal x y then x
    else failwith @@
      "Inconsistent data assigned to the same path " ^ String.concat "." @@ List.rev rev_path
  let shadow ~rev_path:_ _x y = y
  let compare : t -> t -> int = compare
end

(** An environment is a mapping from paths to data. *)
type env = Data.t Trie.t

(** [remap pattern env] uses the [pattern] to massage
    the environment [env]. *)
let remap pattern env =
  let pp_path = function [] -> "(root)" | path -> String.concat "." path in
  match Action.run ~union:Data.merge pattern env with
  | Ok env -> env
  | Error (`BindingNotFound path) ->
    failwith ("Expected binding(s) not found within the subtree at " ^ pp_path path ^ ".")

(** [import env pattern imported] imports the environment
    [imported] massaged by [pattern] into [env]. *)
let import env pattern imported =
  Trie.union Data.shadow env @@ remap pattern imported

module DataSet = Set.Make (Data)

(** [select env pattern] returns the set of matched data. *)
let select env pattern =
  DataSet.of_seq @@ Trie.to_seq_values @@ remap pattern env

Examples from Other Languages

This section shows how import mechanisms can be implemented using this package.

Haskell

  • Haskell syntax:

    import Mod -- x is available an both x and Mod.x

    Corresponding Yuujinchou pattern:

    Pattern.(union [any; renaming [] ["Mod"]])
  • Haskell syntax:

    import Mod (x,y)

    Corresponding Yuujinchou pattern:

    Pattern.(union [only ["x"]; only ["y"]])
  • Haskell syntax:

    import qualified Mod

    Corresponding Yuujinchou pattern:

    Pattern.renaming [] ["Mod"]
  • Haskell syntax:

    import qualified Mod hiding (x,y)

    Corresponding Yuujinchou pattern:

    Pattern.(seq [except ["x"]; except ["y"]; renaming [] ["Mod"]])

Racket

  • Racket syntax:

    (require (only-in ... id0 [old-id1 new-id1]))

    Corresponding Yuujinchou pattern:

    Pattern.(seq [...; union [only ["id0"]; seq [only ["old-id1"]; renaming ["old-id1"] ["new-id1"]]]])
  • Racket syntax:

    (require (except-in ... id0 id1]))

    Corresponding Yuujinchou pattern:

    Pattern.(seq [...; except ["id0"]; except ["id1"]])
  • Racket syntax:

    (require (prefix-in p: ...))

    Corresponding Yuujinchou pattern:

    Pattern.(seq [...; renaming [] ["p"]])
  • Racket syntax:

    (require (rename-in ... [old-id0 new-id0] [old-id1 new-id1]))

    Corresponding Yuujinchou pattern:

    Pattern.(seq [...; renaming ["old-id0"] ["new-id0"]; renaming ["old-id1"] ["new-id1"]])
  • Racket syntax:

    (require (combine-in require-spec0 require-spec1 ...))

    Corresponding Yuujinchou pattern:

    Pattern.(union [require-spec0; require-spec1; ...])

What is "Yuujinchou"?

"Yuujinchou" is the transliteration of "友人帳" in Japanese, which literally means "book of friends". It is a powerful notebook in the manga Natsume Yuujinchou (夏目友人帳) that collects many real names (真名) of youkais (妖怪) (supernatural and spiritual monsters). These real names can be used to summon and control youkais, but the protagonist decided to return the names to their original owners. The plot is about meeting all kinds of youkais.

This magical book will automatically turn to the page with the correct name when the protagonist pictures the youkai in his mind. This package is also about finding real names of youkais.

Notes on the transliteration: "Yuujinchou" is in the Wāpuro style so that it uses only the English alphabet; otherwise, its Hepburn romanization would be "Yūjin-chō".

OCaml

Innovation. Community. Security.