package yuujinchou

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Introduction
1. Namespaces and Modules
Using the Library
What is "Yuujinchou"?

package yuujinchou

yuujinchou
- Yuujinchou
  - Action
  - Pattern
  - Trie
    
    Result

Legend:
Library
Module
Module type
Parameter
Class
Class type

Yuujinchou is an OCaml package of name patterns.

Introduction

This library was motivated by the name modifiers in the "import" or "include" statements present in all practical programming languages. Here are a few examples of such statements:

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`.

Arguably, common designs of these hiding or renaming mechanisms are quite limited. The goal of the Yuujinchou library is to provide a compositional calculus of these modifiers of names, which we call name patterns. Currently, the library supports renaming, scopes, sequencing, unions, and custom hooks for extending the pattern engine.

Namespaces and Modules

This package intends to treat a namespace as the shared prefix of a group of names; there is no standalone namespace a, but a group of unrelated declarations that happen to have names sharing the prefix a. This design is different from many others that attempt to group a collection of bindings as a standalone module.

There are fundamental differences between modules (records) and namespaces. A module (or a record) is typed, in the sense that there will be a single type assigned to it. The typedness enables considering an abstract module of a module type. Signatures and functors in Standard ML and OCaml follow this approach. On the other hand, a namespace is untyped, which forbids the notion of abstract namespaces but enables flexible operations such as direct injection of a definition into a namespace. It seems impossible to have a unified design that is typed and supports flexible manipulations. Thus, we (the authors) believe that equating these two will necessarily limit operators on namespaces, which is the case in Standard ML and OCaml. (The modules in Haskell and Agda are namespaces in the above discussion.) Another approach is to have separate notions of namespaces and modules/records, as in C++ and our proof assistant cooltt.

Using the Library

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
      Result.ok x
    else
      Result.error @@ `Inconsistent (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 (`Inconsistent path) ->
    failwith ("Inconsistent data assigned to the same path " ^ pp_path path)
  | 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

Library Organization

The library code is split into three parts:

module Trie : module type of Trie

The Trie module implements mappings from paths to values that support 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.

Implementing Features

This section shows how mechanisms in other languages can be implemented using this package. We use Haskell and Racket as examples.