Осуществимые и неосуществимые пути
От: Nick_ Россия  
Дата: 19.10.04 15:23
Оценка: 71 (13)
#Имя: FAQ.functional.ways
Что бы не было скучно, я сделал вольный перевод статейки из журнала "Functional Programming" (ACM SIGPLAN). Я перевел только ключевые места. Полную статью можно найти в интернете.

"Paths between Imperative and Functional Programming" Thomas Ball tball@research.bell-labs.com

Предлагаю обсудить.

Осуществимые и неосуществимые пути.

Независимо от языка программирования, программа исполняет путь или последовательность инструкций. В императивных программах путь состоит из последовательности операторов. В функциональных программах из последовательности вычислений выражений.
В программе может быть огромное число путей исполнения, но не все они осуществимы. Путь в программе называется осуществимым, если существуют такие входные данные, при которых исполнение проходит по этому пути.
Неосуществимые пути появляются из-за того, что в программе могут быть кореллирующие условные переходы.
Например:
int foo1(int x)
{
  int y = x;
  if(x < 10) y++;
  if(x < 20) y++;
  return y;
}

В этой программе четыре пути исполнения, так как в ней два условных оператора. При этом один из путей неосуществим. Так как если x < 10, то также x < 20.
Мы можем переписать программу, что бы в ней не было неосуществимых путей:
int foo2(int x)
{
  if(x < 10)
    return x+2;
  else if(x < 20)
    return x+1;
  else
    return x;
}

Такие изменения уменьшили сложность программы и сделали ее эффект более явным.

Более сложный пример

Это часть реализации алгоритма упорядоченого бинарного дерева из книги "Introduction to Algorithms", T. Cormen, C. Leiserson и R. Rivest.
Node *DeleteNode(Node *z)
{
  Node *x, *y;

  if(z->left == 0 || z->right == 0)
    y = z;
  else
    y = leftmostNode(z->right);

  if(y->left == 0)
    x = y->right;
  else
    x = y->left;

  x->parent = y->parent;

  if(y->parent == 0)
    root = x;
  else if(y == y->parent->left)
    y->parent->left = x;
  else
    y->parent->right = x;

  if(y != z)
    z->key = y->key;

  return y;
}

Функция удаляет узел дерева, сохраняя порядок. Поиск узла, который должен встать вместо удаляемого делает функция leftmostNode.
Node *leftmostNode(Node *n)
{
  while(n->left != 0)
    n = n->left;
  return n;
}

В DeleteNode 36 путей. И только 8 из них осуществимы.
Ниже одна из возможных реализаций DeleteNode.
Node *DeleteNode(Node *z)
{
  if(z->left ==0)
    return reparent(z, z->right);
  else if(z->right == 0)
    return reparent(z, z->left);
  else
  {
    Node *y = leftmostNode(z->right);
    z->key = y->key;
    return reparent(y, y->right);
  }
}

Node *reparent(Node *y, Node *x)
{
  x->parent = y->parent;
  
  if(y->parent == 0)
    root = x;
  else if(y == y->parent->left)
    y->parent->left = x;
  else
    y->parent->right = x;

  return y;
}

В этой реализации всего 9 путей. Из них 8 осуществимы.
Программа стала яснее, из-за того, что теперь нет ненужных зависимостей между условными операторами.

Неосуществимые пути и связь императивного и функционального стиля.

Вторая реализация DeleteNode более функциональна по следующим причинам:
1) Было удалено большинство ненужных зависимостей порядка выполнения операторов.
Рассмотрим, первые два условных оператора в оригинальной процедуре. Есть три пути выполения первого оператора и два пути выполнения второго. Всего шесть путей через оба условных оператора, но осуществимы из них только три: путь через первый условный оператор однозначно определяет путь через второй.
2) Были удалены или локализованы временные переменные.
На самом деле, в каждой процедуре переменные присваиваются ровно один раз. Так что вторая реализация в Static Single Assignment форме.

Определение порядка выполнения операторов и деструктивные изменения переменных(присваивание) — императивный стиль программирования.
Императивные языки одобряют программирование в виде последовательности шагов. И это приводит к программам как оригинальный DeleteNode. Каждый шаг может быть ясным и корректным, но результат может оказаться очень сложным, с большим количеством неосуществимых путей. Эти неосуществимые пути делают код сложнее для понимания, потому что программисту приходится разбираться, какие сценарии поведения возможны, а какие нет.
Кроме того, неосуществимые пути могут являться причиной неэффективности кода из-за кореллирующих условных операторов.

