Журнал «Практика функционального программирования»

Внимание!: Конкурс завершён, результаты опубликованы!

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

Вы только что изучили Nemerle и мечтаете зарабатывать с его помощью деньги? Побеждайте, и получайте денежный приз.

Вы жаждете личной славы? Победа в конкурсе — прекрасный способ заявить о себе со страниц нашего журнала.

Вы давно искали повод показать, что никакие Erlang и Haskell в подметки не годятся старому доброму C++? Побеждайте — и у вас появится аргумент для будущих споров, способный сразить любого.

Подробнее о целях проведения конкурса

Мы предлагаем нашим читателям вместе с нами сравнить подходы к решению задач в рамках разных парадигм программирования и соответствующих им инструментальных средств.

Как же будут сравниваться подходы и инструментальные средства? С помощью объективного и субъективного оценивания решений нескольких практических задач.

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

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

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

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

Мы хотим построить эксперимент так, чтобы он был лишен существенных недостатков, присущих другим подобным исследованиям (см. исторический обзор ниже): задачи будут «практические», а не «академические», они будут подобраны так, чтобы не давать очевидного преимущества той или иной парадигме программирования. Для этого мы собрали около тридцати заданий разных уровней сложности и попросили 18 программистов-профессионалов (в разных парадигмах программирования) ранжировать задачи по интересности и адекватности в качестве конкурсных задач. Уверены, что использование такого «разношёрстного» жюри для оценки задач — лучшее, что мы можем сделать для того, чтобы исключить «уклон» в сторону конкретного языка или парадигмы. Для того чтобы исключить влияние случайных факторов на выбор членов жюри, мы взяли для конкурса не одну, а две самых популярных задачи.

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

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

Условия проведения конкурса

Конкурс стартует в момент выхода в свет этого (третьего) номера журнала и заканчивается 1 марта 2010 года. Результаты исследования будут опубликованы в пятом номере. Любые изменения в графике будут загодя опубликованы на этой странице, а также в LJ-сообществе fprog.

В конкурсе могут участвовать все желающие.

Как будут оцениваться решения? Даже с учётом предположения, что присылать вы будете только работающие программы, встаёт проблема оценки решений. Что лучше: короткий код, работающий медленно, или грузный, но работающий мгновенно? А может быть, лучше всего тот код, который структурирован для расширяемости? Конечно, все эти метрики мы попробуем проанализировать интегрально, для разных задач и для разных языков. Но задачу определения победителя это не облегчит! Мы думаем, что заставив членов разношёрстного жюри ранжировать присланные варианты по «качеству решения», а затем скомбинировав их ответы, мы сможем на основании субъективных метрик получить лучшее приближение к объективности, на которое мы только можем рассчитывать в рамках подобного конкурса.

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

Победители конкурса получат специальное упоминание на страницах журнала, а также ценные призы:

За первое место, по результатам голосования жюри, для каждой задачи — 8192 рубля;
За второе место, для каждой задачи — 4096 рублей;
За третье место, для каждой задачи — упоминание на страницах журнала.

Кроме того, все победители получат по экземпляру книг «Практика работы на языке Haskell» и «Справочник по языку Haskell» Р. Душкина с дарственной подписью автора.

Требования к оформлению решений

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

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

Короткое, элегантное и читаемое решение;
Устойчивое к ошибкам;
Содержащее тесты или тестовые примеры;
С поясняющими комментариями в ключевых местах.

Пишите на любом языке, который вам нравится, если для него есть свободно доступный компилятор или интерпретатор для Linux или Windows (если язык очень уж экзотический, не забудьте указать адрес, с которого этот самый компилятор можно скачать). При желании можно комбинировать в решении несколько языков одновременно.

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

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

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

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

Фиксируйте время, ушедшее на разработку. Если это возможно — фиксируйте отдельно время, ушедшее на разработку, и время, потребовавшееся на «наведение красоты» (написание документации, тестов и так далее). Кроме того, постарайтесь зафиксировать, сколько всего «грязного» (календарного) времени у вас ушло на решение. Не занижайте ваши оценки — время решения не будет учитываться при выборе победителей.

Присылайте ваши решения на адрес contest2009@fprog.ru в архиве любого распространённого формата (zip, rar, tar.gz, ...), каждую задачу — в отдельном файле. Чтобы облегчить нам обработку результатов, назовите файл так: <код задачи>-<ваш nick>-<номер варианта решения>.<suffix>. Используйте номер варианта для того, чтобы указать, какое решение является более новым. В корне архива должна находится директория с именем <код задачи>-<ваш nick>-<номер варианта решения>, и все относящиеся к решению файлы должны содержаться в ней.

Разместите в архиве файл README, описывающий решение в формате:

Name: <ваше имя или ник>
Task: <код задачи, см. ниже>
Level: <уровень решения, см. ниже>
Language: <название языка>
Work: <чистое время, затраченное на решение, в часах>
Duration: <грязное время, затраченное на решение, в днях>
<пустая строка>
<многострочный комментарий произвольной формы>

Пример архива с оформленным решением: gantt-jwizard-01.zip.

Условия задач

