Tilt Is Like TRAC¶
TRAC is an interesting (or perhaps just curious?) programming language from the 1960’s, developed by Calvin Mooers and first implemented on a PDP-1 by Peter Deutsch.
In the age of LISP and FORTRAN, TRAC was quite different, as hinted by its full name: Text Reckoning And Compiling. TRAC is in fact a text processing language, i.e. transforming pure text (7-bit ASCII at the time) into different text by parsing and evaluating embedded “macro calls”, similar to Unix’s m4 macro processor, some 20 years later.
This text, for example:
Fifteen times seventeen is #(ml,15,17)!'
Will “evaluate” to this:
Fifteen times seventeen is 255!
TRAC is intended to be used from an interactive terminal. The single-quote “meta character” is the default end-of-input marker, at which point TRAC processes its input and prints the result.
Calls can nest and recurse, which means that all the usual features in a programming language are available. There are about three dozen primitives, and you can define your own functions (called “forms”). Forms have names and there is a way to replace text with “segment markers”, to be replaced with actual arguments later on.
TRAC is described in the March 1966 issue of the Communications of the ACM, in an article by Calvin Mooers titled: “TRAC, A Procedure-describing Language for the Reactive Typewriter”.
It’ll easily fit on a modern µC, is simple to implement, and felt like a nice
experiment (or was it a distraction? I always mix those up), so that’s what this
article is about. As there seem to have been some messy details w.r.t.
as a protected trade name, my implementation is called
Tilt instead, which
stands for “Tilt Is Like TRAC”.
But first, one more example:
#(ds,fact,(#(eq,1,X,1,(#(ml,X,#(cl,fact,#(su,X,1))))))) #(ss,fact,X)' 5! = #(cl,fact,5)' 10! = #(cl,fact,10)' 20! = #(cl,fact,20)'
The output is:
5! = 120 10! = 3628800 20! = 2432902008176640000
dsis “define string”, which defines a string (eh, form) called
sssegments a given string (eh, form) by matching all the X’s
clcalls a form, replacing segment mark(s) with the actual argument(s)
- this is essentially a functional language, with the only side effect being the ability to store (and replace/delete) forms in “form storage”
- forms can also be saved to external “block storage”, and re-used in a future session
My original plan was to use Tilt as a very basic scripting language for writing all sorts of tests (e.g. for JeeH and whatever else gets built on top). It would not be hard to add a few special primitives to JeeH’s peripherals and datatypes. But it quickly became clear that such “scripts” would be quite messy and tedious to write. While even entire compilers and interpreters have been implemented in TRAC, which means that any notation could in principle be supported, I didn’t really want to go down that lengthy path myself.
What remains is a project which allows me to build something on top of the latest JeeH design, while also validating the implementations of VaryVecs and a “Mapped Romable File Store” - both used to implement form storage and persistence for Tilt.
Tilt currently runs on “native” (i.e. MacOS/Linux) and on an STM32L432 µC board. It has been set to use 40 kB of RAM, which gives it room for very substantial “programs”, with up to 192 kB of flash memory available for permanent form storage.
Tilt is implemented almost exactly as documented in the book “Etudes for Programmers” by Charles Wetherell, from 1978. In it, section 28 is called “Off the beaten TRAC”, which fully describes the parsing / evaluation algorithm and all the primitives.
In true macro-processor style, arithmetic is done on the actual characters and limited only by available storage. As WolframAlpha will easily confirm, 640! has 1520 digits:
640! has #(sl,#(cl,fact,640)) digits' 640! has 1520 digits
Caveat: I did cut one corner, in that I didn’t implement an unlimited-precision version of division, but fell back to using 32-bit arithmetic for this one operation. Maybe some day …
Forms are “strings with segment markers”. In Tilt, these are implemented as two
separate items: 1) the 8-bit clean “string” (which can contain any byte value
from 0-255), and 2) a sorted index of
<mark,offset> pairs (encoded as 8+24 bits in an array of
All resident forms are linked as a chain of heap-allocated RAM.
In permanent storage, i.e. the “block store”, a set of forms is saved as a file, using a VaryVec, with 3 entries per form: the form name, the string, and the index vector. This storage uses a memory-mapped file on MacOS / Linux, or the high end of flash memory on STM32L432. The mechanism is called “Mapped Romable File Store” (MRFS), and is still work-in-progress.
The entire implementation is written in C++, see https://git.jeelabs.org/doodle/tree/tilt.