среда, 30 декабря 2009 г.

[comp.prog.flame] Почему мне не понравилась статья “Элементы функциональных языков”

Выполняю обещание, данное в предыдущей заметке, и пытаюсь объяснить, почему мне не понравилась статья Евгения КирпичёваЭлементы функциональных языков”. Если коротко, то тремя вещами:

  • не соответствием поставленной цели и содержимого статьи;
  • стилем статьи и
  • приведенными в статье примерами.

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

Поставленная цель и содержимое

Во введении указывается, какую цель преследует автор:

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

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

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

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

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

Стиль статьи

Стиль статьи не понравился мне тремя вещами.

Во-первых, восторженными эпитетами. Такие речевые обороты, как:

В статье-«жемчужине» «Generic descrimination: sorting and partitioning unshared data in linear time» Фрица Хенгляйна…

Ralph Hinze, «Fun with Phantom Types» ([75]): превосходный обзор, описывающий: язык…

Ralf Hinze, Johan Jeuring, и Andres Löh, «Typed Contracts for Functional Programming» ([76]): интереснейшая статья

…а также в потрясающей диссертации Нила Митчелла «Transformation and analysis of functional programs»…

лично мне в техническом тексте кажутся чужеродными. Сюда же можно отнести и другие характеристики в превосходной степени, которые автор дает статьям/книгам, примерам и внешним инструментам. Например, “в его знаменитой работе”, “в его знаменитой лекции”, “в его знаменитой статье”, “знаменитая библиотека” – все это вызывает смешанные чувства: сам себя ощущаешь неучем (поскольку ничего раньше об этих “знаменитых” вещах не слышал), но и подозреваешь, что эта знаменитость достигнута в очень узких кругах ;)

Во-вторых, подача материала с отсылками читателя к будущим разделам, для меня оказалась сложной для восприятия. Например, в разделе 5.7 упоминается какая-то система уравнений, которая будет обсуждаться только в разделе 5.10. А в разделе 5.9 дается рекомендация читателю поискать материал самостоятельно где-то в разделе 5.11:

Для всякого алгебраического типа определена чрезвычайно общая операция свертки (см. 11), абстрагирующая способ вычисления «по индукции» (снизу вверх) над значениями такого типа. Предлагается обратиться за разъяснениями к соответствующей подстатье.

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

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

В программировании данная идея впервые появилась, вероятно, в конкатенативных языках, таких как FORTH.

Вот вы раньше слышали о конкатенативных языках? Я нет.

Сюда же я бы отнес и использование автором некоторых понятий, которые либо не раскрываются в статье (например, “В языке Haskell соблюдается ссылочная прозрачность…” – хорошо, если читатель знает, что это такое), либо раскрываются уже после того, как были упомянуты (например, CPS-преобразования).

Ну а главное в стиле автора – это “заумность” текста. Это проявляется как в подаче материала (скажем, главу о свертках я так и не понял, еще хорошо, что о foldl и foldr я читал раньше и имел опыт их использования в Scala), так и в отдельных фразах.

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

При дефункционализации программ высшего порядка зачастую получаются знакомые и несколько неожиданные алгоритмы: к примеру, из программы, составляющей список узлов дерева при помощи разностных списков, получается программа, использующая хвосторекурсивный алгоритм (см. 7) с аккумулятором.

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

Monoid — класс типов, чьи значения образуют алгебраическую структуру «моноид» (см. статью «Моноиды в Haskell и их использование» (Дэн Пипони, перевод Кирилла Заборского) [137], а также презентацию Эдварда Кметта «Introduction to monoids» [98]), т. е. на значениях определена бинарная операция «комбинирования»:
mappend :: (Monoid m) => m -> m -> m
А также задан «нейтральный элемент» mempty :: (Monoid m) => m, являющийся единицей для mappend); а также похожий класс MonadPlus;

