me.neoascetic

Почему Haskell "просто работает"? 

Я много раз читал, что если программа на Хаскеле скомпилировалось, то, скорее всего, она будет работать как запланировано. Меня заинтересовало, с чем эта черная магия связана, и поиски привели меня к статье на wiki языка, которой я и спешу поделиться. Описанное здесь можно использовать как иллюстрацию того, почему функциональный подход “лучше” императивного, т. е. относится не только к Хаскелю, но и к любым функциональным языкам.

Множество людей сталкиваются с интересным феноменом, когда начинают знакомиться с Хаскелем: стоит их коду скомпилироваться, он обычно сразу же корректно работает. Причём это, судя по всему, не проявляется в императивных языках даже с сильной типизацией, вроде Java или C#. Этот текст делает попытку пролить немного света на причины, которые приводят к подобному.

1. Типы ошибок

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

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

  2. Неумышленные ошибки. Более серьёзные, чем глупые ошибки, но, тем не менее, не связанные с недопониманием алгоритма.

  3. Умышленные ошибки. Это ошибки, которые чаще всего являются следствием недопонимания алгоритма. Программист, на самом деле, старался заставить программу делать, что она должна, и причина того, что она работает некорректно только в том, что программист не понял алгоритм должным образом.

Самая важная для нас разница - это разница между двумя последними типами ошибок. Кому-то даже покажется, что эти два типа на самом деле можно объединить под одной категорией. Другими словами, если код компилируется, но не работает,

Мы вернёмся к этой категоризации позже, по ходу дискуссии.

2. Способ вычисления

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

Фундаментальная операция при вычислениях в императивном языке - это модификация состояния. Императивная программа состоит из определённой последовательности команд, модифицирующих состояние. Это, конечно же, правда только до определённой степени, потому как функциональный стиль программирования может быть использован и в императивном языке программирования, но в целом чаще всего вычисления производятся именно путём модификации состояния. Важный вывод здесь в том, что результат вычисления в императивном языке программирования указывается не напрямую, а неявно, как сайд-эффект от исполнения команд модификации состояния. Уже исходя из этого можно сделать вывод, что результат императивного вычисления зависит от двух вещей: команд, учитывающих состояние, и порядка, в котором они исполняются. Из этих двух вещей только первая может быть проверена статически. Императивные языки, используемые в наши дни, делают весьма мало осмысленных статических проверок порядка следования команд (и не удивительно, ведь это весьма трудно!). Именно это и является причиной, почему множество программ, даже написанных на императивном языке с сильной типизацией и вполне себе нормально компилирующихся в итоге попросту не работают; статическая проверка, выполняемая компилятором, способна выявить только малую часть всех возможных ошибок.

Функциональное программирование немного иное. Здесь фундаментальная операция вычисления - это использование функций. В чистом функциональном языке, как, например, Хаскель, попросту не стоит вопроса об очерёдности исполнения команд. Итак, ответ на главный вопрос уже должен быть очевиден: при условии, что главная вычислительная операция в функциональных языках (применение функции) сильно типизирована, у нас попросту меньше места для возникновения ошибок и нам проще их отловить. Поэтому разница, с точки зрения статического анализа, в том, что в императивных языках только часть кода проверяется на самом деле, в то время как в функциональных языках он может быть проверен весь.

Давайте разберём на примере. Мы будем писать на вымышленном сильно типизированном императивном языке, сперва в императивном стиле, а после - в функциональном. Мы не будем использовать настоящие языки, чтобы лучше показать разницу между двумя подходами. Чтобы пример был прост, давайте реализуем часть алгоритма сортировки слиянием (merge sort). Мы предполагаем, что нам доступна функция merge, способная слить два сортированных списка в один (для двух не сортированных списков результат попросту будет некорректен).

list.sort() {
  if (self.size <= 1) {
      return;
  }

  (list1, list2) = self.split(self.size / 2);

  list1.sort();
  list2.sort();
  merged_list = merge(list1, list2);
  self.set(merged_list);
}

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

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

Давайте перепишем тот же кусок кода в более функциональном стиле. Я подчёркиваю, что это код не на Хаскеле, а все на том же псевдо-языке, что и в примере выше.

list.sort() : list {
  if (self.size <= 1) {
      return self;
  }

  (list1, list2) = self.split(self.size / 2);

  sorted_list1 = list1.sort();
  sorted_list2 = list2.sort();
  merged_list = merge(sorted_list1, sorted_list2);
  return merged_list;
}

Обратите внимание, что изменений весьма мало. Самое важное здесь - это то, что метод теперь не меняет список “на месте”, а попросту возвращает его, сортированный.

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

Можно поспорить, что такая же ошибка может-таки проявится, если попытаться слить list1 и list2 вместо того, чтобы передвинуть строчку с merge немного вверх, но это, на самом деле, не тот же случай. Мы говорим здесь об ошибках второго типа. Если программист понимает алгоритм, он будет пытаться слить сортированные списки. В императивной версии программы переменные list1 и list2 ссылались либо на сортированные списки, либо на не сортированные, в зависимости от того, из какой точки к ним обращались, что и являлось корнем проблемы, в то время как в функциональном подходе только переменные sorted_list1 и sorted_list2 ссылаются на сортированные списки.

3. Типы ошибок, отлавливаемых на этапе компиляции

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

  1. Глупые ошибки. Эти ошибки, вероятно, могут быть пойманы при обоих подходах, при условии что язык программирования сильно типизированный и имеет хороший дизайн. На эту категорию меньше влияет выбранный стиль программирования, чем на остальные.

  2. Неумышленные ошибки. Как мы уже увидели, этот тип ошибок зачастую может ускользнуть от проверок компилятора в императивном языке из-за того, что при императивном стиле программирования порядок исполнения операций не проверяется. Мы также увидели, как эти проблемы решаются при использовании функционального стиля в совокупности со статической проверкой типов. Тот факт, что функциональное программирование позволяет находить такие ошибки в то время как императивное - не позволяет, это, пожалуй, самая главная причина, по которой программы на Хаскеле “просто работают”.

  3. Умышленные ошибки. Это более серьёзные ошибки, которые ещё сложнее отловить в императивных языках. Тем не менее, даже они зачастую отлавливаются в функциональных языках программирования по той же причине, что и ошибки второго типа. Если вы недопоняли алгоритм, очень вероятно, что это приведёт к какой-либо ошибке на этапе компиляции при его реализации в функциональном стиле, в то время как при реализации в императивном стиле это недопонимание может принять форму неверного порядка следования команд, которые (в общем случае) не могут быть отловлены. Программисты на Хаскеле часто заявляют, что при работе над какой-либо сложной проблемой система типов сама помогала им заметить изъян в их логике, и только единицы раз ошибки этого типа были пофикшены благодаря самим программистам.