PaperlayerView exact revision on arXiv

Source-linked AI summary

Executable Archaeology of Programs That Model Programming: Reanimating the Heuristic Compiler (1961) and KBEmacs (1984)

Jeff Shrager, Kent M. Pitman, Mia Golec

arXiv:2610.36341v1cs.AIcs.HCcs.PL

TL;DR

The paper examines how two historical programs made programming itself a subject of computation, an issue relevant to understanding how programming knowledge is represented in AI coding tools. It reanimates the Heuristic Compiler and KBEmacs from historical code, reproducing published outputs while revealing both overlap in their theories and limits in the recovered systems.

  • Problem

    Modern AI coding tools are far more capable, but their programming knowledge is largely implicit, while explicit, executable accounts of how people program are scarce.

    Source: §1 · p. 2, §7 · p. 12

  • Method

    The paper reanimates the Heuristic Compiler and KBEmacs by running recovered code, examining their structured routine representations and cliche-based adaptation mechanisms.

    Source: §3.2 · pp. 4–5, §7 · p. 12

  • Results

    The recovered programs reproduce Simon’s published examples and KBEmacs’s 1984 SQRT sequence, with KBEmacs generating matching code that runs.

    Source: §7 · p. 12

  • Takeaways & Limitations

    Executable reanimation makes the systems’ programming mechanisms available for examination and testing, but matching historical behavior does not establish that their theories are correct.

    Source: §7 · p. 12

    The recoveries are partial: the Heuristic Compiler’s English front end lacks the input sentences needed to run, and KBEmacs had only a few dozen cliches.

    Source: §2.2 · p. 4, §6 · p. 11

Abstract

from arXiv · show

Early AI programs were often also theories of how people think, and programs that wrote programs were, in part, theories of how people program. Here we report on the reanimation of two such programs that offer two seemingly different theories of programming and were developed for quite different purposes. The first, Herbert Simon's Heuristic Compiler (1961), was an experimental model of programming as problem-solving, applying the means-ends analysis methods of the General Problem Solver to investigate the nature of the programming task. The second, KBEmacs (1984), was a working prototype of an intelligent programming assistant developed by MIT's Programmer's Apprentice project, built on the view that expert programmers recognize and combine familiar patterns, or "cliches." It let a programmer build up programs by combining cliches through a stylized English command language. We approach both through the methodology of Executable Archaeology, the study of historical computational systems by running their original code, a process we call "reanimation." Our reanimation of the Heuristic Compiler reproduces the compiled code appearing in Simon's 1963 paper, and our reanimation of KBEmacs reproduces the SQRT sequence of its December 1984 self-test. Examined side by side, the two theories turn out to have much in common: the Heuristic Compiler also works by adapting existing routines, and Simon later argued that search alone requires a large body of programming knowledge. To highlight the reflexivity of this project, we deliberately used a modern AI-assisted programming tool, Anthropic's Claude Code (Opus 5.5), to carry out much of the detailed reanimation work, building on a significant base of existing software. The explicit, executable theories of programming that both systems embodied are largely absent from today's far more capable AI coding assistants.

1 Introduction

The paper examines two historical programs as explicit theories of how people program: Simon’s Heuristic Compiler models programming as problem-solving, while KBEmacs builds programs from familiar cliches. It reanimates both systems to compare their mechanisms and their relevance to questions addressed by modern AI coding tools.

1 Introduction

  • The Heuristic Compiler treats programming as a problem-solving task, applying means-ends analysis to reduce differences between a routine as it stands and the desired routine.Simon’s system searches for differences and applies operators to reduce them.Source: §1 · p. 2
  • KBEmacs lets programmers describe desired programs in stylized English, then combines cliche proto-code to build them.Its approach resembles theories that expert programmers work from reusable plans rather than first principles.Source: §1 · p. 2
  • The two systems address questions also faced by modern AI coding tools, including how tasks are specified, where programming knowledge resides, and how human and machine work is divided.Source: §1 · p. 2
  • The study reanimates the programs by running code transcribed from historical listings on emulation stacks close to the originals, with much of the work carried out using Claude Code.The Heuristic Compiler was run on an IPL-V interpreter; KBEmacs ran under a Zetalisp compatibility layer.Source: §1 · p. 2