Ну и еще пара придирок по стилю:

  • видимо, каждый раздел статьи раньше был самостоятельной статьей. Поскольку после их объединения в одну большую статью в тексте так и остались фразы вида “Часть способов имитации замыканий описана в статье о функциях высшего порядка (см. 3).” Это создает впечатление некоторой халтурности, т.е. отдельные статьи объединили в качестве разделов, но не изменили способ именования соседних частей большой статьи;
  • лично меня напрягает, когда автор в тексте ссылается на свои собственные статьи в третьем лице: “см. статью «Изменяемое состояние: опасности и борьба с ним» Евгения Кирпичёва [180]”. Может это вполне допустимо и нормально, но меня раздражает.

Примеры кода в статье

К примерам кода в статье есть три претензии.

Во-первых, слишком большое количество языков было использовано для иллюстраций. Если не ошибаюсь, то в статье использованы: Haskell, Scheme, Python, C, Java, Matematica, Erlang, РЕФАЛ. Для меня это явный перебор. Для того, чтобы показать принципиальные элементы функциональных языков достаточно было бы использование всего лишь одного языка. Того же Haskell, к примеру.

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

  • фрагмент кода для балансировки “черно-белых” деревьев (раздел 5.10):
       balance :: Color -> Tree a b -> (a,b) -> Tree a b -> Tree a b
       balance B (T R (T R a x b) y c) z d
         = T R (T B a x b) y (T B c z d)
       balance B (T R a x (T R b y c)) z d
         = T R (T B a x b) y (T B c z d)
       balance B a x (T R (T R b y c) z d)
         = T R (T B a x b) y (T B c z d)
       balance B a x (T R b y (T R c z d))
         = T R (T B a x b) y (T B c z d)
       balance color a x b = T color a x b
    чтобы понять суть моих претензий, попробуйте представить, что в этом коде есть ошибка, и подумайте, как ее найти.
  • наплевательское отношение функциональщиков к именованию сущностей демонстрируется в разделе 10:
       toUnixMillis :: String -> Integer
       toUnixMillis s = case (parseDate "YYYY/MM/DD hh:mi:ss" s) of
         Date y mon d h m ss -> ss + 60*m + 3600*h + ....
    Вот интересно, почему параметру ss (это секунды) не было дано имя s, по аналогии с параметрами d, h, m? Потому, что имя s уже занято? А до имени sec не удалось додуматься? Или же это экономия на спичках? За такой код своему подчиненному я бы устроил выволочку и заставил бы переписать, например, так:
       toUnixMillis :: String -> Integer
       toUnixMillis strDateTime = case (parseDate "YYYY/MM/DD hh:mi:ss" strDateTime) of
         Date year mon day hour min sec -> sec + 60*min + 3600*hour + ....

В-третьих, я не понял, зачем был приведен ряд примеров. Скажем, примеры на языке пакета Mathematica в разделе 10. Может быть они интересны изучающему этот пакет, но не мне. Или, к примеру, фрагмент из раздела 9:

   data JSValue = JSNull
                | JSBool Bool
                | JSRational Bool Rational
                | JSString JSString
                | JSArray [JSValue]
                | JSObject (JSObject JSValue)

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

Ну и другие непонравившиеся мне моменты

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

Тем не менее, в течение очень долгого времени в силу ряда трудностей реализации (см. секции «Имитация» и «Реализация») «промышленные»-языки предоставляли крайне ограниченную поддержку функций высшего порядка.

Тут хочется напомнить про Smalltalk и его блоки кода, которые суть функции высшего порядка и замыкания. Никаких проблем с реализаций ни в конце 70-х, ни в 80-х с этим делом не наблюдалось.

Из-за некоторой путаницы с тем, что понимать под порядком функции при наличии каррирования (считать ли isAsubstringOfB функцией второго порядка из-за того, что результат ее применения к одному аргументу — функция первого порядка типа String -> Bool?), иногда порядком функции считают глубину самой вложенной слева стрелки: ниже приведены три типа, соответствующих функциям первого, второго и третьего порядков.

Ни из этого определения, ни из последующих примеров я так и не понял, что же такое порядок функции.

Таким образом, идея замыканий появилась еще до появления программирования, в момент создания лямбда-исчисления — в 1930 гг.