Неосуществимые пути в программах, главным образом, возникают из-за ненужных зависимостей в порядке выполнения операторов и деструктивного изменения состояния(переприсваивания).
Последовательности условных операторов приводят к экспоненциальному росту количества путей. Операция присваивания может порождать зависимости между условными операторами сильно разнесенными в коде друг от друга.

Вывод.
Было аргументировано, что неосуществимые пути приводят к сложному для понимания коду. А возникают они из-за ненужных использований: последовательностей условных переходов, промежуточных переменных и оператора присваивания. Удаление неосуществимых путей делает программу более функциональной и понятной.
Re: Осуществимые и неосуществимые пути
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.10.04 22:13
Оценка:
Здравствуйте, Nick_, Вы писали:

N_>В этой программе четыре пути исполнения, так как в ней два условных оператора. При этом один из путей неосуществим. Так как если x < 10, то также x < 20.


Честно говоря меня совершенно не напрягают лишние пути если я могу четко понять алгоритм. Приведенный упрощенный вариант мне тоже больше нравится. Но не из-за меньшего количества путей, а из-за того что он более четко выражен. В нем выделена общая процедура (reparent).

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

Для сравнить я создал две реализации функции бинарного описка. Одну итеративную/императивную. Другую рекурсивную/функциональную:

using System;
using System.Collections.Generic;

class Program
{
    public static int BinarySearchImperative<T>(T[] array, int lo, int hi, T value, IComparer<T> comparer)
    {
        while (lo <= hi)
        {
            int i = (lo + hi) >> 1;
            int cmpResult = comparer.Compare(array[i], value);
            if (cmpResult == 0)
                return i;
            else if (cmpResult < 0)
                lo = i + 1;
            else
                hi = i - 1;
        }

        return ~lo;
    }

    public static int BinarySearchRecursive<T>(T[] array, int lo, int hi, T value, IComparer<T> comparer)
    {
        if (lo > hi)
            return ~lo;

        int i = (lo + hi) >> 1;
        int cmpResult = comparer.Compare(array[i], value);
        if (cmpResult < 0)
            return BinarySearchRecursive(array, i + 1, hi, value, comparer);
        else if (cmpResult > 0)
            return BinarySearchRecursive(array, lo, i - 1, value, comparer);
        else
            return i;
    }

    static void Main(string[] args)
    {
        int[] array = new int[] { 2, 4, 7, 8, 10, 20, 22, 23, 24, 26 };
        
        int ir = BinarySearchImperative(array, 0, array.Length - 1, 9, Comparer<int>.Default);
        int rr = BinarySearchRecursive(array, 0, array.Length - 1, 9, Comparer<int>.Default);

        Console.WriteLine("ir = {0} (~ir = {1})", ir, ~ir);
        Console.WriteLine("rr = {0} (~rr = {1})", rr, ~rr);
    }
}


По-моему, итеративный вариант проще в понимании. Так же он явно быстрее, так как нет затрат времени на передачу "баластных" параметров через параметры.

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

Кстати, интересно было бы глянуть на этот алгоритм на Хаскеле, Окамле и т.п. Интересно как без физического разрезания списка или поэлементного перебора получить середину...
... << RSDN@Home 1.1.4 beta 3 rev. 206>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Осуществимые и неосуществимые пути
От: Nick_ Россия  
Дата: 20.10.04 05:10
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Для сравнить я создал две реализации функции бинарного описка. Одну итеративную/императивную. Другую рекурсивную/функциональную:


VD>По-моему, итеративный вариант проще в понимании. Так же он явно быстрее, так как нет затрат времени на передачу "баластных" параметров через параметры.


А по моему, итеративный вариант как раз проще, только потому что в нем нет неосуществимых путей, как и в функциональном варианте.
На счет быстрее, я бы не стал так категорично утверждать. Во первых, нет никаких препятствий компилятору заменить хвостовую рекурсию на goto. Во вторых оптимизирующие компиляторы C/C++ так делают(например Intel C++). Наверное это должен делать и компилятор C#...

