Cerpen

Seorang ilmuwan komputer terkenal, Tarjan , menulis sebuah buku bertahun-tahun yang lalu. Ini berisi kodesemu yang benar-benar aneh. Apakah seseorang tolong jelaskan?

Kisah Panjang

Tarjan dikenal dengan banyak prestasi, termasuk fakta bahwa ia adalah seorang coinventor dari pohon-pohon hamparan . Dia menerbitkan sebuah buku, " Struktur Data dan Algoritma Jaringan ," selama 1980-an.

Semua kode semu dalam buku Tarjan ditulis dalam bahasa yang dirancangnya sendiri. Konvensi kode semu sangat ketat. Itu hampir merupakan bahasa yang benar, dan orang bisa membayangkan menulis kompiler untuk itu. Tarjan menulis bahwa bahasanya didasarkan pada tiga berikut:

• Bahasa Perintah Terlindungi Dijkstra
• SETL
• ALGOL

Saya berharap seseorang yang akrab dengan satu atau dua bahasa di atas, atau karya Tarjan, akan dapat menjawab pertanyaan saya.

Contoh fungsi yang ditulis dalam bahasa Tarjan ditunjukkan di bawah ini:

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;

Saya telah melihat banyak kode semu, tetapi saya belum pernah melihat yang seperti Tarjan. Bagaimana cara kerja pseudocode Tarjan? Bagaimana contoh pseudocode Tarjan dapat ditulis ulang sebagai sesuatu yang lebih mirip C atau Java? Bahkan tidak perlu C atau Java. Konstruksi if-else dalam bahasa Tarjan tidak hanya berbeda dari bahasa C-family, tetapi juga berbeda dari Python, MATLAB dan banyak lainnya.

Daftar Isi

Saya akan membagi penjelasan saya tentang pseudocode Tarjan menjadi bagian-bagian berikut:

1. Blok If-else Tarjan ( operator ->& |)
2. Tes Penugasan dan Kesetaraan ( :=dan =)
3. Ada else if, tetapi tidak ada elsekonstruksi
4. Operator Tugas Bersyarat Tarjan := if

5. Contoh Tambahan Tarjan's ifdan:= if
   5.5. Tarjan Arrays (atau Daftar)

6. Ringkasan Operator

7. Operator Panah Berujung Ganda ( ⟷)
8. Do-loop Tarjan seperti C / Java while-loop
9. Operator penugasan bersyarat Tarjan dengan semua kondisi salah

(1) Blok If-else Tarjan

(operator →dan |)

The if-elsemembangun mungkin yang paling struktur pengendalian mendasar dalam bahasa Tarjan ini. Selain C-like if-blok, perilaku if-else hampir tertanam di dalam tugas Tarjan dan loop sementara Tarjan. Operator panah Tarjan ->(atau →) adalah pembatas antara kondisi pernyataan-if dan blok eksekusi pernyataan-if.

Misalnya, dalam bahasa Tarjan kita mungkin memiliki:

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

Jika kami menerjemahkan sebagian kode Tarjan di atas ke dalam C atau Java, kami mendapatkan yang berikut:

if (a = 4)
    x := 9
fi 

Alih-alih kurung kurawal kanan (seperti di C dan Jawa) Tarjan mengakhiri if-block dengan ejaan mundur-seperti ALGOL dari kata kunci:fi

Jika kami terus menerjemahkan contoh kami di atas, kami mendapatkan:

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

(2) Tes Penugasan dan Kesetaraan ( :=dan =)

Tarjan mengambil operator ini dari ALGOL (kemudian juga terlihat dalam Pascal).

Tarjan digunakan =untuk tes kesetaraan, bukan tugas (sehingga berfungsi seperti Java ==).

Untuk tugas, Tarjan menggunakan :=, yang berfungsi seperti Java =.

Jadi, jika kita terus menerjemahkan contoh kita, kita memiliki:

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

Bilah vertikal (atau "pipa" atau |) dalam bahasa Tarjan setara dengan else ifkata kunci dalam C atau Java.
Misalnya, dalam bahasa Tarjan kita mungkin memiliki:

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

Kode-Tarjan di atas diterjemahkan menjadi:

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

