Algorithm Representation

Algorithms.md

In the example below, a "group" is a sequence of moves surrounded in parentheses.

Design goal

A representation of algorithms in JSON that also maps to native data structures and classes in most programming languages.

Desirable properties:

1. Easy to represent in a programming language with lists and "classes" (objects with pre-defined patterns of properties).
2. The data structures are straightforward to flatten to/from JSON.
3. A single "Algorithm" type (rather than Algorithm and AlgPart).
4. Being able to call and chain methods on an algorithm instance, e.g. a.invert().toString()
5. Compatible with immutable data types (prevents errors, and encourages performant data structures)

Algorithms are represented as plain lists of AlgParts

type Algorithm = AlgPart[]

interface AlgPart {...}
Group implements AlgPart {
  nestedAlgs: Algorithm
}
Commutator implements AlgPart: {
  A: Algorithm
  B: Algorithm
}

Pros:

• Very straightforward JSON.

Cons:

• (4) requires modifying or extending the builtin list type.
• Weak type systems might allow an arbitrary list (especially a list of Algorithms) to be mistaken for an Algorithm.
• Allows calling map() (think functional programming) directly on an alg instead of forcing all computations to go through the alg interface (can prevent mistakes in case an operation at the top level of an alg can change the top-level structure).

One option with this approach is to give up hope of calling methods directly on objects that represent algs, and instead construct all functions that operate on algorithms to use multiple dispatch/overloading (which is not natively/efficiently supported in all languages, particulary Javascript).

Algorithm wraps a list

class Algorithm {
  nestedAlgs: AlgPart[]
}

abstract class AlgPart {...}
Group implements AlgPart {
  nestedAlg: Algorithm
}
Commutator implements AlgPart {
  A: Algorithm
  B: Algorithm
}

Pros:

• Easy to understand and implement.
• Alternating nested types prevent unflattened "list of lists".

Cons:

• (2) JSON either contains "unnecessary" wrappers for nested algs, or requires flattening the Algorithm type into a list as a special case.
  • Flattening would still allows an arbitrary list (especially a list of Algorithms) to be mistaken as a single alg when dealing directly with the JSON.
• (3) Not a single Algorithm type.

Only one algorithm type can contain an arbitrary list of moves

interface Algorithm {}

Sequence implements Algorithm {
  nestedAlgs: Algorithm[]
}
Group implements Algorithm {
  nestedAlg: Algorithm
}
Commutator implements AlgPart {
  A: Algorithm
  B: Algorithm
}

Cons:

• Group looks like it maybe wants to be a Sequence.
• It's possible to construct a sequence containing sequences instead of enforcing a flat structure for the Sequence type.

Multiple algorithm types can contain an arbitrary list of moves

interface Algorithm {}

Sequence implements Algorithm {
  nestedAlgs: Algorithm[]
}
Group implements Algorithm (maybe extends Sequence?) {
  nestedAlgs: Algorithm[]
}
Commutator implements AlgPart {
  A: Algorithm
  B: Algorithm
}

Alternatively, Group and Sequence could be the same type of Algorithm with a special property (e.g. boolean) indicating semantics.

Cons:

• Two kinds of "sequence".
• Implementations of calculations on algs need to make sure that Sequence and Group both handle their lists correctly.