La petite histoire

Tarjan , un célèbre informaticien , a écrit un livre il y a plusieurs années. Il contient un pseudo-code absolument bizarre. Quelqu'un pourrait-il s'il vous plaît l'expliquer?

La longue histoire

Tarjan est connu pour de nombreuses réalisations, notamment le fait qu'il était le co-inventeur des arbres évasés . Il a publié un livre intitulé " Structures de données et algorithmes de réseau " dans les années 1980.

Tous les pseudo-codes du livre de Tarjan sont écrits dans un langage qu'il a lui-même conçu. Les conventions de pseudo-code sont très strictes. C'est presque un vrai langage, et on pourrait imaginer écrire un compilateur pour cela. Tarjan écrit que son langage est basé sur les trois suivants:

• Langage de commande gardé de Dijkstra
• SETL
• ALGOL

J'espère qu'une personne connaissant une ou deux des langues ci-dessus, ou le travail de Tarjan, pourra répondre à ma question.

Un exemple de fonction écrite dans la langue de Tarjan est présenté ci-dessous:

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;

J'ai vu beaucoup de pseudo-codes, mais je n'ai jamais rien vu de semblable à Tarjan. Comment fonctionne le pseudocode de Tarjan? Comment des exemples du pseudo-code de Tarjan peuvent-ils être réécrits en quelque chose qui ressemble plus à C ou à Java? Il n'est même pas nécessaire que ce soit C ou Java. La construction if-else dans la langue de Tarjan est non seulement différente des langues de la famille C, mais également de Python, MATLAB et bien d'autres.

Table des matières

Je diviserai mon explication du pseudocode de Tarjan dans les sections suivantes:

1. Les blocs If-else de Tarjan (les opérateurs ->& |)
2. Tests d'assignation et d'égalité ( :=et =)
3. Il y a else if, mais pas de elseconstruction
4. Opérateur d'affectation conditionnelle de Tarjan := if

5. Exemples supplémentaires de Tarjan ifet:= if
   5.5. Tarjan Arrays (ou Listes)

6. Résumé des opérateurs

7. Opérateur de flèche à double pointe de Tarjan ( ⟷)
8. Les boucles de Tarjan ressemblent aux boucles while / C de Java
9. Opérateur d'affectation conditionnelle de Tarjan avec toutes les conditions fausses

(1) Les blocs If-else de Tarjan

(les opérateurs →et |)

La if-elseconstruction est peut-être la structure de contrôle la plus fondamentale dans le langage de Tarjan. En plus des if-blocks de type C, le comportement if-else est pratiquement intégré aux assignations de Tarjan et aux boucles while de Tarjan. L'opérateur de flèche de Tarjan ->(ou →) est un délimiteur entre la condition d'une instruction if et le bloc d'exécution d'une instruction if.

Par exemple, dans le langage de Tarjan, nous pourrions avoir:

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

Si nous traduisons partiellement la ligne de code Tarjan ci-dessus en C ou en Java, nous obtenons ce qui suit:

if (a = 4)
    x := 9
fi 

Au lieu d'une accolade droite (comme en C et Java), Tarjan termine un ifbloc par une orthographe inversée du type mot-clé ALGOL:fi

Si nous continuons à traduire notre exemple ci-dessus, nous obtenons:

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

(2) Tests d'assignation et d'égalité ( :=et =)

Tarjan prend ces opérateurs d'ALGOL (plus tard également vu en Pascal).

Tarjan utilise =pour des tests d'égalité, pas des assignations (donc ça fonctionne comme Java ==).

Pour les affectations, Tarjan utilise :=, qui fonctionne comme Java =.

Ainsi, si nous continuons à traduire notre exemple, nous avons:

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

Une barre verticale (ou "pipe" ou |) dans la langue de Tarjan équivaut au else ifmot - clé en C ou en Java.
Par exemple, dans le langage de Tarjan, nous pourrions avoir:

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

Le code Tarjan ci-dessus se traduit par:

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

(3) else ifseulement et pas de elseconstruction

