Reconstructing Herbert Simon’s Heuristic Compiler: A Guide to Executable Archaeology

Summary

This guide examines Herbert Simon’s Heuristic Compiler, a 1961 IPL-V program that treated programming itself as a problem for General Problem Solver-style means-end analysis. Simon’s design had a State Description Compiler, a Functional Description Compiler, and a General Compiler executive that selected between them. Its objects were routines represented as nested description lists, while IPL words, symbols, states, arguments, and phrases were also encoded as structured data rather than text. Jeff Shrager transcribed the “HEURISTIC CODER 7/16/61” line-printer listing, a deck of about 4,470 cards preserved in the Herbert A. Simon Papers, and ran it in a modern Common Lisp IPL-V interpreter. The restored program reproduces the paper’s INSERT AT END OF VALUE LIST code, the SET SIGNAL MINUS routine, and the assembly and decomposition of the J77 flow diagram. The guide explains how the executive finds differences, selects relevant operators, and recursively constructs prefix and suffix subproblems, as well as how functional descriptions are transformed from already compiled routines. It also documents important qualifications: one print routine and the T1 start card were reconstructed, the English-language front end has not been run, and the listed deck does not compile J3 unless its functional description is removed so the state-description path is selected. The state compiler knows only two operators, and the project still needs proofreading, analysis of pencilled corrections, and reconciliation with Simon’s published example. The guide presents the program as an early experiment in automatic programming and knowledge representation, while preserving Simon’s caution that it was not a practical compiler-construction method.