chris blogs

June 2006

17jun2006 · The Design of Brne


Brne only knows one type of value: bi-relations that sometimes can be ordered. Imagine this as a multimap (i.e. keys don’t have to be unique) of keys to values. Relations map atoms (which aren’t directly accessible from the language) to other atoms. The literal 42 would, for example, really be a relation of one tuple that maps 42 to 42. Atoms can be numbers, strings, symbols (which often serve as primary keys) or the special value nil, maybe things like dates will be added.


Operators are functions of arity 0 (mediadic), 1 (monadic) or 2 (dyadic). All dyadic operators are used infix and consist of ASCII non-letter symbols, all mediadic and monadic operators use prefix and can either consist of non-letter symbols or only letters and digits (usually, one would call them a “method” or a “function” then, but Brne only knows operators).

The result of an operation is another relations. Internally, this works using a lazily evaluated generator: every operator implements a certain set of operations: reset, which resets the generator; next? which returns a boolean value if there is another element to be generated and next, which returns this element. Therefore, operators are very much like forward iterators that embody a calculation.

All operators in Brne are purely functional, that is, they don’t have side effects. This allows for excellent parallelism: every argument of the operator can be evaluated independently.

A few example operators would be (this is not written into stone yet):

  • nil: Always returns nil.

  • id: Returns the identity relation that maps every key as value.

  • keys a: Returns the “left column” of the relation a.

  • values a: Returns the “right column” of the relation a.

  • flip a: Returns the relation a with keys and values exchanged.

  • a -> b: Creates a relation of the first key of a to the first key of b.

  • a ++ b: Unifies the relations a and b.

  • a . b: Creates a new relation that maps the values of a to the keys of b, that is, a semi-join.

  • a = b: Selects the tuples of a whose keys are keys of b.

There will be more operators for basic arithmetics, comparision and SQLish aggregates like sum, avg, min and max.

Additionally, there are adverbs that modify the behavior of an operator. So far, the only adverb is ', which works like this: a op' b becomes (flip a) op (flip b). That, e.g. allows for easy selection by value. As special syntax, a’ generally is (flip a).

I’ve already written a parser in Racc and some of the operators. I also have a QDBM based datastore and hacked RbTree for in-memory representation. Now, it’s all a matter of putting these things together, converting some database queries and watching which parts of the prototype are too slow.

Then, I can start modeling this evaluation scheme to C and connect it with libsew.

NP: Syd Matters feat. Ane Brun—Little Lights

Copyright © 2004–2016