Осуществимые и неосуществимые пути
От: 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. Каждый шаг может быть ясным и корректным, но результат может оказаться очень сложным, с большим количеством неосуществимых путей. Эти неосуществимые пути делают код сложнее для понимания, потому что программисту приходится разбираться, какие сценарии поведения возможны, а какие нет.
Кроме того, неосуществимые пути могут являться причиной неэффективности кода из-за кореллирующих условных операторов.

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

Вывод.
Было аргументировано, что неосуществимые пути приводят к сложному для понимания коду. А возникают они из-за ненужных использований: последовательностей условных переходов, промежуточных переменных и оператора присваивания. Удаление неосуществимых путей делает программу более функциональной и понятной.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.