Как работает псевдокод Тарьяна (объяснил кто-то знакомый с C или Java)?

40

Короткая история

Известный компьютерный ученый Тарьян написал книгу несколько лет назад. Он содержит абсолютно странный псевдокод. Кто-нибудь, пожалуйста, объясните это?

Длинная история

Тарьян известен многими достижениями, в том числе тем, что он был соавтором кустарников . Он опубликовал книгу " Структуры данных и сетевые алгоритмы » в 1980-х годах.

Весь псевдокод в книге Тарьяна написан на языке его собственного изобретения. Соглашения о псевдокоде очень регламентированы. Это почти настоящий язык, и можно было бы написать для него компилятор. Тарьян пишет, что его язык основан на следующих трех:

Я надеюсь, что кто-то, знакомый с одним или двумя из вышеперечисленных языков или работой Тарьяна, сможет ответить на мой вопрос.

Пример функции, написанной на языке Тарьяна, показан ниже:

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;

Я видел много псевдокода, но я никогда не видел ничего подобного Тарьяну. Как работает псевдокод Тарьяна? Как можно переписать примеры псевдокода Тарьяна как нечто, похожее на C или Java? Это даже не должно быть C или Java. Конструкция if-else на языке Тарьяна не только отличается от языков семейства C, но также отличается от Python, MATLAB и многих других.

programming-languages Сэм Малдун
источник
6
Что конкретно вы не понимаете? Какое объяснение синтаксиса и семантики дается в книге?
Рафаэль
8
Вы скопировали образец откуда-то или расшифровали его сами? Неужели последние две строки внутри тела функции больше не имеют отступов? И действительно ли returnутверждение заканчивается запятой?
Берги

Ответы:

63

Оглавление

Я разделю свое объяснение псевдокода Тарьяна на следующие разделы:

  1. Блоки Тарьяна If-else ( операторы ->& |)
  2. Тесты по назначению и равенству ( :=и =)
  3. Есть else if, но нет elseконструкции
  4. Оператор условного присвоения Тарьяна := if

  5. Дополнительные примеры Тарьяна ifи:= if
    5.5. Тарьяновые массивы (или списки)

  6. Резюме операторов

  7. Оператор двухконечной стрелки Тарьяна ( ⟷)
  8. Do-циклы Тарьяна похожи на циклы while C / Java
  9. Оператор условного присваивания Тарьяна со всеми ложными условиями

(1) Блоки Тарьяна, если бы еще

(операторы →а |)

if-elseКонструкция является , пожалуй, наиболее фундаментальной структурой управления на языке Tarján в. В дополнение к C-подобным if-блокам, поведение if-else очень близко встроено в назначения Тарьяна и циклы while. Оператор стрелки Тарьяна ->(или →) является разделителем между условием оператора if и блоком выполнения оператора if.

Например, на языке Тарьяна мы можем иметь: 

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

Если мы частично переведем приведенную выше строку кода Тарьяна в C или Java, мы получим следующее:

if (a = 4)
    x := 9
fi

Вместо правильных фигурных скобок (как в C и Java) Тарьян оканчивает if-блок с помощью слов на английском языке в стиле АЛГОЛ:fi

Если мы продолжим перевод нашего примера выше, мы получим: 

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

(2) Тесты на присвоение и равенство ( :=и =)

Тарьян берет эти операторы из ALGOL (позже это также можно увидеть в Pascal).

Тарьян использует =для тестов на равенство, а не для заданий (поэтому он работает как Java ==).

Для назначения Тарьян использует :=, который работает как Java =.

Таким образом, если мы продолжим перевод нашего примера, мы получим: 

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

Вертикальная черта (или «труба» или |) на языке Тарьяна эквивалентна else ifключевому слову в Си или Java.
Например, на языке Тарьяна мы можем иметь:

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

Tarjan-код выше переводится как: 

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

(3) else ifтолько и без elseконструкции

Раньше я освещал основы if-слов без описания нюансов. Однако мы не будем обсуждать мелкие детали. Последнее предложение в if-elseблоке Tarjan-ian всегда должно содержать оператор arrow ( →). Таким образом, нет только elseна языке Тарьяна else if. Самым близким к else-блоку в языке Тарьяна является создание самого правильного условия теста true.

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

