Teckel — An Interpreter for Abstract Algorithms in LaTeXby Dick Grune**** Provisional ****ContentsShort Intro
Teckel
is an interpreter for non-deterministic and deterministic
algorithms written in a mathematical style and expressed in LaTeX.
For example, the Teckel program
%Teckel on \Tdefine{Q}{\{ n ^ 2 , n \in \mathbb{N} \}} \Tdefine{C}{\{ n ^ 3 , n \in \mathbb{N} \}} \Toutput{Q \cap C} %Teckel offprints the infinite sequence of natural numbers that are both squares and cubes: 0, 1, 64, ... .
And the Teckel program segment
%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 offdefines 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 Execution ModelThe 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. Project Status
Some parts work:
DocumentationThis is all very much under construction.
Further documents
Last update: Nov. 3, 2014
Teckel — An Interpreter for Abstract Algorithms in LaTeX / Dick Grune /
dick@dickgrune.com
|