Wrapping

This document describes a concept of wrapping values for unify().

Why

In classic logical languages, the most used data structure is a singly linked list. It is usually processed using some recursive algorithm and deconstructed as a head and a tail. It is a very efficient data structure because splitting it does not require creating new objects.

The most used data structures in JavaScript are an object (works as a dictionary with hashed keys) or an array. Selecting a subobject (e.g., a tail) involves creating a new object with complexity O(N), where N is the size of the subobject.

We cannot force a user to abandon efficient built-in objects using something like a singly linked list instead of arrays, or some more elaborate structure to represent dictionaries. In any case, we are not creating a new programming environment. The unification library should interface easily with existing code.

Equality

While primitive values are easy to compare, more high-level objects (e.g., containers) should be checked for their structure and included items should be compared as well.

Exact objects

Several unification modes were considered. The simplest one is "exact". This mode checks that objects are structurally the same and have the same items.

Example:

import unify from 'deep6/unify.js';

!!unify({a: 1}, {a: 1});       // true
!!unify({a: 1}, {a: 0});       // false
!!unify({a: 1}, {b: 1});       // false
!!unify({a: 1}, {a: 1, b: 1}); // false

!!unify([1], [1]);    // true
!!unify([1], [0]);    // false
!!unify([1], [1, 2]); // false

Open objects

In many cases, we want to check only certain properties. A use case: we got an object from a server, which includes some technical information and some properties, which are irrelevant in our context. For this use case, a new comparison mode was introduced: "open". In this mode, only common properties are compared. All other properties are effectively ignored and considered to be automatically unified.

Example:

import unify, {open} from 'deep6/unify.js';

!!unify({a: 1, b: 1}, {a: 1});       // false
!!unify({a: 1, b: 1}, open({a: 1})); // true
!!unify(open({a: 1}), {a: 1, b: 1}); // true

!!unify(open({a: 1, b: 2}), open({a: 1, c: 3})); // true
!!unify(open({a: 1, b: 2}), open({a: 3, c: 1})); // false

!!unify([1, 2], [1]);       // false
!!unify([1, 2], open([1])); // true

Soft objects

In some cases, we don't want to mess with properties we are not interested in, but we want to collect missing properties if our common properties are unified. It can be done with a new comparison mode: "soft". In this mode, all common properties are compared, and all other properties are added to a "soft" object:

import unify, {soft} from 'deep6/unify.js';

const x = {a: 1};

!!unify({a: 1, b: 1}, x);       // false
!!unify({a: 1, b: 1}, soft(x)); // true
!!unify({a: 1, b: 1}, x);       // true

const a = [1];

!!unify([1, 2], a);       // false
!!unify([1, 2], soft(a)); // true
!!unify([1, 2], a);       // true

How modes are compared

As you can see, while comparing in the "soft" mode, objects marked as soft can be modified. Other modes ("exact" and "open") do not modify their objects.

It doesn't make sense to mark primitives. Modes are used with regular objects, arrays, Set and Map objects.

Marking something as "open" or "soft" acts only at the top level and does not propagate down to children. Children should be marked explicitly.

Example:

!!unify([{a: 1, b: 2}, {c: 3}], [{a: 1}]);             // false
!!unify([{a: 1, b: 2}, {c: 3}], open([{a: 1}]));       // false
!!unify([{a: 1, b: 2}, {c: 3}], open([open({a: 1})])); // true

In order to automate marking an object recursively, there is a utility for that: preprocess().

Design decisions

Internally unify() uses an object of class Wrap to indicate that an object needs a special treatment. Unwrapped objects are treated as exact.

Wrap is not exposed directly. It is based on Unifier and has the following properties:

• type — a string, which can be either "open" or "soft".
• object — an arbitrary object, which is now wrapped.

Such objects can be created by factory functions exposed by unify module:

• open(x) — creates a wrapper for an object x with type equals "open".
• soft(x) — creates a wrapper for an object x with type equals "soft".

The same module exposes test functions: isWrapper(), isOpen(), isSoft().

Custom unifiers

The mechanism described above is not extensible. If you want to change how to unify your own objects, consider writing a custom unifier. See unify.registry and unify.filters for more details.