2 Historical Background

The historical background traces two approaches to programming assistance: Simon’s Heuristic Compiler applied means-ends analysis to programming, while the Programmer’s Apprentice project developed cliches, plans, and a division of labor between programmer and assistant.

2.1 The Heuristic Compiler

  • The Heuristic Compiler applied means-ends analysis, a proposed cognitive skill, by repeatedly finding differences between present and desired objects and applying relevant operators.Source: §2.1 · p. 3
  • Simon’s aim was to investigate the nature of programming, not to build a practical compiler; he later described systems based on heuristic search as “almost toy systems.”Source: §2.1 · p. 3

2.2 The Programmer’s Apprentice

  • The Programmer’s Apprentice framed cliches as standard computational methods with fixed structures, plans as hierarchical flowcharts, and the assistant’s role as handling routine details while the programmer makes design decisions.These ideas were aligned with theories of expert programmers’ reusable programming plans.Source: §2.2 · p. 3
  • KBEmacs realized the Apprentice ideas in a working editor that could build and modify programs within its available cliches, but it knew only a few dozen where a practical tool would need many hundreds.It was a research prototype and was later mothballed.Source: §2.2 · pp. 3–4

3 Reanimating the Heuristic Compiler

The Heuristic Compiler represents routines as structured descriptions and uses compilers as operators in a means-ends loop. Its functional-description compiler adapts existing routines, and the reanimated system reproduces Simon’s published compiled code, with a reported exception requiring a repair to the recovered deck.

3.1 The Listing

  • The recovered Heuristic Compiler source is a 1961 line-printer listing containing an executive, two compilers, an English front end, an IPL-V knowledge base, and a code renderer.The listing is about 4,470 lines across 94 pages.Source: §3.1 · p. 4

3.2 Everything Is a Description List

  • Routines are represented as IPL-V description lists whose attributes encode possible definitions, states, flow diagrams, and code; the program transforms these structures and renders IPL-V text at the end.Source: §3.2 · p. 4
  • The executive selects a compiler based on the closest available definition and tests for improvement; the state-description compiler classifies cell-state differences and recursively compiles subproblems using LOAD and REPLACE operators.The executive gives up if a routine has not improved, with no failed-path handling or backtracking.Source: §3.2 · pp. 4–5
  • The functional-description compiler searches previously compiled routines for a matching process and adapts one to new arguments, including recursively compiling described computations.It also generates argument-fetching code and instructions to save and restore working cells.Source: §3.2 · p. 5

3.3 Running the Heuristic Compiler

  • The reanimated compiler produced the published code for INSERT AT END OF VALUE LIST; a J3 result required removing its functional description so the state-description compiler could proceed.The recovered state compiler uses described states, unlike the bare-symbol representation reported for the 1963 listing.Source: §3.3 · p. 5

J13 INSERT (1) AT END OF THE VALUE-OF THE ATTRIBUTE (0) OF (2)

The reanimation reproduces the state-description compilation result and reconstructs a routine’s flow diagram from its segments. A recovered-deck quirk means reproducing the published J3 result required removing its functional description.

J13 INSERT AT END OF VALUE LIST

J3 SET SIGNAL MINUS

  • The state-description compiler assembles J3 as 10J3 20H5 0, matching the code in Simon’s paper.It uses REPLACE for the named-cell change and LOAD for the prefix subproblem.Source: J13 INSERT (1) AT END OF THE VALUE-OF… · p. 6
  • The recovered deck did not initially compile J3 because its functional description took precedence and failed without a fallback to the state description.Removing the functional description lets the state-description compiler produce the published code.Source: J13 INSERT (1) AT END OF THE VALUE-OF… · p. 6

Flow diagrams

4 Reanimating KBEmacs

The reanimation uses a transcribed KBEmacs source listing and reconstructs its cliche-based workflow through plans and a compatibility layer. Replaying the SQRT self-test reproduces the 1984 generated code, though the reanimation targets only the headless core.

