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.
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.
Internally, binary (weight) balanced trees are used to represent sequences, expressions and symbols.
The concatenation, splitting and combining of trees is performed in O(log(n)), where n is the number of leafs. To get an idea of how Enchilada encodes expressions internally, a representation of the expression: '[1;2] [3=4;5=6] + [7;8;=9;=10] |' is shown: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.
A small sample of Scala code will demonstrate how Enchilada is able to achieve low computational bounds on certain operations.
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)
}
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.
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
}
}
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)).
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
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)
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.