Die Kurzgeschichte

Ein berühmter Informatiker, Tarjan , schrieb vor Jahren ein Buch. Es enthält absolut bizarren Pseudocode. Würde es bitte jemand erklären?

Die lange Geschichte

Tarjan ist für viele Leistungen bekannt, einschließlich der Tatsache , dass er der Miterfinder der war spreizen Bäume . In den 1980er Jahren veröffentlichte er ein Buch mit dem Titel " Datenstrukturen und Netzwerkalgorithmen ".

Der gesamte Pseudocode in Tarjans Buch ist in einer eigenen Sprache verfasst. Die Pseudocode-Konventionen sind sehr reglementiert. Es ist fast eine wahre Sprache, und man könnte sich vorstellen, einen Compiler dafür zu schreiben. Tarjan schreibt, dass seine Sprache auf den folgenden drei basiert:

• Dijkstra's Guarded Command Language
• SETL
• ALGOL

Ich hoffe, dass jemand, der mit einer oder zwei der oben genannten Sprachen oder dem Werk von Tarjan vertraut ist, meine Frage beantworten kann.

Ein Beispiel für eine in Tarjans Sprache geschriebene Funktion ist unten dargestellt:

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;

Ich habe viel Pseudo-Code gesehen, aber ich habe noch nie so etwas wie Tarjan gesehen. Wie funktioniert Tarjans Pseudocode? Wie können Beispiele für Tarjans Pseudocode so umgeschrieben werden, dass sie eher wie C oder Java aussehen? Es muss nicht einmal C oder Java sein. Das if-else-Konstrukt in Tarjans Sprache unterscheidet sich nicht nur von den Sprachen der C-Familie, sondern auch von Python, MATLAB und vielen anderen.

Inhaltsverzeichnis

Ich werde meine Erklärung von Tarjans Pseudocode in die folgenden Abschnitte unterteilen:

1. Tarjans If-else-Blöcke (die ->& |Operatoren)
2. Zuordnungs- und Gleichstellungsprüfungen ( :=und =)
3. Es gibt else ifaber kein elseKonstrukt
4. Tarjans Operator für bedingte Zuweisungen := if

5. Zusätzliche Beispiele für Tarjan ifund:= if
   5.5. Tarjan Arrays (oder Listen)

6. Zusammenfassung der Operatoren

7. Tarjans Doppelpfeil-Operator ( ⟷)
8. Tarjans do-Schleifen sind wie C / Java-while-Schleifen
9. Tarjans Bedingungszuweisungsoperator mit allen falschen Bedingungen

(1) Tarjans If-else-Blöcke

(die Betreiber →und |)

Das if-elseKonstrukt ist vielleicht die grundlegendste Kontrollstruktur in Tarjans Sprache. Zusätzlich zu C-ähnlichen if-Blöcken ist das Verhalten von if-else in Tarjans Zuweisungen und Tarjans while-Schleifen nahezu integriert. Tarjans Pfeiloperator ->(oder →) ist ein Trennzeichen zwischen der Bedingung einer if-Anweisung und dem Ausführungsblock einer if-Anweisung.

In Tarjans Sprache könnten wir zum Beispiel haben:

# Example One
if a = 4 → x := 9 fi    

Wenn wir die obige Zeile des Tarjan-Codes teilweise in C oder Java übersetzen, erhalten wir Folgendes:

if (a = 4)
    x := 9
fi 

Anstelle einer geschweiften Klammer (wie in C und Java) beendet Tarjan einen ifBlock mit einer ALGOL-ähnlichen Rückwärtsschreibung des Schlüsselworts:fi

Wenn wir das obige Beispiel weiter übersetzen, erhalten wir:

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

(2) Zuordnungs- und Gleichheitsprüfungen ( :=und =)

Tarjan übernimmt diese Operatoren von ALGOL (später auch in Pascal zu sehen).

Tarjan verwendet =für Gleichheitstests keine Zuweisungen (so funktioniert es wie Java ==).

Für die Zuordnung verwendet Tarjan :=, was wie Java funktioniert =.

Wenn wir also unser Beispiel weiter übersetzen, haben wir:

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

Ein vertikaler Strich (oder "Pipe" oder |) in Tarjans Sprache entspricht dem else ifSchlüsselwort in C oder Java.
In Tarjans Sprache könnten wir zum Beispiel haben:

# Example Two
if a = 4 → x := 9 |  a > 4  → y := 11 fi 

Der obige Tarjan-Code übersetzt:

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

(3) else ifnur und kein elseKonstrukt

Zuvor habe ich die Grundlagen von if-statements behandelt, ohne die Nuancen zu beschreiben. Wir werden jedoch nicht auf ein kleines Detail eingehen. Die letzte Klausel in einem Tarjan-ian- if-elseBlock muss immer einen arrow ( →) -Operator enthalten. Als solches gibt es keine nur elsein Tarjans Sprache else if. Das, was elsein Tarjans Sprache einem Block am nächsten kommt, ist die Testbedingung ganz rechts true.

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

In C / Java hätten wir:

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

