Whide Tree Conversion Language

This repository holds the tree conversion language used by the Whide IDE. The purpose of this language is to validate the formats of WHILE binary trees, and to convert them to a more human-friendly representation.

This language was loosely inspired by TypeScript’s type declaration syntax; namely by its union operator (|), its any type, and its support of literal types.

Note	The term "type" is used in this document to refer to any valid atom or structure in the expression language.

Language description

Formally, the language’s syntax can be expressed as the following context-free grammar:

ROOT    = <ROOT.ROOT>       //Binary tree
        | ROOT[]            //List of type ROOT
        | [FIX_INT]         //List of a fixed structure
        | (ROOT)            //Parentheses
        | ROOT\|ROOT        //Accept any of these types
        | ATOM              //Accept atomic values
        | NAT               //Accept all the natural numbers

//Fixed structure list
FIX_LST = []                //Empty list
        | [FIX_INT]         //Populated list

FIX_INT = ROOT,FIX_INT      //Comma separated list of types
        | ROOT              //Final list element
        | ...               //Ignore any further elements

//Built-in atomic types
ATOM    = any               //Accept any type
        | bool              //Accept either 'true' or 'false'
        | boolean           //Same as 'bool'
        | false             //Accept the value 'false' ('nil')
        | int               //Integer
        | nil               //The value `nil` exactly
        | true              //Accept the value 'true' ('<nil.nil>')

//The natural numbers
NAT     = 0|1|2|...

Informal Description

Atoms

The language contains several built-in atomic types. See Data Structures for a description of the tree forms of these types.

• nil matches the nil value

• any matches any valid tree, and returns it unchanged

• false matches the value 'false' (represented as nil)

• true matches the value 'true' (represented as <nil.nil>)

• bool/boolean matches either true or false.

• int matches any valid number, and converts it to its numerical representation. E.g:

  • nil becomes 0

  • <nil.nil> becomes 1

  • <nil.<nil.nil>> becomes 2

• Number literals (0, 1, 2, …​) match exactly that number

Alternative types

Alternative types can be easily specified using the | operator; the string A|B first attempts to use type A, then type B.

For example int|any first attempts to convert the tree to an integer, but returns the tree unchanged if it is invalid.

Binary trees

Binary trees are represented in the form <L.R> where L is the type of the left-hand node, and R is the type of the right-hand node.

For example, <int.nil> matches any tree with an integer as the left child.

Lists

There are two supported types of list in the language; generic and fixed lists.

Generic lists (A[] or (A|B)[]) represent arbitrary length lists of a fixed type.

For example: * A[] represents a list where each element is of type A * (A|B)[] represents a list where each element is of type A or type B

Note	[] binds more tightly than | so A|B[] would be equivalent to A|(B[]).

Fixed structure lists match against lists which have a fixed length and each element has a known type:

• [] represents the empty list.

• [A] represents a list with exactly one element of type A.

• [A,B,C] represents a list with exactly 3 elements of type A, B, and C respectively.

• [A,B,…​] represents a list with 2 or more elements, the first two of types A and B respectively, and any further elements of any type.

Note	Any type can be turned into a generic list by adding [] to the end; int[][] would match a list of lists of integers, and <int.int>[] would match a list of trees of integers.

Error handling

If the provided tree does not match the conversion string, the converter returns the original tree in place of the mismatched token, with an error message describing the issue.

For example, the tree <<nil.nil>.nil> with conversion string int would return the tree <<nil.nil>.nil> with the error "not a valid number". Similarly, conversion string <any.nil> acting on tree nil would return nil with the error message "expected a tree".

If the error is non-recoverable (e.g. a syntax error) the converter throws an exception.

Examples

Conversion String	Input tree
int	nil → 0 <nil.nil> → 1 <nil.<nil.nil>> → 2
any	nil → nil <nil.nil> → <nil.nil> <<nil.nil>.<nil.nil>> → <<nil.nil>.<nil.nil>>
<int.any>	nil → Invalid <nil.nil> → <0.nil> <<nil.nil>.<nil.nil>> → <1.<nil.nil>>
int[]	nil → [] <nil.nil> → [0] <<nil.nil>.<nil.nil>> → [1,0]
int[][]	nil → [] <nil.nil> → [] <<nil.nil>.<nil.nil>> → [[0],[]]
bool	nil → false <nil.nil> → true

Stringify

In addition to the conversion language, this module also provides a stringify method. This accepts a converted binary tree (the resulting type of the conversion) and converts it to a string representation. The format used by this method is similar to that used in this documentation:

• nil nodes are shown as nil

• Trees are shown as <A.B.C…​> where A, B, and C are the stringified representations of each of the child nodes. In most cases there will be only 2 children.

• Lists are shown as [A,B,C,…​] where A, B, and C are the stringified lsit elements.

• Numbers are shown as numbers (i.e. 1 is 1 etc)

• Booleans are shown as true or false

• Other strings are shown as-is, wrapped in "double quotes"

Data Structures

Data structures are based on the types provided by Dr Bernhard Reus in his textbook Limits of Computation.

Lists are represented by a tree of depth N, where each "left" node at depth n represents the nth element in the list, and the final right-node is null, acting as a terminator.

Each integer n is represented as a list of nils of depth n.

Tree Input/Output Types

The language accepts trees represented as objects in the following format. Nodes can be null (representing nil) or point to left and right nodes.

type BinaryTree = {
	left: BinaryTree,
	right: BinaryTree,
}|null;

The conversion produces a tree of type ConvertedBinaryTree. This tree is represented differently to the input type due to having a more flexible format.

Every node may contain the following information:

• A list of children (each a ConvertedBinaryTree)

  There may be more than 2 children to any given node

• A string value describing the node

• A boolean describing whether the node represents a list rather than a tree

• A string containing an error message for the current node

export type ConvertedBinaryTree = {
    children?: ConvertedBinaryTree[],
    value?: string|number|null,
    list?: boolean,
    error?: string,
};

Future features

• ❏ counters

• ❏ strict mode (error on invalid nodes)