В C / Java мы бы имели:

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

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

Примеры легче понять, чем общие описания. Однако теперь, когда у нас есть несколько примеров за поясом, знайте, что общий формал конструкции Тарьяна if-else выглядит следующим образом:

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

Персонаж |какif else

Символ →отделяет тестовое условие от материала для дел.

(4) Оператор условного присвоения Тарьяна := if

Тарьяна ifможно использовать двумя совершенно разными способами. До сих пор мы описали только одно из применений тарджанцев if. Несколько запутанно, но Тарьян все еще использует нотацию / синтаксис ifдля второго типа if-construct. То if, что используется, основано на контексте. Анализ контекста на самом деле очень прост, поскольку второй тип таржана ifвсегда предопределен оператором присваивания.

Например, у нас может быть следующий код Тарьяна: 

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

Начните отступление

Поработав некоторое время с кодом Тарьяна, вы привыкаете к порядку операций. Если мы заключим условие проверки в скобки в приведенном выше примере, мы получим:

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

a = 4не является операцией присваивания. a = 4это как a == 4- он возвращает истину или ложь.

Конец отступления

Это может помочь представить := ifсинтаксис для одного оператора, отличного от :=и, ifфактически, мы будем ссылаться на:= if оператор оператором условного присваивания.

Ибо ifмы перечислим (condition → action). Поскольку := ifмы перечисляем, (condition → value)где valueнаходится значение правой стороны, мы могли бы присвоить левой сторонеlhs

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

в C или Java может выглядеть так: 

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

Рассмотрим следующий пример «условного присваивания» в коде Тарьяна:

# Тарьян Пример пятого примера x: = a = 4 → 9 | a> 4 → 11 | правда → 99 фи

В C / Java мы бы имели: 

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

(5) Резюме операторов:

Пока что имеем:

  • :=...... Оператор присваивания (C / Java =)

  • =...... Тест на равенство (C / Java ==)

  • → ...... Разделитель между тестовым состоянием блока if и телом блока if

  • | ..... C / Java еще-если

  • if ... fi ..... блок if-else

  • := if... fi ..... Условное присвоение на основе блока if-else

(5.5) Тарьянские списки / массивы:

Язык Тарьяна имеет встроенные контейнеры, похожие на массивы. Синтаксис для массивов Тарьяна намного более интуитивен, чем запись для if elseоператоров Тарьяна .

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

Доступ к элементам массива Тарьяна осуществляется с помощью круглых скобок (), а не квадратных скобок[]

Индексирование начинается с 1. Таким образом, 

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

Ниже показано, как создать новый массив, содержащий 1-й и 5-й элементы [1, 2, 3, 4, 5, 6, 7]

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

Оператор равенства определен для массивов. Следующий код печатаетtrue

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

Тарьян может проверить, является ли массив пустым, - сравнить его с пустым массивом. 

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

Можно создать представление (не копировать) подмассива, предоставив оператору несколько индексов в ()сочетании с..

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) Дополнительные примеры Тарьяна ifи:= if

Ниже приведены другие примеры условного присваивания Тарьяна ( := if): 

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

(true --> b)самый левый (cond --> action)пункт, имеющий истинное условие. Таким образом, исходный пример шестого присваивания имеет то же поведение присваивания, что иa := b

Ниже приведен наш самый сложный пример кода Тарьяна:

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

Ниже приведен перевод кода Тарьяна для объединения двух отсортированных списков. Следующее не совсем C или Java, но гораздо ближе к C / Java, чем версия 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..]);
    }
}

Ниже приведен еще один пример кода Tarjan и перевода в нечто похожее на C или 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;

Ниже приведен перевод 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) Оператор двухконечной стрелы Тарьяна (<--> )

Ниже приведен пример кода Тарьяна: 

x <--> y

Что делает оператор Double Arrow ( ⟷) на языке Тарьяна?
Ну, почти все переменные в языке Тарьяна являются указателями. <-->это операция обмена Следующие принтыtrue 

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

После выполнения x <--> y, xуказывает на объект , который yиспользуется для указания , и yуказывает на объект , который xиспользуется для указания.

Ниже приведено выражение Tarjan с использованием <-->оператора:

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

