апликативное программирование 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

[spamsink.livejournal.com]

Факториал от нуля, между прочим, равен единице, так что нефиг тут
return n < 3 ? n ...

[ivan-gandhi.livejournal.com]

Спасибо, пофиксю.

[smalgin.livejournal.com]

На самом интересном месте? :)

[ivan-gandhi.livejournal.com]

Всё не совсем элементарно тривиально. Требуется время сформулировать; тексты почитать (типа EIP, что Джош Суерец сказал, что Тони Моррис сказал, что Эрик Торре Борре сказал...)

[dair-targ-one.livejournal.com]

Тогда уж не

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

а что-то типа:

int fact(int n) {
  assert n < 0 || n > 16, "won't calculate factorial for " + n + ", should be between 0 and 16";
  return n < 3 ? n : n * fact(n-1);
}

Иначе приложение начинает через чур страдать паранойей.

[ivan-gandhi.livejournal.com]

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

[udpn.livejournal.com]

На самом деле это всё херня. Если все типы exception'ов рассовывать по монадам и монадами монады погонять, получится такой же говнокод с обилием синтаксического мусора для избежания NPE, только на хаскелле. Там это всё вольётся в типы, liftM и прочую херню.

Так делать нельзя.

Лучше это делать как в Agda, попросту включив ограничения на аргументы функции в её тип. Факториал просто будет определён на int'ах от 0 до 12.

Или хотя бы сделать исключения эффектами и воспользоваться языком с системой эффектов и effect inference.

[starshoi.livejournal.com]

Вот вы мне не подскажете, как вы желающие, но несведующие массы заставляете мыслить правильно? У нас есть некоторая масса инженеров, которые как бы правильные слова знают, и модели есть на месте, общий дизайн и генерируемый код правильный. Но остаток надо писать руками. И вот эти руки норовят всюду вставить эти самые иф-зен-элзы так, что через пол-страницы начинает кружиться голова. Я уже старый, я им в код не лезу, про монады они не знают, но функциональное программирование в школе учили, про главные вещи им рассказали. Но как только посмотришь в сторону, все, кранты. Пишут они, естественно, на Джаве. Я им рассказал, что в Action Script есть closure и показал пару примеров. Но они только плечами пожали и тут же написали сложную логику на две страницы.

У вас все правильно мыслят?

[ivan-gandhi.livejournal.com]

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

[agathpher.livejournal.com]

А что, размер int фиксированный 48 битов во всех вариантах Джавы? А у float мантисса не больше раэмером?

Интересно, что в питоне на моем маке до 1000! вычисляеся правильно, а потом наступает переполнение стека %)

[ivan-gandhi.livejournal.com]

В джаве как бы не фиксированный, но де факто выбора немного.

[bravit.livejournal.com]

За метод резолюции спасибо, буду студентам рассказывать!

[ivan-gandhi.livejournal.com]

Ещё есть такая фамилия Робинсон. Его метод.

[yakov-sirotkin.livejournal.com]

Вроде Kotlin у нас тоже про NPE?

[ivan-gandhi.livejournal.com]

Любопытно.

[akuklev.livejournal.com]

Пример с факториалом мне не очень нравится, потому что тут использование эксепшна или option — решение, продиктованное никак не сущностью факториала, а только и исключительно слабостью системы типов джавы. В языке, где есть чистые инты и constrained-типы, это бы не понадобилось. Как-то нехорошо показывать элегантные идеи (Вы же, наверное, к аппликативным функторам и idiom brackets ведёте?) следует показывать на неэлегантных примерах.

Кстати, с неущербными примерами всё даже в Хаскеле плохо: Во всех языках с тьюринг-полной рекурсией в качестве примитива, все функции на самом деле не функции, а частичные функции, так что с точки зрения пуриста там весь мир надо оборачивать в idiom brackets для Option и рассматривать композицию функций не как честную композицию функций, а “(f ∘ g) if g terminates, ⊥ otherwise”.

Вот не люблю вот это вот всей душой, но отчего-то никто не пишет на агде, а эпиграмма-2 вообще не готова.

