La historia corta

Un famoso informático, Tarjan , escribió un libro hace años. Contiene pseudocódigo absolutamente extraño. ¿Alguien podría explicarlo?

La larga historia

Tarjan es conocido por muchos logros, incluido el hecho de que fue el coinventor de los árboles . Publicó un libro, " Estructuras de datos y algoritmos de red ", durante la década de 1980.

Todo el pseudocódigo del libro de Tarjan está escrito en un lenguaje de su propia invención. Las convenciones de pseudocódigo están muy regimentadas. Es casi un lenguaje verdadero, y uno podría imaginarse escribiendo un compilador para él. Tarjan escribe que su lenguaje se basa en los siguientes tres:

• Lenguaje de comando guardado de Dijkstra
• SETL
• ALGOL

Espero que alguien familiarizado con uno o dos de los idiomas anteriores, o el trabajo de Tarjan, pueda responder mi pregunta.

A continuación se muestra un ejemplo de una función escrita en el idioma de Tarjan:

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;

He visto muchos pseudocódigos, pero nunca he visto nada como el de Tarjan. ¿Cómo funciona el pseudocódigo de Tarjan? ¿Cómo pueden reescribirse ejemplos del pseudocódigo de Tarjan como algo que se parece más a C o Java? Ni siquiera necesita ser C o Java. La construcción if-else en el lenguaje de Tarjan no solo es diferente de los lenguajes de la familia C, sino también diferente de Python, MATLAB y muchos otros.

Tabla de contenido

Dividiré mi explicación del pseudocódigo de Tarjan en las siguientes secciones:

1. Bloques If-else de Tarjan (los operadores ->& |)
2. Pruebas de asignación e igualdad ( :=y =)
3. Hay else if, pero no hay elseconstructo
4. Operador de asignación condicional de Tarjan := if

5. Ejemplos adicionales de Tarjan's ify:= if
   5.5. Tarjan Arrays (o Listas)

6. Resumen de operadores

7. Operador de flecha de doble punta de Tarjan ( ⟷)
8. Los do-loops de Tarjan son como los loops while de C / Java
9. Operador de asignación condicional de Tarjan con todas las condiciones falsas

(1) Bloques If-else de Tarjan

(los operadores →y |)

La if-elseconstrucción es quizás la estructura de control más fundamental en el lenguaje de Tarjan. Además de los bloques if similares a C, el comportamiento if-else está casi integrado en las asignaciones de Tarjan y en los bucles while de Tarjan. El operador de flecha de Tarjan ->(o →) es un delimitador entre la condición de una instrucción if y el bloque de ejecución de una instrucción if.

Por ejemplo, en el idioma de Tarjan podríamos tener:

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

Si traducimos parcialmente la línea de código Tarjan anterior a C o Java, obtenemos lo siguiente:

if (a = 4)
    x := 9
fi 

En lugar de una ifllave derecha (como en C y Java), Tarjan termina un bloque con una ortografía hacia atrás similar a ALGOL de la palabra clave:fi

Si continuamos traduciendo nuestro ejemplo anterior, obtenemos:

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

(2) Pruebas de asignación e igualdad ( :=y =)

Tarjan toma estos operadores de ALGOL (más tarde también visto en Pascal).

Tarjan usa =para pruebas de igualdad, no asignaciones (por lo que funciona como Java ==).

Para la asignación, Tarjan usa :=, que funciona como Java =.

Por lo tanto, si continuamos traduciendo nuestro ejemplo, tenemos:

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

Una barra vertical (o "tubería" o |) en el lenguaje de Tarjan es equivalente a la else ifpalabra clave en C o Java.
Por ejemplo, en el idioma de Tarjan podríamos tener:

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

El código Tarjan anterior se traduce en:

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

(3) else ifsolo y sin elseconstrucción

Anteriormente, cubrí los conceptos básicos de las ifdeclaraciones sin describir los matices. Sin embargo, no discutiremos un pequeño detalle. La última cláusula en un if-elsebloque Tarjan-ian siempre debe contener un →operador arrow ( ). Como tal, no existe elseen el idioma de Tarjan, solo else if. Lo más parecido a un elsebloque en el lenguaje de Tarjan es hacer la condición de prueba más adecuada true.

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

En C / Java, tendríamos:

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

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

Los ejemplos son más fáciles de entender que las descripciones generales. Sin embargo, ahora que tenemos algunos ejemplos en nuestro haber, sepa que la formal general de una construcción if-else de Tarjan es la siguiente:

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

El personaje |es comoif else

El personaje →separa la condición de prueba de las cosas por hacer.

(4) Operador de asignación condicional de Tarjan := if

Tarjan's ifse puede usar de dos maneras muy diferentes. Hasta ahora, solo hemos descrito uno de los usos del tarjaniano if. Un tanto confuso, Tarjan todavía usa la notación / sintaxis ifpara el segundo tipo de ifconstrucción. Lo que ifse está utilizando se basa en el contexto. Analizar el contexto es realmente muy fácil de hacer, ya que el segundo tipo de Tarjan ifsiempre está preestablecido por un operador de asignación.

Por ejemplo, podríamos tener el siguiente código Tarjan:

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

Comience la digresión

Después de trabajar con el código Tarjan por un tiempo, te acostumbras al orden de las operaciones. Si ponemos entre paréntesis la condición de prueba en el ejemplo anterior, obtenemos:

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

a = 4No es una operación de asignación. a = 4es como a == 4: devuelve verdadero o falso.

Fin de la digresión

Puede ayudar pensar := ifen la sintaxis de un solo operador, distinto :=y if, de hecho, nos referiremos al := ifoperador como el operador de "asignación condicional".