Ниже приведен перевод кода Тарьяна выше в альтернативный псевдокод:

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;

В качестве альтернативы мы могли бы иметь: 

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

Ниже приведен пример одной из функций Тарьяна с использованием ⟷оператора:

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;

Ниже приведен перевод функции Тарьяна meshв псевдокод, который не является C, но больше похож на C (условно говоря). Цель этого - показать, как работает ⟷оператор Тарьян .

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-циклы Тарьяна похожи на циклы while C / Java

Язык ifи forконструкции Тарьяна знакомы программистам C / Java. Однако ключевое слово Tarjan для цикла while - это do. Все do-loops заканчиваются ключевым словом od, которое является обратным написанием do. Ниже приведен пример:

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

В псевдокоде в стиле C мы имеем: 

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

Вышесказанное на самом деле не совсем верно. Do-цикл Tarjan - это действительно C / Java while(true)с вложенным в него блоком if-else. Более буквальный перевод кода Тарьяна выглядит следующим образом:

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

Ниже у нас есть более сложный Tarjan- doцикл: 

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

Псевдокод в стиле C / Java для сложного doцикла Tarjan выглядит следующим образом:

sum = 0;
while(true) {

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

(9) Оператор условного присваивания Тарьяна со всеми ложными условиями

Хотя длинное объяснение выше охватывает большинство вещей, некоторые вопросы все еще остаются нерешенными. Я надеюсь, что кто-то еще когда-нибудь напишет новый улучшенный ответ, основанный на моем, который отвечает на эти проблемы.

Примечательно, что когда используется оператор условного присваивания := if, и никакое условие не является истинным, я не являюсь тем, какое значение присваивается переменной.

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

Я не уверен, но возможно, что никакое назначение не сделано x: 

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

Вы могли бы потребовать, чтобы переменная левой стороны, видимая в := if выражении, была предварительно объявлена. В этом случае, даже если все условия ложные, переменная все равно будет иметь значение.

В качестве альтернативы, возможно, все ложные условия представляют собой ошибку времени выполнения. Другой вариант - вернуть специальное nullзначение и сохранить его nullв левом аргументе присваивания.

Сэм Малдун
источник
7
Я думаю, что простая реализация переводчика / переводчика и / или написание операционной семантики была бы более ценным способом использования вашего времени в этом отношении.
Дерек Элкинс
2
Стоит отметить, что некоторые из этих функций более «экзотичны», чем другие. Например, существует, вероятно, столько языков, где =означает сравнение, чем где это означает присвоение (если бы я когда-либо писал язык, я сделал бы это синтаксической ошибкой, и просто имел бы :=и ==). С другой стороны, оператор подкачки - это то, что происходит только в специализированных языках, где это была обычная операция; на других языках, хотя, вы могли бы просто взять на себя функцию библиотеки под названием swapи заменить h1 ⟷ h2с , swap(h1, h2)а не выписывая об осуществлении каждый раз.
IMSoP
2
Почему это [1, 2] = [1, 2, 3, 4, 5]правда?
Эрханнис
3
|Оператор является охранником . Они используются в Haskell (и я полагаю, что другие функциональные языки) в определениях функций: f x | x == 0 = 1; x == 1 = 1; otherwise = f (x-1) + f(x-2)здесь otherwiseесть псевдоним Trueи fопределяет числа Фибоначчи.
Бакуриу
2
@DerekElkins Почему ты так думаешь? По сравнению с простым написанием своего понимания на естественном языке (до уровня детализации, достаточного для понимания другими людьми), обе упомянутые вами работы потребуют значительно больше времени, насколько я могу судить. Не ясно, что это было бы более ценным использованием времени (особенно если цель, которую мы ищем, - это прежде всего понимание ).
ShreevatsaR
7

Никогда раньше такого не видел, но я думаю, что могу понять, что имеется в виду из контекста. Предположительно, ⟷ операция должна быть операцией подкачки и if G1 -> S1 | G2 - >S2 | ... fiявляется конструкцией типа if / then / else, которая также возвращает значение, как троичный ?:оператор в C и Java.

Имея это в виду, мы могли бы написать вышеупомянутую функцию на 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;
}
Дэниел МакЛори
источник