Существует мнение, что программирование появилось несколько раньше 1930 года, как попытка создания вычислительных программ для машины Бэббиджа. Не случайно первым программистом считают Аду Ловлес. Так что замыкания вряд ли появились еще до программирования :D

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

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

вообще говоря, алгебраические типы намного лучше подходят для описания структур данных и позволяют намного естесственнее записывать алгоритмы их обработки (при помощи сопоставления с образцом (см. 10)), чем структуры (записи) или объекты

Такое мощное утверждение нуждается в доказательстве.

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

Старые страшилки для маленьких детишек.

Что еще?

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

Еще несколько умиляют и настораживают упоминания “интересных” задач и приемов программирования. Оно понятно, интересные задачи – это классно, это здорово. Редко, правда, с достойной оплатой совместимо ;)

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

Итого

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

27 комментариев:

jkff комментирует...

Критика весьма по делу, спасибо.

Комментарии:

> Во-первых, восторженными эпитетами.
Я понимал, что большинство читателей не обратится ни к одному из упомянутых в статье источников, поэтому постарался как-то сакцентировать внимание хотя бы на самых интересных. Эпитеты я расставлял не просто так «для понта», а потому, что, например, диссертация Митчелла действительно потрясающая, и мне очень хотелось, чтобы читатели не прошли мимо нее. Отсутствием пафоса пришлось пожертвовать.

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

> слышали о конкатенативных языках?
Это секция <>, и понимание всей упоминающейся там терминологии не критично. Впрочем, допускаю, что читателю неприятно читать непонятную терминологии, так что добавлю небольшое пояснение.

> либо не раскрываются в статье
Про ссылочную прозрачность и CPS-преобразование добавлю разъяснения.

> как не нужно писать статьи для обычных программистов
Ну — да, кое-где приходится внимательно вчитываться; это все-таки не разжеванный туториал, а скорее энциклопедия: следует прочитать, заинтересоваться, прочитать интересные части внимательно, в случае очень интересных — обратиться к источникам. От читателя тоже требуются усилия.
Из трех приведенных примеров мне кажется, что только второй не содержит достаточно информации, чтобы быть понятым среднестатистическим программистом, при условии что программист вообще прочитает абзац, а не просто сделает шокированно-оскорбленное лицо при виде более чем двух «жутковатых» слов в одном предложении. Его я исправлю.

> еще пара придирок по стилю:
Не совсем понял первую придирку. Прошу дополнительных пояснений.

> на свои собственные статьи в третьем лице
Вроде бы, так обычно и делают. Я исходил из наблюдаемой мною общепринятой практики в чужих статьях.

> слишком большое количество языков было использовано для иллюстраций
Это было осознанное решение: например, в главе про pattern matching, мне кажется, не упомянуть Mathematica и REFAL было бы кощунством: они предоставляют возможности, которых у Хаскелла нету, и для понимания современного состояния дел в области pattern matching важно знать, что эти возможности существуют. Я старался подбирать примеры, которые можно понять и с нулевым знанием соответствующего языка; если Вы укажете на примеры, не удовлетворяющие этому критерию, то я добавлю к ним пояснения.

> и подумайте, как ее найти.
А вы для начала посмотрите, как этот код выглядит на более привычных языках. Это несколько экранов таинственных манипуляций указателями. Вот как раз в таком-то коде ошибку найти практически невозможно (несмотря на то, что каждый statement по отдельности понятен) — а вот в приведенный код достаточно просто вчитаться: он один-в-один копирует картинки, которые приводят для этого алгоритма в учебниках.

jkff комментирует...

> до имени sec не удалось додуматься?
Да, sec лучше; исправлю. ss тоже взято не от балды, но если уж использовать ss, то надо было написать «case … of Date yyyy mm dd hh mi ss -> …».

> но не мне
Выше уже объяснил, зачем.

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

> хочется напомнить про Smalltalk и его блоки кода,
Мне кажется, распространенность Smalltalk как промышленного языка недалеко ушла от распространенности Scheme; я не имел его в виду, говоря о промышленных языках. Но я согласен, что его стоит упомянуть в секции «история» и «реализация».

