Colorful Trees

Programs are trees... !

This project is a (tiny) toolbox containing all you need to build programs with complete binary trees with colored leaves.

The objective is to show another way to approach functional programming (leaves are our functions!). It also show some properties of functional paradigm: naturally parallelizable, virtualizable.

Wait, what ?

We work with binary complete trees (it means, each node is a leaf or has exactly two children). Only leaves have a value, which is a color. Depending on the color, we associate a transition in order to make the tree evolve. A description of built-in colors comes after. The user can describe new colors with a tree which will be replaced at runtime.

For the incoming explanations, we will use a simple parenthesized notation: in the node (A . B), A is the left children and B the right children.

One color is one function. We can pass parameters to the function by creating a new binary node, put the function as the left child and the parameter as the right child. Repeat while there is parameter. For example, the tree for X(Y, Z) ("normal" notation) is ((X . Y) . Z).

Built-in colors

| Name | Color | Stand for... | Letter | Input | Output | |-----------|---------|--------------|--------|---------------------|---------------------| | Ivory | #fffff0 | Identity | I | (I . X) | X | | Turquoise | #40e0d0 | True | T | ((T . X) . Y) | X | | Fuchsia | #ff0080 | False | F | ((F . X) . Y) | Y | | Salmon | #ff8c69 | Structure | S | (((S . X) . Y) . Z) | ((X . Z) . (Y . Z)) | | Chocolate | #d2691e | Composition | C | (((C . X) . Y) . Z) | (X . (Y . Z)) | | Red | #ff0000 | Recursion | R | (R . X) | (X . X) | | Blue | #0000ff | ?? | B | (B . X) | ((X . S) . T) |

With these colors, we can produce every existing program.

Funny fact: all the colors can be produced with Salmon and Turquoise only.

For example: F = (S . T) because if we pass X and Y the steps are :

• (((S . T) . X) . Y)
• ((T . Y) . (X . Y))
• Y

The result is the same as expected.

How do I use this repository?

This is a NodeJS module, you can find it on NPM with the name "colorful-trees".

npm install --save colorful-trees

Then, in your code:

const ColorfulTrees = require('colorful-trees')

You can :

• Access axioms (turquoise and salmon):

const turquoise = ColorfulTrees.Axioms.Turquoise
const salmon = ColorfulTrees.Axioms.Salmon

• Access embedded functions:

const ivory = ColorfulTrees.EmbeddedPrograms.Ivory
const fuchsia = ColorfulTrees.EmbeddedPrograms.Fuchsia
const chocolate = ColorfulTrees.EmbeddedPrograms.Chocolate
const red = ColorfulTrees.EmbeddedPrograms.Red
const blue = ColorfulTrees.EmbeddedPrograms.Blue

• Create trees:

const tree = new ColorfulTrees.Tree(ivory, fuchsia) // === (I . F)

• Define custom functions:

const program = new ColorfulTrees.Program('#000000', tree)

• Make the replacement in a tree (so that there is only axioms):

const replaced = ColorfulTrees.replace(tree)
// `tree` was (I . F)
// `replaced` is (((S . T) . T) . (S . T))
// Glad that this function exists, hmmm ? ;)

• Execute a tree (will work if there is only axioms):

ColorfulTrees.execute(replaced) // === (S . T)

Future improvements

• Implementation of parallelization in the execution function.