Programs for Linux that run in the terminal often use color. There are a few approaches to making this work. Many programs use hardcoded ANSI compatible escape sequences, which are widespread enough today that they work almost everywhere. There are drawbacks to hardcoding these and for that reason there’s a database called terminfo, which has its own stack-based Domain Specific Language (DSL).

The terminfo database has entries for most terminals that were ever made, even very obscure brands. My machine has 1743 entries in /lib/terminfo and /usr/share/terminfo. Terminfo provides a standardized interface towards all these terminals, including future terminals.

The terminfo database is also used by ncurses, a library for making programs like the one shown above. These programs will work more or less the same on all terminals that supports cursor movement. If there is no color support then they are monochrome, but still they work. Terminfo has a standard set of booleans and numbers that tell you how many colors the terminal supports, how many rows and columns it has (by default), whether it supports a mouse and also which quirks it has.

$ echo "$(tput bold; tput setaf 3;
tput setab 4)Yellow on blue$(tput sgr0)"

The tput tool uses the terminfo library to generate escape sequences for the current terminal, which it finds through the TERM environment variable.

A dumb terminfo entry

The infocmp tool can inspect terminfo entries:

$ TERM=dumb infocmp -x
dumb|80-column dumb tty,
    am,
    cols#80,
    bel=^G, cr=\r, cud1=\n, ind=\n,

All terminfo entries consist of named fields (called capabilities) that are either booleans, numbers or strings. The names are short and cryptic, although there is a longer version available as well. The terminfo(5) manpage has a short description of all fields, e.g. cud1 means cursor_down and contains the bytes that move the cursor down one line. Unsurprisingly, it’s a newline character. A pre-requisite is that the terminal is in raw mode, so the kernel does not translate newline to newline + carriage return as it would normally do.

There is also support for extended capabilities, which are not in the pre-defined list. The difference is basically that the binary terminfo format then has to explicitly encode the name of the field, whereas otherwise it is implicit by its location in the file. Terminfo can use these to encode new and interesting capabilities, like support for 24-bit color.

An advanced entry

Let’s go from dumb to advanced. The terminal emulator xterm has a variant with support for 24-bit color. It’s big and cryptic!

