апликативное программирование 1

[juan_gandhi]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

int fact(int n) {
  return n < 2 ? 1 : n * fact(n-1);
}

и довольны типа. И интервьюёр доволен. А того не смекнули, что ваша функция для 17 вернёт -288522240. Разве ж це факториал? Это уже скорее гамма-функция от -0.0000000346593739, примерно, то есть, (-1.0000000346593739)! (примерно).

На самом деле ещё смешнее, fact(13) = 1932053504 даже не делится на 13; правильный ответ был бы 6227020800.

Тут что-то не так. И для отрицательных чисел тоже фигня получается; гамма функция для них, для целых отрицательных, не определена.

Правильнее было бы написать что-нибудь вроде

int fact(int n) {
  if (n < 0 || n > 12) throw new IllegalArgumentException("won't calculate factorial for " + n + ", should be between 0 and 12");
  return n < 2 ? 1 : n * fact(n-1);
}

Так, конечно, никто не делает, потому что непривыкшие мы. Мы, зато, можем легко найти объяснения, почему такое происходит и даже винить особенности JVM, или предлагать использовать long вместо int (и, соответственно, 20 вместо 12). Проблема, конечно, не в этом. Всегда найдутся обстоятельства.

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

А откуда вам-то всё это так хорошо известно? А вы в логи посмотрели; ну и вообще опыт подсказывает. Но так вы эти ваши выводы могли бы показать прямо на странице, чем мучать посторонних людей; если это, конечно, внутренняя страница.

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

С таким оптимизмом можно ж и в Вегас ездить - вы ведь не лох, вы обязательно выиграете!

Я что хочу сказать - в реальности наш код имеет дело не с результатом, а с возможным результатом. Это монада такая. Если нам пофиг если что не так, но мы знаем, что бывает что-то не так, то это у нас монада Option, aka Maybe. В принципе, вполне моделируется списком или множеством из не более чем одного элемента. Да и в цикле неплохо смотрится:

for (int f: factorial(n)) {
  System.out.println("factorial(" + n + ") = " + f);
}

List<int> factorial(final int n) {
  if (n < 0 || n > 12) return Collections.emptyList<Integer>();
  return n < 2 ? Arrays.asList(1) :
      factorial(n-1).map(new Function <Integer, Integer>() {
        public Integer apply(Integer k) {
          return n * k;
        }
      });
}

Это я написал в предположении, что в джаве у класса List есть метод map; такого метода, конечно, нету, поэтому нам тут надо бы переписать без рекурсии, с циклом. Но это неважно; важен принцип.

И тут я собираюсь покинуть простую нашу народную джаву и буду дальше использовать скалу в качестве иллюстрации, потому что на скале всё проще, и тот же пример пишется так:

for (f <- factorial(n)) {
  println("factorial(" + n + ") = " + f);
}

def factorial(n: Int): List[Int] = {
  if      (n < 0 || n > 12) List()
  else if (n < 2)           List(1) 
  else                      factorial(n-1) map (x => n * x)
}

Точнее, вместо списка в скале, конечно, надо использовать Option:

def factorial(n: Int): Option[Int] = {
  if      (n < 0 || n > 12) None
  else if (n < 2)           Some(1) 
  else                      factorial(n-1) map (x => n * x)
}

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

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

В джаве это у нас любимый приём: вызвать функцию и потом проверять, уж не null ли нам вернула эта функция. И понеслась, if (connection != null)... if (userId != null)... if (user != null).... Этим говнокодом, как фликр фотографиями кошек, заполнены все гиты, эсвээны, сивиэсы, перфорсы, виэсэсы, и в наибольшей степени - клиеркейсы.

И всё мало - процента на 84 беды джавного софтвера состоят в NPE, NullPointerException, внезапно выскакивающем неведомо откуда, хоть ты святой водой кропи этот код, а всё равно.

Я уж про си и говорить не буду, в отличие от джавы, где NPE можно уподобить мокрым штанам, в си всякий такой сегфолт - практически теракт, в следующее мгновение иранские хакеры проникнут к вам в компьютер и скачают номер вашей кредитной карточки. И ничего не поделаешь! Пойнтер так и норовит занулиться сам по себе, как будто это его естественное состояние! Но в си программисты более напуганные, и поэтому в си это значительно реже случается - что, конечно, обходится недёшево.

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

Comments

[agathpher.livejournal.com]

но, как я выяснил, 17! это как раз первый факториал размером в 49 битов - странный что Джава на нем выдыхается.

[yakov-sirotkin.livejournal.com]

На самом деле она видимо выдохнется на 13!, а 17! - первое отрицательное значение. Так что код в посте нужно поправить.

[ivan-gandhi.livejournal.com]

О блин, действительно. Спасибо!

[yakov-sirotkin.livejournal.com]

Зато теперь у нас есть не только отличная задача для интервью, но и хорошая иллюстрация того, насколько можно надеяться на проверку корректности параметров, насколько эффективен code review, как тяжело исправляются ошибки (у тебя до сих пор проверка n > 13 и сообщение про "between 0 and 16") и как легко ошибки копируются и как их потом не закрасить обратно.

[ivan-gandhi.livejournal.com]

О блин. Роскошная иллюстрация. :)