else if (a > 4)  {
    y = 11
}
else { // else if (true)
    z = 99
} 

Beispiele sind leichter zu verstehen als allgemeine Beschreibungen. Nun, da wir einige Beispiele kennen, wissen wir, dass die allgemeine Form eines Tarjans if-else-Konstrukts wie folgt lautet:

if condition
    → stuff to do
 | condition
    → stuff to do
 [...] 
 | condition 
    → stuff to do
fi       

Der Charakter |ist wieif else

Der Charakter →trennt die Testbedingung von der zu erledigenden Aufgabe.

(4) Betreiber der bedingten Zuteilung von Tarjan := if

Tarjan ifkann auf zwei verschiedene Arten verwendet werden. Bisher haben wir nur eine der Verwendungen des Tarjaner beschrieben if. Etwas verwirrend ist, dass Tarjan immer noch die Notation / Syntax iffür den zweiten Typ von if-construct verwendet. Was ifverwendet wird, basiert auf dem Kontext. Das Analysieren des Kontexts ist eigentlich sehr einfach, da der zweite Tarjan-Typ ifimmer von einem Zuweisungsoperator voreingestellt wird.

Zum Beispiel könnten wir den folgenden Tarjan-Code haben:

# Example Three
x := if a = 4 → 9 fi 

Beginnen Sie den Exkurs

Nachdem Sie eine Weile mit Tarjan-Code gearbeitet haben, gewöhnen Sie sich an die Reihenfolge der Operationen. Wenn wir die Testbedingung im obigen Beispiel in Klammern setzen, erhalten wir:

x := if (a = 4) → 9 fi 

a = 4ist keine Zuweisungsoperation. a = 4ist wie a == 4- es gibt wahr oder falsch zurück.

Exkurs beenden

Es kann helfen , zu denken , := ifwie Syntax für einen einzelnen Bediener, die sich von :=und ifin der Tat werden wir zum beziehen := ifOperator als „bedingte Zuweisung“ Operator.

Denn ifwir listen auf (condition → action). Für die := ifAuflistung, (condition → value)wo valuesich der Wert auf der rechten Seite befindet, können wir ihn auf der linken Seite zuweisenlhs

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

in C oder Java könnte so aussehen:

# Example Four
if (a == 4) {
    lhs = rhs
}

Betrachten Sie das folgende Beispiel für "bedingte Zuweisung" im tarjanischen Code:

# Tarjan-Instanziierung von Beispiel 5 x: = a = 4 → 9 | a> 4 → 11 | wahr → 99 fi

In C / Java hätten wir:

// C/Java Instantiation of Example Five
if (a == 4) {
    x = 9
}
else if (a > 4)  {
    x = 11
}
else if (true) { // else
    x = 99
} 

(5) Zusammenfassung der Betreiber:

Bisher haben wir:

• :=...... Zuweisungsoperator (C / Java =)

• =...... Gleichheitstest (C / Java ==)

• → ...... Trennzeichen zwischen Testbedingung eines if-Blocks und dem Body eines if-Blocks

• | ..... C / Java sonst-wenn

• if ... fi ..... wenn-sonst blockieren

• := if... fi ..... Bedingte Zuweisung basierend auf einem if-else-Block

(5.5) Tarjan Listen / Arrays:

Tarjans Sprache verfügt über eingebaute Array-ähnliche Container. Die Syntax für Tarjan-Arrays ist viel intuitiver als die Notation für Tarjan- if elseAnweisungen.

list1  := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3  := ["a", "b", "c", "d"];
list4  := [ ]; # an empty array

Auf Tarjan-Array-Elemente wird mit Klammern zugegriffen (), nicht mit eckigen Klammern[]

Die Indizierung beginnt um 1. Somit,

list3  := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true 

Unten sehen Sie, wie Sie ein neues Array mit dem 1. und 5. Element von erstellen [1, 2, 3, 4, 5, 6, 7]

nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]

Der Gleichheitsoperator ist für Arrays definiert. Der folgende Code wird gedruckttrue

x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)

Tarjans Weg zu testen, ob ein Array leer ist, besteht darin, es mit einem leeren Array zu vergleichen

arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment

Sie können eine Ansicht (nicht eine Kopie) eines Unterarrays erstellen, indem Sie dem Operator in ()Kombination mit mehrere Indizes bereitstellen..

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) Zusätzliche Beispiele für Tarjan ifund:= if

Das Folgende ist ein weiteres Beispiel für eine bedingte Tarjan-Zuweisung ( := if):

# Tarjan Example Six
a  := (false --> a | true --> b | false --> c1 + c2 |  (2 + 3 < 99) --> d)  

(true --> b)ist die am weitesten links stehende (cond --> action)Klausel mit einer wahren Bedingung. Somit hat das ursprüngliche Zuweisungsbeispiel 6 das gleiche Zuweisungsverhalten wiea := b

Unten sehen Sie unser bisher kompliziertestes Beispiel für Tarjan-Code:

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

Das Folgende ist eine Übersetzung von Tarjans Code zum Zusammenführen zweier sortierter Listen. Das Folgende ist nicht genau C oder Java, aber es ist C / Java viel näher als die 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..]);
    }
}