VD>Так что подобные примеры яряд ли можно считать доказательством приемущества функционального стиля. Это скорее доказательство того, что есть более оптимальные пути реализации и люди умеющие их находить.


Это вообще не доказательство, а показательство. Было бы это доказательством — тебе бы нечего было возразить.
Да, есть оптимальные пути реализации, но в функциональных языках большинство неоптимальных просто невозможно закодировать.
Re[2]: Осуществимые и неосуществимые пути
От: fuurin  
Дата: 20.10.04 11:38
Оценка:
VD>Так что я не стал бы все сваливать на избегание путей. Скорее при более четком выражении алгоритма нормализуется и количество путей.

Это верно, но число путей — количественная характеристика, в отличие от субъективного "понимания алгоритма" и его "четкого выражения". В статье утверждается, что большой коеффициент неосуществимых путей говорит о затруднённом понимании алгоритма. А уменьшение этого коэффициента достигается удалением "unnecessary sequencing" и "destructive update". Автор утверждает, что для функционального стиля программирования ни то, ни другое не характерно.

VD>Для сравнить я создал две реализации функции бинарного описка. Одну итеративную/императивную. Другую рекурсивную/функциональную:

VD>По-моему, итеративный вариант проще в понимании.
По мне, так твои примеры абсолютно идентичны. Единственное их отличие в замене while рекурсией не ставит их по разные стороны границы понимания/непонимания. Небольшой акцент в сторону простоты возможен, если читатель неуверенно себя чувствует в одном из примеров.

VD>Кстати, интересно было бы глянуть на этот алгоритм на Хаскеле, Окамле и т.п. Интересно как без физического разрезания списка или поэлементного перебора получить середину...

Так этот алгоритм и работает только с вектором — массивом данных с произвольным доступом. Потому и реализация отличаться сильно не будет при условии, что язык поддерживает такую организацию данных. Скажем, в Лиспе для этого есть vector.
Garbage In Garbage Out
Re[3]: Осуществимые и неосуществимые пути
От: VladD2 Российская Империя www.nemerle.org
Дата: 20.10.04 12:50
Оценка:
Здравствуйте, Nick_, Вы писали:

N_>А по моему, итеративный вариант как раз проще, только потому что в нем нет неосуществимых путей, как и в функциональном варианте.


Ну, т.е. по крайней мере ты согласен со мной в том, что выводы статьи явно надуманы.

N_>На счет быстрее, я бы не стал так категорично утверждать.


А я стану. Проверено не раз. При супер-пупер оптимизации (которой на практике увидить не так то просто) ты получишь тот же итеративый вариант. Учитывая то, что он проще смысла использовать рекурсию в данном случая я не вижу.

N_> Во первых, нет никаких препятствий компилятору заменить хвостовую рекурсию на goto. Во вторых оптимизирующие компиляторы C/C++ так делают(например Intel C++). Наверное это должен делать и компилятор C#...


Шарповский компилятор МС почти не делает оптимизаций. Оптимизации делает джит. А у него не много времени на выбор оптимального решения. Так что сложные вещи вроде раскрутки рекурсии он вряд ли будет делать. А рекурсивная функция с более чем 2 параметрами будет передавать остальные через стэк. А это уже сильный удар по производительности.

В общем, что гадать то? Могу сделать тест. Интеловский компилятор, правда, еще нужно скачать. Но не думаю, что в этом смысле он делает больше оптимизаций чем МС-ный.

VD>>Так что подобные примеры яряд ли можно считать доказательством приемущества функционального стиля. Это скорее доказательство того, что есть более оптимальные пути реализации и люди умеющие их находить.


N_>Это вообще не доказательство, а показательство. Было бы это доказательством — тебе бы нечего было возразить.


Выставляется это как доказательство. Ну, и на счет нечего возразить... скажем так — это зависит от доказательства.

N_>Да, есть оптимальные пути реализации, но в функциональных языках большинство неоптимальных просто невозможно закодировать.


Ну, это точно полная ерунда. Неоптимально можно сделать всегда и на чем угодно. Можно сойтись на том, что в императивном стиле выбор неоптимальных решений шире.
... << RSDN@Home 1.1.4 beta 3 rev. 206>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Осуществимые и неосуществимые пути
От: VladD2 Российская Империя www.nemerle.org
Дата: 20.10.04 12:50
Оценка:
Здравствуйте, fuurin, Вы писали:

