Teckel — An Interpreter for Abstract Algorithms in LaTeX
**** Provisional ****
Contents
Teckel
is an interpreter for non-deterministic and deterministic
algorithms written in a mathematical style and expressed in LaTeX.
For example, the Teckel program
resulting from the LaTeX code
%Teckel on
\Tdefine{Q}{\{ n ^ 2 , n \in \mathbb{N} \}}
\Tdefine{C}{\{ n ^ 3 , n \in \mathbb{N} \}}
\Toutput{Q \cap C}
%Teckel off
prints the infinite sequence of natural numbers that are both squares and
cubes: 0, 1, 64, ... .
And the Teckel program segment
resulting from
%Teckel on
\begin{quote}
\Tdefine{\mathrm{SORT}(x)}{
\{ y_1 \cdots y_n \in \mathrm{PERM}(x) ~ | ~
y_1 \leq \ldots \leq y_n \}
}
\Tdefine{\mathrm{PERM}(x_1 \cdots x_n)}{
\bigcup_{1 \leq i \leq n}
( x_i ~ \mathrm{PERM} (x_{1 ..(i-1)} x_{(i+1)..n}))
}
\end{quote}
%Teckel off
defines a sorting routine.
Teckel tries hard to find solutions, avoid getting sidetracked by
infinite dead ends, and produce at least some results in finite time.
On the other hand, speed has consistently been sacrificed for power.
Teckel allows the same LaTeX text to be run and published, thus cutting
out one conversion layer and a lot of programming.
It is also a convenient means for running non-deterministic programs.
The program is stored as a binary tree; complex operations have been
"binarized".
The tree is reduced (in the functional-programming sense of the word) by the
"Teckel", who searches the tree, finds a redex, reduces it, and repeats
the process.
To prevent the Teckel from getting stuck in (infinite) dead ends, the search
for the redex is performed in breadth-first fashion.
Note that even AND nodes need to be reduced breadth-first: one of the
branches may loop forever while another one comes up with the answer
False.
If the tree or a subtree reduces to a value, breadth-first search will find it
in finite time.
The Teckel finds the redex as follows.
It starts at the top of the tree.
If the node has one unreduced child, it goes to that child.
If the node has two unreduced children, and if it went to the left child last
time the node was visited, it now goes to the right child, and vice versa.
It repeats this procedure at the node thus reached, etc.
Eventually the Teckel finds a node without unreduced children.
This is the redex; the Teckel performs the action the node requires and starts
from the top again.
This procedure distributes the available processing power fairly over
the tree, and guarantees that every node will come up for reduction in finite
time.
Some parts work:
but nothing Internet-worthy yet.
See the documentation.
The time scale of this project is several/many years.
This is all very much under construction.
Last update: Nov. 3, 2014
Updates will be released as they become available.
Teckel — An Interpreter for Abstract Algorithms in LaTeX / Dick Grune /
dick@dickgrune.com
... and my name is not Richard ...
|