(3) else ifhanya dan tanpa elsekonstruksi

Sebelumnya, saya membahas dasar-dasar ifpernyataan tanpa menjelaskan nuansa. Namun, kami tidak akan membahas detail kecil. Klausa terakhir dalam if-elseblok Tarjan-ian harus selalu berisi →operator panah ( ). Dengan demikian, tidak ada elsedalam bahasa Tarjan, hanya else if. Hal yang paling dekat dengan else-block dalam bahasa Tarjan adalah membuat kondisi tes paling kanan true.

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

Di C / Java, kita akan memiliki:

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

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

Contoh lebih mudah dipahami daripada deskripsi umum. Namun, sekarang kita memiliki beberapa contoh di bawah ikat pinggang kita, ketahuilah bahwa formal umum dari konstruksi if-else Tarjan adalah sebagai berikut:

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

Karakternya |sepertiif else

Karakter →memisahkan kondisi uji dari hal-hal yang harus dilakukan.

(4) Operator Tugas Bersyarat Tarjan := if

Tarjan ifdapat digunakan dua cara yang sangat berbeda. Sejauh ini, kami hanya menggambarkan salah satu kegunaan Tarjanian if. Agak membingungkan, Tarjan masih menggunakan notasi / sintaks ifuntuk tipe if-construct kedua . Yang ifdigunakan didasarkan pada konteks. Menganalisis konteks sebenarnya sangat mudah dilakukan karena tipe kedua dari Tarjan- ifselalu diperbaiki oleh operator penugasan.

Misalnya, kami mungkin memiliki kode Tarjan berikut:

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

Mulailah Digression

Setelah bekerja dengan kode Tarjan untuk sementara, Anda terbiasa dengan urutan operasi. Jika kami mengurung kondisi pengujian dalam contoh di atas, kami memperoleh:

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

a = 4bukan operasi penugasan. a = 4seperti a == 4- mengembalikan benar atau salah.

Akhiri Digression

Dapat membantu untuk menganggapnya := ifsebagai sintaks untuk satu operator, berbeda dari :=dan ifpada kenyataannya, kami akan menyebut := ifoperator sebagai operator "penugasan bersyarat".

Untuk ifkita daftar (condition → action). Untuk := ifkami daftar di (condition → value)mana valuenilai sisi kanan kami dapat menetapkan untuk sisi kirilhs

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

di C atau Java mungkin terlihat seperti:

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

Pertimbangkan contoh "penugasan kondisional" berikut dalam kode bahasa Tarjan:

# Instansiasi Tarjan dari Contoh Lima x: = a = 4 → 9 | a> 4 → 11 | benar → 99 fi

Di C / Java, kita akan memiliki:

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

(5) Ringkasan Operator:

Sejauh ini, kami memiliki:

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

• =...... Tes kesetaraan (C / Java ==)

• → ...... Pembatas antara kondisi uji blok-if dan tubuh blok-if

• | ..... C / Java lain-jika

• if ... fi ..... jika-lagi blok

• := if... fi ..... Tugas bersyarat berdasarkan pada blok if-else

(5.5) Daftar / Array Tarjan:

Bahasa Tarjan memiliki wadah mirip array bawaan. Sintaks untuk array Tarjan jauh lebih intuitif daripada notasi untuk if elsepernyataan Tarjan .

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

Elemen array Tarjan diakses dengan tanda kurung (), bukan tanda kurung[]

Pengindeksan dimulai pada 1. Demikian,

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

Di bawah ini menunjukkan cara membuat array baru yang mengandung elemen 1 dan 5 [1, 2, 3, 4, 5, 6, 7]

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

Operator kesetaraan didefinisikan untuk array. Kode berikut dicetaktrue

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

Cara Tarjan untuk menguji apakah array kosong adalah membandingkannya dengan array kosong

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

Seseorang dapat membuat tampilan (bukan salinan) dari sebuah sub-array, dengan menyediakan beberapa indeks untuk ()digabungkan dengan operator..

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) Contoh Tambahan dari Tarjan ifdan:= if

Berikut ini adalah contoh lain dari penugasan bersyarat Tarjan ( := if):

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

