Written in Scala

The current version is written in Scala and compiled against the JVM 1.5. Other (but now defunct) implementations include Java, Factor and Haskell implementations.

Confluently Persistent Data Structures

All (data)structures in Enchilada are purely functional (lazy) confluently persistent data structures.

This means that structures are immutable and that structures from the past can be efficiently combined with structures from the future.

Although some structures are lazy in Enchilada, it is impossible to create cyclic ones, because direct recursive definitions cannot be expressed in Enchilada.

Internal Representation

Internally, binary (weight) balanced trees are used to represent sequences, expressions and symbols.

Here, leaf nodes are depicted as cubes and branch nodes as triangles. Green cubes represent pairs; orange cubes represent expressions that consist of only one atom (in this case, a number sequence).

The next diagrams demonstrate additional (tree) rewrites to further illustrate internal structure:

Branch nodes have (lazy) behavior that depends on the branch type. The default branch type is the concatenative branch. Other branch types are reverse, maximum and minimum.

Scala Code

A small sample of Scala code will demonstrate how Enchilada is able to achieve low computational bounds on certain operations.

Value

The Value trait is the base type from which all other types are derived. Each Value in Enchilada has an ID that must be unique for that particular Value.

It is important that an ID is quickly available. As such, most IDs are stored alongside the Value.

Another trait of a Value is that it can be compared to another Value or tested for equality. A concrete Value must also be able to serialize itself to Memory by implementing memorize.

trait Value[A <: Value[A]] extends Constants
{  
  def compare(v: A) : Int
  def equal(v: A) : Boolean
  def id : ID
  def memorize(m: Memory) : (A, Memory)
}

Tree

The next most important abstract type in Enchilada is the Tree. Each Tree carries an immutable inv(ariant) that is different for every subtype of Tree (Expr, Seq and Symbol).

Note that a Tree has no size restriction (however, its depth may not exceed 2^31).

trait Tree[A, B <: Value[B]] extends Value[Tree[A, B]]
  with SymbolsHolder with Constants
{  
  def depth : Int
  def size : BigInteger
  
  def empty : Empty[A, B]
  
  def left : Tree[A, B]
  def right : Tree[A, B]
  
  def first : B
  def first2 : B

  def last : B
  def last2 : B  
  
  def -+-(other: Tree[A, B]) : Tree[A, B]
  def +++(other: Tree[A, B]) : Tree[A, B]
  
  def head(n: BigInteger) : Tree[A, B]
  def tail(n: BigInteger) : Tree[A, B]
  
  def multiply(m: BigInteger) : Tree[A, B]
  def multipleOf : (Tree[A, B], BigInteger)
  
  def inv : A
}

The method head should yield (the balanced) Tree that contains the first n leafs. The tail method should yield a Tree with the last (size-n-1) leafs.

The contents of the first two leafs can be queried with methods first and first2 respectively. Similarly, the contents of the last two leafs can be queried with last2 and last.

The concatenation(+++) of two Trees A and B should yield a (balanced) Tree that contains the serial concatenation of all leafs taken from A and B.

Concatenation

Because concatenation is the most important operation in Enchilada, it must be very efficient.

The following ConcatMixin implements concatenation in O(log(size)) on top of combine(-+-).

trait ConcatMixin[A, B <: Value[B]] extends Tree[A, B]
{
  final val delta2 = 2
  final val ratio2 = 1
  
  final def +++(r: Tree[A, B]): Tree[A, B] =
  {
    val l = this
    
    val ls = l.size
    val rs = r.size
    
    if (ls == ZERO) r
    else if (rs == ZERO) l
    else if (((ls shiftLeft delta2) compareTo rs) == LT)
    {
      val rl = r.left
      val rr = r.right
      val srr = rr.size
      if (((srr shiftLeft ratio2) compareTo rl.size) == LT)
      {
        (l +++ rl.left) -+- (rl.right -+- rr)
      }
      else (l +++ rl) -+- rr
    }
    else if (((rs shiftLeft delta2) compareTo ls) == LT)
    {
      val ll = l.left
      val lr = l.right
      val sll = ll.size
      if (((sll shiftLeft ratio2) compareTo lr.size) == LT)
      {
        (ll -+- lr.left) -+- (lr.right +++ r)
      }
      else ll -+- (lr +++ r)
    }
    else l -+- r
  }
}

Head and Tail

The HeadTailMixin implements head and tail on top of concatenation(+++).

trait HeadTailMixin[A, B <: Value[B]] extends Tree[A, B]
{
  def head(i: BigInteger): Tree[A, B] =
  {
    if (i == ZERO) empty
    else if ((size compareTo i) == EQ) this
    else
    {
      val l = left
      val ls = l.size
      if ((ls compareTo i) == GT) l.head(i)
      else l +++ right.head(i subtract ls)
    }
  }
  
  def tail(i: BigInteger): Tree[A, B] =
  {
    if (i == ZERO) this
    else if ((size compareTo i) == EQ) empty
    else
    {
      val l = left
      val r = right
      val ls = l.size
      if ((ls compareTo i) == LT) r.tail(i subtract ls)
      else l.tail(i) +++ r
    }
  }
}

The time complexity of head and tail is fully determined by the time complexity of +++, which is O(log(size)).

Expr

The Expr type is a Tree with Term as the leaf type and Boolean as the invariant type.

An Expr is rewritable, or not: this is the boolean invariant that is held for every Expr.

TODO: more documentation

Equality

Every ID of an Enchilada Value is calculated by taking the SHA1 hash of the Value's contents.

In Enchilada, two Values are considered equal if their IDs are equal. (however, two Values that are equal do not need to have the same ID).

The ID of an Enchilada Tree is determined by a scheme that is similar to a Merkle Tree:

The ID of a Tree is determined by concatenating the IDs of its left and right (sub)Tree, and then to compress this concatenation of IDs by (again!) calculating the hash:

tree.id == SHA1(tree.left.id +++ tree.right.id)

Verifiable Computation

The same computation(=unwritten expression) will always yield the same result(=rewritten expression) and thus will yield the same cryptographic hash.

As such, identical (and huge) results that are computed on different computers can be efficiently compared by just comparing their hashes.

So, when more and more nodes compute the same result, there will be more and more confidence that such result is not faulty or tampered with.

With little effort, Enchilada computations can even be cryptographically signed.