> я так и не понял, что же такое порядок функции.
Поменяю определение на более понятное.

> замыкания вряд ли появились еще до программирования
Поправлю.

> проблем с производительностью вызова функций уже не было.
Прошу доказательств. В «Lambda: the Ultimate GOTO» утверждается обратное.

> Такое мощное утверждение нуждается в доказательстве.
Могу добавить туда «на взгляд автора», но я предполагал, что доказательством служат последующие примеры.

> Старые страшилки для маленьких детишек.
Прошу аргументации. Разве это не так? Ну разве что пафос стоит уменьшить.

> практикующий программист мог прочесть и переварить
Конечно, я не читал целиком большинство статей из библиографии. Но для того, чтобы понять, о чем в статье речь, и понять, что ее стоит упомянуть в качестве источника по определенной теме, читать статью целиком не надо.
Таким образом, хоть статья и действительно отняла у меня гигантское количество времени (почти все свободное время с августа), но не настолько гигантское, чтобы у Вас были основания полагать, что я не был «практикующим программистом» во время ее написания :)

> о практической стороне повседневного использования функциональных языков
http://antilamer.livejournal.com/288854.html

> настораживают упоминания “интересных” задач
Если рассказывать в статье о неинтересных задачах, статья получится неинтересной, а мне будет неинтересно ее писать, со всеми вытекающими последствиями для ее качества.

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

> полезной информации для себя я вынес мало
А расскажите, как Вы читали статью (в каком порядке) и какие части прочитали? Мне, например, кажутся самыми интересными и полезными, например, части «Алгебраический тип», «Свертка», «Структурная рекурсия», но я подозреваю, что многие читатели могли до них просто не добраться :(

eao197 комментирует...

>> еще пара придирок по стилю:
>Не совсем понял первую придирку. Прошу дополнительных пояснений.


В нескольких последних разделах идут упоминания предшествующих или текущих разделов как отдельных статей. Например:

"поэтому в рамках данной статьи мы будем предполагать, что речь идет о строгом (энергичном) языке с синтаксисом Haskell"

но ведь речь идет не о всей статье, а о разделе или главе одной большой статьи. Поэтому я ожидал увидеть что-нибудь типа

"поэтому в рамках данной главы (данного раздела) мы будем предполагать, что речь идет о строгом (энергичном) языке с синтаксисом Haskell"

jkff комментирует...

А, в этом смысле. Постараюсь привести терминологию глава/раздел/статья к единообразному виду :)

eao197 комментирует...

>А вы для начала посмотрите, как этот код выглядит на более привычных языках. Это несколько экранов таинственных манипуляций указателями. Вот как раз в таком-то коде ошибку найти практически невозможно (несмотря на то, что каждый statement по отдельности понятен) — а вот в приведенный код достаточно просто вчитаться: он один-в-один копирует картинки, которые приводят для этого алгоритма в учебниках.

Я представляю себе как это выглядит в C++. Но как по именам типа x, y, c, d и т.д. понимать какой узел куда перемещается я не очень себе представляю. И как отследить, что где-то c и d не перепутаны местами так же.

eao197 комментирует...

>Мне кажется, распространенность Smalltalk как промышленного языка недалеко ушла от распространенности Scheme; я не имел его в виду, говоря о промышленных языках. Но я согласен, что его стоит упомянуть в секции «история» и «реализация».

Это сейчас. До середины 90-х он был вполне себе мейнстримом. Даже IBM имел серьезный инструмент для Smalltalk -- VisualAge for Smalltalk (который, afaik, продержался дольше всех остальных продуктов семейства VisualAge).

eao197 комментирует...

>> проблем с производительностью вызова функций уже не было.
>Прошу доказательств. В «Lambda: the Ultimate GOTO» утверждается обратное.


Середина 70-х -- это уже начало эры структурного программирования. Языки C и Pascal находят широкое распространение. Вирт работает над первой Модулой.

Все это невозможно без эффективной реализации вызова функций.

eao197 комментирует...

