Al Dente

This page is very much a work in progress.

Al Dente is an esoteric programming language created by Tanner Swett in 2015, inspired by the paper "Chu Spaces: A Model of Concurrency".

By example

A program consists of a set of classes. The following is an example of a class:

Abc { a; b; c; }

Like in an object-oriented language, a class is a type whose instances are objects, and the state of an object consists of the states of the object's attributes. In the Abc class, a, b, and c are event attributes.

An event has two possible states, unfired and fired. Initially, all events are unfired. There are no instructions or flow control; instead, the way execution works is that events spontaneously fire in an unspecified order (possibly simultaneously), subject to restrictions specified by the program. Once an event fires, it can never go back into the unfired state.

Any given Abc object, therefore, has eight possible states. These states can be restricted by adding restriction declarations, like so:

Abc { a; b; c; a requires b; }

The a requires b restriction prohibits all states where a has fired but b has not. This version of Abc, therefore, has only six possible states. Another example:

Abc { a; b; c; b excludes c; }

The b excludes c restriction prohibits those states where both b and c have fired. This means that once either b or c has fired, the other event can never fire. Again, there are six possible states. The two restrictions can, of course, be combined:

Abc { a; b; c; a requires b; b excludes c; }

Now there are only four states: that where no event has fired; that where only b has fired; that where a and b have both fired; and that where only c has fired.

(Note that we could completely prevent the event a from firing by writing a excludes a.)

Since events can fire simultaneously, there is nothing wrong with a definition like this one:

Abc { a; b; c; a requires b; b requires a; }

These restrictions prohibit any state where either a or b has fired but the other has not. However, it is still possible for both events to fire simultaneously. The restriction a matches b is a synonym of a requires b and b requires a together.

Either side of a restriction declaration can be an expression built with the and and or operators. (There is no not operator, however.) For example:

Abc { a; b; c; (a and b) requires c; }

This definition prohibits any state where a and b have both fired but c has not.

Further code examples can be found at Al Dente examples.

Syntax

An Al Dente program consists of a sequence of tokens, optionally separated by whitespace. A token is a brace, a parenthesis, a semicolon, a period, or a case-sensitive sequence of English letters. A sequence of letters beginning with an uppercase letter is a class identifier; a sequence of letters beginning with a lowercase letter is a variable, unless it is one of the keywords "matches", "requires", "excludes", "and", or "or". Letter sequences must be separated by whitespace. Whitespace has no significance besides separating tokens.

The syntax, in EBNF, is:

<program> ::= (<class> "{" (<declaration> ";")* "}")*
<declaration> ::= [<class>] <variable> | <expression> ("matches" | "requires" | "excludes") <expression>
<expression> ::= [(<variable> ".")*] <variable> | "(" <expression> ")" | <expression> ("and" | "or") <expression>

The . operator takes precedence over the and operator, which takes precedence over the or operator. The and and or operators are associative.

Semantics

A program consists of a set of class definitions, each of which consists of a set of attribute declarations and restriction declarations. An attribute may be declared without a class, in which case it is an event attribute, or with a class, in which case it is an object attribute.

Each class defines a set of events; the events of a class are its event attributes, along with the disjoint union of its object attributes' events. This means that many classes will have infinitely many events. For example:

Chicago { alpha; beta; Chicago tail; }

This defines a class called Chicago, whose events are alpha, beta, tail.alpha, tail.beta, tail.tail.alpha, and so on. (Events are well-founded; an event only exists if it can be referred to using finitely many dots.)

Each class also defines a set of permissible states. Permissible states of a class are sets of events of the class; a set of events is a permissible state if and only if it is finite and it obeys all restriction declarations.

Restriction declarations fall into two categories: event restrictions and object restrictions.

An event restriction consists of a pair of expressions, made up of event attributes and the logical connectives and and or, separated by matches, requires, or excludes. A matches restriction states that the truth values of the expressions on either side must be equal (where the truth value of an event is true if it is in the set and false if it is not). A requires restriction states that the expression on the left cannot be true while the expression on the right is false. An excludes restriction states that the expressions on either side must not both be true.

An object restriction consists of a pair of object attributes of the same class, separated by matches. This restriction states that the objects on either side must be in the same state.

Execution consists of starting in the state of an object containing no events, and repeatedly moving, in an unspecified manner, to a permissible state which is a superset of the current state.