The Short Story

A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it?

The Long Story

Tarjan is known for many accomplishments, including the fact that he was the coinventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.

All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:

• Dijkstra's Guarded Command Language


• SETL


• ALGOL

I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.

An example of a function written in Tarjan's language is shown below:

heap function mesh (heap nodes h1, h2);

 if key(h1) > key(h2) → h1 ⟷ h2 fi;

 right (h1) := if right(h1) = null → h2

 |right(h1) ≠ null → mesh (right(h1), h2) fi;

 if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;

rank (h1) := rank(right(h1)) + 1;

return h1,

end mesh;

I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, MATLAB and many others.

Table of Contents

I will divide my explanation of Tarjan's pseudocode into the following sections:

1. 
   Tarjan's If-else Blocks (the -> & | operators)


2. 
   Assignment and Equality Tests (:= and =)


3. There is else if, but no else construct


4. 
   Tarjan's Conditional Assignment Operator := if



5. Additional Examples of Tarjan's if and := if
   
   5.5.
   Tarjan Arrays (or Lists)




6. Summary of Operators



7. Tarjan's Double-pointed Arrow Operator (⟷)


8. Tarjan's do-loops are like C/Java while-loops


9. Tarjan's Conditional-assignment operator with all false conditions

(1) Tarjan's If-else Blocks

(the operators → and | )

The if-else construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator -> (or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.

For example, in Tarjan's language we might have:

# Example One
if a = 4 → x := 9 fi 

If we partially translate the line of Tarjan code above into C or Java, we get the following:

if (a = 4)
 x := 9
fi 

Instead of a right curly braces (as in C and Java) Tarjan ends an if-block with an ALGOL-like backwards spelling of the key-word: fi

If we continue translating our above example, we get:

if (a = 4) 
 x := 9

(2) Assignment and Equality Tests (:= and =)

Tarjan takes these operators from ALGOL (later also seen in Pascal).

Tarjan uses = for equality tests, not assignments (so it works like Java ==).

For assignment, Tarjan uses :=, which works like Java =.

Thus, if we continue translating our example, we have:

if (a == 4) 
 x = 9

A vertical bar (or "pipe" or |) in Tarjan's language is equivalent to the else if keyword in C or Java.

For example, in Tarjan's language we might have:

# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi 

The Tarjan-code above translates to:

if (a == 4) 
 x = 9

else if (a > 4) 
 y = 11

(3) else if only and no else construct

Earlier, I covered the basics of if-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else block must always contain an arrow (→) operator. As such, there is no else in Tarjan's language, only else if. The closest thing to an else-block in Tarjan's language is to make the rightmost test-condition true.

if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi

In C/Java, we would have:

if (a == 4) 
 x = 9


else if (a > 4) 
 y = 11

else // else if (true)
 z = 99
 

Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:

if condition
 → stuff to do
 | condition
 → stuff to do
 [...] 
 | condition 
 → stuff to do
fi 

The character | is like if else

The character → separates the test-condition from the stuff-to-do.

(4) Tarjan's Conditional Assignment Operator := if

Tarjan's if can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if. Somewhat confusingly, Tarjan still uses the notation/syntax if for the second type of if-construct. Which if is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if is always pre-fixed by an assignment operator.

For example, we might have the following Tarjan code:

# Example Three
x := if a = 4 → 9 fi 

Begin Digression

After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:

x := if (a = 4) → 9 fi 

a = 4 is not an assignment operation. a = 4 is like a == 4 -- it returns true or false.

End Digression

It can help to think of := if as syntax for a single operator, distinct from := and if In fact, we will refer to the := if operator as the "conditional assignment" operator.

For if we list (condition → action). For := if we list (condition → value) where value is teh right-hand-side value we might assign to the left-hand-side lhs

# Tarjan Example Four
lhs := if (a = 4) → rhs fi 

in C or Java might look like:

# Example Four
if (a == 4) 
 lhs = rhs

Consider the following example of "conditional assignment" in Tarjanian code:

# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi

In C/Java, we would have:

// C/Java Instantiation of Example Five
if (a == 4) 
 x = 9

else if (a > 4) 
 x = 11

else if (true) // else
 x = 99
 

(5) Summary of Operators:

So far, we have:

• := ...... Assignment operator (C/Java=)




• = ...... Equality test (C/Java ==)




• → ...... Delimiter between test-condition of an if-block and the body of an if-block




• | ..... C/Java else-if




• if ... fi ..... if-else block




• := if... fi ..... Conditional assignment based on an if-else block

(5.5) Tarjan Lists/Arrays:

Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else statements.

list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array

Tarjan array elementa are accessed with parentheses (), not square-brackets

Indexing begins at 1. Thus,

list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true 

Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]

nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]

The equality operator is defined for arrays. The following code prints true

x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)

Tarjan's way to test if an array is empty is to compare it to an empty array

arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment

One can create a view (not copy) of a sub-array, by providing multiple indices to operator () combined with ..

list3 := ["a", "b", "c", "d"]

beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"

end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"

mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"

# `list3(4)` is valid, but `mid(4)` is not 

(6) Additional Examples of Tarjan's if and := if

