LOR-contest
LOR-contest — набор этюдов для изучения языков программирования и сравнения их особенностей.
Мотивы и предыстория
Этюд -- музыкальная пьеса, основанная на определенном приеме исполнения и предназначенная для развития технического мастерства исполнителя
(C) Энциклопедический словарь, цитируется по Ч. Уэзерелл, Этюды для программистов
Иногда есть желание изучить новый язык программирования, но нет подходящей задачи для "пробы пера". В учебниках обычно приводятся очевидные примеры, к тому же все особенности тщательно описаны и обсуждены. Чтобы испытать свои знания языка на достаточно простой, но нетривиальной задаче и были придуманы "Этюды для программистов".
Идея LOR-contest возникла во время очередного флейма на тему Lisp против Python:
http://www.linux.org.ru/view-message.jsp?msgid=1587106
По ходу было много споров о применимости и эффективности применения различных языков. При этом лисперы утверждали, что достоинства Lisp видны только на достаточно крупных задачах. Их пытались поймать на слове, но задача должна была быть достаточно простой, чтобы ее можно было решить в течение нескольких часов. Так и возникла идея этюда, изложенная в http://www.linux.org.ru/jump-message.jsp?msgid=1587106&cid=1618155 .
В то время у меня (--Евгений Косенко 05-Jul-2008 16:25 MSD) было немного свободного времени, и я решил попробовать свои силы в использовании относительно нового для меня языка. Так были написаны само решение на Лиспе, и "пузомерка" -- программа для измерения лексической длины программы, принципы которой изложены в http://www.linux.org.ru/jump-message.jsp?msgid=1587106&cid=1619364 и http://www.linux.org.ru/jump-message.jsp?msgid=1587106&cid=1623405.
По ходу были также приведены реализации на Python и Ocaml, которые потом несколько раз улучшались. По техническим причинам результаты были опубликованы в новой ветке
http://www.linux.org.ru/view-message.jsp?msgid=1650213,
однако по ходу возникло еще несколько улучшений.
Потом тема была заброшена, однако периодически на linux.org.ru всплывают дискуссии о сопоставлении языков программирования. По ходу мне было бы интересно увидеть решения на Ruby и Perl, но интерес к первому у меня уже поостыл, а второй так и не привлек меня. Недавно у меня опять выдалось немного свободного времени, и я решил покрутить Haskell. Результаты мне понравились, поэтому я решил поднять тему, опубликовав новые результаты.
Условия
http://www.linux.org.ru/jump-message.jsp?msgid=1587106&cid=1618155
1. Сервер при запуске принимает имя файла с картой такого вида:
########## # # $ # # #$ # . # # # ########## # - стена $ - предмет . - вход
2. Сервер понимает следующие комманды
read_world() - возвращает в любой удобной для языка реализации
состояние мира, т.е. карту, положение предметов, инвентарь персонажа, состояние игры (завершена или нет)
perform_action() - выполняет действие. Возможные действия:
north - перейти на одну клетку на север west - перейти на одну клетку на запад south - перейти на одну клетку на юг east - перейти на одну клетку на восток pickup - поднять предмет в текущей клетке drop - бросить переносимый предмет в текущей клетке
В случае если предлагают совершить невозможное действие, например поднять предмет, если в инвенторе уже есть предмет, бросить предмет, если на клетке уже лежит предмет (только на клетку входа можно бросать более одного предмета), или встать на клетку со стеной, то команда игнорируется.
3. Игра заканчивается если все предметы в мире лежат на клетке входа
4. Требуется написать:
4.1. Сервер, процесс который при старте считывает карту мира и
слушает какой-то порт по TCP/IP и обслуживает запросы приходящие по этому порту. Запуск: advserve world.dat 7766
4.2. Клиента для человека, который цепляется к серверу,
считвает состояние мира, отображает эту информация, ждёт ввода комманды и передаёт её серверу. Вывод идёт в stdout, т.е. просто старое состояние уползает вверх, на его место вылазит новое.
Пример вывода:
##########
# # $ # #
#$ # @.
# # #
##########
Game is in progress
You carry an item
Here lies 1 item(s)
> [место для ввода комманды]
@ - персонаж, если на одной клетке находится персонаж и что-то
ещё, то отображается персонаж:
##########
# # # #
# # @
# # #
##########
You won!
Your hand are empty
Here lies 3 item(s)
> [место для ввода комманды]
##########
# #$ # #
#$ # @ .
# $# #
##########
You won!
Your hand are empty
Here lies 0 item(s)
> [место для ввода комманды]
Пример запуска: hclient 127.0.0.1 7766
4.3. Клиента робота, который должен выиграть игру. В процессе игры
на экране отображается состояние мира как для человеческого клиента, только нет приглашения для ввода комманды
Пример запуска: roboclient 127.0.0.1 7766
5. Сравнивается краткость, компактность и концептуальность :-)
исходных текстов всез трёх программ.
Пузомерка
http://www.linux.org.ru/jump-message.jsp?msgid=1650213&cid=1651390
- Общая длина
- число всех лексем в программе. По идее, определяет основной параметр -- интуитивный размер программы.
- Смысловая длина
- число всех значимых лексем (не ключевых слов и не спецсимволов, т.е., идентификаторов, строк, чисел и т.п.). Приблизительно определяет общее количество определений и использования новых сущностей в программе. Параметр может быть определен неточно, так как в "ключевые слова" попали также все идентификаторы, определенные стандартом, или, по другому, использовать которые оказалось возможно без подключения внешних библиотек или пакетов. Сами имена библиотек/пакетов не считаются ключевыми.
- Общий тезаурус
- размер словаря программы, число неповторяющихся лексем. Дает грубую оценку общего числа понятий, используемых в программе.
- Смысловой тезаурус
- размер смыслового словаря программы, число неповторяющихся значимых лексем (определение такое же, как и для смысловой длины). Дает оценку числа новых понятий, определенных в программе.
- Общая насыщенность
- отношение числа смысловой длины к общей, определяет степень "синтаксической засахаренности" наоборот -- чем ниже насыщенность, тем больше в языке синтаксического сахара.
- Насыщенность тезауруса
- отношение размера смыслового тезауруса к общему.
- Общая выразительность
- отношение размера общего тезауруса к общей длине, характеризует повторяемость, "рутиность", "копипастность" языка. Согласно этому определению BrainF*ck и Whitespace имеют самую низкую выразительность.
- Смысловая выразительность
- аналогично общей, отношение смыслового тезауруса к смысловой длине. Для BrainF*ck и Whitespace неопределяема (0/0), но в предельном варианте для них она просто принимается равной нулю.
Система построена таким образом, что улучшая один параметр, неизбежно ухудшаешь другой. Обычно длина должна быть как можно меньше, насыщенность -- как можно ниже, а выразительность -- как можно выше. Задача состоит в том, чтобы получить оптимальный баланс параметров.
Обсуждение
Система критериев придумана мной (--Евгений Косенко 05-Jul-2008 16:56 MSD) ad hoc, чтобы дать примерно равные стартовые условия для языков с очень отличающимся синтаксисом. С этой системой можно не соглашаться, но основные свои мотивы я излагал по ходу дискуссий:
все там же, в ветке "Фраза о Лиспе":
http://www.linux.org.ru/view-message.jsp?msgid=1587106#1619364 http://www.linux.org.ru/view-message.jsp?msgid=1587106#1623405
ну и вообще, сообщения в районе 37-38 страниц:
http://www.linux.org.ru/profile/eugine_kosenko/view-message.jsp?msgid=1587106&page=36 http://www.linux.org.ru/profile/eugine_kosenko/view-message.jsp?msgid=1587106&page=37
Очень важно, что при сравнении решений не учитываются характеристики классической сложности -- скорость работы и потребляемая память. Кроме того, при решении не накладываются ограничения на время реализации и число людей, работающих над решением. То есть, решение можно улучшать до тех пор, пока есть желание. Можно полностью переписать решение, если существующее не нравится. В общем, результаты конкурса не закрыты.
Главным критерием сравнения программ является краткость, то есть, минимальная длина программы. Этот критерий взят согласно статье Краткость - сила Пола Грэма, одного из апологетов Lisp:
Краткость, как мне кажется, и есть то, ради чего создаются языки программирования. Компьютеры были бы настолько же довольны, если бы им давались инструкции непосредственно на машинном языке. Думаю, основная причина, по которой мы беремся разрабатывать языки высокого уровня - получить преимущество выражаться (и что важнее - думать) десятью строками на языке высокого уровня, что потребовало бы 1000 строк машинного кода. Иными словами, основная цель языков высокого уровня - это сделать исходный код короче.
Проблема в том, как измерить длину программы. Простейшие единицы -- число символов или строк кода -- слишком неточны, так как допускают "грязные хаки" вроде сжатия и обфускации кода. Чтобы методика была нечувствительна к таким трюкам, необходимо анализировать число синтаксических структур языка. Но тут возникает проблема существенного различия в синтаксисе языков, плюс необходимость писать полноценный парсер для каждого языка, участвующего в конкурсе, на что, обычно не хватает времени.
В результате было придумано компромиссное решение -- подсчет количества лексем с игнорированием пробельных символов и комментариев. Это позволяет при всей простоте методики нейтрализовать возможности сжатия и обфускации программы.
Результаты
| Параметр | Lisp | Python | Ocaml | Haskell (не завершен) |
|---|---|---|---|---|
| Общая длина | 883 | 1439 | 1341 | 866 |
| Смысловая длина | 246 | 574 | 424 | 460 |
| Общий тезаурус | 158 | 190 | 151 | 163 |
| Смысловой тезаурус | 81 | 147 | 95 | 122 |
| Общая насыщенность (в %) | 28 | 40 | 32 | 53 |
| Насыщенность тезауруса (в %) | 51 | 77 | 63 | 75 |
| Общая выразительность (в %) | 18 | 13 | 11 | 19 |
| Смысловая выразительность (в %) | 33 | 26 | 22 | 27 |
Lisp
Автор: eugine_kosenko
Так как это решение делал я (--Евгений Косенко 05-Jul-2008 20:09 MSD), то смогу рассказать о нем подробнее (если вспомню). Основной фишкой решения является прямой REPL в командной строке клиента, что позволяет исполнять довольно сложные программы, например, с выводом результатов в конце работы программы, или в промежуточных точках, возможность выполнять циклы и условные исполнения. Сама возможность запустить робота -- это команда collect.
Python
Автор: redvasily
К сожалению, последняя версия также не восстановлена, поэтому приведены замеры для последней известной версии. Если автор найдет последнюю версию, исправлю результаты.
Кроме того, есть еще одна версия, которая претендует на очень хороший результат (общая длина -- 1097): http://www.linux.org.ru/jump-message.jsp?msgid=1650213&cid=1653761, автор -- watashiwa_daredeska. Однако, при попытке запуска возникает ошибка синтаксиса, даже в Python 2.5: http://www.linux.org.ru/jump-message.jsp?msgid=1650213&cid=1654656. Поэтому решение пока не принято.
Ocaml
Автор: satanic-mechanic
К сожалению, последняя версия была передана в виде tar-файла восстановлена из моего архива. После проверки цифры почему-то изменились, поэтому результаты в таблице отличаются от опубликованных в http://www.linux.org.ru/view-message.jsp?msgid=1650213. Возможно, я ошибся тогда, не включив один из файлов в результирующий файл. Если я таки где-то просчитался, прошу поправить.
Спорным моментом является учет mli-файла с сигнатурами функций. С одной стороны, у него не совсем окамловских синтаксис, с другой стороны, без него система не соберется. Пока что он не учитывается, если есть возражения -- предлагайте способ учета.
Haskell
Автор: eugine_kosenko
Тоже делал я (--Евгений Косенко 05-Jul-2008 20:44 MSD). К сожалению, решение неполное. Прежде всего, отсутствует сетевое взаимодействие. Далее, вывод неполный -- только карта лабиринта, без подсчета числа вещей в клетке и состояния игрока. Подозреваю, что после полной реализации код увеличится процентов на 20-30, что доведет решение до уровня Ocaml.
Другие решения
http://www.linux.org.ru/forum/development/1650213?cid=1702155
Я так и не понял, что это за язык с расширением .k. Краткость удивила, но невозможность проверить работоспособность не позволила причислить этот язык к участникам. Как только убедимся в работоспособности -- включим.
Есть подозрения, что это http://en.wikipedia.org/wiki/K_(programming_language) , но проверять лень. В дистрибутиве интерпретатора (?) этого языка лежат файлы с очень похожим синтаксисом.
Развитие
Другие примеры
Изначально в задачу заложен простенький лабиринт. По ходу обсуждения были придуманы еще несколько лабиринтов, которые можно использовать для тестирования и отладки.
"Неправильные" лабиринты
В неправильных лабиринтах некоторые вещи недоступны, например:
########## # # $ # # #$ # . # # # # ##########
Необходимо, чтобы программа работала и в этих условиях.
Сложные ("странные") лабиринты
Сложные лабиринты имеют непрямоугольную форму.
####### ########## # # $ # # ### # # ###### #$$# $# # # #### ### # ###### ### # # # $ # ##### # #$ ## # ## # ##### ## ######### # ## $$# ### ####### # $#### # # # ##### # ### ###### # . #####
#### ## ## ######
# ### #### # # # #
# # # # #### # ####
## # ##### # ### # # # # #
## ## ## # # # # # # #
# # ## # # # #### #
# ### # ### # ### ### #
# ## # ## ##### ### #
# ## ##### ## ###### ## # ##
# ### ##### ##### #### # ###
# # # ####### ## ###### # ### #
## # # ########## # ###### ### # #
#### # ########### # ###### ##### #
# ######## # # ############ #
## ## # ## ########## #
#### ## ### # # ### #### #
### ######## #### ## #
# # ######## # ## #
# ### ####### ## ## # # #### #
# ##### ######### #### ### # ##### #
# ###### # $ #### ####################### #
# #### # ############################### #
# ### ###### ####### #
# # #### ##### ####### #####
## # #.# ######## #########
Другие языки
Лично мне (--Евгений Косенко 05-Jul-2008 21:06 MSD) интересно посмотреть решения на Ruby и Perl. Возможно, моей следующей игрушкой будет решение на Erlang. Из других достаточно популярных языков можно назвать C, C++ и Java.
Другие задачи
Задача, поставленная для LOR-contest была определена совершенно спонтанно. На самом деле, таких этюдных задач намного больше. Попробую перечислить тут другие возможные задачи.
- "Пузомерка"
- Собственно, программа для подсчета лексической длины программы, используемая в LOR-contest, сама является хорошим этюдным примером. Реализация на Lisp оказалась интересной, так как за счет метапрограммирования (макросов) текст оказался достаточно коротким и легко расширяемым. Возможно, когда у меня будет свободное время, я попробую написать аналогичную считалку на Haskell. Пока что я не понял подход к построению парсеров в Haskell, возможно, из-за стереотипов классического подхода Lex/Yacc.
- Обработка данных
- http://www.linux.org.ru/view-message.jsp?msgid=1587106&page=20#1607434 Составить структуру данных для хранения информации о том, в каких директориях находится файл. Одинаковые файлы могут храниться в нескольких директориях. Файлы считаются одинаковыми, если совпадает и имя и размер. Создать код, который 1) поштучно добавляет информацию (имя файла, размер, каталог) в структуру, 2) составляет отдельно списки имён файлов, которые есть в равном N количестве, больше или меньше. Для каждого имени нужно передать также информацию о том, в каких директориях он (находится? --wingless)(в постановке [[1]]). Эта задача решается с помощью базовых контейнеров (проверка возможностей структур данных и базовой библиотеки), или же с помощью хранилища в базе данных -- проверка возможностей ORM и работа с СУБД. Там же, во "Фразе о Лиспе" были приведены решения на Lisp и Python, для ORM использовались CL-SQL и SQLAlchemy соответственно. В общем, есть немного неразобранного кода, хотя тут, наверное, есть смысл провести сравнение заново.
- Этюды от Чарльза Уэзерелла
- Книга Чарльза Уэзерелла, Этюды для программистов содержит 27 этюдов различной степени сложности, каждый из них может быть использован для изучения языков и техник программирования. Перечислю некоторые из них:
- Игра Коэна "Жизнь" (клеточные автоматы и машинная графика)
- Автоматическое построение лабиринтов (как дополнение к LOR-contest)
- Интроспекция (печать своего собственного текста)
- Моделирование машины Тьюринга