How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?
Table of Contents

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


Tarjan's If-else Blocks (the -&gt; &amp; | operators)        
Assignment and Equality Tests (:= and =)           
There is else if, but no else construct
Tarjan's Conditional Assignment Operator := if     
Additional Examples of Tarjan's if and := if
5.5.
Tarjan Arrays (or Lists)
Summary of Operators
Tarjan's Double-pointed Arrow Operator (⟷)
Tarjan's do-loops are like C/Java while-loops
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 -&gt; (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 &gt; 4  → y := 11 fi 


The Tarjan-code above translates to: 

if (a == 4) {
    x = 9
}
else if (a &gt; 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 now 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 &gt; 4  → y := 11 | true  → z := 99  fi


In C/Java, we would have:

if (a == 4) {
    x = 9
}

else if (a &gt; 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 := if a = 4 → 9 |  a &gt; 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 &gt; 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 elements 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] --&gt; 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 --&gt; a | true --&gt; b | false --&gt; c1 + c2 |  (2 + 3 &lt; 99) --&gt; d)  


(true --&gt; b) is the leftmost (cond --&gt; 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 =[] --&gt; t
        | t = [ ] --&gt; s
        | s != [ ] and t != [] and s(l) &lt;= t(1) --&gt;
            [s(1)]&amp; merge(s[2..], t)
        | s != [ ]and t != [ ] and s(1) &gt; r(l) --&gt;
            [t(1)] &amp; 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] &lt;= t[1]) {
        return CONCATENATE([s[1]], merge(s[2...], t));
    else  { // else if (s[1] &gt; 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 --&gt; h2
            | h2 = null --&gt; h1
            | h1 not null and h2 not null --&gt; 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 (&lt;--&gt;)

Below is an example of Tarjan code: 

x &lt;--&gt; y    


What Does a Double Arrow (⟷) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
&lt;--&gt; is a swap operation. The following prints true 

x_old := x
y_old := y
x &lt;--&gt; y
print(x == y_old) # prints true
print(y == x_old) # prints true


After performing x &lt;--&gt; 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 &lt;--&gt; operator: 

x := [1, 2, 3]
y := [4, 5, 6]
x &lt;--&gt; 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&lt;int&gt;(1, 2, 3);
    Array* rhs = new Array&lt;int&gt;(4, 5, 6);
    operator_double_arrow(&amp;lhs, &amp;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) &gt; key(h2) → h1 ⟷  h2 fi;
    right (h1) := if right(h1) = null → h2
                   |right(h1) ≠ null → mesh (right(h1), h2)
                  fi;

    if rank (left (h1)) &lt; 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) &gt; h2.key) {

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

    // Now, h2.key &lt;= h1.key   

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

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



    if (h1.left.rank &lt; 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 &lt; 50 → sum := sum + 1 


In C-style pseudocode, we have: 

sum = 0;
while(sum &lt; 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 &lt; 50) {
         sum = sum + 1;
         continue;
         // This `continue` statement is questionable
    }
    break;
}


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

sum := 0
do  sum &lt; 50 → sum := sum + 1 | sum &lt; 99 → sum := sum + 5


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

sum = 0;
while(true) {

    if (sum &lt; 50) {
         sum = sum + 1;
         continue;
    }
    else if (sum &lt; 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 --&gt; 1| False --&gt; 2 | (99 &lt; 2) --&gt; 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 &lt; 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.