Un peu plus tôt, je ifcouvrais les bases des déclarations sans décrire les nuances. Cependant, nous ne discuterons pas d'un petit détail. La dernière clause d'un if-elsebloc Tarjan-ian doit toujours contenir un →opérateur arrow ( ). En tant que tel, il n'y a pas que elsedans la langue de Tarjan else if. La chose la plus proche d'un elsebloc dans la langue de Tarjan est de créer la condition de test la plus appropriée true.

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

En C / Java, nous aurions:

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

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

Les exemples sont plus faciles à comprendre que les descriptions générales. Cependant, maintenant que nous avons quelques exemples à notre actif, sachez que la structure générale d'une construction if-else de Tarjan est la suivante:

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

Le personnage |est commeif else

Le caractère →sépare la condition de test de la tâche à accomplir.

(4) Opérateur d'affectation conditionnelle de Tarjan := if

Tarjan ifpeut être utilisé de deux manières très différentes. Jusqu'à présent, nous n'avons décrit qu'une des utilisations du tarjanien if. De manière quelque peu déroutante, Tarjan utilise toujours la notation / syntaxe ifpour le second type de if-construct. Ce qui ifest utilisé est basé sur le contexte. Analyser le contexte est en fait très facile à faire car le second type de Tarjan ifest toujours pré-fixé par un opérateur d’attribution.

Par exemple, nous pourrions avoir le code Tarjan suivant:

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

Commencer la digression

Après avoir utilisé le code Tarjan pendant un certain temps, vous vous habituez à l'ordre des opérations. Si nous donnons la condition de test entre parenthèses dans l'exemple ci-dessus, nous obtenons:

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

a = 4n'est pas une opération d'affectation. a = 4est comme a == 4- il retourne vrai ou faux.

Mettre fin à la digression

Il peut être utile d’envisager la := ifsyntaxe d’un opérateur unique, distincte de :=et ifEn fait, nous ferons référence à l’ := ifopérateur en tant qu’opérateur "d’affectation conditionnelle".

Pour ifnous lister (condition → action). Car := ifnous listons (condition → value)où valueest la valeur du côté droit que nous pourrions attribuer au côté gauchelhs

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

en C ou en Java pourrait ressembler à:

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

Prenons l'exemple suivant "d'assignation conditionnelle" en code tarjanien:

# Instanciation de Tarjan de l'exemple cinq x: = a = 4 → 9 | a> 4 → 11 | vrai → 99 fi

En C / Java, nous aurions:

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

(5) Résumé des opérateurs:

Jusqu'à présent, nous avons:

• :=...... Opérateur d'affectation (C / Java =)

• =...... Test d'égalité (C / Java ==)

• → ...... Délimiteur entre la condition de test d'un bloc if et le corps d'un bloc if

• | ..... C / Java sinon-si

• if ... fi ..... si-sinon bloquer

• := if... fi ..... Affectation conditionnelle basée sur un bloc if-else

(5.5) Listes / Tableaux Tarjan:

Tarjan's Language intègre des conteneurs de type tableau. La syntaxe des tableaux de Tarjan est beaucoup plus intuitive que la notation des if elsedéclarations de Tarjan .

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

Les éléments de tableau de Tarjan sont accessibles entre parenthèses ()et non entre crochets[]

L'indexation commence à 1. Ainsi,

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

Vous trouverez ci-dessous comment créer un nouveau tableau contenant les 1er et 5ème éléments de [1, 2, 3, 4, 5, 6, 7]

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

L'opérateur d'égalité est défini pour les tableaux. Le code suivant imprimetrue

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

Le moyen utilisé par Tarjan pour vérifier si un tableau est vide consiste à le comparer à un tableau vide.

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

On peut créer une vue (et non une copie) d’un sous-tableau, en fournissant plusieurs indices à l’opérateur ()associé à..

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) Exemples supplémentaires de Tarjan ifet:= if

Voici un autre exemple d'assignation conditionnelle Tarjan ( := if):

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

(true --> b)est la (cond --> action)clause la plus à gauche ayant une condition vraie. Ainsi, l'affectation d'origine, exemple six, a le même comportement d'affectation quea := b