>> Старые страшилки для маленьких детишек.
>Прошу аргументации. Разве это не так? Ну разве что пафос стоит уменьшить.


Ну здесь аргументацию следует спрашивать у сделавшего утверждение. :)
Распараллелить цикл, например, по инкременту всех элементов вектора -- как нефиг делать. При использовании OpenMP для этого даже усилий, afaik, применять не нужно.

eao197 комментирует...

>А расскажите, как Вы читали статью (в каком порядке) и какие части прочитали?

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

Quaker комментирует...

фрагмент кода для балансировки “черно-белых” деревьев (раздел 5.10)
Такое ощущение, что речь идет о программировании на ассемблере, ax и Rc - имена регистров процессора. Здравствуй, каменный век!

jkff комментирует...

Quaker: Точно, каменный век и ассемблер. То ли дело сверхсовременный высокоуровневый язык программирования Java.

private void insertFixup(Node n)
{
while (n.parent.color == RED && n.parent.parent != nil)
{
if (n.parent == n.parent.parent.left)
{
Node uncle = n.parent.parent.right;
if (uncle.color == RED)
{
n.parent.color = BLACK;
uncle.parent.color = BLACK;
uncle.color = RED;
n = uncle.parent;
}
else
{
if (n == n.parent.right)
{
n = n.parent;
rotateLeft(n);
}
n.parent.color = BLACK;
n.parent.parent.color = RED;
rotateRight(n.parent.parent);
}
}
else
{
Node uncle = n.parent.parent.left;
if (uncle.color == RED)
{
n.parent.color = BLACK;
uncle.color = BLACK;
uncle.parent.color = RED;
n = uncle.parent;
}
else
{
if (n == n.parent.left)
{
n = n.parent;
rotateRight(n);
}
n.parent.color = BLACK;
n.parent.parent.color = RED;
rotateLeft(n.parent.parent);
}
}
}
root.color = BLACK;
}

private void rotateLeft(Node node)
{
Node child = node.right;

node.right = child.left;
if (child.left != nil)
child.left.parent = node;

child.parent = node.parent;
if (node.parent != nil)
{
if (node == node.parent.left)
node.parent.left = child;
else
node.parent.right = child;
}
else
root = child;

child.left = node;
node.parent = child;
}

private void rotateRight(Node node)
{
Node child = node.left;

node.left = child.right;
if (child.right != nil)
child.right.parent = node;

child.parent = node.parent;
if (node.parent != nil)
{
if (node == node.parent.right)
node.parent.right = child;
else
node.parent.left = child;
}
else
root = child;

child.right = node;
node.parent = child;
}

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

eao197 комментирует...

>Найдете — тогда и поговорим, у кого тут каменный век.

Алаверды: http://codepad.org/o6fNg85b

Надеюсь, все будет чесно и вы не будете делать diff с публично доступной версией.

jkff комментирует...

Ошибка в строке 126?

jkff комментирует...

Блин, не 126, а 124. В общем, в этой:
append (B(a,x,b)) (B(c,y,d)) = threeformB a x (appendR b y) c d

eao197 комментирует...

Да, в этой

jkff комментирует...

Догадаетесь сами, как я ее нашел менее чем за минуту?

eao197 комментирует...

Думаю, вы написали исходный вариант :)

Quaker комментирует...

Полагаю, что ошибка здесь:
uncle.color = BLACK;
uncle.parent.color = RED;
Если не ошибаюсь, то должно быть с точностью до наоборот:
uncle.parent.color = BLACK;
uncle.color = RED;

jkff комментирует...

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

Quaker: неправильно.

eao197 комментирует...

>В таком коде трудно сделать ошибку и оставить ее незамеченной тайпчекером.

Это следствие того, что я нарушил свое правило -- публиковать код без предварительной компиляции.

Quaker комментирует...

Тогда видимо ошибка в ветке if, а не else:
uncle.parent.color = BLACK; //должно быть red
uncle.color = RED; //должно быть black

Rustam комментирует...