P.S. От души не понимаю, почему Option[T] не назвали Optional[T]. Поскупились на два символа, а как испортили дело. Either тоже неудачное название; вполне удачное для типа Either[A, B], в котором A и B играют симметричные роли, и совершенно идиотское для монады, где роли уже вопиюще асимметричны. Уж не знаю, как это следовало назвать, может Alternate[T, AltT], хотя наверное можно и получше выдумать.

[ivan-gandhi.livejournal.com]

Да, действительно. Спасибо, подумаю над примером.

[freedom_of_sea.livejournal.com]

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

И можно будет добавлять проверки прямо во время вычисления.

А чем вам не нравится perl style?

var = func() || die "cant do it\n";

[thedeemon.livejournal.com]

А с чего он станет вычисляться на всех процессорах? Это в фибоначчи можно параллельно ветки посчитать, а факториал классический он же последовательный.

[anton-solovyev.livejournal.com]

Почему-то все запугивают вот этими NPE, а я их не вижу. Не мешают. Не встречаются особенно.

Вообще, NPE происходят когда нет ясности с object life time, ownership и initialization. В чем, собственно, и состоит сложность любой программы.

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

[sorhed.livejournal.com]

В функциональных программах нет проблем с object life time, ownership и initalization.

Потому что все структуры данных — immutable. В этом-то и фича.

[stas]

Я понимаю, проблема есть. Но фер-то ке?
Эксепшен, собственно, тоже проблему не совсем решает - кто-то его ещё ловить должен, причём правильно ловить, со смыслом - иначе в результате опять белая страничка или надпись "у нас проблемы, приходите вчера".

[grey-kristy.livejournal.com]

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

[lomeo.livejournal.com]

В последнем примере на Java возвращаемый тип List<Integer>.
В примере на Scala всё-таки, наверное, if (n < 0 || n > 16) None, а не Option().

[ivan-gandhi.livejournal.com]

Спасибо!

[snowps.livejournal.com]

Вот мне всегда было интересно - из каких соображений в джаве нет беззнаковых типов?

[sassa-nf.livejournal.com]

зачем? размер результата увеличивается всего на 1 бит, а количество ошибок не меняется.

[sassa-nf.livejournal.com]

было иф - стало фор, особой разницы в ясности не добавится.

Но! Но теперь фор становится обязательным - это уменьшает количество NPE. Но NPE - это же только симптом. Уменьшает ли это количество ошибок?

Если раньше диагностика записывала стек-трейс в лог по NPE (прибор), то теперь нужно то же самое добавить в orElse. Ну, или смотреть на белую страничку.

Способ, конечно, вкусный, но является ли решением заявленных проблем?

[lomeo.livejournal.com]

В scala try/catch является выражением, поэтому ты прав, это то же самое. В общем, нужно было наверное не с NPE начинать примеры приводить.

[poznia.livejournal.com]

хорошее начало.

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

[gabaidulin.livejournal.com]

Справделивости ради надо сказать, что нужно проектировать программу, у которой почти не должно быть null в return. И об этом мы можем сказать с помощью аннотаций @NotNull. А для сухих штанов используем еще и Preconditions.

Ну и в принципе NullObject тащемта про то же, если взять этот частный случай.

И да, этот подход противоположен erlang и php. Но мне он больше нравится, потому что он строг. Если я не жду тут null, то я не хочу пытаться делать вид, что я его ждал. Лучше честно упасть, записав в лог проблему.

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

[vit-r.livejournal.com]

Так, конечно, никто не делает, потому что непривыкшие мы.

Как-то давно, ещё будучи студентом, на одном интервью для задания сделал защиту по входным параметрам и по выходным. Интервьюер сначало удивился, потом хмыкнул снисходительно. Жизнь без приключений - это не спортивно.

[akuklev.livejournal.com]

Кстати, по поводу Idiom Brackets: во втором из неимплементированных функциональных языков, которые я изобретал (вариант 2003 года, чуть подогнанный под синтаксис Скалы, чтобы Вам удобнее читать), для поднятия функции аппликативным функтором использовался значок $ перед аргументом по контейнерному типу которого определялось, куда поднимать.

Например, есть у нас x: Option[Double] и мы хотим посчитать от него синус, то пишем sin($x): Option[Double].
Или вот если есть xs: Set[Double], то можно получить множество синусов этих чисел sin($xs).
Если два аппликативных функтора коммутируют или конвертируются в коммутирующие функторы (например, если задана имплицитная конверсия обоих в некий общий), можно сделать даже $a + $b.

