The Short Story

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

The Long Story #

Tarjan is known for many acomplishments, including the fact that he was co-inventor 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

(4.5) Tarjan Arrays (or Lists)

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

(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 a 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 uses = for equality tests, not assignments.

Tarjan's = is like Java ==

Tarjan uses := for assignment.

Tarjan's := is 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.

Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷ must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi is an if/then/else-type construct that also returns a value, like the ternary ?: operator in C and Java.

With that in hand we could write the above function in a Java-like language like so:

HeapNode mesh(HeapNode h1, HeapNode h2)

{

  if(h1.key > h2.key)

  {

    // swap h1 and h2



    HeapNode t = h1;

    h1 = h2;

    h2 = t;

  }



  // One of the two cases has to hold in this case so we won't get to the

  // exception, but it'd be an exception if none of the cases were satisified

  // since this needs to return *something*.



  h1.right = (h1.right == null) ? h2 

             : (h1.right != null) ? mesh(h1.right, h2) 

             : throw new Exception();



  if(h1.left.rank < h1.right.rank)

  {

    // swap h1.left and h1.right



    HeapNode t = h1.left;

    h1.left = h1.right;

    h1.right = t;

  }



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



  return h1;

}