April 1, 1986

A semicolon in a program line indicates that the rest of the line is acomment.
Lower case letters are converted to upper case on input.

Dr. Landauer:
Enclosed is a description of the time-reversible language JA NUS, along with some sample programs. I showed these to you

B. Parser, and JANUS Language Syntax

briefly when you spoke here last week on physical limits of computation.
JANUS was written by myself and Howard Derby for a classat Caltech in 1982 (or thereabouts). The class had nothing to do directly with this project. We did it out of curiosity over whether suchan odd animal as this was possible, and because we were interested
in knowing where we put information when we programmed. JA NUS forced us to pay attention to where our bits went since none
could be thrown away.
JANUS was fully implemented as described as is bug-free (toour knowledge) despite the disclaimer in the document that it is a“throw-away piece of code.” If it still exists, it is on backup tapes
somewhere at Caltech. Hope you find it interesting.

The recursive descent parser makes use of a SLIMEULA Class forevery node in the parse tree, except for the root node. The root node
is a subroutine which corresponds to the nonterminal Program inthe grammar below. Every other nonterminal corresponds exactly
to a Class of the same name. This correspondence is the reason forthe slightly atypical presentation of the grammar.
The grammar of the JANUS language is as follows:[Terminals in quotes or lower case.
{ }* indicates zero or more repetitions.
[ ] indicates zero or one repetitions.]
Program ::=sincerely,Chris Lutz
IBM Almaden Research Center
K33/801(LUTZ@ALMVMA)

Statements ::=||||||

JANUS: A TIME-REVERSIBLE LANGUAGE
By Christopher Lutz and Howard Derby, circa 1982
JANUS is a compiler and interpreter for the time-reversible
language JANUS. The JANUS compiler is written in SLIMEULA,
and compiles the code into an internal SLIMEULA Class structure
which can be interpreted directly. ‘SLIMEULA’ means SIMULA
running on a DECSYSTEM-20.
JANUS is considered to be a throw-away piece of code. It will
not be maintained and is not purported to be robust.
The compiler consists of four major parts: A lexical analyzer
which tokenizes the input stream and generates a symbol table;
a recursive descent parser made of the Init Code of SLIMEULAClasses; an interpreter which consists of the procedure ’exec’ common to all of the Classes created in the parsing; and the runtime
command scanner.

A.

{ ident [ ’[’ num ’]’ ] }*{ ’PROCEDURE’ ident Statements }*’IF’[ ’THEN’[ ’ELSE’’FI’

Dostmt ::=’FROM’ Expression[ ’DO’
Statements ][ ’LOOP’ Statements ]’UNTIL’ Expression

Callstmt ::=’CALL’ident| ’UNCALL’ ident

Readstmt ::=’READ’ ident

Writestmt ::=’WRITE’ ident

Lvalstmt ::=Lvalue Modstmt| Lvalue Swapstmt

Modstmt ::=’+=’ Expression| ’-=’ Expression| ’!=’ Expression

Swapstmt ::=ident:
An identifier, which is any sequence of letters which is not akeyword. If it has not been encountered before, it is inserted
into the symbol table. An identifier may name a procedure, avariable, or both.

’:’ Lvalue
Minexp| Minexp binop Expression

Minexp ::=’(’ Expression ’)’| ’-’ Expression| ’~’ Expression| Lvalue| Constant

Lvalue ::=ident| ident ’[’ Expression ’]’Constant ::=This article is a part of the personal letter from Christopher Lutz to Rolf
William Landauer in 1986. Under his permission, this article is placed at
http://tetsuo.jp/ref/janus.html as of today (Aug 13, 2010). All
rights belong to Christopher Lutz.

Expression
Statements ]Statements ]Expression

Expression ::=num:
A number, which is any sequence of decimal digits.
binop:
A binary operator, which is any of +, -, ! (exclusive OR), <,>, & (logical AND), | (logical OR), =, # (not equals), <=, >=, *(multiply), / (divide), and \ (remainder).

Statements
Statements
Statements
Statements
Statements
Statements

