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 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 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 > 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 := if 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 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] --> 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.
returnstatement really end in a comma? $\endgroup$