Krótka historia

Słynny informatyk Tarjan napisał książkę lata temu. Zawiera absolutnie dziwny pseudokod. Czy ktoś mógłby to wyjaśnić?

Długa historia

Tarjan jest znany z wielu osiągnięć, w tym z faktu, że był współtwórcą drzew pnia . W latach 80. opublikował książkę „ Struktury danych i algorytmy sieciowe ”.

Cały pseudo-kod w książce Tarjana napisany jest w języku jego własnego autora. Konwencje pseudokodu są bardzo szczegółowe. To prawie prawdziwy język i można sobie wyobrazić napisanie kompilatora. Tarjan pisze, że jego język opiera się na następujących trzech:

• Dijkstra's Guarded Command Language
• SETL
• ALGOL

Mam nadzieję, że ktoś, kto zna jeden lub dwa powyższe języki lub dzieło Tarjana, będzie w stanie odpowiedzieć na moje pytanie.

Przykład funkcji napisanej w języku Tarjan pokazano poniżej:

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;

Widziałem dużo pseudo-kodu, ale nigdy nie widziałem czegoś takiego jak Tarjan. Jak działa pseudokod Tarjana? W jaki sposób przykłady pseudokodu Tarjana można przepisać jako coś, co wygląda bardziej jak C lub Java? Nie musi to być nawet C ani Java. Konstrukcja if-else w języku Tarjana różni się nie tylko od języków rodziny C, ale także różni się od Python, MATLAB i wielu innych.

Spis treści

Moje wyjaśnienie pseudokodu Tarjana podzielę na następujące sekcje:

1. Bloki If-else Tarjana ( operatory ->i |)
2. Testy przydziału i równości ( :=i =)
3. Nie ma else if, ale nie ma elsekonstrukcji
4. Operator warunkowego przydziału Tarjana := if

5. Dodatkowe przykłady Tarjana ifi:= if
   5.5. Tablice Tarjan (lub listy)

6. Podsumowanie operatorów

7. Tarjan's Double-point Arrow Operator ( ⟷)
8. Pętle do Tarjana są jak pętle C / Java while
9. Operator przypisania warunkowego Tarjana ze wszystkimi fałszywymi warunkami

(1) Bloki If-else Tarjana

(operatorzy →i |)

if-elseKonstrukt jest chyba najbardziej podstawową strukturę sterowania w języku Tarjan użytkownika. Oprócz podobnych do C bloków, zachowanie if-else jest prawie wbudowane w zadania Tarjana i pętle while Tarjana. Operator strzałki Tarjana ->(lub →) jest separatorem między warunkiem instrukcji if a blokiem wykonania instrukcji if.

Na przykład w języku Tarjana możemy mieć:

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

Jeśli częściowo przetłumaczymy wiersz powyższego kodu Tarjan na język C lub Java, otrzymujemy:

if (a = 4)
    x := 9
fi 

Zamiast prawych nawiasów klamrowych (jak w C i Javie) Tarjan kończy ifblok -blokiem odwróconej pisowni słowa kluczowego w stylu ALGOL:fi

Jeśli nadal będziemy tłumaczyć nasz powyższy przykład, otrzymamy:

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

(2) Testy przydziału i równości ( :=i =)

Tarjan bierze tych operatorów z ALGOL (później także w Pascal).

Tarjan używa =do testów równości, a nie przypisań (więc działa jak Java ==).

Do przypisania używa Tarjan :=, który działa jak Java =.

Zatem jeśli będziemy kontynuować tłumaczenie naszego przykładu, otrzymamy:

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

Pionowy pasek (lub „potok” lub |) w języku Tarjan jest równoważny else ifsłowu kluczowemu w języku C lub Java.
Na przykład w języku Tarjana możemy mieć:

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

Powyższy kod Tarjan tłumaczy się na:

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

(3) else iftylko i bez elsekonstruktu

