CS Paper Radar

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

Jeff Shrager, Kent M. Pitman, Mia Golec

cs.AI cs.HCcs.PL ·submitted 2026-10-26 22:09 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Executable Archaeology: Reanimating the Logic Theorist

cs.AI cs.LOcs.PLcs.SC ·2026-11-14 ·David Moews, Jeff Shrager
similarity 0.67
Abstract · This paper builds upon a previous ArXiv paper of a similar name: https://arxiv.org/pdf/2603.13514. This paper is NOT a mere rehash of the pr…

The Logic Theorist (LT), created by Allen Newell, J. C. Shaw, and Herbert Simon in 1955--1956, is regarded by some as the first artificial intelligence program. It was originally simulated by hand and written in a pseudocode called the Logic Language (LL), which was later called Information Processing Language One (IPL-I). LT was revised many times. The first machine-executed version was written in IPL-II and ran on the JOHNNIAC, and a late version was published in 1963 by Einar Stefferud as a pedagogical document and written in IPL-V, the only version of IPL that was formally released to the public. We describe a reanimation of both the IPL-I (LL) version of LT and the 1963 IPL-V version. Comparing the two reanimations illuminates the process of the invention of early AI algorithms and computer languages.

0.25

A Design Theory for AI-Assisted Software Development Derived from Christopher Alexander's Theory of Form

cs.SE ·2026-10-01 ·Chien-Tsun Chen, Yu Chin Cheng
similarity 0.58
Abstract