VD>>Так что я не стал бы все сваливать на избегание путей. Скорее при более четком выражении алгоритма нормализуется и количество путей.


F>Это верно, но число путей — количественная характеристика, в отличие от субъективного "понимания алгоритма" и его "четкого выражения". В статье утверждается, что большой коеффициент неосуществимых путей говорит о затруднённом понимании алгоритма. А уменьшение этого коэффициента достигается удалением "unnecessary sequencing" и "destructive update".


С этим я и не спорю.

F> Автор утверждает, что для функционального стиля программирования ни то, ни другое не характерно.


Автор на основании первого умозаключения делает полностью высосанные из пальца выводы. Никакой логической связи тут нет. И мой пример хорошо показывает, что функциональный стиль тут не причем.

Возможно утверждение, что императивный стиль дает больший ростор для неоптимальности и верно. Но это не тоже самое, что функциональный стиль имеет какие-то приемущества.

Где-то рекурсивные алгоритмы явно выигрышнее. Например, при обработке деревьев. А где-то проигрышны. Обрабатывать массивы эффективнее императивно. Да и многие алгоритмы императивно выглядят лучне.

F>По мне, так твои примеры абсолютно идентичны. Единственное их отличие в замене while рекурсией не ставит их по разные стороны границы понимания/непонимания. Небольшой акцент в сторону простоты возможен, если читатель неуверенно себя чувствует в одном из примеров.


По-моему, итеративый вариант проще. Но даже идентичность восприятия разрушает выводы данной статьи. Главное у рекурсии в данном алгоритме нет никаких приемуществ.

F>Так этот алгоритм и работает только с вектором — массивом данных с произвольным доступом. Потому и реализация отличаться сильно не будет при условии, что язык поддерживает такую организацию данных. Скажем, в Лиспе для этого есть vector.


Ну, то есть функциональный стиль идет лесом?
... << RSDN@Home 1.1.4 beta 3 rev. 206>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Осуществимые и неосуществимые пути
От: fuurin  
Дата: 20.10.04 14:37
Оценка:
F>>Это верно, но число путей — количественная характеристика, в отличие от субъективного "понимания алгоритма" и его "четкого выражения". В статье утверждается, что большой коеффициент неосуществимых путей говорит о затруднённом понимании алгоритма. А уменьшение этого коэффициента достигается удалением "unnecessary sequencing" и "destructive update".

VD>Возможно утверждение, что императивный стиль дает больший ростор для неоптимальности и верно. Но это не тоже самое, что функциональный стиль имеет какие-то приемущества.


Говорится о двух примерах неоптимального кодирования: "unnecessary sequencing" и "destructive update".
Ты согласишься с тем, что функциональный стиль ограничивает попытку их применения, и в этом он имеет преимущество перед императивным стилем?

VD>Но даже идентичность восприятия разрушает выводы данной статьи.

Выводы этой статьи — то, что ты выделил жирным, и с ними ты, кажется, согласен. В твоём примере коеффициент неосуществимых путей равен нулю, поэтому твой пример ничего не опровергает.

F>>Так этот алгоритм и работает только с вектором

VD>Ну, то есть функциональный стиль идет лесом?
А какие элементы функционального стиля ты хотел бы увидеть в реализации этого алгоритма? Возможность реализации рекурсией ты сам же и показал. Что ещё? Какой-то особый доступ к элементам вектора по индексу?
Garbage In Garbage Out
Re[4]: Осуществимые и неосуществимые пути
От: Nick_ Россия  
Дата: 20.10.04 15:13
Оценка: +1
Здравствуйте, VladD2, Вы писали:

N_>>Да, есть оптимальные пути реализации, но в функциональных языках большинство неоптимальных просто невозможно закодировать.


VD>Ну, это точно полная ерунда. Неоптимально можно сделать всегда и на чем угодно. Можно сойтись на том, что в императивном стиле выбор неоптимальных решений шире.


Будь конструктивнее. С тобой невозможно спорить только по одной причине:
сначала ты пишешь что я сказал полную ерунду, а потом воспроизводишь мою фразу в другом виде.
"в императивном стиле выбор неоптимальных решений шире" равносильно тому, что "есть такие решения, которые в функциональных языках невозможно закодировать".