4.1 The Listings

  • The reanimation source is a January 1985, four-volume Zetalisp printout; its 1984 self-test reports three successful and three failed command sequences.The successes were HASH, SQRT, and SUMLIST; BUCKET, DELETE, and MEMQ failed.Source: §4.1 · p. 7

4.2 Text and Plans

  • KBEmacs represents cliches as plans describing segments, ports, data and control flow, and roles, then converts plans back into text after commands.The two-way translation keeps text and plan consistent when the programmer edits either representation.Source: §4.2 · p. 7, Figure 2 · p. 7

4.3 Running KBEmacs (headless)

  • KBEmacs depends on Lisp Machine software, so the reanimation uses a modern Common Lisp compatibility layer rather than a usable environment for this release.The layer accommodates missing Zetalisp and Lisp Machine functionality and behavior differences.Source: §4.3 · p. 8
  • The reanimation targets KBEmacs’s headless core, leaving out the editor, windows, actors, and Ada and PL/I front ends.The compatibility layer was debugged against SQRT; five other self-test sequences remain as possible next tests.Source: §4.3 · p. 8
  • The SQRT sequence builds two programs in fourteen commands, combining three cliches and filling their roles to complete a 32-segment plan.The second program is a variant with an extra parameter.Source: §4.3 · pp. 8–9
  • All fourteen SQRT commands parse correctly, and the generated programs equal the 1984 code and run successfully.(mysqrt 2.0) returns 1.4142157.Source: §4.3 · p. 9, Figure 3 · p. 9

5 Then and Now: Two Historical Systems and Today’s AI Coding Assistants

The historical systems and modern coding assistants differ technically, but they raise related questions about task specification, programming knowledge, human-machine responsibilities, and progress checking. The older systems used explicit representations and reusable routines, while modern assistants combine learned models with conventional program components.

5 Then and Now: Two Historical Systems and Today’s AI Coding Assistants

  • The Heuristic Compiler and KBEmacs are not direct technical ancestors of modern AI coding assistants, though they address recognizable questions about AI-assisted programming.The historical systems use explicit proto-programs or cliches and internal code representations; LLMs use numerical networks and program text.Source: §5 · p. 9
  • Simon distinguished state descriptions from functional descriptions, and KBEmacs adopted the functional approach through named cliches.Simon described functional descriptions as more natural and powerful at higher levels; modern assistants accept both functional prompts and tests.Source: §5 · pp. 9–10
  • Both systems rely on reusing known solutions, but their knowledge stores were limited: the Heuristic Compiler had two state operators or required a previously compiled routine, and KBEmacs had a few dozen cliches.Waters estimated a practical tool would need many hundreds of cliches; the paper describes LLMs as a vast implicit cliche library without an explicit, inspectable representation.Source: §5 · p. 10
  • The Heuristic Compiler was a computational experiment, whereas KBEmacs was designed as a noninvasive assistant that left design decisions to the programmer and handled routine details.The Programmer’s Apprentice approach treated the boundary between human and system responsibility as a central design question.Source: §5 · p. 10
  • The Heuristic Compiler’s means-ends loop applies a compiler, checks for improvement, and stops at the goal or when progress ceases; modern coding agents use a recognizable iterative architecture.Modern harnesses use tests rather than hand-coded state comparisons, while learned models choose actions and interpret results and conventional programs compile, execute, compare, and track changes.Source: §5 · pp. 10–11
  • Both historical systems reason from explicit internal representations, whereas modern assistants’ neural-network representations are not readily interpretable as explicit plans or cliches.KBEmacs also re-analyzes hand-edited code to keep the code and plan consistent; Waters reported that well over half its effort went into an analyzer and coder.Source: §5 · pp. 9, 11

6 Technical Next Steps

The technical next steps concern unfinished recovery work in both systems. The Heuristic Compiler’s English front end remains uncertain, and KBEmacs has been debugged against only one self-test sequence.