Para la iflista (condition → action). Para := ifque enumeremos (condition → value)dónde valueestá el valor del lado derecho que podríamos asignar al lado izquierdolhs

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

en C o Java podría verse así:

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

Considere el siguiente ejemplo de "asignación condicional" en código tarjaniano:

# Instancia Tarjan del ejemplo cinco x: = a = 4 → 9 | a> 4 → 11 | verdadero → 99 fi

En C / Java, tendríamos:

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

(5) Resumen de operadores:

Hasta ahora, tenemos:

• :=...... Operador de asignación (C / Java =)

• =...... Prueba de igualdad (C / Java ==)

• → ...... Delimitador entre la condición de prueba de un bloque if y el cuerpo de un bloque if

• | ..... C / Java else-if

• if ... fi ..... bloque if-else

• := if... fi ..... Asignación condicional basada en un bloque if-else

(5.5) Listas / matrices de Tarjan:

El lenguaje de Tarjan tiene contenedores incorporados tipo matriz. La sintaxis para las matrices de Tarjan es mucho más intuitiva que la notación para las if elsedeclaraciones de Tarjan .

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

Se accede a los elementos de la matriz de Tarjan entre paréntesis (), no entre corchetes[]

La indexación comienza a las 1. Así,

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

A continuación se muestra cómo crear una nueva matriz que contenga los elementos primero y quinto de [1, 2, 3, 4, 5, 6, 7]

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

El operador de igualdad se define para matrices. Se imprime el siguiente códigotrue

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

La forma de Tarjan de probar si una matriz está vacía es compararla con una matriz vacía

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

Se puede crear una vista (no copia) de una submatriz, proporcionando múltiples índices al operador ()combinados con..

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) Ejemplos adicionales de Tarjan ify:= if

Los siguientes son otros ejemplos de una asignación condicional de Tarjan ( := if):

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

(true --> b)es la (cond --> action)cláusula más a la izquierda que tiene una condición verdadera. Por lo tanto, la asignación original del Ejemplo Seis tiene el mismo comportamiento de asignación quea := b

A continuación se muestra nuestro ejemplo más complicado de código Tarjan hasta ahora:

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

La siguiente es una traducción del código de Tarjan para fusionar dos listas ordenadas. Lo siguiente no es exactamente C o Java, pero está mucho más cerca de C / Java que la versión 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..]);
    }
}

A continuación se muestra otro ejemplo de código Tarjan y una traducción en algo similar a C o 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;

A continuación se muestra la traducción 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) Operador de flecha de doble punta de Tarjan ( <-->)

A continuación se muestra un ejemplo de código Tarjan:

x <--> y    

¿Qué hace un ⟷operador de doble flecha ( ) en el idioma de Tarjan?
Bueno, casi todas las variables en el lenguaje de Tarjan son punteros. <-->Es una operación de intercambio. Las siguientes impresionestrue

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

Después de realizar x <--> y, xapunta al objeto que ysolía señalar y yapunta al objeto que xsolía señalar.

A continuación se muestra una declaración de Tarjan utilizando el <-->operador:

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

A continuación se muestra una traducción del código Tarjan anterior a un pseudocódigo alternativo:

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; 

Alternativamente, podríamos tener:

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

A continuación se muestra un ejemplo de una de las funciones de Tarjan utilizando el ⟷operador:

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;

A continuación se muestra una traducción de la meshfunción de Tarjan a un pseudocódigo que no es C, pero se parece más a C (en términos relativos). El propósito de esto es ilustrar cómo funciona el ⟷operador 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) Los do-loops de Tarjan son como los loops while de C / Java

El lenguaje ify las forconstrucciones de Tarjan son familiares para los programadores de C / Java. Sin embargo, la palabra clave Tarjan para un ciclo while es do. Todos los dobucles terminan con la palabra clave od, que es la ortografía hacia atrás de do. A continuación se muestra un ejemplo:

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

En el pseudocódigo de estilo C, tenemos:

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

Lo anterior en realidad no es del todo correcto. Un Do-loop de Tarjan es realmente un C / Java while(true)con un bloque if-else anidado en su interior. Una traducción más literal del código Tarjan es la siguiente:

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

A continuación, tenemos un dobucle Tarjan más complicado :

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

El pseudocódigo de estilo C / Java para el complicado docircuito de Tarjan es el siguiente:

sum = 0;
while(true) {

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

(9) Operador de asignación condicional de Tarjan con todas las condiciones falsas

Aunque la larga explicación anterior cubre la mayoría de las cosas, algunos asuntos aún quedan sin resolver. Espero que alguien más escriba algún día una nueva respuesta mejorada basada en la mía que responda a estas preguntas.

Notablemente, cuando := ifse usa el operador de asignación condicional , y ninguna condición es verdadera, no sé qué valor se asigna a la variable.

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

No estoy seguro, pero es posible que no se haga ninguna asignación para x:

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

Podría requerir que la variable del lado izquierdo vista en una := ifdeclaración se declare previamente. En ese caso, incluso si todas las condiciones son falsas, la variable seguirá teniendo un valor.

Alternativamente, quizás las condiciones totalmente falsas representan un error de tiempo de ejecución. Otra alternativa es devolver un nullvalor especial y almacenar nullen el argumento de la izquierda de la asignación.

Nunca he visto esto antes, pero creo que puedo inferir lo que se entiende por contexto. Presumiblemente, ⟷ debe ser una operación de intercambio, y if G1 -> S1 | G2 - >S2 | ... fies una construcción de tipo if / then / else que también devuelve un valor, como el ?:operador ternario en C y Java.

Con eso en la mano, podríamos escribir la función anterior en un lenguaje similar a Java así:

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