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) => []
• (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

The alphabet of the Titan reference language is in the Unicode 10 character set. Several subsets are named here for future reference:

• 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

The full grammar of the Titan reference language is:
E ::= | AE
A ::= name | variable | number | string | [E] | {E} | (E)
Note that there are no reserved identifiers.

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

The Language part contains the abstract data types of the core constructs of the language.

Algorithms

The Algorithms part contains the abstract data types for complex operations on the core constructs of the language.

Environment

The Environment part contains data types for interfacing with other systems.

Reference Implementation

Titan's reference implementation will be code-named Othrys, after the mountain home of the Greek titans (as opposed to Olympus, the home of the Olympian deities).

Bootstrap Implementation

Titan's bootstrap implementation, in progress, is code-named Chaos, after the root deity of the Greek Pantheon.

Daniel Campos do Nascimento © 2025-