Titan

Databases for the people

Synopsis

Titan is a development platform for incremental optimisable search and enumeration. In Titan, programs are defined as relations between values, which can be defined by formulae according to rules for application and search. For this, Titan defines:

1. A reference language in which to express these rules;
2. A standard library by which to facilitate development; and
3. Implementation constraints to provide performance guarantees.

Reference Language

Titan's reference language is extremely simple: conceptually, programs are databases of relations specified as sums of rows, each row relating the values in its columns together. The major tricks added to this, however, are:

1. Relations can be partially applied, yielding the projection of the search for the rows with the given values in the corresponding columns onto the other columns;
2. A row of a single column decays to the value in that column;
3. A sum of a single row decays to that row; and
4. Unary relations correspond to column types.

• (gcd 111 259) => 37
• (gcd 111 259 37) => True
• (gcd) =>

  {
  	[@_1  0    @_1]
  	[@_1  @_2  (gcd @_2 (% @_1 @_2))]
  }

• (gcd 111) =>

  {
  	[0    111]
  	[@_2  (gcd @_2 (% 111 @_2))]
  }

• (gcd @_1 259) => [@_1 (gcd 259 (% @_1 259))]

Alphabet

• Letters, consisting of the Unicode General Category L, named letter;
• Digits, consisting of the Unicode General Category N, along with the following subsets:
  • the decimal digits 0123456789, named digit,
    and the nonzero digits ndigit = digit - 0;
  • the binary digits 01, named bdigit;
  • the octal digits 01234567, named odigit;
  • the hexadecimal digits 0123456789ABCDEF, named hdigit;
• Alphanumerics, named alpha = digit|letter;
• Punctuation and delimiters, consisting of ()[]{}'"@;
• Symbols, consisting of `.\/%^*+-#&|~=<>!?:;,, named symbol;
• Whitespace, consisting of the union of the Unicode General Categories Zs, Zl, Zp and Cc; and
• The underscore _.

Tokens

• The delimiters () [] {};
• Names, denoted by the regular expression name
  (_|letter|symbol)(_|alpha|symbol)^*
• Variables, defined by the regular expression variable
  @name
• Numbers, defined by the regular expressions number
  -^?ndigit(digit ⁺(.digit ⁺)^?|(.digit ⁺)^?(e-^?ndigit digit ^*)^?)^?
  0(.digit⁺|bbdigit⁺|oodigit⁺|xhdigit⁺)^?
  '((\|')^-|\(\|'))'
• Strings, defined by the regular expression string
  "("^-|\("|\))^*"
• Comments, defined by the regular expressions
  \*(*\)^-*\
\\(newline)^-newline

Grammar

Standard Library

Titan's standard library is divided into three major parts: Language, Environment, and Algorithms. All definitions in the standard library are abstract data/negative types, meaning they are defined in terms of their projection relations. Only the Language part is mandatory, and the two other parts can be defined in terms of it.

Language

Algorithms

Environment

Reference Implementation

Bootstrap Implementation