Can You Explain How Tarjan's Pseudocode Works to Someone Familiar with C or Java?












2












$begingroup$


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.










share|cite|improve this question







New contributor




Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    2












    $begingroup$


    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.










    share|cite|improve this question







    New contributor




    Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      2












      2








      2





      $begingroup$


      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.










      share|cite|improve this question







      New contributor




      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      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.







      programming-languages






      share|cite|improve this question







      New contributor




      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question







      New contributor




      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question






      New contributor




      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 2 hours ago









      Sam MuldoonSam Muldoon

      313




      313




      New contributor




      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          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.






          share|cite|improve this answer








          New contributor




          Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.






          $endgroup$





















            1












            $begingroup$

            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;
            }





            share|cite|improve this answer









            $endgroup$













              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "419"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: false,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });






              Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.










              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103816%2fcan-you-explain-how-tarjans-pseudocode-works-to-someone-familiar-with-c-or-java%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              2












              $begingroup$

              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.






              share|cite|improve this answer








              New contributor




              Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$


















                2












                $begingroup$

                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.






                share|cite|improve this answer








                New contributor




                Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  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.






                  share|cite|improve this answer








                  New contributor




                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  $endgroup$



                  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.







                  share|cite|improve this answer








                  New contributor




                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  share|cite|improve this answer



                  share|cite|improve this answer






                  New contributor




                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  answered 1 hour ago









                  Sam MuldoonSam Muldoon

                  313




                  313




                  New contributor




                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.





                  New contributor





                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  Sam Muldoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.























                      1












                      $begingroup$

                      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;
                      }





                      share|cite|improve this answer









                      $endgroup$


















                        1












                        $begingroup$

                        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;
                        }





                        share|cite|improve this answer









                        $endgroup$
















                          1












                          1








                          1





                          $begingroup$

                          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;
                          }





                          share|cite|improve this answer









                          $endgroup$



                          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;
                          }






                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered 1 hour ago









                          Daniel McLauryDaniel McLaury

                          27216




                          27216






















                              Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.










                              draft saved

                              draft discarded


















                              Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.













                              Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.












                              Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
















                              Thanks for contributing an answer to Computer Science Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103816%2fcan-you-explain-how-tarjans-pseudocode-works-to-someone-familiar-with-c-or-java%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              CARDNET

                              Boot-repair Failure: Unable to locate package grub-common:i386

                              濃尾地震