Wcześniej ifopisywałem podstawy wypowiedzi bez opisywania niuansów. Nie będziemy jednak omawiać drobnego szczegółu. Ostatnia klauzula w if-elsebloku Tarjan-ian musi zawsze zawierać →operator arrow ( ). W związku z tym nie ma elsetylko języka Tarjan else if. elseNajblizszą opcją dla -block w języku Tarjan jest wykonanie warunku testowego znajdującego się po prawej stronie true.

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

W C / Java mielibyśmy:

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

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

Przykłady są łatwiejsze do zrozumienia niż ogólne opisy. Jednak teraz, gdy mamy już kilka przykładów, wiedz, że ogólna formalność konstruktu Tarjan if-else jest następująca:

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

Ta postać |jest jakif else

Znak →oddziela warunek testowy od rzeczy do zrobienia.

(4) Operator warunkowego przydziału Tarjana := if

Tarjana ifmożna używać na dwa różne sposoby. Jak dotąd opisaliśmy tylko jedno z zastosowań Tarjaniana if. Nieco mylące, Tarjan nadal używa notacji / składni ifdla drugiego typu if-construct. To, co ifjest używane, oparte jest na kontekście. Analiza kontekstu jest w rzeczywistości bardzo łatwa, ponieważ drugi typ Tarjan- ifjest zawsze wstępnie ustalany przez operatora przypisania.

Na przykład możemy mieć następujący kod Tarjan:

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

Rozpocznij dygresję

Po pewnym czasie pracy z kodem Tarjan przyzwyczajasz się do kolejności operacji. Jeśli nawiasujemy warunek testu w powyższym przykładzie, otrzymujemy:

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

a = 4nie jest operacją przypisania. a = 4jest jak a == 4- zwraca true lub false.

Koniec dygresji

Może pomóc myśleć o := ifskładni dla pojedynczego operatora, odrębnej od :=i w ifrzeczywistości będziemy nazywać := ifoperatora „operatorem przypisania warunkowego”.

Do iflisty (condition → action). Gdyż := ifpodajemy, (condition → value)gdzie valuejest wartość po prawej stronie, którą możemy przypisać po lewej stronielhs

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

w C lub Java może wyglądać następująco:

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

Rozważ następujący przykład „przypisania warunkowego” w kodzie Tarjanian:

# Tworzenie instancji w Tarjan z przykładu piątego x: = a = 4 → 9 | a> 4 → 11 | prawda → 99 fi

W C / Java mielibyśmy:

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

(5) Podsumowanie operatorów:

Do tej pory mamy:

• :=...... Operator przypisania (C / Java =)

• =...... Test równości (C / Java ==)

• → ...... Ogranicznik między warunkiem testu bloku if a korpusem bloku if

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

• if ... fi ..... jeśli-inny blok

• := if... fi ..... Przypisanie warunkowe na podstawie bloku if-else

(5.5) Listy / tablice Tarjan:

Język Tarjana ma wbudowane pojemniki podobne do tablicy. Składnia tablic Tarjan jest znacznie bardziej intuicyjna niż notacja if elseinstrukcji Tarjan .

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

Elementy tablicy Tarjan są dostępne w nawiasach (), a nie w nawiasach kwadratowych[]

Indeksowanie zaczyna się od 1. A zatem,

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

Poniżej pokazano, jak utworzyć nową tablicę zawierającą 1 i 5 element [1, 2, 3, 4, 5, 6, 7]

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

Operator równości jest zdefiniowany dla tablic. Zostanie wydrukowany następujący kodtrue

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

Sposobem Tarjana na sprawdzenie, czy tablica jest pusta, jest porównanie jej z pustą tablicą

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

Można stworzyć widok (a nie kopiować) pod-macierzy, zapewniając operatorowi wiele indeksów w ()połączeniu..

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) Dodatkowe przykłady Tarjana ifi:= if

Poniżej znajdują się kolejne przykłady warunkowego przypisania Tarjan ( := if):

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

(true --> b)jest (cond --> action)klauzulą najbardziej wysuniętą w lewo , mającą prawdziwy warunek. Tak więc pierwotne zadanie przydziału Szósty ma takie samo zachowanie przydziału jaka := b

