Branch Forward Only

Indeed, if memory serves (it's been a while since I read about this)...
The fly-by-wire flight software for the Saab Gripen (a lightweight fighter) went a step further. It disallowed both subroutine calls and backward branches, except for the one at the bottom of the main loop. Control flow went forward only. Sometimes one piece of code had to leave a note for a later piece telling it what to do, but this worked out well for testing: all data was allocated statically, and monitoring those variables gave a clear picture of most everything the software was doing. The software did only the bare essentials, and of course, they were serious about thorough ground testing.

No bug has ever been found in the "released for flight" versions of that code.

A quote from John Carmack on Inlined Code. I'm interested in hearing more about that style of programming, and any programming language that facilitates that style.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


There is Statically Allocated Parallel Functional Language (SAFL) by Mycroft and Sharp that also enforces this style:

  • All allocations are static.
  • All loopy code is tail call optimized.

It doesn't quite guarantee progress (i.e. a loop could diverge), though it probably could with some extra analysis.

Also, while not yet suitable for 'performance' concerns...

I've developed a simple functional bytecode, ABC, that lacks any jumps, neither forward nor backward. Bytecode is evaluated in one direction. But ABC can represent first class functions - a finite 'block' of code. Conditional behavior is expressed by conditional application of a block, and loopy code via a simple fixpoint combinator.

ABC was developed to support streamable code, ability to express applications (and full virtual environments) as append-only logs, and easily share and distribute both behavior and data. Performance wasn't a primary concern, though I have strategies that should make it competitive long term.

Bitcoin scripting language uses the same rule.

Bitcoin supports a scripting language that allows coins to be spent only when a script runs and produces a positive result. The usual script just checks that the transaction spending it is signed with a private key that matches the public-key signature on the coins.

Satoshi Nakamoto (designer of Bitcoin) initially had a forth-ish stack language for the scripting. Hal Finney demonstrated several attacks that would be enabled by subroutines and/or back branching - they ranged from locking problems and race conditions to excessive resource consumption of CPU, bandwidth, and/or memory. Bitcoin went live with all back branch and subroutine enabling instructions removed from the scripting language. So there can be jumps forward (sections of code can be skipped) but no jumps backward. Every subsequent instruction in serialization order is also a subsequent instruction in execution order.

"Single-loop code"

This is a pretty common compilation strategy for synchronous dataflow languages. The mathematical idea is that you can represent an arbitrary stream transducer f : Stream(Input) -> Stream(Output) as a state machine, with an initial state s : S and a transition function step : S * Input -> S * Output.

So the generated code for f has a single while loop, which waits for inputs, and runs the body of the loop implementing the step function to incrementally produce outputs. Marc Pouzet has some slides describing how this works here.

Single-loop code has subroutine calls

Hi Neel,

I agree that this looks quite similar to the so-called "single-loop compilation" of Lustre-like languages. However, modern Lustre compilers generate backward branches in the guise of subroutine calls (for modularity) or bounded loops (for array iterators à la map/fold).


Purely of historical interest, the first paper of which I'm aware which touches on this issue is from just over half a century* ago:

Corrado Böhm et Guiseppe Jacopini, « Flow diagrams, Turing Machines and Languages with only Two Formation Rules », CACM v9n5, 1966

(* early enough that it's written in the language of flowcharts, and I have difficulty following the arguments. WP suggests that the "single while loop" is a folk version of their result, and probably predates it, going back to [computer] antiquity)

other contents of the same issue, a pair which may have aged more gracefully: « a note on "program structures for parallel processing" » and « Additionally comments on a problem in concurrent program control » and one which probably is also now purely of historical interest: « 11/16" perforated paper tape ».

historical footnote: PLCs and PIMs

A related historical footnote: the early (1960s) PLC used this "no backward branches" approach to achieve hard real time performance.

We evolved this approach (I worked for Dick Morley, the "father" of the PLC, from the mid-1970s) in several machines into the 2000s, such as the PIM with it's massively parallel real time architecture and proprietary Paracell language. In the PIM there are tens of thousands of threads that are "systolically" synchronized and all free of backward branches, other than the frame (PLC "scan"). These machines are still deployed, including a few large installations for the Shinkansen, described here and here.