Особенно ценно это всё было в применении к стейт-монаде Var[T] (точнее, аппликативу Volatile[T], от которого Var[T] наследуется): вот есть у нас некая переменная a: Var[Double], а мы берём и пишем sin($a) и получаем (lazy) Volatile[Double].

Но функции ещё иногда комбинируют, а писать вещи типа 2 * $sin($b) или $square($sin($x)) слишком тяжеловесно. Поэтому пришлось придумать и idiom-brackets (правда тогда они так не назывались, статья про аппликативные функторы ещё не вышла).

До скального варианта for(x <- xs) {square(sin(x))} я тогда не догадался, поэтому там была несколько неказистая конструкция implicit(Volatile[Any]) {square(sin(x))}. Эта конструкция использовалась и для поддержки исключений на уровне системы типов: если метод пометить аннотацией @throws[SomeException], то его тип превращался из T в Either[T, SomeException], а контекст внутри него в implicit(Either(Any, SomeException, такой же контекст делался внутри блока catch(SomeException e), очень удобно.

А если в каком-то месте нужно было взять штуку типа подходящего под описание Volatile[Any], но _не_ эскейпить его, можно было использовать escape brackets <> (это придумал sorhed в 2006 году). Иногда возможна многозначность: напр. если xs: Volatile[Set[Double]], то т.к. Volatile и Set коммутируют, во вложенных контекстах могут существовать (Set[Double])<sin(xs)> и (Volatile[Double])<sin(xs)>.

Очень удобно было запихивать целые процедуры в implicit(Volatile[Any])-контекст и писать в императивном стиле функциональный код:
Если у нас x: Var[Double], то можно написать
val v = 2 * sin(x / 2)
и получить v: Double, а можно
val w = <2 * sin(x / 2)>
и получить w: Volatile[Double].

Потом дошло, что пурые функции это не совсем пурые функции, потому что они имеют ненулевое время выполнения, так что строго говоря каждое factorial(800) это не Integer, а Process[Integer], просто мы всегда работаем в implicit(Process[Any])-контексте. Соответственно всегда можно сделать вместо n = factorial(800) что-нибудь интересное вроде
p = <factorial(800)>
p.start
Log.info("Started!")
n = p // Evaluate
Log.info("Finished, duration was " + p.duration)

А можно и ещё хлеще: определить в методе public properties.

def someLengthyCalculation(n: Integer) {
  var _progress = 0.0
  def progress = progress
  ...
  for (val i <- 0..count) {
    progress = (Double) i/count
    ...
  }
}
 
p = <someLengthyCalculation(800)>
p.start
while(!p.finished) {
  Log.info("Progress: " + p.progress)
  wait(500 ms)
}

Ещё удобно, если глобальный контекст также содержит Logged[Any], позволяя в пурых на применении функциях писать в лог.

Несколько расширив понятие аппликативного контекста с использованием зависимых типов, можно сделать текущий синтаксис Cкалы этакой do-нотацией, которая после обработки макросами превращается в пурый код. Ставишь этак перед методом аннотации
@Reads(inRessourcesList), @Writes(outRessourcesList), @Suspends(blockersList)
и его тип T превращается в CPS(blockerList)[RW(inRessourceList, outRessourceList)[T], а тело в implicit packed do-notation для категории стрелок CPS+RW.

... я вот думаю, а не рассказать ли об этом синтаксисе скальщикам в EPFLе? Ведь стараниями xeno_by там скоро будут макросы, а ими это всё можно будет малой кровью имплементировать...

[ivan-gandhi.livejournal.com]

О как классно. С этим публикуемым прогрессом я трахался ещё хрен знает когда, изобретая cps; но тут всё как-то очень логично выглядит.

А где-нибудь это изложено подробнее?

[selfmade.livejournal.com]

> Но ваша картина мира не включает в себя возможность неполадок.

На это есть netflix chaos monkey.

[vaggie.livejournal.com]

Вам надо книжку написать для детей, что-нибудь наподобие Перельмана: "Занимательная Монада"

[ivan-gandhi.livejournal.com]

Роскошный текст; спасибо.