Code generated by large language models (LLMs) cannot be assumed to meet specified requirements. Reviews, testing, and static analysis still apply, but which of them a sufficient harness needs, and in what role, is open. We propose a design theory derived from Christopher Alexander's theory of form, and a methodology for applying it. In Alexander's account, fit between a form and its context can be perceived only negatively, through the absence of identified misfits. We make the organization's tradition explicit and derive the misfits from it and from the problem's classification. The theory models the LLM as a non-native vernacular builder, trained on many codebases but native to none, whose output tends to drift toward mainstream conventions rather than the local tradition. We engineer four pieces of machinery: explicit representations of the problem (Jackson's problem frames) and of the tradition (a four-form pattern language); deterministic misfit detectors; a fix loop; and a human-gated legislative circuit governing the representations and detectors. We call the resulting methodology, a practice of harness engineering, Misfit-Governed Development (MGD). Its dual-loop process separates an autonomous inner loop, where the LLM iterates against the gates, from a human outer loop, where specifications are judged against the world. Together they form the S = P = T = W assurance model (specification, program, tests, world), whose equals signs name relations, not identity. We report evidence from building and rebuilding a Scrum system of four event-sourced aggregates from 64 problem-frame specifications, verified by about 1,300 generated tests and 28 blocking gates, one applying 188 rules. This addresses the generativity dimension of Alexander's 1996 OOPSLA challenge. The moral dimension, whether the specification still fits the world, requires human judgment and belongs to the outer loop.

0.33

Hypothesis-guided discovery of cognitive algorithms via program refinement

cs.AI ·2026-10-01 ·Huiwen Alex Yang, Mark K. Ho, Bill D. Thompson
similarity 0.54
Abstract

Developing cognitive models of algorithmic reasoning from behavioral data is a central problem in cognitive science that challenges current methods. Traditional approaches to cognitive modeling are interpretable and benefit from human expertise, but lack flexibility and scalability. Emerging techniques using large language models (LLMs) for de novo generation of cognitive models are scalable and flexible, but lack a role for human expertise and have mostly been applied to simpler tasks than algorithm recovery. We propose a hybrid system that treats discovery of cognitive algorithms as a program refinement problem. Human-created cognitive models are expressed as probabilistic programs and provided to a system of LLM agents with a mandate to: identify mismatches between model and behavior; propose code-level modifications within researcher-specified constraints; and verify structural fidelity. Revisions propagate to a probabilistic inference module that performs inference for latent variables and data likelihood computations. We evaluate the pipeline on human behavior in a problem-solving paradigm that exposes a variety of cognitive algorithms. Revised models consistently improve model fit relative to ancestral models and reveal a small set of recurring innovations that capture meaningful behavioral variability in this task.

0.26

Ceci n'est pas une pipe -- Toward a Symbolic Solver for the Abstraction and Reasoning Corpus Using Evolutionary Computation

cs.AI ·2026-11-10 ·Luca Favole, Giorgio Mongardi, Giovanni Squillero, Alberto Tonda
benchmark similarity 0.53
Abstract · Submitted to the ARC Prize 2026 Paper Track (Fairly Symbolic)

The Abstraction and Reasoning Corpus (ARC) is a benchmark designed to assess the capability of Artificial Intelligence (AI) systems to generalize starting from a few samples, a task humans excel at. The ARC-AGI contests held since 2020 have been the focus of intense competition, with participants proposing approaches ranging from traditional symbolic AI to Transformer architectures. Despite a long history of successes, evolutionary algorithms (EAs) were notably absent from the approaches appearing in the main contest. As score-and-search program synthesis approaches, EAs suffer from issues related to choosing the proper representation in the Domain-Specific Language applied to the problem (for example, pixel-level or object-level), and distinguishing between two candidate solutions producing the same outputs. In this work, we present the first fully symbolic, evolutionary-based program synthesis approach submitted to the ARC-AGI-2 main contest. The main contributions are: evolving the grid parser and the output projector together with the program that transforms the grid, so that a task-specific language emerges during program synthesis; grounding the symbols the parser can extract in core knowledge theory from cognitive psychology; and an object-aware fitness that grades partially correct outputs beyond pixel-level discrepancies.

0.10

Instructions Are Evidence, Not Objectives: Measuring Outcome Alignment of Agents

cs.AI cs.SE ·2026-10-13 ·Kaiming Liu, Yuxuan Liu, Jinrui Ju, Minyuan Ruan, Xuanyu Lei +2 more
benchmark similarity 0.53
Abstract

Large language model agents can follow complex human instructions to solve real-world tasks. In practice, however, initial instructions are often incomplete. In our analysis of 100 user-agent trajectories from SWE-chat, 56\% of initial instructions omit requirements that later emerge as necessary, and 52\% of the useful follow-up requirements could have been inferred from the project. A user states requirements from their own understanding of the task, and these \textbf{stated requirements} often differ from the \textbf{true requirements} that completing the task imposes. An agent should therefore treat the instruction as evidence rather than as the objective, inferring the true requirements from the instruction and the environment and satisfying them even when the user is not yet aware of all of them. We call this ability \textbf{outcome alignment}. In this work, we construct \textbf{TiGanEval}, a benchmark of software engineering and research tasks. In every task the user genuinely lacks part of the requirements, each requirement stays discoverable from the code and runtime behaviour of the environment, and requirements the agent infers are separated from those the user adds after observing delivered work. These properties together make outcome alignment measurable. Evaluating eight frontier models including GPT-5.6-Sol, we find outcome alignment broadly missing: the models lose 53 to 67 points of success rate when moving from the full specification to the partial instruction, and consequence feedback across four submissions does not close the gap. Furthermore, a plan-mode harness cannot compensate for the missing ability of the model itself, which places outcome alignment among the abilities the next generation of models should be developed for.

0.18

Humans vs. Machines: A Comparison With AI Agents in Software Reverse Engineering

cs.SE cs.AI ·2026-10-10 ·Samuele Doria, Stefano De Rosa, Ruoyu Wang, Zion Leonahenahe Basque, Eleonora Losiouk +1 more
similarity 0.53
Abstract

Can an autonomous AI agent reverse engineer a binary as well as a skilled human analyst? Do they adopt the same strategy, and can agents scale to real-world programs? We compare human and LLM-based software reverse engineering (SRE): nine models tackle two compact static-analysis challenges previously solved by human analysts, scored with a common understanding rubric, and we record their complete interactions with IDA Pro. This lets us compare not only what humans and agents recover, but also how they investigate a binary. The best agents (GPT-5.5 Pro, Claude Opus 4.8, and Kimi K3) achieve statistically human-competitive understanding on both tasks, while weaker models remain far behind. Ablations show that the gap depends on code representation and workflow demands, not on model capability alone: open-weight models improve substantially with richer code representations, whereas frontier models show no significant change. Similar success rates hide different workflows. Humans repeatedly revisit functions and follow local program structure; strong agents jump across the binary, retrieve information broadly, and rarely return to inspected code, a behavior we call greedy fetching. This strategy is not fixed: given semantically richer code, agents fetch less without losing understanding. Because greedy fetching aggregates large amounts of code in the agent's context, we measure context-window saturation across 4,000 real-world binaries: large windows accommodate many programs, but larger applications and lower-level representations quickly exhaust them. Autonomous reverse engineering is becoming competitive, with a large speed advantage, but scaling it will require better navigation, selective retrieval, and persistent analysis state, not merely larger context windows.

0.24

EvolveScaler: Synthesizing Information-Evolution Contexts via Executable State Machines and Natural-Language Rendering

cs.AI cs.SE ·2026-09-08 ·Ziliang Zhao, Zenan Xu, Shuting Wang, Zhao Wang, Bowen Cao +4 more
similarity 0.53
Abstract

In persistent interactions, long contexts may encode an evolving process rather than a fixed record: later events can revise or revoke earlier information, changing what remains valid and what conclusions follow. We call this setting information evolution (IE). Solving IE requires identifying valid records, applying updates in order, and reconstructing the query-relevant state from the event history. Existing text-first synthesis pipelines make such data difficult to verify because state transitions and answer logic remain implicit. We introduce EvolveScaler, a code-driven framework that defines information evolution before rendering it as natural language. Human-authored operational specifications define state transitions, record validity, difficulty controls, and executable answer logic; a strong LLM then synthesizes a self-contained simulator from each specification. Executing validated simulators produces natural-language multi-turn event histories, while deterministic replay computes reference answers and atomic checklists. We instantiate EvolveScaler with 117 task prototypes and 159 final-question operators across five difficulty levels spanning approximately 7 to 1,200 events per instance, yielding about 35,100 training examples and 585 validated evaluation instances. On the very_long tier, the strongest model reaches 59.3% avg@5, while six models score below 10%. Training an internal A3B model on 6,000 EvolveScaler examples improves performance over its base checkpoint on all eight independently constructed out-of-distribution benchmarks, with a 5.25-point average gain. These results show that code-driven IE synthesis provides both challenging evaluation and transferable training supervision.

0.14

Knowledge as Code

cs.SE ·2026-10-20 ·Martin Monperrus
similarity 0.53
Abstract

For millennia, knowledge has been carried by language, and large language models still put language at the center. Yet the coding agents built on these models mostly write code. This paper is a contribution to epistemology, which asks what kind of knowledge code is and how it is obtained. We define knowledge as code as knowledge written in a programming language or in a machine-parsable data format, whose validity can be checked by executing it. We define thirteen epistemic properties of knowledge media and show that code is the first medium to have all of them. We distinguish two ways in which knowledge enters code, encoding and learning by execution, where code is both the experiment and the record of its result. Agents make learning by execution observable, since their trajectories record every probe, observation and line of code they keep. Code is thus not only a tool of knowledge work but a knowledge medium in its own right, the first that can check what it holds.

0.24