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

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:

-
Tarjan's If-else Blocks (the -> & | 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 Tarjan's pseudo-code, every while-loop and assignment statement has an if-statement or if-else statement built into it.

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 begin translating the line of Tarjan code above into C or Java, we might obtain the following intermediate result:

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 == in the Java programming language).

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

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

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

The if-statement provided above is syntactically correct for C-family languages such as C itself, C++, and Java.

In somthing halfway between English and computer code, we have:

if
    the memory address labeled `a` contains the number `4`
then
    store the number `9` in the memory address labeled `x`

Else Clauses

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:

// This is C-style syntax   

if (a == 4) {
    x = 9; 
}
else if (a > 4) {
    y = 11;   
}

(3) else if only and no else construct

We have gone over the basics of Trajan's if-statements without describing the nuances.

We will now discuss a small detail.

The last clause in one of Tarjan's if-else blocks must always contain an arrow (→) operator.

There is no else keyword in Tarjan's language; there is only somthing analygous to else if.

The closest thing to an else-block in Tarjan's language is to make the rightmost test-condition true.

# Tarjan Syntax

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

In C/Java, we would have:
// C-style or Java-style syntax.

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 the C-style use of a Tarjan if.

Somewhat confusingly, Tarjan still uses the notation/syntax if for assignment statements.

Whether and if statement is an assignment-statment or not is dependent upon whether or not the if is preceded 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

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

In C or Java, it might lo

StackExchange Computer Science Q#103816, answer score: 64