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. TRAC 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

Some notes:

ds is “define string”, which defines a string (eh, form) called fact
ss segments a given string (eh, form) by matching all the X’s
cl calls 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.

Implementation¶

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 uint32_t).

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.