Unten ist noch ein Beispiel für Tarjan-Code und eine Übersetzung in etwas ähnlichem wie C oder 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;

Unten ist die C / Java-Übersetzung:

HeapNode meld (HeapNode h1, HeapNode h2) {

    if (h1 == null) {
       return h2;
    }   
    else if (h2 == null) {
        return h1;
    } else {
        mesh(h1, h2)
    }
} // end function

(7) Tarjans Doppelpfeil-Operator ( <-->)

Unten sehen Sie ein Beispiel für Tarjan-Code:

x <--> y    

Was macht ein Doppelpfeil ( ⟷) in Tarjans Sprache?
Nun, fast alle Variablen in Tarjans Sprache sind Zeiger. <-->ist ein Swap-Vorgang. Die folgenden Ausdrucketrue

x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true

Nach dem Durchführen x <--> y, xzeigt auf das Objekt , das yzu und Punkt verwendet , yum die Objektpunkte , die xbis zu Punkt verwendet.

Nachfolgend finden Sie eine Tarjan-Anweisung mit dem <-->Operator:

x := [1, 2, 3]
y := [4, 5, 6]
x <--> y 

Unten ist eine Übersetzung vom obigen Tarjan-Code in einen alternativen 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; 

Alternativ könnten wir haben:

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

Unten sehen Sie ein Beispiel für eine der Funktionen von Tarjan, die den ⟷Operator verwenden:

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;

Unten ist eine Übersetzung von Tarjans meshFunktion in Pseudocode, der nicht C ist, sondern eher wie C aussieht (relativ gesehen). Dies soll veranschaulichen, wie der Tarjan- ⟷Operator funktioniert.

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) Tarjans do-Schleifen sind wie C / Java-while-Schleifen

Tarjans Sprache ifund forKonstrukte sind C / Java-Programmierern vertraut. Das Tarjan-Schlüsselwort für eine while-Schleife lautet jedoch do. Alle do-loops enden mit dem Schlüsselwort od, bei dem es sich um die umgekehrte Schreibweise handelt do. Unten ist ein Beispiel:

sum := 0
do  sum < 50 → sum := sum + 1 

Im C-Pseudocode haben wir:

sum = 0;
while(sum < 50) {
    sum = sum + 1;
}

Das obige ist eigentlich nicht ganz richtig. Eine Tarjan-do-Schleife ist wirklich ein C / Java while(true)mit einem darin verschachtelten if-else-Block. Eine wörtlichere Übersetzung des Tarjan-Codes lautet wie folgt:

sum = 0;
while(true) {
    if (sum < 50) {
         sum = sum + 1;
         continue;
         // This `continue` statement is questionable
    }
    break;
}

Unten haben wir eine kompliziertere Tarjan- doSchleife:

sum := 0
do  sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5

Der C / Java-Pseudocode für die komplizierte Tarjan- doSchleife lautet wie folgt:

sum = 0;
while(true) {

    if (sum < 50) {
         sum = sum + 1;
         continue;
    }
    else if (sum < 99) {
         sum = sum + 5;
         continue;
    }
    break;
}

(9) Tarjans Bedingungszuweisungsoperator mit allen falschen Bedingungen

Obwohl die obige ausführliche Erklärung die meisten Dinge abdeckt, bleiben einige Fragen immer noch ungelöst. Ich hoffe, dass eines Tages jemand anderes eine neue, verbesserte Antwort auf der Grundlage meiner Antwort schreiben wird, die diese Probleme beantwortet.

Insbesondere wenn der Operator für bedingte Zuweisungen := ifverwendet wird und keine Bedingung zutrifft, ist mir nicht bekannt, welcher Wert der Variablen zugewiesen wird.

x  := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi

Ich bin nicht sicher, aber es ist möglich, dass keine Zuordnung vorgenommen wird zu x:

x = 0;
if (false) {
     x = 1;
}
else if (false) {
     x = 2;
}
else if (99 < 2) {
     x = 3;
}
// At this point (x == 0)

Möglicherweise müssen Sie die in einer := ifAnweisung angegebene linke Variable zuvor deklarieren. In diesem Fall hat die Variable auch dann noch einen Wert, wenn alle Bedingungen falsch sind.

Alternativ stellen möglicherweise nur falsche Bedingungen einen Laufzeitfehler dar. Eine andere Alternative besteht darin, einen speziellen nullWert zurückzugeben und nullim linken Argument der Zuweisung zu speichern .

Nie zuvor gesehen, aber ich denke, ich kann aus dem Kontext ableiten, was gemeint ist. Vermutlich ⟷ muss es sich um eine Swap-Operation handeln. Es if G1 -> S1 | G2 - >S2 | ... fihandelt sich um ein Konstrukt vom Typ if / then / else, das ebenfalls einen Wert zurückgibt, wie der ternäre ?:Operator in C und Java.

Mit dieser Hand könnten wir die obige Funktion in einer Java-ähnlichen Sprache wie folgt schreiben:

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