Это мне напоминает годы, когда я ходил в детский сад. Однажды я спорил с другом, как называются фишки в игре. Я говорил что это фишки, а он что это ракетки. В конце концов он выдал фразу: "я же говорил что это фишки!". После этого спор пошел на тему того, что это я так говорил а не он...

Не надо тут разводить детсад.
Re[5]: Осуществимые и неосуществимые пути
От: VladD2 Российская Империя www.nemerle.org
Дата: 20.10.04 16:18
Оценка:
Здравствуйте, fuurin, Вы писали:

F>Говорится о двух примерах неоптимального кодирования: "unnecessary sequencing" и "destructive update".

F>Ты согласишься с тем, что функциональный стиль ограничивает попытку их применения, и в этом он имеет преимущество перед императивным стилем?

Возможно. Но при этом я ограничен в выразительности, что явно является недостатком.

VD>>Но даже идентичность восприятия разрушает выводы данной статьи.

F>Выводы этой статьи — то, что ты выделил жирным, и с ними ты, кажется, согласен. В твоём примере коеффициент неосуществимых путей равен нулю, поэтому твой пример ничего не опровергает.

Вывод статьи такой какой есть. Я согласен с некоторыми утвержедниями и предпослыками. Но несогласен с выводом.

F>А какие элементы функционального стиля ты хотел бы увидеть в реализации этого алгоритма? Возможность реализации рекурсией ты сам же и показал. Что ещё? Какой-то особый доступ к элементам вектора по индексу?


Я вот вижу, что большинство ФЯ почему-то работают со списками так как будто они могут быть реализованы только в виде связанного списка. И это меня сильно коробит. Я вот не очень понимаю каковы приемущества функциональных языков если нужно реализовать те самые эффективные алгоритмы. Ну, и не очень вижу разницу между рекурсией в ИЯ и ФЯ. Возможно я просто чего-то не вижу. Вот и прошу меня подтолкнуть к верному видению.
... << RSDN@Home 1.1.4 beta 3 rev. 206>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: ФЯ ограничены связанными списками?
От: fuurin  
Дата: 20.10.04 20:52
Оценка:
VD>Я вот вижу, что большинство ФЯ почему-то работают со списками так как будто они могут быть реализованы только в виде связанного списка. И это меня сильно коробит. Я вот не очень понимаю каковы приемущества функциональных языков если нужно реализовать те самые эффективные алгоритмы.

Тут уж я могу только строить догадки — сам разбираюсь с ФЯ только пару месяцев.
Очевидный ответ — ты видел те алгоритмы, которые в своей реализации требуют связанный список. Предположу, что это примеры использования рекурсии взамен итерации. Так же предположу, что это были эффективные примеры использования связанных списков. Для эффективной реализации других алгоритмов имеются другие типы: array (vector), tuple, hashtable.


VD>Ну, и не очень вижу разницу между рекурсией в ИЯ и ФЯ.

Смею утверждать, что твой пример реализации бинарного поиска с помощью рекурсии — и есть ФЯ.
Практикующих ФЯ прошу меня поправить, если я заблуждаюсь.
Garbage In Garbage Out
Re[5]: Осуществимые и неосуществимые пути
От: VladD2 Российская Империя www.nemerle.org
Дата: 20.10.04 23:36
Оценка: -1
Здравствуйте, Nick_, Вы писали:

N_>Будь конструктивнее. С тобой невозможно спорить только по одной причине:

N_>сначала ты пишешь что я сказал полную ерунду, а потом воспроизводишь мою фразу в другом виде.

Ерунда одно из утверждений. В измененном виде я с ней могу согласиться. Так что вроде как я полностью конструктивен.

N_>"в императивном стиле выбор неоптимальных решений шире" равносильно тому, что "есть такие решения, которые в функциональных языках невозможно закодировать".


Совсем не равносильны. Опять таки эту фразу я мог бы принять если ее записать так: "Есть такие решения которые в функциональном стиле труднее закодировать." Те же самые лишние пути без проблем можно реализовать.

N_>Это мне напоминает годы, когда я ходил в детский сад. Однажды я спорил с другом, как называются фишки в игре. Я говорил что это фишки, а он что это ракетки. В конце концов он выдал фразу: "я же говорил что это фишки!". После этого спор пошел на тему того, что это я так говорил а не он...