6 Technical Next Steps

  • The Heuristic Compiler’s English front end—including its scanner, dictionary, parser, and parse-to-functional-description routine—remains an undiscovered part of the system.Running these routines requires input sentences that are absent from the listing.Source: §6 · p. 11
  • The Heuristic Compiler’s front-end routines may be the linguistic components H. S. Kelly credited, but running them requires input sentences not present in the listing.Source: §6 · p. 11
  • KBEmacs’s compatibility layer was debugged against only the SQRT sequence, whose fourteen commands build MYSQRT and MYOTHERSQRT; the remaining five self-test sequences are a next step.Further possibilities include implementing Ada and PL/I front ends to reproduce the UNIT-REPAIR-REPORT demonstration, or connecting KBEmacs to modern Emacs.Source: §6 · p. 11

7 Conclusion

The reanimations recover two explicit, executable accounts of programming, and show that the systems’ apparently different theories overlap. Their historical behavior can be examined and tested again, but reproducing it does not establish that the theories are correct.

7 Conclusion

  • The Heuristic Compiler’s functional compiler adapted already-compiled routines, bringing its means-ends account closer to KBEmacs’s cliche-based account; Simon also argued that search needs indexed operators and higher-level strategies.Source: §7 · p. 11
  • The recovered programs reproduce Simon’s published examples and KBEmacs’s 1984 SQRT sequence, generating historically matching code that runs for KBEmacs, but this does not validate the underlying theories.The recoveries are partial; they make the described mechanisms executable, examinable, and testable rather than known only through prose.Source: §7 · p. 12
  • Much reanimation work used a modern AI coding assistant, highlighting a contrast between its largely implicit programming knowledge and the historical systems’ explicit accounts.The paper argues that understanding how a system programs requires being able to reason about how it does so, which requires representation.Source: §7 · p. 12

8 Code Availability

The project makes its reanimation materials and guides available as open source. The repositories include or link to original source scans.

8 Code Availability

  • The transcriptions, interpreters, compatibility layer, and guides to both programs are open source.Source: §8 · p. 12
  • The project’s repositories contain the original source scans or provide links to them.Source: §8 · p. 12
  • The materials are hosted in repositories for Executable Archaeology and KBEmacs.Source: §8 · p. 12

Author Contributions and Use of AI

The authors divide archival research, software development, historical verification, and revision across the team. AI systems performed most of the programming work, with the authors directing and verifying the work.

Author Contributions

  • Shrager directed the project and IPL-V interpreter work; Golec selected and scanned the Heuristic Compiler listing; Pitman supplied KBEmacs scans and compatibility guidance.Shrager and Golec also worked in the Simon and Newell archives, and Pitman was a member of the original KBEmacs team.Source: Author Contributions and Use of AI · p. 12

Use of AI

  • AI systems performed most programming work: ChatGPT transcribed listings, while Claude Code adapted software, reanimated both programs, and drafted the paper.The authors checked claims against listings, program runs, and historical sources, and take responsibility for the final text.Source: Author Contributions and Use of AI · p. 12
  • The reanimations used about 1,500 Claude Opus 5.5 calls, 1,600 tool invocations, and six hours of active machine time, excluding ChatGPT’s KBEmacs scan extraction.Claude also adapted the IPL-V interpreter and Common Lisp ports of Spice Lisp Flavors and LetS, and developed the KBEmacs compatibility layer.Source: Author Contributions and Use of AI · p. 12

About the Authors

The authors bring backgrounds in cognitive science, computing, biology, technology development, and public policy, alongside work on historical and archival projects.

Jeff Shrager

  • Shrager is a cognitive scientist, computer scientist, and molecular biologist who is developing CogLean and serves as Chief Scientist of Bennu Climate.CogLean is described as a Lean-based library of formal components for proving claims about cognitive models.Source: About the Authors · p. 15

Kent M. Pitman

  • Pitman has worked on technologies spanning hypertext, symbolic algebra, programming languages, document formatting, and web services.He was involved in design and development of those technologies.Source: About the Authors · p. 15

Mia Golec

  • Golec studies Ethics, History, and Public Policy and Decision Science at Carnegie Mellon, and assists with research and University Archives projects.Source: About the Authors · p. 15

Related papers

Loading 2610.36341v1…