Janus: a reversible programming language born at Caltech

Janus appeared in 1982 as a programming language designed to run computations in both forward and backward directions. The language was created at Caltech by Christopher Lutz, Howard Derby, Tetsuo Yokoyama, and Robert Glück. Unlike most imperative languages that only move time forward, Janus treats every computation as reversible — meaning the machine can undo its own steps.

Core design: global store and 32-bit integers

Janus programs operate on a global store without heap allocation. The language deliberately avoids dynamic data structures in its core form, though later variants added support for lists and other structures. All values in Janus are 32-bit integers. In the theoretical specification, these integers are non-negative, ranging from 0 to 4294967295. The TOPPS interpreter, however, uses standard two's complement 32-bit integers, so values there range from −2147483648 to 2147483647. Every variable starts at 0, and the language carries no type information because the integer format is fixed.

Syntax: declarations and statements

Janus syntax follows Backus-Naur form. A program consists of a sequence of variable declarations, then a sequence of procedure declarations. Variable declarations can define a simple variable or a one-dimensional array. Array sizes have no theoretical upper bound, but the TOPPS interpreter requires at least one element.

Procedure declarations begin with the keyword "procedure" followed by a unique identifier and a statement block. The entry point of a program is a procedure named "main". If no main exists, the last procedure in the text becomes the entry point.

Statements in Janus cover several forms. Assignments move values between variables using modification operators. A swap expression ( "<=>" ) exchanges two variables and is trivially reversible. Conditional statements require both a test and an assertion — the test must hold before the then-branch, and the assertion must hold after. In the inverted program, these swap roles. Loop constructs similarly need an assertion on entry and a test on exit, with the ability to run extra work after the test turns false. Procedure calls execute a procedure forward; uncall runs it backward. Procedures have no parameters; all data passing happens through side-effects on the global store.

Expressions consist of constants (integers), variables, indexed array elements, or binary operations. Binary operators in Janus resemble their C counterparts: +, -, ^, *, /, %, &, |, &&, ||, >, <, =, !=, <=, >=. Modification operators, a subset of binary operators, must be bijective — meaning each input maps to a unique output — which makes them invertible. The inverse of "+" is "-", the inverse of "-" is "+", and the inverse of "^" is "^".

Reversibility: the core constraint

For an assignment to remain reversible, the variable on the left-hand side must not appear in any expression on either side of the assignment. This constraint proves that Janus's inference system is both forward and backward deterministic. Without it, undoing a computation would yield multiple possible histories, breaking reversibility.

The 2007 formalization and implementations

Tetsuo Yokoyama and Robert Glück formalized Janus's operational semantics in 2007, including a program inverter and an invertible self-interpreter. The TOPPS research group at DIKU made a Janus inverter and interpreter freely available. A Prolog implementation followed in 2009. An optimizing compiler exists within the RC3 research group for reversible computing.

Fibonacci example demonstrates loop inversion

The Wikipedia article includes a Fibonacci procedure written in Janus. The procedure uses a from-do-until loop structure. The loop's assertion (i = n) holds only before the first iteration, and the test (i = 2) becomes true only after the last iteration when n > 2. The body increments a Fibonacci calculation using addition and a swap operation.

The inverse of this procedure reverses the loop by swapping the assertion and test, reversing the statement order, and inverting each statement. In the inverse direction, the loop starts at i = 2 and increments toward n, undoing the forward computation. This transformation shows how Janus programs can be mechanically inverted at the language level.

Why reversibility matters

Reversible computing promises energy efficiency since no information is discarded during computation. Janus provides a concrete implementation where every forward step has a corresponding backward step. The language's design constraints — no heap allocation, fixed integer width, and the LHS variable restriction — ensure that inversion remains possible without complex runtime support. Researchers have explored Janus as a model for understanding how to build practical reversible systems, though widespread hardware support remains limited.

Janus stands as an early example of a reversible programming language that gave the research community a working model long before reversible hardware became a realistic goal. Its influence appears in later work on reversible semantics, self-interpreters, and optimizing compilers for the paradigm.