MIXAL

MIXAL (MIX Assembly Language) is the assembly language of MIX, a computer that Donald Knuth invented for The Art of Computer Programming (TAOCP). MIX was never built as a commercial product. It is a fully specified paper machine, created so that Knuth could present algorithms as real machine-level programs and count exactly how much time and memory they use. From the first volume of TAOCP in 1968 until the MMIX transition began decades later, MIXAL was the language in which one of the most influential works in computer science expressed its programs.

History & Origins

In January 1962, Addison-Wesley asked Knuth, then a graduate student in mathematics at Caltech, to write a book on compiler design. He proposed something far larger, a survey of the fundamental algorithms of programming. Writing the first volume took most of the 1960s, while Knuth also worked as a consultant to Burroughs. In the preface he thanks Burroughs for the use of the B220 and B5500 computers on which most of the programs were tested.

Knuth needed a way to state algorithms precisely enough to analyze their running time. High-level languages hid the costs he wanted to measure. Choosing any one real machine would tie the book to a single manufacturer and to hardware that would soon be obsolete. His answer was to design an idealized machine that resembled the computers of the day, “but, perhaps, nicer”, in Knuth’s words, and to write every program for it.

Fundamental Algorithms appeared in 1968. Section 1.3 introduces MIX and MIXAL, and the rest of the series is built on them.

The name

MIX is the Roman numeral for 1009. Knuth explained the number with a joke. He took sixteen real computers that were “very similar to MIX and on which MIX could easily be simulated” and averaged their model numbers with equal weight:

⌊(360 + 650 + 709 + 7070 + U3 + SS80 + 1107 + 1604 + G20 + B220
  + S2000 + 920 + 601 + H800 + PDP-4 + II) / 16⌋ = 1009

The same number, he added, “may also be obtained in a simpler way by taking Roman numerals.” The list also records which machines Knuth thought of as MIX’s peers: IBM, UNIVAC, CDC, Burroughs, Philco, Honeywell, DEC and others.

Design Philosophy

Binary and decimal

The most unusual design decision in MIX is that it is deliberately vague about its own number base. A MIX byte must hold at least 64 distinct values (6 bits on a binary machine) and at most 100 (two decimal digits on a decimal machine). A program that never relies on more than 64 values per byte runs the same on both. Knuth described the idea this way: MIX programmers do not actually know whether they are programming a base-2 or a base-10 machine, so algorithms written in MIX carry over to either kind with little change. In 1968 binary and decimal machines were both in wide commercial use, and this choice kept the book neutral between them.

A 1960s word machine

MIX is an accumulator machine with sign-magnitude arithmetic, typical of its time:

Every instruction fits in one word with four parts: a signed two-byte address, an index byte naming which rI register to add to the address, a modification byte (usually a field specification), and an operation code byte.

Instructions with known costs

Each MIX instruction has a fixed execution time in abstract units, u. A load or add takes 2u, a multiply 10u, and a divide 12u. These timings let Knuth state a program’s running time as an exact formula in terms of how often each instruction runs. Building that analysis into the language was the central purpose of MIX.

Key Features of MIXAL

Field specifications

The most distinctive feature of MIX is the partial field. Most memory instructions take a suffix (L:R) that selects bytes L through R of a word, where byte 0 is the sign. LDA X(1:3) loads only bytes 1-3 of X, and STA X(4:5) stores into just the last two bytes. This makes packed records and bit fields easy to handle without separate shift-and-mask instructions.

Assembler conveniences

MIXAL is a small symbolic assembler, and Knuth gave it several features that keep listings readable:

• Pseudo-operations: EQU defines symbols, ORIG sets the location counter, CON assembles a constant word, ALF assembles five characters, and END ends the program and names its entry point.
• The location counter *, as in JMP * or JGE *+3.
• Literal constants written between equals signs, such as =1000=. The assembler places the constant in memory for you.
• Local symbols 0H through 9H, referenced as 2B (“the nearest 2H backward”) or 2F (“the nearest 2H forward”). They remove the need to invent names for every small loop.

Self-modifying subroutine linkage

MIX has no stack and no return instruction. A jump stores the address of the next instruction in rJ. The subroutine then patches its own exit instruction, storing rJ into the address field of a jump at its end. Knuth’s Program M from Section 1.3.2, which finds the maximum of an array, shows the idiom:

X       EQU  1000
        ORIG 3000
MAXIMUM STJ  EXIT        Subroutine linkage: save return address
INIT    ENT3 0,1         k <- n
        JMP  CHANGEM
LOOP    CMPA X,3         Compare X[k] with current maximum
        JGE  *+3