Ifstmt ::=Lexical Analyzer

The lexical analyzer tokenizes the input stream and sets the global
variables token, token value, and token type in accordancewith the current token. The following terminal classes are recognized:

Ifstmt
DostmtCallstmt
Readstmt
Writestmt
Lvalstmt
nullnum

For every ( ident [ ’[’ num ’]’ ] ) encountered, theparser’s root node (procedure parseprog) creates an instance ofClass dotaarray, which contains an array for the storage corre1

sponding to the variable ident. The array is of size num, and defaults to size 1 when num is not included. A pointer to this class isplaced in the variable column of the symbol table entry for ident.
For every ( ’PROCEDURE’ ident Statements ) encountered,
the root node creates an instance of Class Statements, whichparses Statements. A pointer to this class is placed in the procedure column of the symbol table entry for ident.

C.

Semantics

C.1

Variablestion” results. An error condition could be resolved by reversing thedirection of execution of the program at the point of the attempted
singular operation, but since error conditions are considered abnormal and do not normally happen in “working” programs, therun-time system responds by simply halting execution of the program. This allows examination of the state at the time of the error
condition.
Subscripts out of range are considered an error condition.
C.6 Procedures
All executable statements are contained in exactly one procedure,
which is named by the ident following ’PROCEDURE’. A procedure can be executed in the foreward direction by the ’CALL’ident statement, or in reverse by the ’UNCALL’ ident statement.
Note that the direction of execution is toggled each time ’UNCALL’is used. For example, a procedure which is ’UNCALL’ed from a procedure which is itself ’UNCALL’ed from the top level is executedfrom top to bottom.
Procedures are infinitely recursive, and foreward references areallowed.

Every variable is contained in an array of integers. All arrays are
named by an ident and must be declared in the ( ident [ ’[’num ’]’ ] ) section of the program. The size of the array is num
unless ’[’ num ’]’ is omitted, in which case the size defaults
to 1. Array indices go from zero to arraysize−1. All variables areglobal. In the second part of the program, a reference to ident
without a subscript is equivalent to ident[0]. All variables areinitialized to zero.
C.2

Expressions

C.7 Read and Write

Expressions are evaluated with signed integer arithmetic. The resultof the operators =, *, <, >, <=, and >= is either 0 (for FALSE) or -1(for TRUE). All operators have the same precedence. Expressions
are evaluated from left to right, except for parenthetization. The
unary operators - (negation) and ~ (logical NOT) bind tightly.
C.3

The ’READ’ statement can be considered a swap between a variable
and the outside world. It prints the current value of the variable, andreplaces it with the num typed by the user to the run-time system. If
it is to be time-reversible, when executed backwards, the user must
retype its previous value when it was executed forwards.
The ’WRITE’ statement simply types the value of the variable.

Modification Operators and the Swap Operator

The modification operators (+=, -=, and !=) and the swap operator(:) are the only means for changing the value of variables.
The modification operators evaluate the expression on the right,
and modify the variable on the left according to the operator.
+= adds the expression into the variable. -= subtracts it out. !=exclusive-or’s it in. The expression may not contain the ident of
the variable on the left, since that event could potentially specify asingular operation.
The swap operator swaps the values of the variables on its
left and right. The ident’s of the variables may appear in theexpression in the subscript of neither variable, since that event
could potentially specify a singular operation.
C.4

C.8 Run Time System
The JANUS run time system is provided to allow the user to initialize and inspect variables, call or uncall procedures, and otherwise
control the interpretation of his code. When JANUS is run, it will
respond with the query “file?”, asking for the name of the file tobe parsed. After parsing, JANUS will prompt with “>”. Commands
may be typed to JANUS in either upper or lower case. The commands accepted by JANUS are:var[index]
Prints out the value of var[index]
var
Prints out all elements of array var

Control Structures