Хорошо тебе... помнишь что с тобой в детсаду было.

N_>Не надо тут разводить детсад.


Дык отличай разные вещи и не будешь видеть детсад где попало.
... << RSDN@Home 1.1.4 beta 3 rev. 206>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: вред лишних деталей
От: beroal Украина  
Дата: 31.10.04 17:10
Оценка: 1 (1) +1
Здравствуйте, VladD2, Вы писали:

F>>Говорится о двух примерах неоптимального кодирования: "unnecessary sequencing" и "destructive update".

F>>Ты согласишься с тем, что функциональный стиль ограничивает попытку их применения, и в этом он имеет преимущество перед императивным стилем?
VD>Возможно. Но при этом я ограничен в выразительности, что явно является недостатком.
Ограничение выразительность не является недостатком. Чем проще семантика языка, тем быстрее его выучишь и легче разобраться в программе.
Статья доказывает, что если в программе нет лишних конструкций (путей исполнения, например), то новый человек быстрее разберется в её логике, и, следовательно, быстрее возьмёт на поддержку. Ведь каждый новый, как бы это сказать, факт в программе требует дополнительных умственных усилий: «а что, если исполнение пойдёт по этой ветке?». Сначала выбрасываем лишнее из программы, затем из языка. Это первый шаг к функциональному программированию.
Я бы не писал это так подробно, если бы меня не достали программы-монстры. Они требуют к себе гораздо больше внимания, чем достойны.
P.S. IMHO вторая реализация из статьи действительно понятнее. Я даже разобрался, что она делает, хотя и непонятно, зачем. А в первой, пожалуй, без автора не разберусь...
Re[7]: ФЯ ограничены связанными списками?
От: beroal Украина  
Дата: 31.10.04 17:22
Оценка:
Здравствуйте, fuurin, Вы писали:

VD>>Я вот вижу, что большинство ФЯ почему-то работают со списками так как будто они могут быть реализованы только в виде связанного списка. И это меня сильно коробит.

F>Тут уж я могу только строить догадки — сам разбираюсь с ФЯ только пару месяцев.
Догадки совершенно верные. Для примера из статьи подошло бы бинарное дерево, которое реализуется ничуть не сложнее списка. array (vector), tuple, hashtable — всё это есть например в Haskell, думаю, и в других ФЯ. Для алгоритмов не только можно, но и нужно использовать те представления данных, которые наиболее естественны и эффективны. ФП вовсе не ограничивает программиста последовательности как связанного списка, если он сам себя не ограничивает. Например, я видел реализацию последовательности специально для быстрой их конкатенации.
Re[7]: вред лишних деталей
От: TheBeard Россия  
Дата: 01.11.04 15:17
Оценка:
Что-то тут не так. Вот язык машины Тьюринга или нормальные алгорифмы
Маркова весьма просты семантически. Выучить легко, да. А вот написать
что-нибудь нетривиальное или разобраться в уже написанном...

Если МТ кажется вм слишком абстрактным примером, то АМ реализованы в
виде языка Рефал, и я даже видел программную систему, где он использовался.

beroal wrote:

> Чем проще семантика языка, тем быстрее его выучишь и легче разобраться в программе.
Posted via RSDN NNTP Server 1.9 gamma
Re[8]: вред лишних деталей
От: beroal Украина  
Дата: 01.11.04 17:01
Оценка:
Здравствуйте, TheBeard, Вы писали:

TB>Что-то тут не так. Вот язык машины Тьюринга или нормальные алгорифмы

TB>Маркова весьма просты семантически. Выучить легко, да. А вот написать
TB>что-нибудь нетривиальное или разобраться в уже написанном...
Наверное, потому, что они использовались для решения неестественных для них задач. И МТ, и АМ, и лямбда-исчисление создавались для теоретических построений. То, что лямбда-исчисление применяется и в более приземленных задачах просто чудо, случайная удача. У МТ на практике применимость вообще нулевая, так как она больше напоминает ассемблер, а ассемблер сейчас не в моде.
Может показаться, что я предлагаю упрощать семантику до нуля. Нужен разумный компромисс, и не должно быть явно дублирующих и малоиспользуемых конструкций.
Я останусь при своём мнении. Меньше знаешь — крепче спишь.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.