Source-linked AI summary
Programming with a Differentiable Forth Interpreter
Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, Sebastian Riedel
TL;DR
The paper asks how neural networks can exploit procedural knowledge when training data is scarce. It introduces ∂4, a differentiable Forth interpreter with sketches whose unspecified behavior is learned from input-output data. The system learns sorting, addition, and natural-language quantity reasoning, achieving state-of-the-art accuracy for the latter task.
Problem
The central problem is incorporating partial procedural knowledge into neural networks when training data is scarce.
Method
∂4 is a differentiable Forth abstract machine that lets programmers specify sketches while learning underspecified transition behavior through backpropagation.
Results
∂4 learns sorting, addition, and word algebra reasoning from sketches and input-output pairs, achieving state-of-the-art end-to-end reasoning about quantities in natural-language narratives.
Takeaways & Limitations
Forth sketches provide a procedural prior that complements learned behavior for tasks requiring low-level input representations and higher-level reasoning.
Takeaways & Limitations
The approach can become unstable when backpropagation unrolls large numbers of machine states, particularly for quadratic-time sorting executions.
Abstract
from arXiv · showhide
Given that in practice training data is scarce for all but a small set of problems, a core question is how to incorporate prior knowledge into a model. In this paper, we consider the case of prior procedural knowledge for neural networks, such as knowing how a program should traverse a sequence, but not what local actions should be performed at each step. To this end, we present an end-to-end differentiable interpreter for the programming language Forth which enables programmers to write program sketches with slots that can be filled with behaviour trained from program input-output data. We can optimise this behaviour directly through gradient descent techniques on user-specified objectives, and also integrate the program into any larger neural computation graph. We show empirically that our interpreter is able to effectively leverage different levels of prior program structure and learn complex behaviours such as sequence sorting and addition. When connected to outputs of an LSTM and trained jointly, our interpreter achieves state-of-the-art accuracy for end-to-end reasoning about quantities expressed in natural language stories.
1. Introduction
The paper addresses how neural networks can use procedural knowledge when training data is scarce. It introduces differentiable Forth sketches that combine programmer-specified structure with learned behavior and support sorting, arithmetic, and natural-language quantity reasoning.
- 1. Introduction: The framework targets scarce-data settings where programmers know program structure or subroutines but must learn unspecified algorithmic details.This motivates exploiting varied forms of prior knowledge when learning algorithms.
- 1. Introduction: The approach injects procedural background knowledge into neural networks by fixing part of a program's behavior while learning the remainder from data.The resulting neural programs remain consistent with the sketch while being optimized against training data.
- 1. Introduction: ∂4 implements Forth's abstract machine as a differentiable neural interpreter whose underspecified sketch behavior can be trained by backpropagation.It is differentiable with respect to machine transitions and distributed input representations.
- 1. Introduction: Forth sketches encode different degrees of prior knowledge, including general recursive structure for sorting, and can generalize to unseen input sizes from input-output pairs.The experiments also connect ∂4 to an upstream LSTM for word algebra reasoning.
- 1. Introduction: ∂4 achieves state-of-the-art end-to-end reasoning about quantities in natural-language narratives when trained jointly with an LSTM.The system reads narratives, extracts numerical quantities, reasons over them, and answers mathematical questions without explicit intermediate representations.
2. The Forth Abstract Machine
Forth represents computation as transitions over a simple stack-based abstract machine. The paper uses this structure as the basis for program execution and sketches with learned transition behavior.
- 2. The Forth Abstract Machine: The Forth machine state contains data and return stacks, a heap for random memory access, and a program counter.The data stack stores values for manipulation, while the return stack supports return pointers and subroutine calls.
- 2. The Forth Abstract Machine: Forth is chosen because its modular control structures and simple abstract machine permit a straightforward continuous approximation.The language is general-purpose, close to machine code, and supports branching, loops, and function calls.
- 2. The Forth Abstract Machine: Forth programs are sequences of words, each defining a transition between machine states at the current program counter.Words include language keywords, primitives, and user-defined subroutines.
- 2. The Forth Abstract Machine: The Bubble sort example factors common control flow around alternative comparison or stack-manipulation behaviors represented by the PERMUTE and COMPARE sketches.The listing distinguishes common lines from alternative-specific lines for the three implementations.
3. ∂4: Differentiable Abstract Machine
∂4 represents Forth program execution as a differentiable recurrent abstract machine, allowing fixed transition functions and trainable slots to operate over continuous stacks, heap, and program-counter state.
- 3. ∂4: Differentiable Abstract Machine: ∂4 models Forth execution as an RNN whose transition functions and inputs are differentiable, enabling gradient-based learning of underspecified program behaviour.The RNN executes program transitions while preserving differentiability with respect to program code and inputs.
- 3.1. Machine State Encoding: The continuous machine state contains differentiable data and return stacks, a heap, and a program-counter attention vector over the low-level sketch code.Stack pointers support differentiable push and pop operations, while the program counter indicates the currently executed word.
- 3. ∂4: Differentiable Abstract Machine: A Forth sketch is a sequence of continuous transitions combining neural Forth words with trainable slots that fill underspecified program behaviour.Users define slots through state encoders and decoders, which determine how machine state is observed and modified.
- 3.3. The Execution RNN: At each execution step, ∂4 applies every program function to the current state and combines their next states using the program-counter components as attention weights.When no slots are present and values are one-hot, the final RNN state corresponds to symbolic execution.
- 3.4. Optimisations: Symbolic execution collapses branch-free sequences of Forth words into single transitions, reducing the cost of interpreting the program one word at a time.This optimization derives a transition from the difference between the initial and symbolically executed machine states.
- 3.5. Training: Training minimizes masked cross-entropy between predicted and target final data-stack states and pointers, with slot parameters optimized by backpropagation.The mask excludes stack components that are outside the relevant stack depth, and intermediate-state supervision can also be included.
4. Experiments
The experiments evaluate ∂4 on sorting, addition, and word algebra, varying how much procedural structure sketches provide. Across these tasks, the sketches generalize beyond training lengths and achieve the highest reported CC-dataset result without data augmentation.
- Sorting: The sorting sketches encode the outer recursive loop while learning either both permutation and comparison behavior or only the comparison.The COMPARE sketch supplies more prior structure than PERMUTE, leaving fewer behaviors to learn.
- Sorting: ∂4 learns to sort 64-element sequences perfectly after training only on sequences of length two and three, whereas Seq2Seq performs near chance on longer sequences.Both sketches under-perform when trained on length-four sequences because of computational difficulties; COMPARE performs better because it imposes more structure.
- Addition: The addition sketches specify recursive control flow and learn the digitwise carry-and-sum operation from data.CHOOSE directly specifies carry and result-digit outputs, whereas MANIPULATE learns behavior that directly manipulates the machine state.
- Addition: Both addition sketches generalize to all tested sequence lengths, while Seq2Seq fails to generalize beyond training lengths.MANIPULATE requires more data to train perfectly, and both sketches also succeed when trained on length-24 inputs and tested up to length 128.
- Word Algebra Problems: ∂4 slightly outperforms Seq2Seq on the CommonCore word-algebra dataset and achieves the highest reported result without data augmentation.Unlike the baselines, it predicts answers directly from input-output pairs without an explicit intermediate formula representation.
5. Discussion
The discussion identifies computational difficulty as the main challenge of faithfully simulating the abstract machine. Greater procedural structure can improve learning, but long machine-state executions create training instability.
- Computational Challenges: Quadratic machine executions make sorting difficult to train because backpropagation through long unrolled RNN sequences causes instability and failures.Sorting length four produces 120 machine states, while addition is easier because its underlying execution is shorter.
- Scope of Generalization: Although ∂4 can generalize perfectly to arbitrary sequence lengths after learning the correct sketch behavior, modest training lengths can still expose computational difficulties.The limitation arises from the size of the underlying machine-state execution rather than from the stated generalization capability.
- Role of Prior Knowledge: Higher prior knowledge improves successful learning: COMPARE performs better on longer sorting sequences, and softmax over manipulated memory enables perfect MANIPULATE training for addition.These observations connect sketch structure and memory treatment with training success in the reported experiments.
6. Related Work
The paper relates ∂4 to program synthesis, probabilistic programming, differentiable abstract structures, and neural compilation. Its distinctive contribution is using a differentiable interpreter for an actual programming language to inject procedural priors.
- Probabilistic and Bayesian Programming: ∂4 resembles probabilistic programming through its learned sketch slots, but trains slot behavior with gradient descent rather than posterior inference.The comparison is framed around how each framework handles underspecified program behavior.
- Neural Approaches: Prior neural approaches approximate data structures, abstract machines, or code execution, whereas ∂4 implements a differentiable abstract machine for Forth.The paper distinguishes this from Autograd, which computes gradients for Python code without differentiable access to an underlying abstract machine.
- Program Synthesis: Unlike program-synthesis approaches that induce code, ∂4 focuses on injecting programmer-specified procedural knowledge into neural computation.The sketches leave selected transition behaviors to be learned from data while retaining the programmer’s specified structure.
- Neural Compilation: The authors present ∂4 as the first working neural implementation of an abstract machine for an actual programming language, enabling straightforward procedural-prior injection.This positions the work as a bridge between neural interpreters and language-compilation research.
7. Conclusion and Future Work
The paper presents ∂4 as a differentiable Forth abstract machine that learns unspecified behavior in program sketches using program input-output pairs. It reports successful sorting, addition, and word-algebra reasoning, while identifying broader NLP applications and non-differentiable transitions as future directions.
- ∂4 learns unspecified behavior in Forth sketches from program input-output pairs, complementing programmers’ prior procedural knowledge.
- The ∂4 RNN successfully learns to sort and add and solve word algebra problems using program sketches and input-output pairs.
- Future work targets machine reading, knowledge-base inference, and integration of non-differentiable transitions from real-environment interaction.
A. Forth Words and their implementation
The implementation provides a differentiable subset of Forth words and executes programs through data and return stacks, control flow, subroutines, and heap operations. A Bubble sort example illustrates how these components manipulate stack state during recursive execution.
- ∂4 implements Forth words across data-stack, heap, comparator, return-stack, control-flow, subroutine, and variable-creation groups.
- Table 4 defines the stack and memory terminology used for Forth words, including TOS, NOS, DSTACK, RSTACK, and HEAP.
- Table 5 implements the described Forth words with fixed-address variable allocation and inlined MACRO words.
- In the Bubble sort example, SORT pushes the input sequence and length, then repeatedly calls BUBBLE through a DO loop.
- BUBBLE uses stack duplication, comparison, conditional swapping, return-stack storage, decrementing, and recursive calls to process the sequence.
- After the loop completes, SORT drops the sequence length and leaves the ordered sequence [7 4 2 2] on the data stack.
C.1. Accuracy per training examples
The learned sketches benefit from stronger procedural structure and generalize to longer sequences, whereas Seq2Seq generalizes poorly beyond its training length. On addition, both sketches achieve perfect length generalization from 256 examples.
- After 256 training instances, COMPARE and PERMUTE learn correct Bubble sort behavior and generalize equally well, although PERMUTE initially tests worse.
- Stronger COMPARE structure quickly maximizes training accuracy, showing that additional prior knowledge benefits optimization.
- Seq2Seq trained on length 3 generalizes only to that length and achieves no more than 45% when tested on length 8.
- Both addition sketches perfectly generalize from 256 examples trained on length 8 to inputs of length 16, while Seq2Seq reaches only 19.7% under the same test setting.
- The addition Seq2Seq baseline reaches 98% only when trained and tested on length 8, using 16384 examples.
C.2. Program Code Optimisations
The paper evaluates symbolic-execution and if-branch interpolation optimizations for Bubble sort across input lengths. These optimizations produce large relative runtime improvements over non-optimized ∂4 code.
- Symbolic execution and interpolation of if-branches yield large relative runtime improvements over non-optimized ∂4 Bubble sort code.
- The runtime comparison uses ten repeated Bubble sort runs on sequences of varying length with and without the proposed optimizations.
- The PERMUTE sketch assumes recursive BUBBLE calls, termination at length 1, and a learned transformation of the current length and top stack elements.
- Figure 2 traces ∂4 execution using a program counter, partially filled data and return stacks, and one-hot representations of stack contents and pointers.
E. Experimental details
The experiments use task-specific training setups, with dataset sizes and optimization settings varying across sketch-based and baseline models. The Permute and Compare experiments used especially small development and test sets because of sketch complexity.
- Sketch parameters were trained with Adam, gradient clipping at 1.0, gradient noise, and random-search tuning of learning rate, batch size, and noise parameters.
- Seq2Seq baselines used single-layer 50-dimensional LSTMs and were trained for 500 Adam epochs with batch size 128, learning rate 0.01, and gradient clipping.
- Permute and Compare sketches used 256 training, 32 development, and 32 test instances, with the small development and test sets attributed to computational complexity.
- Batch size varied between 64 and 16 depending on problem size, with an initial learning rate of 1.0 for the corresponding experiments.
- Addition Choose and Manipulate sketches used 512 training, 256 development, and 1024 test instances with batch size 16 and initial learning rate 0.05.
- The Common Core dataset contained 300 training, 100 development, and 200 test questions, with batch size 50, learning rate 0.02, 75-dimensional word vectors, and a stack of width 150 and size 5.
Analysis on BubbleSort of PC traces
BubbleSort program-counter traces show the differentiable sketch progressing from unstable execution to learned permutations that follow the intended control flow and halt correctly. The trace visualizes recursive calls, returns, sorting calls, and the final halting command.
- Analysis on BubbleSort of PC traces: After a few training epochs, ∂4 learns better permutations, enabling crisp program-counter decisions and halting in the correct state.
- Analysis on BubbleSort of PC traces: Early training deviates from the one-hot program-counter representation, and ∂4 fails to determine the next word after two SORT iterations.
- Analysis on BubbleSort of PC traces: Figure 6 traces recursive BUBBLE calls, recursion returns, SORT calls, and the final halting command across training stages.
- Word Algebra Problem sketch: The complete WAP sketch manages heap buffers and pointers for question, representation, and number data before executing its stack operations.
- Word Algebra Problem sketch: The WAP sketch's core operations permute data-stack numbers, choose arithmetic operators, and optionally swap intermediate results using representations on the return stack.
- Word Algebra Problem sketch: The sketch concludes by emptying the return stack after the learned operations are executed.