MUNCH and Munching Squares on the MIT CADR

Conclusion

MUNCH is an interactive CADR implementation of Munching Squares, a classic point-display hack associated with the PDP-1. It is a graphics demonstration, not a file utility or part of the Lisp evaluator. A 16-bit parameter controls the order in which a simple XOR relation visits a 256 by 256 field; changing that parameter yields the moving squares, lattices, and related patterns for which the hack is known.

The contemporary Lisp Machine Manual describes LMIO; HACKS more generally as a holding place for useful functions whose organization had not yet been settled. The later LM-3 tree turns MUNCH into a named menu demo, but that later presentation should not be projected backward onto System 46.

The public sources preserve two useful CADR layers:

The System 303 source is the better guide to the version exposed by the current LM-3 tree. The System 46 source remains important historical evidence for the earlier CADR implementation. They share the same plotting core but are not the same program text.

Historical identity

The System 303 demo description identifies Munching Squares as “a classic display hack from the PDP-1” in demo/munch.lisp.17. This agrees with HAKMEM, MIT AI Memo 239: item 146 reports a very small display program thought to have been discovered by Jackson Wright on the RLE PDP-1, and item 147 characterizes the display as successive views of Y = X XOR T.

That is evidence for the hack's earlier identity, not for authorship of either Lisp Machine port. Neither inspected CADR source file names its porter or author. The attribution to Jackson Wright should therefore attach to the reported PDP-1 hack, not automatically to the preserved CADR code.

The common plotting engine

Both CADR implementations maintain a 16-bit accumulator and a 16-bit parameter. In equivalent modern notation, each point is:

accumulator = (accumulator + parameter) mod 65536
x = accumulator & 0xff
t = (accumulator >> 8) & 0xff
y = x XOR t
pixel[x, y] = pixel[x, y] XOR 1

The exact System 46 loop appears in hacks.189, lines 290-298. Its 177777 and 377 literals are octal masks for 16 and 8 bits, and LDB 1010 selects the other 8-bit field. The System 303 rewrite retains the same operations in MUNCH-BITS-PANE :DO-MUNCHING.

The code toggles an existing pixel instead of merely setting it. This matters: a second visit removes a point. Parameter changes reset the accumulator and clear the plot, making each selection a fresh traversal.

The LM-3 System 303 presentation

The LM-3 tree's HACKS system loads MUNCH as a dedicated demo module alongside the older miscellaneous hacks in OHACKS; see sys/sysdcl.lisp.200. Once that system is present, Munching Squares is available from HACKS:DEMO and as HACKS:MUNCH.

The System 303 window has four panes:

• an octal parameter display labeled Munching Squares;
• a centered 256 by 256 plotting pane;
• a 16-position graphical switch register; and
• persistent keyboard help.

The pane construction and font selection are explicit in demo/munch.lisp.17, lines 185-256. The displayed number is formatted in octal. The switch pane uses FONTS:TOG, can be changed with the mouse, and groups bits visually by alternating glyph colors. The reusable switch mixin identifies TOG character codes 060/061 as one off/on switch pair, 062/063 as a second-color pair, and 101 through 104 as indicator lights; the source does not expand the font name TOG. See demo/munch.lisp.17, lines 1-25.

The compact System 46 implementation

The 1980 System 46 HACKS version operates in the selected terminal rather than a four-pane frame. It clears the terminal, installs a 16-switch display, prints the current value at the top, and plots until a hardware character becomes available. Its setup and input loop are preserved in hacks.189, lines 190-298.

This version temporarily installs CPTFONT and 43VXMS, using 43VXMS explicitly for the current numeric value. Its switch-register helper loads TOG when necessary and chooses glyphs from the font according to each bit's value and display color; see CREATE-SWITCH-REGISTER. The museum's recovered public specimens are the 43VXMS sheet and TOG sheet.

The older dispatch supports BREAK, ESCAPE, digits, CLEAR, +, shifts, FORM, ?, and a row of bit-toggle keys. There are unresolved discrepancies between that dispatch and its printed help: the help says SPACE increments where the visible branch tests +, describes an M operation where the source tests character octal 025, and advertises CIRCLE-PLUS single stepping without a corresponding explicit branch. These may reflect stale help or keyboard-encoding behavior, but static source inspection cannot choose between them. Runtime testing on the preserved keyboard paths remains a TODO.

The HAKMEM helper

Both versions define NHNWSNOOB, expanded by their source comment as “next higher number with same number of one bits.” It isolates the lowest set bit, carries that bit left, then moves the remaining changed bits to the low end. The implementation matches Bill Gosper's HAKMEM item 175 and special-cases zero to zero. In MUNCH this lets a user move among parameters with the same binary population count, often changing pattern geometry without changing how many switches are on.

MUNCHING-TUNES is a separate sound demo. The System 303 menu describes it as computer-composed music based on the Munching Squares algorithm, but it computes beep frequencies and does not call the screen MUNCH function. Its source is adjacent in demo/ohacks.lisp.39.

Preservation record

The System 46 observations use the public mietek/mit-cadr-system-software snapshot at Git commit 8e978d7d1704096a63edd4386a3b8326a2e584af:

The recovered media inventory dates HACKS source versions 188 and 189 to 27 July 1980 and the preserved QFASL to 31 July 1980. That ordering does not by itself prove which exact source produced the compiled file.

The LM-3 observations use the public sys Fossil repository's system-303 check-in, 4df393c68d7f083ce42d5c377039d26043cc18a9:

System 303 is a maintained LM-3 restoration branch, not a synonym for the System 46 snapshot. Claims above are attached to the source generation that supports them.

Open questions

• Who wrote or ported the System 46 and later window-system CADR implementations?
• How do the contradictory System 46 help keys behave with each emulated historical keyboard path?
• What effects were intended by the recommended constants beyond what static arithmetic demonstrates?
• Does the current System 303 world reproduce every drawing and pause behavior in the checked-in source? No runtime comparison was performed for this article.

Sources

• M. Beeler, R. W. Gosper, and R. Schroeppel, HAKMEM, MIT AI Memo 239, 1972, especially items 146, 147, and 175; the searchable programming-hacks transcription is useful for navigation.
• MIT CADR System 46, LMIO1; HACKS 189, with dates from the recovered media inventory.
• Lisp Machine Manual, HACKS introduction.
• LM-3 sys Fossil repository, System 303, DEMO; MUNCH 17.

Last verified: 2026-07-17.