Во-первых, не обязательно. Преимушества по объему кода для ФЯ показывается на маленьких примерах. В больших же проектах, в которых начинает работать повторное использование и ОО декомпозиция, выигрыш ФЯ еще не был продемонстрирован, имхо.

Я тоже так думал, но тут http://www.rsdn.ru/forum/philosophy/2766286.flat.aspx#2766286 на проектах вполне достаточного объема показали что я ошибаюсь.

Во-вторых, тот же Eclipse -- это более 25M строк кода. Даже если ФЯ дают код в пять раз компактнее, то это 5M строк. Потянут ли ФЯ проекты таких размеров с таким количеством разработчиков? Терзают меня смутные сомнения, в особенности из-за того, что код на ФЯ пишется в обобщенном стиле.

Думаю про ООП тоже самое говорили, про C++ относительно Си я это точно слышал.

Как с этой сложностью справляться в ФЯ -- ХЗ. Слишком много противоречий с внешним миром (одна иммутабельность чего стоит).

Да также справляется, особенно если не возводить функциональность в догму. Никто в этих языках не мешает использовать мутабельные вещи когда это необходимо, при этом такое использование легко изолируется и контролируется. (Так же как сырые указатели в хороших C++ программах).

Поэтому я бы не стал противопоставлять ОО проектирование и ФЯ кодирование.

Так я и не противопоставляю, я сказал только то что в мощных ФЯ часть того что является проектированием (большая часть того что Макконнелл называет конструированием)в мейнстримных ОО языках, переходит в стадию кодирования.

Rustam комментирует...

Чуть промахнулся :)

Rustam комментирует...

Да по критике статьи я согласен с Евгением в одном, написано очень тяжеловесно. Плюс по моему попытка объять необъятное, даже мне пропуская при чтении большую часть (как уже известную) статья показалась больше похожей на роман :)

Skynin комментирует...

Почитавши это и связанные обсуждения наметились мыслишки:
1. contra пример - не на Java. Как и встречал другие - не на С++. Они на процедурные, а не ООПшные, на процедурном ЯП. В ООП работа с красно-черным деревом вероятно должна выглядеть как взаимодействие объектов-листьев. Надо будет на досуге набросать, и прикинуть-сравнить эффективность с процедурной реализацией.
2. Имена переменных в ФП такие короткие потому что они там длинные и не нужны. В функциональном стиле сплошь "глаголы", а не "существительные". То есть переменные там - либо рудимент, либо малозначительные детали.
3. ... поэтому декомпозиция в ФП таки другая - мы повышаем абстракцию "глаголов", а не "данных". Аналог - создаем для каждой задачи DSL, а не набор процедур над данными, или объекты связанные отношениями, реализуемых в виде "обмена сообщениями". И поэтому в ФП как такового нет рефакторинга, у нас там нет "кирпичей", а всегда "пластилиновая" конструкция.
4. ... поэтому и ощущение как от ассемблера - базовые конструкции слишком низкоорувневые, а методов создания "кирпичей" - нет. И поэтому ощущения как от скриптинга - конструкции получаются текучими, гибкими, без затрат на продумывание и притирку "кирпичей". "Легко пишу" - ведь любимый аргумент и питонщиков.

Джереми Младший Кролик комментирует...

> Скажем, примеры на языке пакета Mathematica в разделе 10. Может быть они интересны изучающему этот пакет, но не мне.

А почему не интересны?
Чем Mathematica хуже других языков?

eao197 комментирует...

2Джереми Младший Кролик:

>А почему не интересны?

Ну вот взять пример с tooSmall и tooBig:

/. {x_/;x<3 :> tooSmall, x_/;x>5 :> tooBig}

Мне он не интересен, поскольку я понятия не имею о языке Matematica, слышал только, что он есть в одноименном пакете. Мне не интересно разбираться, является ли /. отдельной операцией или двумя последовательными операциями. Мне не интересно гадать, что значит x_ и чем он отличается от x. И т.д.

Поэтому мне и не интересно, что язык Matematica находится далеко за пределами моих текущих интересов.

>Чем Mathematica хуже других языков?

Язык не причем. Причем наличие примеров на нем в статье.