CHANGEM ENT2 0,3         j <- k
        LDA  X,3         m <- X[k]
        DEC3 1           k <- k - 1
        J3P  LOOP        Repeat while k > 0
EXIT    JMP  *           Return; address filled in by STJ

STJ EXIT writes the caller’s return address into the address field of the final JMP *, so control returns to the caller when execution reaches it. Self-modifying code like this was common practice on 1960s machines, and MIX keeps it.

Hello, World

The following program is the “hello world” from the GNU MDK documentation. It sends the block starting at MSG to the typewriter terminal (unit 19); the first four words of that block hold the message:

TERM    EQU    19          the MIX console device number
        ORIG   1000        start address
START   OUT    MSG(TERM)   output data at address MSG
        HLT                halt execution
MSG     ALF    "MIXAL"
        ALF    " HELL"
        ALF    "O WOR"
        ALF    "LD   "
        END    START       end of program

In Knuth’s original definition, MIXAL is written in fixed card columns and the five characters of an ALF operand are given unquoted. Modern implementations such as GNU MDK and 9front’s mix accept free-form fields and require the quotes, as above.

Evolution

The core MIX machine stayed essentially the same through all three editions of Volumes 1-3 (1968-1998). Volume 2 adds optional extensions: floating-point instructions for the chapter on arithmetic, and a set of binary-only operations described in Section 4.5.2 (SLB, SRB, JAE, JAO, JXE, JXO). GNU MDK added those binary-only instructions in its 1.2.9 release in December 2015.

By the 1990s the machine’s age was showing. Nothing in 1990s hardware looked like a six-bit, sign-magnitude, accumulator-based, self-modifying design. In the third edition of Volume 1 (1997), Knuth wrote that MIX had become “quite obsolete.” In 1999 he introduced MMIX, a 64-bit RISC machine with its own assembler, MMIXAL. MMIX was published as Volume 1, Fascicle 1, in 2005 and is intended to replace MIX in future editions. The large job of translating the existing MIX programs was taken on by volunteers and completed in book form by Martin Ruckert’s The MMIX Supplement (2015). Until the fourth edition of Volume 1 appears, the printed volumes still present their programs in MIXAL.

Implementations

MIX is simple and fully documented, so simulating it has long been a popular exercise. Knuth’s TAOCP web pages have pointed readers to MIX simulators, and many independent implementations exist. Notable ones include:

• GNU MDK. José Antonio Ortega Ruiz released version 0.1 on 31 October 2000. It became an official GNU package with 0.3 (March 2001), gained a GTK interface (gmixvm), Guile scripting (mixguile), and an Emacs debugger interface, and has been actively maintained. Version 1.3.0 (October 2020) moved the GUI to GTK+ 3, and version 1.3.1 followed in September 2025. Debian ships it as the mdk package.
• Emacs mixal-mode. It was written by Pieter Pareit for MDK 1.0.1 (2003) and later merged into GNU Emacs (reportedly from Emacs 22).
• 9front mix(1). An assembler and interactive emulator in the 9front Plan 9 distribution, installed as games/mix.
• Hardware::Simulator::MIX. A Perl simulator module on CPAN.
• mix-fpga. Michael Schröder’s 2021 implementation of MIX in FPGA logic for the Lattice iCE40 family.

There is no official Docker image for MIXAL. On Debian or Ubuntu, apt install mdk provides mixasm and mixvm.

Current Relevance

Nobody writes production software in MIXAL, and nobody ever did. Its role has always been to explain. That role is shrinking as TAOCP moves to MMIX, but it has not ended. The printed Volumes 1-3 that sit on many programmers’ shelves still present their algorithms in MIXAL, so readers who work through the exercises still assemble and run MIX programs, usually with GNU MDK. Retro-computing and hardware hobbyists also keep implementing the machine, sometimes in real logic.

Why It Matters

MIXAL is probably the most widely studied assembly language for a computer that was never manufactured. Knuth’s decision to write his algorithms for a concrete, timed machine rather than in pseudocode is a large part of what made TAOCP rigorous. Running times could be stated as exact formulas instead of loose estimates. The choices in MIX also preserve the 1960s in miniature: hedging between binary and decimal, sign-magnitude words, partial-field access, and self-modifying return addresses. MIX’s replacement by MMIX in turn shows how quickly computer architecture moved between 1968 and 1999.

Sources: MIX (abstract machine), Wikipedia, The Art of Computer Programming, Wikipedia, GNU MDK, GNU MDK NEWS (release history), jao: “two decades of gnu mdk” (31 Oct 2020), 9front mix(1), mix-fpga on GitLab, The MMIX Supplement (Pearson).