Vous trouverez ci-dessous notre exemple le plus complexe de code Tarjan à ce jour:

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

Ce qui suit est une traduction du code de Tarjan pour la fusion de deux listes triées. Ce qui suit n'est pas exactement C ou Java, mais il est beaucoup plus proche de C / Java que la version Tarjan.

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..]);
    }
}

Vous trouverez ci-dessous un autre exemple de code Tarjan et une traduction similaire à C ou 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;

Ci-dessous, la traduction C / Java:

HeapNode meld (HeapNode h1, HeapNode h2) {

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

(7) Opérateur de flèche à double pointe de Tarjan ( <-->)

Voici un exemple de code Tarjan:

x <--> y    

Que fait un ⟷opérateur en double flèche ( ) dans la langue de Tarjan?
Eh bien, presque toutes les variables de la langue de Tarjan sont des indicateurs. <-->est une opération d'échange. Les impressions suivantestrue

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

Après avoir terminé x <--> y, xpointe vers l’objet qui ypointait et pointera yvers l’objet qui xétait pointé.

Ci-dessous, une déclaration de Tarjan utilisant l' <-->opérateur:

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

Ci-dessous, une traduction du code Tarjan ci-dessus en pseudocode alternatif:

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; 

Alternativement, nous pourrions avoir:

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

Vous trouverez ci-dessous un exemple de fonction de Tarjan utilisant l' ⟷opérateur:

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;

Ci-dessous, une traduction de la meshfonction de Tarjan en pseudo-code qui n'est pas C, mais qui ressemble plus à C (relativement parlant). Ceci a pour but d'illustrer le fonctionnement de l' ⟷opérateur de Tarjan .

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) Les boucles de Tarjan sont comme des boucles en boucle C / Java

Le langage ifet les forconstructions de Tarjan sont familiers aux programmeurs C / Java. Cependant, le mot clé Tarjan pour une boucle while est do. Toutes les doboucles se terminent par le mot-clé od, qui est l'orthographe en arrière de do. Ci-dessous un exemple:

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

Dans le pseudocode de style C, nous avons:

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

Ce qui précède n’est pas tout à fait correct. Une boucle de Tarjan est vraiment un C / Java while(true)avec un bloc if-else imbriqué à l'intérieur. Une traduction plus littérale du code Tarjan est la suivante:

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

Ci-dessous, nous avons une doboucle de Tarjan plus compliquée :

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

Le pseudocode de style C / Java pour la doboucle compliquée de Tarjan est le suivant:

sum = 0;
while(true) {

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

(9) Opérateur d'assignation conditionnelle de Tarjan avec toutes les conditions fausses

Bien que la longue explication ci-dessus couvre la plupart des choses, il reste quelques questions en suspens. J'espère que quelqu'un d'autre écrira un jour une nouvelle réponse améliorée basée sur la mienne qui répond à ces dilemmes.

Notamment, lorsque l'opérateur d'affectation conditionnelle := ifest utilisé et qu'aucune condition n'est vraie, je ne sais pas quelle valeur est affectée à la variable.

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

Je ne suis pas sûr, mais il est possible qu'aucune cession ne soit faite à x:

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

Vous pouvez exiger que la variable de gauche vue dans une := ifinstruction soit déclarée auparavant. Dans ce cas, même si toutes les conditions sont fausses, la variable aura toujours une valeur.

Sinon, peut-être que toutes les conditions fausses représentent une erreur d'exécution. Une autre alternative consiste à renvoyer une nullvaleur spéciale et à stocker nulll'argument de gauche de l'affectation.

Jamais vu cela auparavant, mais je pense pouvoir déduire ce que l'on entend par contexte. On suppose que l'opération ⟷ doit être une opération d'échange. Il if G1 -> S1 | G2 - >S2 | ... fis'agit d'une construction de type if / then / else qui renvoie également une valeur, comme l' ?:opérateur ternaire en C et Java.

Avec cette main en main, nous pourrions écrire la fonction ci-dessus dans un langage semblable à Java:

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