Poniżej znajduje się nasz najbardziej skomplikowany przykład kodu Tarjan do tej pory:

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

Poniżej znajduje się tłumaczenie kodu Tarjana do scalania dwóch posortowanych list. Poniżej nie jest dokładnie C lub Java, ale jest znacznie bliżej C / Java niż wersja 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..]);
    }
}

Poniżej znajduje się kolejny przykład kodu Tarjan i tłumaczenia w czymś podobnym do C lub 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;

Poniżej znajduje się tłumaczenie 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) Operator strzała z podwójnymi szpicami Tarjana ( <-->)

Poniżej znajduje się przykład kodu Tarjan:

x <--> y    

Co robi ⟷operator Double Arrow ( ) w języku Tarjana?
Cóż, prawie wszystkie zmienne w języku Tarjana są wskaźnikami. <-->jest operacją zamiany. Następujące wydrukitrue

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

Po wykonaniu x <--> y, xpunkty do obiektu, który ywykorzystywany do punktu do ypunktów do obiektu, który xwykorzystywany do punktu celu.

Poniżej znajduje się instrukcja Tarjan używająca <-->operatora:

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

Poniżej znajduje się tłumaczenie z powyższego kodu Tarjan na alternatywny pseudokod:

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; 

Alternatywnie możemy mieć:

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

Poniżej znajduje się przykład jednej z funkcji Tarjana używającej ⟷operatora:

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;

Poniżej znajduje się tłumaczenie funkcji Tarjana meshna pseudo-kod, który nie jest C, ale bardziej przypomina C (względnie mówiąc). Ma to na celu zilustrowanie działania ⟷operatora Tarjana .

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) Pętle do Tarjana są jak pętle C / Java while

Język ifi forkonstrukcje Tarjana są znane programistom C / Java. Jednak słowem kluczowym Tarjan dla pętli while jest do. Wszystkie dopętle kończą się słowem kluczowym od, które jest literowaniem wstecznym do. Poniżej znajduje się przykład:

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

W pseudokodzie w stylu C mamy:

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

Powyższe nie jest właściwie słuszne. Pętla do Tarjan to tak naprawdę C / Java while(true)z zagnieżdżonym blokiem if-else. Bardziej dosłowne tłumaczenie kodu Tarjan jest następujące:

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

Poniżej mamy bardziej skomplikowaną dopętlę Tarjan :

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

Pseudokod w stylu C / Java dla skomplikowanej dopętli Tarjan wygląda następująco:

sum = 0;
while(true) {

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

(9) Operator warunkowego przypisania Tarjana ze wszystkimi fałszywymi warunkami

Chociaż powyższe długie wyjaśnienie obejmuje większość rzeczy, kilka spraw pozostaje nierozwiązanych. Mam nadzieję, że ktoś inny napisze kiedyś ulepszoną odpowiedź na podstawie mojej, która odpowiada na te pytania.

W szczególności, gdy := ifużywany jest operator przypisania warunkowego i żaden warunek nie jest spełniony, nie jestem tym, jaką wartość przypisano zmiennej.

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

Nie jestem pewien, ale możliwe jest, że nie zostanie przypisane x:

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

Możesz wymagać, aby zmienna po lewej stronie widoczna w := ifinstrukcji była wcześniej zadeklarowana. W takim przypadku, nawet jeśli wszystkie warunki są fałszywe, zmienna nadal będzie miała wartość.

Alternatywnie, być może warunki całkowicie fałszywe oznaczają błąd czasu wykonywania. Inną alternatywą jest zwrócenie specjalnej nullwartości i zapisanie nullw lewym argumencie przypisania.

Nigdy wcześniej tego nie widziałem, ale myślę, że mogę wywnioskować, co to znaczy z kontekstu. Prawdopodobnie ⟷ musi to być operacja zamiany i if G1 -> S1 | G2 - >S2 | ... fijest to konstrukcja typu if / then / else, która również zwraca wartość, podobnie jak ?:operator trójskładnikowy w języku C i Java.

Mając to w ręku, moglibyśmy napisać powyższą funkcję w języku podobnym do 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;
}