Tamerlane

Chris Pressey
Created Jan 29 2000

Introduction to Tamerlane

Tamerlane is a "constraint flow" language. The point of its creation is to attempt to break as many paradigmal stereotypes and idioms that I'm aware of; at least, to make it tricky and confounding to pigeonhole easily.

It has some concepts in it from imperative languages, some from functional languages, some from dataflow and object oriented languages, and some from graph rewriting and other constraint-based languages, and they're all muddled together into a ridiculous potpourri.

Despite being such a mutt, there might actually be some algorithms that would be dreadfully easy to write in Tamerlane.

Overview of Tamerlane

A Tamerlane program consists of a mutably weighted directed graph.

Each node is considered to be an independent updatable store. The data held in each store is represented by the weights of the arcs exiting the node.

An arc of weight zero is functionally equivalent to the absence of an arc.

Description and Example

At this point we may introduce the syntax in a sample ASCII notation for a simple, almost pathological Tamerlane program:

  Point-A: 1 Point-B,
  Point-B: 1 Point-C,
  Point-C: 1 Point-A.

The user of a Tamerlane program may submit messages to the program at runtime. In this sense the user and the program are both objects which share the symmetrical relationship user-of/used-by. The program object's interface exposes a query method to the user, which is to be considered runtime-polymorphic.

Using this message-passing mechanism, queries are submitted by the user to a running Tamerlane program, much as queries would be submitted to a running Prolog program.

Queries have their own syntax and semantics. Unlike Prolog, the user's queries are interpreted as rules, perhaps accompanied by information about where and when the rules are "introduced" into the graph.

As an example of a query that could be submitted to the above Tamerlane program:

  1 Point-A -> 0 Point-A @ Point-A

This would introduce the rewriting rule

This rule is applied to the weights of the nodes in the graph starting with the node specified after the @ symbol. In this instance it would start by trying to apply the rewrite to the node Point-A, but finding Point-A to contain 1 Point-B, nothing would change.

Each time a further query is submitted, each rule which has been introduced into the graph, disappears from the node it was working on, and is transmitted to the adjacent node with the lowest positive weight value. If there is a tie for lowest weight, the rule is transmitted to all of the adjacent nodes with the same lowest weight.

For efficacy we can consider the user able to submit a nop query. This would not introduce any new rules into the graph, but it would cause all active rules to propogate to new nodes on the graph.

So assume the user submits nop. The rule that was introduced by the last query 'moves' from the node labelled Point-A to the node labelled Point-B (since it's the only positive route out of Point-A.) It tries to rewrite Point-B, but finding only 1 Point-C in Point-B, nothing happens.

Assume the user nops again. The rule is propogated to Point-C. Finally the pattern match succeeds, and Point-C is rewritten to a new Point-C:

  Point-C: 0 Point-A.

After one more nop, the engine will generate a

  Rule stopped at Point-C (no adjacent nodes)

message back to the user. This uses the operation that the user object's interface supplies to the running program, called messageback, which the user must supply, but is, like query, considered runtime-polymorphic.

Advanced Topics

Rule Priority

Obviously, the user can enter more than one query in succession; s/he doesn't need to explicity nop to wait for rules to resolve. Since the graph can contain cycles, this would lead to a form of inherent, synchronous concurrency: each time the query or nop methods are invoked, more than one rule may be applied to the same node.

The order in which these competing rules is applied is based on the rule's priority. Rules can be submitted with a specific priority in the following manner:

  1 Point-A -> 0 Point-A @ Point-A ! 10

If there is a tie in priority when two rules are competing to rewrite the same node, the outcome is guaranteed to be not simply undefined, but rather, non-deterministic, or at least probabilistic.

The user can also specify a delay, measured in number of method calls (querys or nops) from the present query, at which the rule will be introduced into the graph, like so:

  1 Point-A -> 0 Point-A @ Point-A in 10

And, for the sake of efficacy, the nop method on the program object has overloaded syntaxes whose semantics are 'keep noping until some or all rules have stopped.'

Negative Weights

A negative weight from one node to another is interpreted in a rather negative fashion with respect to the running program.

A negative weight is selected for propogation when it is closer to zero (while still being non-zero) than any other weight (absolute value.) When a negative weight is selected, however, the semantics of propogation are different.

When a rule encounters an arc of the form:

  X: -1 Y.

The rule is not "just" copied to Y like "usual". Instead, it "rolls back" the rule to Y in the fashion of a functional continuation.

All of the nodes that have been "touched" by this rule, since it was last at node Y, are reset to their condition when the rule was last at node Y. The rule itself is deleted from X and propogated to Y, and rewriting continues from there.

If the rule has never visited Y, however, then such an exit arc is not considered a valid candidate. It has an effective weight of 0 (non-existent.)

Lambda Graphs

Lambda abstraction is a powerful form of referring to non-numeric calculatory items such as functions and, in the case of Tamerlane, graphs.

A user may submit a rule in the form

  1 X -> 1 Y ? Y: 1 Z, Z: 1 Y

Y is like a 'local variable' in this respect. When the rule is applied to the node, and the pattern match succeeds, the nodes named Y and Z need not actually exist, as they are simply created dynamically and 'attached' to the program graph.

Lambda graphs are subject to garbage collection, since they can only be used by the rule that created them.

Pigeonholes (Updatable)

Variables may be supplied which are explicitly updatable, and these are termed pigeonholes. Pigeonholes acknowledge events. Their assignment is associated with both nodes and arcs. They can occur when:

• a rule enters a node
• a rule leaves a node
• a rule chooses an arc
• a rule passes through an arc
• a rule rewrites an arc

Updatable variables are always named after the node (or node.arc) they're associated with, preceded by a $ symbol. The data in the variable is, of course, the arc weight (or in the case of nodes, the node's internal key.)

If the pigeonhole is assigned the special value %Cancel, the rule is cancelled from moving to the node/through the arc/rewriting the arc.

Placeholders (Unification)

Variables may also be supplied as "placeholders". These are the same as bindable (unifiable) variables in logical languages like Prolog. An example of such might be:

  1 X 7 ^Y -> 7 X 1 ^Y

Which would replace "1 X 7 Foo" with "7 X 1 Foo", "1 X 7 Bar" with "7 X 1 Bar", etc.

Horn Rules

Horn rules only succeed if all of their rules succeed. A Horn rule is specified like:

  1 X -> 1 Y + 1 Z 0 G -> 1 G

(Remember that 0 G is equivalent to "the absence of an arc to G." If you have a pattern like

  ^a G ^b G 0 G -> ^b Q

It will only match when there are exactly two different exit arcs to the same node G, which is not disallowed (nor is a node with an exit arc which points to itself.))

Note also that arcs are unordered amongst themselves. The rule

  1 A 1 B 1 C -> 1 E 3 D

is the same as

  1 B 1 A 1 C -> 3 D 1 E