# 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](https://mikaelmayer.github.io/bam/sandbox.html) 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 `up`s 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.