(true --> b)adalah (cond --> action)klausa paling kiri yang memiliki kondisi sebenarnya. Dengan demikian, tugas asli Contoh Enam memiliki tugas-perilaku yang sama dengana := b

Berikut ini adalah contoh kode Tarjan kami yang paling rumit:

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

Berikut ini adalah terjemahan kode Tarjan untuk menggabungkan dua daftar yang diurutkan. Berikut ini bukan C atau Java, tetapi lebih dekat ke C / Java daripada versi 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..]);
    }
}

Di bawah ini adalah contoh lain dari kode-Tarjan dan terjemahan dalam sesuatu yang mirip dengan C atau 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;

Di bawah ini adalah terjemahan 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 Panah Runcing Dua ( <-->)

Di bawah ini adalah contoh kode Tarjan:

x <--> y    

Apa yang ⟷Dilakukan oleh Operator Double Arrow ( ) dalam Bahasa Tarjan?
Yah, hampir semua variabel dalam Bahasa Tarjan adalah pointer. <-->adalah operasi swap. Cetakan berikuttrue

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

Setelah melakukan x <--> y, arahkan ke xobjek yang ydigunakan untuk menunjuk dan ymenunjuk ke objek yang xdigunakan untuk menunjuk.

Di bawah ini adalah pernyataan Tarjan menggunakan <-->operator:

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

Di bawah ini adalah terjemahan dari kode Tarjan di atas ke 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; 

Atau, kita dapat memiliki:

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

Di bawah ini adalah contoh dari salah satu fungsi Tarjan menggunakan ⟷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;

Di bawah ini adalah terjemahan dari meshfungsi Tarjan menjadi pseudo-code yang bukan C, tetapi lebih mirip C (secara relatif berbicara). Tujuannya adalah untuk menggambarkan cara ⟷kerja operator 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) Do-loop Tarjan seperti C / Java while-loop

Bahasa ifdan forkonstruk Tarjan tidak asing bagi programmer C / Java. Namun, kata kunci Tarjan untuk while-loop adalah do. Semua do-loop diakhiri dengan kata kunci od, yang merupakan ejaan mundur dari do. Di bawah ini adalah contohnya:

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

Dalam pseudocode C-style, kami memiliki:

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

Di atas sebenarnya tidak sepenuhnya benar. Do-loop Tarjan sebenarnya adalah C / Java while(true)dengan blok if-else yang bersarang di dalamnya. Terjemahan kode Tarjan yang lebih harfiah adalah sebagai berikut:

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

Di bawah, kami memiliki Tarjan do-loop yang lebih rumit :

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

Kode semu gaya Java untuk tarjan do-loop yang rumit adalah sebagai berikut:

sum = 0;
while(true) {

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

(9) Operator penugasan bersyarat Tarjan dengan semua kondisi salah

Meskipun penjelasan panjang di atas mencakup sebagian besar hal, beberapa hal masih belum terselesaikan. Saya berharap bahwa orang lain suatu hari nanti akan menulis jawaban baru yang lebih baik berdasarkan milik saya yang menjawab pertanyaan ini.

Khususnya, ketika operator penugasan bersyarat := ifdigunakan, dan tidak ada kondisi yang benar, saya bukan nilai apa yang ditugaskan untuk variabel.

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

Saya tidak yakin, tetapi mungkin saja tidak ada tugas yang dilakukan untuk x:

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

Anda bisa meminta agar variabel sisi kiri yang terlihat dalam := ifpernyataan dideklarasikan sebelumnya. Dalam hal itu, bahkan jika semua kondisi salah, variabel masih akan memiliki nilai.

Atau, mungkin semua kondisi false merupakan kesalahan runtime. Alternatif lain adalah mengembalikan nullnilai khusus , dan menyimpannya nulldi argumen sebelah kiri penugasan.

Belum pernah melihat ini sebelumnya, tetapi saya pikir saya dapat menyimpulkan apa yang dimaksud dari konteks .. Agaknya ⟷ harus operasi swap, dan if G1 -> S1 | G2 - >S2 | ... fimerupakan konstruksi if / then / else-type yang juga mengembalikan nilai, seperti ?:operator ternary di C dan Java.

Dengan itu di tangan kita bisa menulis fungsi di atas dalam bahasa mirip Java seperti:

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