TERM=vt100 infocmp -x
#    Reconstructed via infocmp from file: /lib/terminfo/v/vt100
vt100|vt100-am|dec vt100 (w/advanced video),
    OTbs, am, mc5i, msgr, xenl, xon,
    cols#80, it#8, lines#24, vt#3,
    acsc=``aaffggjjkkllmmnnooppqqrrssttuuvvwwxxyyzz{{||}}~~,
    bel=^G, blink=\E[5m$<2>, bold=\E[1m$<2>,
    clear=\E[H\E[J$<50>, cr=\r, csr=\E[%i%p1%d;%p2%dr,
    cub=\E[%p1%dD, cub1=^H, cud=\E[%p1%dB, cud1=\n,
    cuf=\E[%p1%dC, cuf1=\E[C$<2>,
    cup=\E[%i%p1%d;%p2%dH$<5>, cuu=\E[%p1%dA,
    cuu1=\E[A$<2>, ed=\E[J$<50>, el=\E[K$<3>, el1=\E[1K$<3>,
    enacs=\E(B\E)0, home=\E[H, ht=^I, hts=\EH, ind=\n, ka1=\EOq,
    ka3=\EOs, kb2=\EOr, kbs=^H, kc1=\EOp, kc3=\EOn, kcub1=\EOD,
    kcud1=\EOB, kcuf1=\EOC, kcuu1=\EOA, kent=\EOM, kf0=\EOy,
    kf1=\EOP, kf10=\EOx, kf2=\EOQ, kf3=\EOR, kf4=\EOS, kf5=\EOt,
    kf6=\EOu, kf7=\EOv, kf8=\EOl, kf9=\EOw, lf1=pf1, lf2=pf2,
    lf3=pf3, lf4=pf4, mc0=\E[0i, mc4=\E[4i, mc5=\E[5i, rc=\E8,
    rev=\E[7m$<2>, ri=\EM$<5>, rmacs=^O, rmam=\E[?7l,
    rmkx=\E[?1l\E>, rmso=\E[m$<2>, rmul=\E[m$<2>,
    rs2=\E<\E>\E[?3;4;5l\E[?7;8h\E[r, sc=\E7,
    sgr=\E[0%?%p1%p6%|%t;1%;%?%p2%t;4%;%?%p1%p3%|%t;7%;%?%p4%t;5%;m%?%p9%t\016%e\017%;$<2>,
    sgr0=\E[m\017$<2>, smacs=^N, smam=\E[?7h, smkx=\E[?1h\E=,
    smso=\E[7m$<2>, smul=\E[4m$<2>, tbc=\E[3g,

Many interesting things are going on here. All the string capabilities that start with k, plus a few more, tell you how the terminal encodes keys. The home entry says that the Home key sends \E[H (i.e. ESC [ H). A quirky thing with this terminal is that it requires delays after some commands. Those are encoded as e.g. $<5>, which is a 5 millisecond delay. The delays are generated by sending an amount of NUL bytes that will generate the appropriate delay given the terminal’s current baud rate (although today they are often omitted).

Anatomy of a string

All non-dumb terminals can be told to move the cursor using the cup (cursor_address) capability. When tput is called as tput cup 5 10 it takes two arguments: the row and the column. In this vt100 entry this string is fairly simple:

cup=\E[%i%p1%d;%p2%dH$<5>

It’s ASCII soup. This is a program written in a DSL. Actually, all the strings that generate output are written in this DSL, even if they just output the same bytes every time. I have written a parser and compiler in R6RS Scheme for this DSL, which you can find in the text-mode package. Here is the result of tokenizing the string:

> (import (text-mode terminfo parser))
> (parse-term-string (string->utf8 "\x1b;[%i%p1%d;%p2%dH$<5>"))
((print #vu8(27 91))      ;prints ESC [
 (inc-p1/p2)              ;increment parameters 1 and 2
 (parameter 1)            ;push parameter 1 to the stack
 (printf "%d" #f #f #f #\space #f #f #\d)  ;pop and printf as %d
 (print #vu8(59))         ;print ;
 (parameter 2)            ;push parameter 2 to the stack
 (printf "%d" #f #f #f #\space #f #f #\d)  ;pop and printf as %d
 (print #vu8(72))         ;print H
 (msleep #vu8(53) #f #f)) ;sleep for 5 ms

Parameters passed to the program itself are addressed by their index (1-9), whereas operations in the program implicitly pop from or push to an argument stack. Some operations pop their arguments, e.g. the %d operation that pops a number and formats it as the printf function in the C library would. Other arguments push to the stack, e.g. %p1 that pushes the first parameter.

The %i operation is an interesting special operation that increments the first two parameters. This is useful because terminfo (and termcap, its historical predecessor) uses zero-based indexing for rows and columns, whereas VT100/ANSI terminals use one-based indexing.

The terminfo language

The terminfo language is a simple stack-based DSL that has parameters, if-then-else, built-in printf (with padding and decimal, octal and hex output), persistent variables and basic math/logic operators.

It is a dynamically typed language that supports integers of some unspecified type (i.e. signed 32-bit) and NUL terminated strings. There are two operations on strings: %l (pop and push the length of a string) and %s (pop and print a string). Terminfo generally has no clue if what is on the argument stack is a valid string or not, so these operations can very easily be made to cause segfaults in C implementations of terminfo.

The persistent variables are interesting. There are two sets of them: the static and the dynamic. Historically there was likely some difference between these, but today they appear to be the same. They are commonly used as temporary variables inside programs, as a way to get around the need to manage the argument stack properly. But they can also be used to store information that persists between calls to the terminfo library (when used through tparm/tiparm rather than tput).

So basically terminfo comes equipped with a language that can scan arbitrary addresses for NUL bytes (strlen), copy memory from arbitrary addresses in your program to the terminal, and persist information between library calls and perform basic logic and arithmetic. It lacks loops, which means it is not really Turing complete as such, but that can be worked around by relying on multiple calls to the program and by using the persistent variables to drive control flow through if-then-else constructs. Let’s hope your terminfo entry comes from a trustworthy source.

Compiling terminfo programs

The ncurses implementation of terminfo uses a simple combined lexer-and-interpreter to run the programs. One of my hobbies is compilers, so I decided to do things differently in the text-mode package. I decided to compile the programs.

Let’s have a look at the setab string from the xterm-direct entry:

> (import (text-mode terminfo parser))
> (define setab "\x1b;[%?%p1%{8}%<%t4%p1%d%e48\\:2\\:\\:%p1%{65536}%/%d\\:%p1%{256}%/%{255}%&%d\\:%p1%{255}%&%d%;m")
; Tokenizer output
> (parse-term-string (string->utf8 setab))
((print #vu8(27 91))
 (if)
 (parameter 1)
 (push 8)
 (<)
 (then)
 (print #vu8(52))
 (parameter 1)
 (printf "%d" #f #f #f #\space #f #f #\d)
 (else)
 (print #vu8(52 56 92 58 50 92 58 92 58))
 (parameter 1)
 (push 65536)
 (quotient)
 (printf "%d" #f #f #f #\space #f #f #\d)
 (print #vu8(92 58))
 (parameter 1)
 (push 256)
 (quotient)
 (push 255)
 (bitwise-and)
 (printf "%d" #f #f #f #\space #f #f #\d)
 (print #vu8(92 58))
 (parameter 1)
 (push 255)
 (bitwise-and)
 (printf "%d" #f #f #f #\space #f #f #\d)
 (endif)
 (print #vu8(109)))
; Compiler output
> (expand/optimize (terminfo-expression setab))
(lambda (p dvar svar baudrate lines p1 p2 p3 p4 p5 p6 p7 p8 p9)
  (put-bytevector p #vu8(27 91))
  (if (< p1 8)
      (begin
        (put-u8 p 52)
        (ti-printf p "%d" p1 #f #f #f #\space #f #f #\d))
      (begin
        (put-bytevector p #vu8(52 56 92 58 50 92 58 92 58))
        (let ([v (quotient p1 65536)])
          (ti-printf p "%d" v #f #f #f #\space #f #f #\d)
          (put-bytevector p #vu8(92 58))
          (let ([v (bitwise-and 255 (quotient p1 256))])
            (ti-printf p "%d" v #f #f #f #\space #f #f #\d)
            (put-bytevector p #vu8(92 58))
            (let ([v (bitwise-and 255 p1)])
              (ti-printf p "%d" v #f #f #f #\space #f #f #\d))))))
  (put-u8 p 109)
  (void))

The output from the compiler is ready to be consumed by eval, which in Chez Scheme will generate fast machine code for this program.

The process is a whole lot more complex than it looks. The compiler has to translate stack-based code to direct code, which means that it has to keep track of the argument stack and translate it to procedure arguments and return values. It has to implement if-then-else and handle arguments going into the branches and possibly going out of the branches. On top of that the first two parameters can be mutated and the resulting code should still be efficient.

To make things easier, I relied on cp0 (compiler pass 0). This is a partial evaluator described in Oscar Waddell’s Ph.D. dissertation and is built-in to Chez Scheme. It basically lets my compiler write pretty terrible code, but terrible in a particular good way that cp0 likes. The call to expand/optimize above shows the output after cp0 has done its job.

The first thing the compiler does is to statically analyze the operations in the program to find the required stack size. Taking the %+ operation as an example, it first pops two values and then pushes a value. This means that: the stack has to have room for at least two values, there are two values going in to the operation, and there is one value going out. The concatenative nature of the language makes the analysis simple to perform for any sequence of operation. This analysis is carried out for the whole program, but also for branches in the program.

The stack is made explicit as variables in the generated program. This is key to letting cp0 get rid of the stack completely. Here is the code generated for the program %p1%d before cp0:

(lambda (p dvar svar baudrate lines p1 p2 p3 p4 p5 p6 p7 p8 p9)
  (define (k . x) (if #f #f))
  (let ([p1^ p1] [p2^ p2] [s0 0])
    (let ()
      ((lambda (s0)
         (let ([s0 p1^])
           ((lambda (s0)
              (let ([v s0])
                (ti-printf p "%d" v #f #f #f #\space #f #f #\d)
                (k s0)))
             s0)))
        s0)))
  (if #f #f))

This is lambda soup. The k procedure acts as a continuation in the case when the compiler detects that it can’t generate sequential code for an if-then-else. This is rare, but happens when a branch affects the explicit program state in a bad way. It can be due to either a side-effect in a branch (i.e. %i) or that a branch affects the stack. In these cases the output from the branches has to be passed to the continuation of the program, which is therefore made explicit as a new k procedure. In all examples I looked at, cp0 optimized this quite well.

The program after cp0:

(lambda (p dvar svar baudrate lines p1 p2 p3 p4 p5 p6 p7 p8 p9)
  (ti-printf p "%d" p1 #f #f #f #\space #f #f #\d)
  (void))

Notice that the program before cp0 has an s0 variable. This is the single stack location needed for this program. Pushing a value to the stack is simply done by rebinding s0 to the new value, (let ([s0 p1^]). This binds s0 to p1^, which is the program’s current value of parameter 1. It is different from p1, because incrementing p1 in %i is handled by rebinding p1^ as (+ 1 p1). The mutable program state (s0 in this case) is passed to the rest of the program by application of a procedure that rebinds all state variables and contains the rest of the program, in this case ((lambda (s0) ...) s0).

When popping from the stack, a temporary variable is bound to s0 and the rest of the stack is rebound. The temporary variable is then used in the implementation of the operation, in this case ti-print. Since this example only has one stack slot nothing happens to s0, but otherwise s0 would be rebound to s1, and so on.

This is a lot of rebinding and unnecessary lambdas, but cp0 eats this kind of code for breakfast and transforms it into (most of the times) optimal code. This approach to compiling the programs is made easier by the fact that there is no advanced control flow.

Summary

Down the rabbit hole, indeed. Terminfo has a strangely powerful DSL that specializes in generating escape sequences for terminals. Although ncurses uses an interpreter to run the programs, it is also possible to compile them and get efficient direct code.

Someone clever in a white hat should probably have a look at how good it is that terminfo programs, in the ncurses implementation, can copy arbitrary memory to the terminal. This has not been possible to implement in the Scheme implementation of the same.