The following is another examples of an Tarjan conditional assignment (:= if):

# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d) 

(true --> b) is the leftmost (cond --> action) clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b

Below is our most complicated example of Tarjan code thus far:

# Tarjan Example -- merge two sorted lists

list function merge (list s, t);

return if s = --> t
 | t = [ ] --> s
 | s != [ ] and t != and s(l) <= t(1) -->
 [s(1)]& merge(s[2..], t)
 | s != [ ]and t != [ ] and s(1) > r(l) -->
 [t(1)] & merge (s,t(2..))
 fi
end merge;

The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.

list merge (list s, list t) { 

 if (s is empty) 
 return t;
 
 else if (t is empty)
 return s;
 
 else if (s[1] <= t[1]) 
 return CONCATENATE([s[1]], merge(s[2...], t));
 else // else if (s[1] > t[1])
 return CONCATENATE ([t[1]], merge(s,t[2..]);
 

Below is yet another example of Tarjan-code and a translation in something similar to C or Java:

heap function meld (heap h1, h2);

 return if h1 = null --> h2
 | h2 = null --> h1
 | h1 not null and h2 not null --> mesh (h1, h2) 
 fi
end meld;

Below is the C/Java translation:

HeapNode meld (HeapNode h1, HeapNode h2) 

 if (h1 == null) 
 return h2;
 
 else if (h2 == null) 
 return h1;
 else 
 mesh(h1, h2)
 
 // end function

(7) Tarjan's Double-pointed Arrow Operator (<-->)

Below is an example of Tarjan code:

x <--> y 

What Does a Double Arrow (⟷) Operator Do in Tarjan's Language?

Well, almost all variables in Tarjan's Language are pointers.
<--> is a swap operation. The following prints true

x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true

After performing x <--> y, x points to the object which y used to point to and y points to the object which x used to point to.

Below is a Tarjan statement using the <--> operator:

x := [1, 2, 3]
y := [4, 5, 6]
x <--> y 

Below is a translation from the Tarjan code above to alternative pseudocode:

Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to; 

Alternatively, we could have:

void operator_double_arrow(Array** lhs, Array** rhs) 

 // swap lhs and rhs

 int** old_lhs = 0;
 old_lhs = lhs;
 *lhs = *rhs;
 *rhs = *old_lhs;
 return;


int main() 

 Array* lhs = new Array<int>(1, 2, 3);
 Array* rhs = new Array<int>(4, 5, 6);
 operator_double_arrow(&lhs, &rhs);
 delete lhs;
 delete rhs;
 return 0;
 

Below is an example of one of Tarjan's functions using the ⟷ operator:

heap function mesh (heap nodes h1, h2);
 if key(h1) > key(h2) → h1 ⟷ h2 fi;
 right (h1) := if right(h1) = null → h2
 |right(h1) ≠ null → mesh (right(h1), h2)
 fi;

 if rank (left (h1)) < rank (right (h1))
 → left(h1) ⟷ right(h1)
 fi;

 rank (h1) := rank(right(h1)) + 1;
 return h1;
end mesh;

Below is a translation of Tarjan's mesh function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷ operator works.

node pointer function mesh(node pointers h1, h2) 

 if (h1.key) > h2.key) 

 // swap h1 and h2
 node pointer temp;
 temp = h1;
 h1 = h2;
 h2 = temp;
 

 // Now, h2.key <= h1.key 

 if (h1.right == null) 
 h1.right = h2;

 else // h1.key != null 
 h1.right = mesh(h1.right, h2);
 



 if (h1.left.rank < h1.right.rank ) 
 // swap h1.left and h1.right

 node pointer temp;
 temp = h1;
 h1 = h2;
 h2 = temp;
 

 h1.rank = h1.right.rank + 1;
 return h1;
 

(8) Tarjan's do-loops are like C/Java while-loops

Tarjan's language if and for constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do. All do-loops end with the keyword od, which is the backwards spelling of do. Below is an example:

sum := 0
do sum < 50 → sum := sum + 1 

In C-style pseudocode, we have:

sum = 0;
while(sum < 50) 
 sum = sum + 1;

The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true) with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:

sum = 0;
while(true) 
 if (sum < 50) 
 sum = sum + 1;
 continue;
 // This `continue` statement is questionable
 
 break;

Below, we have a more complicated Tarjan do-loop:

sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5

C/Java-style pseudocode for the complicated Tarjan do-loop is as follows:

sum = 0;
while(true) 

 if (sum < 50) 
 sum = sum + 1;
 continue;
 
 else if (sum < 99) 
 sum = sum + 5;
 continue;
 
 break;

(9) Tarjan's Conditional-assignment operator with all false conditions

Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.

Notably, when the conditional assignment operator := if is used, and no condition is true, I am not what value is assigned to the variable.

x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi

I am not sure, but it is possible that no assignment is made to x:

x = 0;
if (false) 
 x = 1;

else if (false) 
 x = 2;

else if (99 < 2) 
 x = 3;

// At this point (x == 0)

You could require that the left-hand-side variable seen in an := if statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.

Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null value, and store null in the left-hand argument of the assignment.