bam.js

bam.js is a JavaScript implementation of an Edit Action language. It's a way to summarize how to transform data in another format, which makes it suitable for reversing changes. It makes it easy to create and maintain reversible interpreters written in JavaScript. It features:

• An edit action language
  • Easy-to-use constructs for deterministic and non-deterministic (i.e. with variants) rewriting of records and primitives.
  • Operations to compose, merge and reverse these edit actions
• Documentation
  • How to transform an interpeter into a "Abstract Machine"
  • How to transform an "Asbstract Machine" to a "Bidirectional Abstract Machine"
  • Examples

Sandbox online

The sandbox is a nice place to experiment with BAM. Click on the buttons to apply edit actions to objects, and to back-propagate edit actions from edit actions.

To illustrate the example explained in details below:

• Put {a: 1} in the top left box
• Put New({b: Reuse("a"), c: Reuse("a")}) in the top middle box
• Press the button bam.apply(evaluation step, program).
• Now in the bottom right box, replace the program with {b: 2, c: {d: 1}} The middle right box is filled automatically
• Press the button user step' = backPropagate(evaluation step, user step) The middle left and middle bottom boxes are filled automatically.

Quick node.js install

Remove the -g parameter to install it for a single node project:

npm install -g bam.js

Learn BAM from Examples

BAM handles trees whatever they might represent. BAM does not care about the fields names, just that every object is a tree whose children are labelled by field names.

Here are the most basic two examples. The New() operator creates something from scratch, and the Reuse() operator reuses the previous tree:

apply(New("x"), {a: {}, b: "cd"}) == "x"

apply(Reuse(),  {a: {}, b: "cd"}) == {a: {}, b: "cd"}

We can nest these operations to get more advanced transformations: Reuse can take an argument which is an object whose fields indicate which fields should be changed and how:

apply(New({x: New("y")}), {a: {}, b: "cd"}) == { x: "y" }

apply(New({x: Reuse()}),  {a: {}, b: "cd"}) == { x: {a: {}, b: "cd"} }

apply(Reuse({a: New(x)}), {a: {}, b: "cd"}) == {a: "x", b: "cd"}

We can also reuse elements down the tree by providing string arguments to Reuse:

apply({Reuse("a"), {a: {b: 2}})      == {b: 2}

apply({Reuse("a", "b"), {a: {b: 2}}) == 2

apply({Reuse("stack", "hd"), {stack: {hd: {ctor: "hello"}}}) == {ctor: "hello"}

We can also reuse elements up the tree by providing the keyword up to Reuse:

apply({Reuse({a: Reuse(up, "b")}), {a: {}, b: "cd"}) = {a: "cd", b: "cd"}

apply({Reuse({stack: Reuse(up, "state", "hd")}), {stack: 1, state: { hd: 2} }) = {stack: 2, state: { hd: 2 } }

Language API

Deterministic Edit Actions

The standard way to express how to transform a record into another is to create a "Deterministic Edit actions". A deterministic edit action is either:

• Create a new object, whose fields are also edit actions (New)
• Reuse an object existing at a relative path from the location, modifying a subset of its fields by other edit actions (Reuse)
• Create a new object with a way to explicitely reuse some field ranges (ReuseArray) which is especially useful for arrays or strings whose field names are numbers.

Deterministic Edit Actions are well suited to represent what an evaluator step did on the input.

In this section, all functions are accessible under bam.*, for example New means bam.New.

New

For primitives, New() takes one arguments:

apply(New(1), 42) == 1
apply(New(true), 42) == true
apply(New("abc"), 42) == "abc"

For records, New() takes a record whose values are edit actions:

apply(New({a: New(1)}), 42) == {a: 1}
apply(New({b: New(1), c: New(3)}), 42) == {b: 1, c: 3}

New() can also take an extra argument which is the skeleton it should build the value from.

apply(New({a: New(1)}, {b: 3}), 42) == {a: 1, b: 3}
apply(New({}, {a: 1, b: 3}), 42) == {a: 1, b: 3}
apply(New({}, {b: 1, c: 3}), 42) == {b: 1, c: 3}

This is especially useful in the case of arrays or JavaScript Maps. By passing an array or a Map as the second argument, the record of edit actions will be interpreted as actions to perform on the provided array or Map:

apply(New({0: New(1)}, []), 42) == [1]
apply(New({1: New(3)}, [1]), 42) == [1, 3]

apply(New({1: New(3)}, new Map()), 42) == new Map([[1, 3]])
apply(New({2: New(5)}, new Map([[2, 4], [1, 3]])), 42) == new Map([[2, 5], [1, 3]])

The reason to provide a non-empty Map as a skeleton is that it keeps the key ordering. Now that we know how to create new values from scratch using edit actions, we'll see in the next section how we can reuse values.

Reuse

To reuse a value, we build Reuse() with one argument, which is a record of edit actions that should apply on the modified fields.

apply( Reuse({c: New(4)}), {a: 1, b: 2, c: 42} ) == {a: 1, b: 2, c: 4}
apply( Reuse({1: New(54)}), [40,30,90] ) == [40,54,90]
apply( Reuse({key: New(true)}), new Map([["key", false]])) == new Map([["key", true]])

Reuse() should not be used to create new keys, only modify existing ones. To add numeric keys while keeping previous keys the same, it can be useful to look at the ReuseArray below.

Reuse()'s first arguments can also be a path, which consists of a comma-separated list of either the special string ".." also named "up" (up the tree), or other strings or numbers (down the tree), or arrays of these. In this case Reuse() will fetch the tree pointed to by the path before applying its edit actions:

apply( Reuse("b"), {a: 1, b: 2, c: 42} )                   == 2
apply( Reuse(["b", "c"], "d"), {a: 1, b: {c: {d: 42}}} )   == 42
apply( Reuse({c: Reuse("..", "b")}), {a: 1, b: 2, c: 42} ) == {a: 1, b: 2, c: 2}
apply( Reuse({c: Reuse(up, "b")}), {a: 1, b: 5, c: 42} )   == {a: 1, b: 5, c: 5}

One can call Reuse() with both path elements and the edit actionr record argument to obtain clone-and-modify behaviors:

apply( Reuse({c: Reuse(up, "b", { x: New(2) })}), {b: {x: 1, y: 3}, c: 42} ) == {b: {x: 1, y: 3}, c: {x: 2, y: 3}}

path for Reuse

Instead of providing the list of path elements, it's also possible to provide a single path value. A path is a special record of type:

{up: number, down: List String}

For example, the path "..", "b" can be represented as

{up: 1, down: List.fromArray(["b"])}

The path function enables to build such paths by combining paths and path elements. Arrays are exploded to single paths or path elements. The path above could be computed in all the following ways:

path("..", "b")
path("..", ["b"])
path(["..", "b"])
path(path(".."), path("b"))
...

ReuseArray

In the case of records with consecutive numeric keys (arrays, string or even user-defined records like an "heap" in an interpreter), the ReuseArray edit action splits the original array into two, apply its two edit actions respectively to apply each part, and recombine the result.

ReuseArray(count, editAction1, editAction2)

For example, if for two edit actions E1 and E2 we have:

apply(E1, [1, 2, 3]) = [6]
apply(E2, [4, 5]) = [5, 4]

then

apply(ReuseArray(3, E1, E2), [1, 2, 3, 4, 5]) = [6, 5, 4]

Cloning path

It is possible to clone another array instead of modifying the current one. For that, just include a path right after ReuseArray(, or some path elements like up, numbers, paths, strings, or array of these, just as for Reuse. The last number is considered to be the split count and is not part of the path.

apply(Reuse({a: ReuseArray(up, "b",  3, New([]), Reuse())}), {a: 1, b: [1, 2, 3, 4, 5]})
= {a: [4, 5], b: [1, 2, 3, 4, 5]}

Syntax shortcut

As a shorthand, we enable

ReuseArray([path, ] count1, e1, count2, e2, count3, e3, e4)

to represent

ReuseArray([path, ] count1, e1, ReuseArray(count2, e2, ReuseArray(count3, e3, e4)))

Cloning up

Only the first nested ReuseArray increases the context stack length by adding the top-level array. All consecutively nested ReuseArray only modify further the portion of the array being considered. Therefore, whatever number of ReuseArray, only one "up" is necessary in a clone path to access the entire array from any sub-array. In the following example, only two ups are required to access the entire array from the element "d", despite the intermediate windows ["c", "d", "e", "f"] obtained after splitting the first array at index 2 and taking the second half, and ["c", "d", "e"] after splitting the second array at index 3 and taking the first half.

apply(ReuseArray(2, Reuse(), ReuseArray(3, Reuse({1: Reuse(up, up, 5)}), Reuse())),
  ["a", "b", "c", "d", "e", "f"])
= ["a", "b", "c", "f", "e", "f"] 

Full example

Here is an illustrative example, featuring deleting, keeping, cloning, inserting, and moving:

var prog = ["To move elsewhere", "Keep", "Keep with next", "Keep and to clone"};

var step = ReuseArray(
    1, New([]),                            // Deletes 0
    1, Reuse(),                            // Keeps 1
    0, New({0: Reuse(up, 2)},[]),              // Clones the field 3 before 2
    2, Reuse(), // Keeps 2 and 3
    0, New({0: Reuse(up, 0)}, []),         // Move the field "0" there
    0, New({0: New("Inserted at end")}, []) // Inserts a new value
  );

var res = apply(step, prog);
console.log(res);
// Displays
// {0: "Keep", 1: "Keep and to clone", 2: "Keep with next", 3: "Keep and to clone", 4: "To move elsewhere", 5: "Inserted at end"}

Note that ReuseArray(n, edit action, m, edit action, X) is a shortcut for ReuseArray(n, edit action, ReuseArray(m, edit action 2, X)).

The meaning of ReuseArray(n, edit action, X) is to consider the first n elements of the provided array extract, apply the given edit action to the sub-array and concatenate the result with the result of applying X to the remaining view of the array. Similar to Reuse, ReuseArray's argument list can be prefixed with as many path elements as needed, but these path elements should not be numbers as the first number indicates how many items to extract.

Caching output length If you happen to use ReuseArray or Reuse with a path inside a ReuseArray edit action named e1, you will have to wrap the edit action like bam.setOutLength(e1, count), where count is the length of the edit action. The reason is, merging algorithms require this length to determine whether or not edit actions are "aligned".

Special case: Strings

Strings can be treated either as primitives (for a full replacement regardless of how the string was edited), or using the ReuseArray described before.
For example, to transform:

"Hello world! ?"

to

"Hello big world, nice world! ??"

one can use the following edit action

ReuseArray(
  5, Reuse(),                       // "Hello"
  6,                                // " world"
    ReuseArray(
      0, New(" big world, nice"),   // insertion
      6, Reuse()                    // " world"
    ),
  2, Reuse(), // The string "! "
  0, New("?"), // The inserted string "?"
  1, Reuse()
)

Custom lenses

bam.js supports a custom kind of user-defined lens. Here is an example on how to define a reversible addition that backs-propagates the diff either to the left or to the right:

> var plusEditAction =
    Custom(bam.Reuse("args"),
         ({left, right}) => left + right,
         function(outputDiff, {left, right}, outputOld) {
           if(outputDiff.ctor === bam.Type.New) {
             let diff = outputDiff.model - outputOld;
             return nd.Reuse({left: nd.New(left + diff)}).concat(nd.Reuse({right: nd.New(right + diff)}));
           } else {
             console.log(stringOf(outputDiff));
             throw "Unsupported output edit action for the + operator"
           }
         });

> bam.apply(plusEditAction, {type: "Add", args: {left: 1, right: 3}});
4

> nd.backPropagate(plusEditAction, nd.New(5));
[Reuse({args: [Reuse({left: [New(2)]})]}),
 Reuse({args: [Reuse({right: [New(4)]})]})]

Language API: Non-deterministic variants

nd.New, nd.Reuse and nd.ReuseArray are the non-deterministic variants of the constructs mentioned above. Non-determinism means that wherever edit actions were needed in argument, arrays of edit actions should be used, and these nd.* constructs all return an array of edit action. The original edit actions are useful to describe unambiguous interpreter steps, whereas the non-deterministic variant is useful to describe the ambiguous user-defined transformations.

Example:

`nd.New(42)`
`nd.Reuse(1)`

Non-deterministic edit actions can be combined using the nd.or operator -- or the JavaScript's native concat operator:

`nd.or(nd.New(42), nd.Reuse(1))`
`nd.New(42).concat(nd.Reuse(1))`

For example, a more complete non-deterministic edit action associated to the transformation of the string:

"Hello world! 1"

to

"Hello big world, nice world! ??"

one can use the following edit action:

nd.ReuseArray(
  5, Reuse(),
  6, nd.or(                         // " world"
    nd.ReuseArray(
      0, New(" big world, nice"),   // insertion
      6, Reuse()                    // " world"
    ),
    nd.ReuseArray(
      1, Reuse(),                   // " "
      0, New("big world, nice "),   // insertion
      5, Reuse()                    // "world"
    ),
    nd.ReuseArray(
      1, Reuse(),
      0, New("big "),
      
    )
    )
  2, nd.Reuse(), // The string "! "
  1, nd.or(
    nd.ReuseArray(
      0, New("?"),
      1, Reuse()
    ),
    nd.ReuseArray(
      0, Reuse(),
      1, New("?")
    ))
)

There are several ways to apply a non-deterministic edit action to a program, depending on the expected result.

1. To obtain the first result, just use nd.apply

   `nd.apply(nd.or(nd.New(42), nd.Reuse(1)), [41, 43]) == 42`

2. To obtain the last result, use nd.apply and provide true as an extra argument:

   `nd.apply(nd.or(nd.New(42), nd.Reuse(1)), [41, 43], true) == 43`

3. To list all results, use nd.applyAll:

   `nd.applyAll(nd.or(nd.New(42), nd.Reuse("b")), {a: 41, b: 43}) == [42, 43]

4. To list all results as a record where all fields are arrays of possibilities, use nd.applyVSA (VSA stands for Version Space Algebra):

   ```
   nd.applyVSA(nd.or(nd.New({b: nd.or(nd.Reuse("a"), nd.New(43))}),
                     nd.New({c: nd.Reuse("a")})), {a: 42}) == [{b: [42, 43]}, {c: [42]}]```

Note that the last will fail in the case of a non-deterministic nd.ReuseArray applied to a string. Use one of the other three versions instead.

Compute edit actions automatically

bam.js has some support to compute deterministic and non-deterministic edit actions from two values. Here is how it works:

> bam.diff(1, 2)
New(2)
> bam.diff(1, 1)
Reuse()
> bam.diff(1, [1, 2])
New({ 0: Reuse(), 1: 2}, [])
> bam.diff([1, 2], 1)
Reuse(0)

It is also possible to ask for all edit actions it can find:

> bam.nd.diff(1, 2)
[New(2)]
> bam.nd.diff(1, 1)
[Reuse()]
> bam.nd.diff([2, 1], [1, 2])
[Reuse({0: [Reuse(up, 1),
            New(1)],
        1: [Reuse(up, 0),
            New(2)]}),
 ReuseArray(0, [New({ 0: [Reuse(up, 1),
                          New(1)]}, [])],
               [ReuseArray(1, [Reuse()],
                              [New([])])]),
 ReuseArray(1, [New([])],
               [ReuseArray(1, [Reuse()],
                              [New({ 0: [Reuse(up, 0),
                                         New(2)]}, [])])]),
 New({ 0: [Reuse(1)],
       1: [Reuse(0)]}, [])]

It's possible to add options as the third parameter.
The option onlyReuse (default: false) prunes out all New solutions if there are solutions that use Reuse:

> bam.nd.diff([2, 1], [1, 2], {onlyReuse: true})
[Reuse({0: [Reuse(up, 1)],
        1: [Reuse(up, 0)]}),
 ReuseArray(0, [New({ 0: [Reuse(up, 1)]}, [])],
               [ReuseArray(1, [Reuse()],
                              [New([])])]),
 ReuseArray(1, [New([])],
               [ReuseArray(1, [Reuse()],
                              [New({ 0: [Reuse(up, 0)]}, [])])])]

The option maxCloneUp (default: 2) specifies the number of maximum depth traversal when going up, when looking for clones.

> diff([1, [[2]]], [1, [[1]]], {maxCloneUp: 2})
Reuse({1: Reuse({0: Reuse({0: New(1)})})})
> diff([1, [[2]]], [1, [[1]]], {maxCloneUp: 3})
Reuse({1: Reuse({0: Reuse({0: Reuse(up, up, up, 0)})})})

The option maxCloneDown (default: 2) specifies the number of maximum depth traversal when going down (even after going up), when looking for clones.

> diff([1], 1, {maxCloneDown: 1})
Reuse("0")
> diff([1], 1, {maxCloneDown: 0})
New(1)

Aligning elements when diffing.

When diffing arrays of elements, the options

{isCompatibleForReuseObject: (oldValue, newValue) => Boolean,
 isCompatibleForReuseArray: (oldValue, newValue) => Boolean,
}

respectively indicates to diff if it can try an alignment using Reuse (if it shares the same keys) and ReuseArray for arrays. By default, this option is enabled for all arrays. A useful use case is to make a function isCompatibleForReuseArray return false if one of the value is not really an array but a tuple, e.g. ["tag", [...attributes], [...children]]]. That way, it prevents a lot of comparisons.

Another useful option is:

{findNextSimilar: (array: Array[A], element: A, fromIndex: Int) => (newIndex: Int | -1)}

It takes an array, an index from which it searches the element A, and return the first index at which it finds it. By default, the element must be exactly the same for an alignment to occur; but it might be useful to specify a function to find a partial match, especially if the match changed as well.

Debugging edit actions

Tip: Use bam.stringOf(...) to convert an edit action to its string representation, or use bam.debug(...) to directly pretty-print an edit action to the standard output.

Operations on edit actions

Combination

andThen(b, a)

is defined so that

apply(b, apply(a, x)) == apply(andThen(b, a), x)

Note that andThen simplifies at the maximum the resulting edit action. If you do not want to simplify, use the equivalent:

Sequence(a, b)

Test commutativity

commute(a, b)

returns true if we can guarantee that, for all x,

apply(b, apply(a, x)) == apply(a, apply(b, x))

Advanced: Language example

In this example, let us have a dummy program {a: 1} that an interpreted transforms into {b: 1, c: 1} in one step. We are interested in how to propagates changes from the output back to the program.

1. First, we rewrite the interpreter so that it does not output the result anymore, it outputs a term in our Edit Action language (evalStep) that transforms the program to the result. This step is explained later in this README.
2. For example, evalStep = New({b: Reuse("a"), c: Reuse("a")});, meaning the 1 was cloned from field a.
3. A user modifies the output so that it becomes {b: 2, c: {d: 1}}.
4. Suppose that userStep = nd.Reuse({b: nd.New(2), c: New({d: nd.or(nd.Reuse(), nd.Reuse("..", "b"))})}); is the edit action associated to this transformation. It encodes two possibilities: Either the 1 came from wrapping the field "c" (more likely) or was simply cloned from the field "b". "nd" stands for "non-deterministic", i.e. we can offer multiple variants. Using "nd" only makes sense for user steps.

We are interested to replicate the user step but on the program level. This library enables it in the following way:

var program1 = {a: 1};
var {Reuse, New, apply, backpropagate, nd, up} = bam;
var evalStep = New({b: Reuse("a"), c: Reuse("a")});
var output1 = apply(evalStep, program1);

console.log(output1);       // Displays: {b: 1, c: 1}

var userStep = nd.Reuse({b: nd.New(2), c: nd.New({d: nd.or(nd.Reuse(), nd.Reuse("..", "b"))})});
var output2 = nd.apply(userStep, output1); // Applies the first variant.

console.log(output2);       // Displays: {b: 2, c: {d: 1}}

var userStepOnProgram = backpropagate(evalStep, userStep);

console.log(userStepOnProgram);
                            // Displays: nd.Reuse({a: nd.New({d: nd.New(2)})})

var program2 = nd.apply(userStepOnProgram, program1);

console.log(program2);      // Displays: Reuse({a: {d: 2}})

var output3 = apply(evalStep, program2); // You'd run the evaluator instead, in case some conditions changes...

console.log(output3);       // Displays: {b: {d: 2}, c: {d: 2}}

This concludes a basic illustration of this API.