Ifstmt is the analog of the conventional IF statement. On entry, the Expression after ’IF’ is evaluated. If it is true (non-zero)then the Statements following ’THEN’ is executed, if there is a’THEN’ clause. Otherwise the Statements after ’ELSE’ is executed, if there is an ’ELSE’ clause. The expression after ’FI’ isthen evaluated an verified to have the same truth as that after the’IF’. If this is not the case, an error condition has resulted, and theprogram halts, returning control to the command interpreter.
Dostmt is the analog of the conventional DO statement. Onentry, the Expression after ’FROM’ is evaluated, and verified tobe true (non-zero). If this is not the case, an error condition hasresulted. The Statements after ’DO’ is then executed, followedby evaluating the Expression after ’UNTIL’. If the expression istrue, the ’DO’ structure is exited. If it is false, the Statements
after ’LOOP’ is executed. The Expression after ’FROM’ is thenreevaluated, and verified to be false (equal to zero) on penalty ofan error conditions. The Statements after ’DO’ is executed again,and control loops in this manner until the ’UNTIL’ expression
is found to be true.
C.5

var=n
Sets var[0] to n.
var[index]=nSets var[index] to n.
CALL nameCalls procedure name.
UNCALL nameUncalls procedure name.
SYMBOLS
Types table of all symbols and their attributes.
TRACETurns on the trace feature. Lists statements as they are executed,
along with the values of any variables that are modified.
UNTRACE
Turns off the trace feature.
RESET
Resets all variables to zero.

Error Conditions and Time-Reversibility

RESET var
Resets all elements of array var to zero.

When an attempt is made to perform an operation that is singular(destroys information and so cannot be reversed) an “error condi2

; Factorization program in the time reversible language Janusnum;Number to factor. Ends up zero
try;Attempted factor. Starts and ends zeroz;Temporary. Starts and ends zeroi;Pointer to last factor in factor table. Starts zerofact[20];Factor table. Starts zero. Ends with factors in ascending orderprocedure factor
from (try=0) & (num>1)
loop call nexttry
from fact[i]#tryloop i += 1
fact[i] += tryz += num/tryz : numz -= num*try
until (num\try)#0
until (try*try)>num
if
thenelsefiifthen;factor num into table in fact[]

num # 1i += 1
fact[i] : num
num -= 1
fact[i] # fact[i-1];Divide out all occurrences of this; factor;Exit early if possible;Put last prime away, if not done; and zero num;Zero tryelsefi(fact[i-1]*fact[i-1]) < fact[i]from (try*try) > fact[i]loop uncall nexttry
until try=0
try -= fact[i-1](fact[i-1]*fact[i-1]) < fact[i]callzeroi;Zero iprocedure zeroi
from fact[i+1] = 0
loop i -= 1
until i = 0
procedure nexttry
try += 2
if
try=4
then try -= 1
fi
try=3
procedure readf
read ifrom z=0loop z += 1
read fact[z]until i=zz -= i;zero z
call zeroi;Load table of factors (to be multiplied by; uncalling procedure factor)

3list[12]perm[12]
ni j;List to sort;Permutation done during sort.
;Number of numbers;Loop counters

Initially the identity permulation

procedure sort;Bubble sort list, permuting perm.
from i=0loop j += n-2
from j=n-2loop iflist[j] > list[j+1]then list[j] : list[j+1]perm[j] : perm[j+1]fiperm[j] > perm[j+1]j -= 1
until j=i-1
j -= i-1
i += 1
until i=n-1
i -= n-1
procedure makeidperm;Add identity permutation to perm. Use to initialize perm
from i=0loop perm[i] += ii += 1
until i=ni -= nprocedure readlist;Use to initialize list by reading each entry from terminalfrom j=0loop read list[i]i += 1
until i=ni -= nnum root

z bit

procedure root;root := floor (sqrt(num))
bit += 1
from bit=1;find exponential ball park
loop call doublebit
until (bit*bit)>num
from (bit*bit)>num
douncall doublebit
if((root+bit)*(root+bit))<=numthen root += bitfi((root/bit)\2) # 0
until bit=1
bit -= 1
num -= root*root
procedure doublebit
z += bit
bit += zz -= bit/24