В рамках каждой задачи существуют градации сложности, называемые уровнями. Только от вас зависит, сколько задач и в каком объёме вы будете решать. Мы постарались сделать, чтобы решение обеих задач в минимальном объёме («уровень 1») заняло у вас суммарно не более 4-10 часов.

Задача 1: усечение карты (geo)
Задача 2: составление плана-графика (gantt)

Экскурс в историю

Мы, конечно же, не первые, кто пытается сравнивать языки программирования.

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

Одной из первых работ, поставившей своей целью сравнить сразу несколько принципиально различных языков, можно считать [Hudak94vs.ada]. В этом классическом исследовании приведены данные, из которых следует, что скриптовые и функциональные языки имеют где-то 2-3 кратный выигрыш во времени программирования и объеме кода по сравнению с программами на C++ и Ada. С другой стороны, программы на C++ и Ada оказываются в 2-3 раза быстрее программ на других языках программирования. Впрочем, авторы справедливо посчитали, что имевшиеся в их распоряжении данные не составляли репрезентативной выборки (мало участников исследования, большая разница в степени владения языками) и ограничились в своих выводах осторожными общими фразами.

Шесть лет спустя в исследовании Лутца Прехельта ([Prechelt_anempirical]) было рассмотрено семь языков (C, C++, Java, Perl, Python, Rexx и Tcl), которые использовались для написания простой программы, преобразующей номер телефона в набор слов по определенным правилам. В исследовании принимали участие добровольцы, всего было накоплено около 80 вариантов решений. В результате автор пришел, в частности, к таким выводам:

Разработка и написание программ на Perl, Python, Rexx или Tcl требует примерно в два раза меньше времени, чем написание аналогичного кода на C, C++ или Java. Получающийся в результате программный код также вдвое короче.
Не наблюдается существенной зависимости между выбранным языком и надежностью программы.
Программы на скриптовых языках потребляют примерно в два раза больше памяти, чем программы на C/C++. Программы на Java потребляют в два раза больше памяти, чем программы на скриптовых языках (правда, в статье не указаны параметры запуска JVM и методика измерений в случае Java)
В группе скриптовых языков Python и Perl оказались быстрее, чем Rexx и Tcl.

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

Сравнение всего двух-трех языков, зачастую — со сходной семантикой или синтаксисом (например, [Zeigler], [Bull01benchmarkingjava], [Prechelt99comparingjava], [Gat00lispas], [Zeigler])
Исследование нескольких языков в условиях, когда весь код написан одним и тем же автором, при этом степень его знакомства с языками никак не оценивается (например, [ShahNine])
Явная предрасположенность исследователей в пользу одного из языков или группы языков (например, [FlyingFrog], [Hudak94vs.ada])
Исследование исключительно производительности конкретных реализаций языков (например, [shootout], [Kernighan98timingtrials], [Bull01benchmarkingjava], [ShahNine])
Игнорирование временных и прочих аспектов процесса разработки (сколько времени ушло на разработку программы) (например, [Kernighan98timingtrials], [FlyingFrog])
Несоотвествие результатов нынешним реалиям, так как исследование проведено 5-10 лет тому назад (все вышеупомянутые).

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

Список литературы

[shootout]: The Computer Language Benchmarks Game, http://shootout.alioth.debian.org/.
[FlyingFrog]: Ray tracer language comparison, http://www.ffconsultancy.com/languages/ray_tracer/, 2005-2007.
[Bull01benchmarkingjava]: J. M. Bull, L. A. Smith, L. Pottage, and R. Freeman. Benchmarking Java against C and Fortran for Scientific Applications. In In Proceedings of ACM Java Grande/ISCOPE Conference, pages 97–105. ACM Press, 2001.
[ShahNine]: Christopher W. Cowell-Shah. Nine Language Performance Round-up: Benchmarking Math & File I/O, http://www.osnews.com/story/5602/Nine_Language_Performance_Round-up_Benchmarking_Math_File_I_O, 2004.
[Gat00lispas]: Erann Gat. Lisp as an Alternative to Java. Intelligence, 11:2000, 2000.
[Hudak94vs.ada]: Paul Hudak and Mark P. Jones. vs. Ada vs. C++ vs. Awk vs. ... An Experiment in Software Prototyping Productivity Available from http://www.haskell.org/papers/NSWC/jfp.ps. Technical report, Yale University, 1994.
[Kernighan98timingtrials]: B W Kernighan and C J Van Wyk. Timing trials, or the trials of timing: experiments with scripting and user-interface languages, http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html, 1998.
[Prechelt99comparingjava]: Lutz Prechelt and Fakultat Fur Informatik. Comparing Java vs. C/C++ efficiency differences to inter-personal differences, 1999.
[Prechelt_anempirical]: Lutz Prechelt and C C++ Java. An empirical comparison of C, C++, Java, Perl, Python, Rexx, and Tcl for a search/string-processing program, 2000.
[Zeigler]: Stephen F. Zeigler. Comparing Development Costs of C and Ada, http://www.adaic.com/whyada/ada-vs-c/cada_art.html. 1995.

Этот документ был получен из L^AT_EX при помощи H^EV^EA