add more notes

[cdsspec-compiler.git] / notes / sequential_spec.txt

diff --git a/notes/sequential_spec.txt b/notes/sequential_spec.txt
new file mode 100644 (file)
index 0000000..6cdf5b8
--- /dev/null
+++ b/notes/sequential_spec.txt
@@ -0,0 +1,73 @@
+/**
+       This file contains the design thoughts and details about how we use set
+       theory and more formalized way to design a simple specification language to
+       abstractly describe a sequential data structure.
+*/
+
+1. Design goals:
+   We should design a specification language that users (developers of data
+   structures) can use to describe the specification of sequential data
+   structures. The language should be as mathematical and precise as possible,
+   while it provides enough expressiveness and usability for users. That's to
+   say, users can learn the language easily and take advantage of it to describe
+   as many data structures as possible, e.g, Lock, Queue, Dequeue, LinkedList,
+   Stack, Vector, Hashtable, and UnorderedPool(maybe).
+
+2. Common data structures:
+   Data structures, to some degree, can be viewed as a collector with specific
+   operation on it. Those operations are done according to the maintained state
+   and pre-defined logic. Set in mathematics has similar characteristics, which
+   contains a collection of elements. However, elements in a set are distint.
+   Order_list, which is a list of elements that have a total order and can
+   duplicate, can be used to complement set. For example, a queue is a container
+   that has a FIFO order on the elements while a stack with a LIFO order. For
+   hashtable, it is a set of pairs (tuples) that has restrictions on the pairs.
+
+3. Potential constructs:
+   a) Set
+   The set here is conceptually similar to the set in Set Theory. We define our
+   set as a collection of unique and unordered elements. Uniqueness here
+   implicates that the set element should provide an internal equality check.
+   The following is some basic manipulations on set:
+   1) Tuple
+   Every element is an n-dimentional tuple, and each element of a tuple is a
+   tuple. This is basically used to represent the mapping between elements such
+   as a HashMap. Some examples:
+   a or (a) // 1-dimentional tuple, actually any variable is a 1-dimentional tuple
+   (key, value) // 2-dimentional tuple
+   (a, (a, b)) // 2-dimentional tuple, while the second column is a tuple too
+   1-dimentional tuple is the most basic part, it should have a type, such as
+   integer, boolean, or other templated types. The type of a set can be derived
+   from the tuple too. For example, A, B and C are basic types or templated
+   types, we can have Set<(A)>, Set<(A, B)> or Set<(A, (B, C))> as different
+   types. Set<(A)> contains elements of type A, Set<(A, B)> contains tuples of
+   (A, B) and Set<(A, (B, C))> contains tuples of (A, (B, C)). We can get an
+   instance of tuple in a way like (key, value).
+      The tuple has its basic operation dimention(n), which returns the tuple of
+         its nth column.
+   2) Union, intersection, and complement.
+   new_set = union(s1, s2); // returns a new set
+   or
+   s1.union(s2); // s1 becomes the union of s1 and s2, and it returns the new s1
+   It takes two sets and return the union of the two sets. Same for the
+   intersection and complement.
+   3) Cartesian product
+   new_set = prod(s1, s2); // returns the cartisian product of s1 & s2
+   The result of this operation is that a new set of tuples of s1 and s2.
+   4) Remove
+   set.remove(elem);
+   5) Find
+   subset = set.find((key, *)); // use wildcard to find possible subset
+   b) Order_List
+   This is a list of tuples that has an order. It should have the following
+   operations:
+   1) push_back
+   list.push_back(elem);
+   2) push_front
+   list.push_front(elem);
+   3) remove_back
+   elem = list.remove_back();
+   4) remove_front
+   elem = list.remove_front();
+   5) Find
+   elem = list.find(elem);