kaipa: (Default)
Раз недавно зашел разговор о языках программирования (ЯП) и выяснилось, что среди френдов есть даже больше программистов, чем мне казалось, предлагаю неоригинальный опрос.

1. Какие ЯП вы используете (использовали) профессионально (то есть получали за работу деньги)
2. На каких ЯП, не вошедших в первый пункт, вы писали нетривиальные (то есть не уровня Hello, world) программы (во время учебы, для себя, и т.п.)
3. Какие ЯП, не вошедшие в первые два пункта, вы пробовали на уровне хотя бы небольшой программы.

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

Мой список выглядит так, если ничего не упустил:
1. С++ (Borland, MSVC, GNU), Delphi, VBA, Clarion, Java, Scala, SQL (разных диалектов), bash.
2. C (на разных операционках), (Turbo) Pascal, Basic, FoxPro, FORTH, LISP, Assembler (x86,Z80), Matlab, машкод МК-52 :)
3. J, R, Haskell, Smalltalk.

Показательно, что весь второй пункт -- это школа, университет, аспирантура. Кроме С++ из того периода, ничего профессионально использовать не пришлось. Это хорошо отражает принцип преподавания computer science, с которым я полностью согласен: учебные и промышленные языки должны быть разными, так как что-то удобно для обучения, а что-то для работы. Сейчас, впрочем, некоторые учебные языки, тот же Common Lisp, вполне себе успешно используются и для коммерческих проектов, но это, скорее, исключение, чем правило.

Julia

Dec. 8th, 2014 04:32 pm
kaipa: (Default)
Программистское.

А смотрел ли кто-нибудь на julia? Команда разработчиков ставит своей целью собрать лучшее из Матлаба, R, Mathematica и т.д., для того чтобы сделать новый хороший инструмент для инженерного программирования и статистического моделирования.

В Университете больше 15 лет назад мы делали расчеты и мат.мадели на матлабе. Это было, как сейчас помню, круто. Матричные операции и мощные средства визуализации позволяли очень много с минимальными усилиями. Язык не мешал, и не помогал. Его просто не было видно за решением задачи.

Несколько лет назад игрался с J. Удивительный, необычный, очень "вкусный" язык программирования. В умелых руках эффективный инструмент (пример умелых рук -- dr-klm из Донецкого физтеха).

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

На первый взгляд, Julia не сильно лучше в этом плане. Из объективных плюсов по сравнению с R -- скорость (JIT), лучше система типов. Отзывы в сети отдают предпочтение Julia как языку, но предостерегают, что библиотеки и средства визуализации еще не так развиты, как в R. Что понятно.

А вот к читателям у меня вопрос -- какой язык программирования вы недавно (или давно, но последний) выучили и зачем. За себя отвечу -- Scala (использую профессионально), и J -- для души.
kaipa: (Default)
Алёша: Степан, у гостя карета сломалась
Степан: Вижу, барин. Ось полетела и спицы менять надо.
Алёша: За сколько сделаешь?
Степан: За день сделаю.
Алёша: А за два?
Степан: Ну, за два... Сделаем и за два.
Алёша: А за пять дней?
Степан: Ну, ежели постараться, можно и за пять.
Алёша: А за десять?
Степан: Ну, барин, ты задачки ставишь! За десять дней одному не справиться, помощник нужен.
(С)

Как передать проект (простенький) от одного человека к другому, немного его улучшив? На днях в нашей компании была попытка (вроде бы успешно пресеченная) сделать это классическим анекдотическим способом:

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

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

В этой связи придумал эмпирическое правило: время разработки прямо пропорционально числу участников (обычно).

Сейчас напишу несколько очевидных вещей, которые можно не читать.

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

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

Суть работы самого программиста от этого мало меняется, но время разработки естественно вырастает в разы. Зато прогнозируемо.

P.S. Лучшая книга о разработке ПО (психологии, организации и т.п.) -- "Мифический человеко-месяц" Брукса. Ей уже почти 30 лет, но основные идеи вечны. Кто не читал, не пожалеете.
kaipa: (Default)
Либителям data science и алгоритмов кластеризации есть шанс попробовать себя в по-настоящему практической задаче: поиске бозона Хиггса на основе статистического анализа реальных данных по столкновению частиц.

Чуть более подробно на русском -- на "Элементах"

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

Никто не хочет поучаствовать? В отличие от конкурсов типа ICFP времени тут гораздо больше, в том числе и на подумать, почитать умные книжки и т.д.
kaipa: (Default)
Попробуем описать окружающие нас предметы. Стол — коричневый, чашка — белая, лист бумаги — прямоугольный. Вы не можете мне указать на коричневость, белизну, прямоугольность, легкость, умность и прочие качества сами по себе. Они всегда существуют как прилепленные к чему-то. То, к чему они прилеплены, и есть субстанция. А эти все качества называются акциденциями, случайными признаками. И весь наш взгляд на мир — это взгляд на некую совокупность качеств, которые существуют не сами по себе, а прилеплены к тому, что мы называем вещами. А под словом «вещь» мы всегда подразумеваем некоторую субстанцию. На этом стоит европейская философия.

...


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

Это отрывок из относительно старой статьи на "Эксперте", которую я выудил в архиве [livejournal.com profile] whiteferz.


Прочитав это противопоставление западного и восточного мировоззрения в такой формулировке (обычно формулируют несколько по-другому), мне вдруг подумалось, что западному миру соответствует объектно-ориентированная парадигма программирования, тогда как восточному -- функциональная или процессо-ориентированная. Это либо забавное совпадение, либо факт, требующий осмысления, так как в последние лет 5-7 наблюдается явный разворот в сторону функциональной парадигмы.

Нельзя не заметить также, что это перекликается со статьей Лосева о связи грамматики и мышления. Еще одно подтверждение тому, что язык определяет сознание.
kaipa: (Default)
Лучшая отладка -- ночью, в полной тишине. Днем бывает тяжело сконцентрироваться, то одно отвлекает, то другое. Даже отдельный кабинет не помогает. Разве что закрывать дверь и отключать скайп с телефоном. Хорошо нам совам, как жаворонки с этим справляются, не понимаю.
kaipa: (Default)
Подумалось, что гипотеза лингвистической относительности Сепира-Уорфа вполне применима и к программированию. Программисты, которые учились программировать на конкретном языке, начинают думать в терминах его конструкций, и тем самым сильно себя ограничивают. Переход на другой язык и тем более парадигму может быть весьма проблематичен. Иногда можно наблюдать, как на новом для себя языке программист пишет "по-старому", как будто переводит мысли с языка на язык. В последнее время с ростом популярности языка Скала, такое случается особенно часто, так как Скала допускает этакий суржик с Джавой, чем активно пользуются неофиты.

Чтобы избежать языковой привязки, учиться программированию лучше либо в надязыковых терминах, например на языке блок-схем, либо же во время обучения пробовать возможно большее количество разных подходов. Тогда вырабатывается понимание, что инструмент или язык -- это лишь средство, и ментальные процессы решения конкретной задачи слабо с ним связывается. Например, нас учили (и в школе и на ВМК) машине Тьюринга, машине Маркова, ЛИСПу, ФОРТу, ПРОЛОГу, не говоря об "обычных" императивных и объектно-ориентированных языках. Те, кому такое разнообразие кажется бесполезным, скорее всего попали в плен какого-то конкретного языка или подхода.

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

P.S. В некотором роде это является продолжением моего поста двухгодичной давности.
kaipa: (Default)
Немного потрахавшись, поставил на Мак Haskell, чтобы понять, с чем его едят. Удивлен скоростью. Эталоном скорости в интерактивном режиме для меня всегда был J. Но тут Хаскель обскакал.

Факториал.

Хаскель (ghci):
let { f 1 = 1 ; f n = n * f(n-1) }

J:
f =: */@(>:@i.), хотя значительнее нагляднее просто */1+i.10000x, подставляя нужное число.

На тысяче разницы не видно.
На десяти тысяч J чуть запинается, а Хаскель -- нет.
На ста тысячах J пыхтел минут 5, а Хаскель вернул секунд за 30.

Но это, конечно, к языку не относится. На самом деле мне интересно, насколько на хаскеле удобнее программировать на типах, а то про Скалу совершенно справедливо пишут, что некоторые простые вещи часто становятся очень сложными.
kaipa: (Default)
С подачи [livejournal.com profile] beroal с огромным интересом и удовольствием прочитал статью Дейкстры 88года On the cruelty of really teaching computing science.

Основная мысль, как ни странно, не о преподавании Computer Science, а об опасности аналогий и упрощений. За аналогиями теряется новизна, иногда -- радикальная новизна. Этой мысли в ее различных проявлениях он уделяет большую часть статьи. В приложении же к программированию он предостерегает от аналогии Software Engineering, и совершенно правильно пишет, что программирование -- это в первую очередь формальная логика и формальные методы. Но в отличии, скажем, от примитивной дискретной математики, объекты программирования -- огромной размерности.

Статья написана живым, хотя и не самым простым, языком, с юмором, порой переходящим в сарказм. И увы, почти все, что он "видит" в магическом кристале, на самом деле произошло и происходит сейчас. О деградации преподавания Computer Science я писал, по-моему, не один раз.

Кстати, идеальное преподавание Computer Science он видит тогда, когда программы нельзя запустить! В этом случае приходится проводить максимальную ментальную работу, чтобы на самом деле доказать (себе и преподавателю), что программа "работает" правильно. К тому же:

It is now two decades since it was pointed out that program testing may convincingly demonstrate the presence of bugs, but can never demonstrate their absence.

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

Teaching to unsuspecting youngsters the effective use of formal methods is one of the joys of life because it is so extremely rewarding. Within a few months, they find their way in a new world with a justified degree of confidence that is radically novel for them; within a few months, their concept of intellectual culture has acquired a radically novel dimension. To my taste and style, that is what education is about. Universities should not be afraid of teaching radical novelties; on the contrary, it is their calling to welcome the opportunity to do so. Their willingness to do so is our main safeguard against dictatorships, be they of the proletariat, of the scientific establishment, or of the corporate elite.
kaipa: (Default)
Начал было писать библиотеку для динамического программирования на Scala, чтобы поглубже погрузиться в программирование на типах. Все хорошо, даже сложные рекурсивные типы получаются, но одна штука безумно отравляет жизнь: в Scala нет generic числового типа. То есть нельзя задать тип "просто число", чтобы типичные операции числового поля выполнялись естественным образом, а не через костыли. Вернее, можно, но тогда придется написать тип "просто число" самому. Или ограничиться полем действительных чисел :)

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

Наверное, я непонятно объясняю, время позднее. Очень хорошо о математическом подходе к программированию на Scala изложено тут.
kaipa: (Default)
Написал тут давеча такую строчку.

val dam = (for ( (m, da) <- mda; (d, oa) <- da; a <- oa) yield ((d,a), m)).groupBy(_._1).map( x => (x._1, x._2 map (_._2)))

Это преобразование:

List[(M, List[(D, Option[A])]) -> Map[(D, A), List[M]]

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

Но я не об этом. Поскольку преобразование довольно нетривиальное, его можно совершить разными "путями", возможно, с разной эффективностью. Например, раскрывать, Option можно в самом конце. Чтобы было понятно, о чем я, возьмем более простой пример, на котором это очевидно. Предположим, нам над списком надо совершить две операции: filter и reverse. Так получилось, что они коммутативны, то есть можно в любом порядке их применять. Однако, очевидно, что эффективнее сначала список отфильтровать, а потом развернуть, а не наоборот.

Я довольно далек от формальных логик, преобразования программ, суперкомпиляции и проч., но может, кто подскажет, как современная наука смотрит на такие вещи? Может ли компилятор сам "додуматься" до эквивалентных преобразований функциональных выражений? Или это удел суперкомпиляции?
kaipa: (Default)
Как всегда искрометный Китя Карлсон объясняет коллеге-индусу в маленькой софтверной компании на букву М:

"- Допустим, - говорю, - для того чтобы завершить работу нужно написать 100 килобайт кода. В день ты пишешь 10 килобайт. Но начальство, хоть и работает в 10 раз медленнее тебя, постоянно придумывает новые изменения в задание, прибавляющие по 1 килобайту ненаписанного кода в день. Сначала ты думаешь, что закончишь работу всего за 10 дней. Но через десять дней к работе прибавятся ещё 10 килобайт. Теперь чтобы закончить работу тебе потребуется ещё только один день, но и за этот день задание немножко изменится и останется написать ещё килобайт кода. И так далее, до бесконечности. Таким образом, получается, что ты никогда не сможешь закончить работу."
kaipa: (Default)
Поучаствовал в конкурсе по функциональному программированию. Автор, который ведет интересный и нескучный блог, и уже не первый раз устраивает конкурсы, в качестве призов предлагая свои книги. Я слежу за конкурсами с самого начала, но раньше как-то не хватало времени. В этот раз, впрочем, конкурс был менее всего функциональным, и показался простым и интересным.

Задача простая -- дешифровка текста, зашифрованного самым примитивным методом, которым я баловался еще в школе: XOR с кодовым словом. Задача облегчалась тем, что был известен тип текста -- программа на Хаскеле, чем многие воспользовались, и длина ключа. Если бы длина ключа была бы не известна, но ограничена сверху, то задача была бы куда сложнее. А так -- всего лишь несколько строк. Кроме длины автор любезно сообщил алфавит, чем еще более сократил варианты.

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

Далее несколько Scala-примеров.Немного кода с комментариями )

В общем, текст я декодировал, получившуюся программу на Хаскеле запустил в вебовском интерпретаторе, код выслал и занял счастливое 13е место. Впрочем, по большому счету там есть места первое -- и остальные, не на скорость же соревнование. В качестве приза получил личный электронный, подписанный автором экземпляр книги "Методы получения, представления и обработки знаний с НЕ-факторами". Давно не читал современной литературы по обработке и представлениям знаний, поэтому прочту с интересом. Когда появится время.

P.S. Что такое ФП(ФП)? Если не догадались, то ищите ответ у [livejournal.com profile] _darkus_ :)
kaipa: (Default)
[livejournal.com profile] ivan_gandhi на днях заметил, что Хаскель -- асоциальный язык. Новичок в нем утонет, и вынырнет с какой-нибудь пользой в лучшем случае через год. Это язык одиночек, гуру и научных работников. Набрать и построить команду очень непросто.

Этим Хаскель отличается от Скалы, где даже новичок, никогда раньше не знавший Скалы и ЛИСПа, но умевший на чем-нибудь программировать, может довольно быстро начать писать полезный код, пусть плохой и "неправильный", и постепенно приобщаться к прекрасному. При наличии желания и способностей, конечно. А еще лучше -- хорошего наставника.

Наблюдение, как мне кажется, верное, и оно имеет исторические параллели. Например, популярность и быстрый рост Джавы во многом обусловлена ее социальностью -- легко научиться что-то программировать. В сравнении с внешне похожим, но куда более сложным С++, в умелых руках способным творить чудесные программы и системы.

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

Flashback

Dec. 15th, 2011 12:06 pm
kaipa: (Default)
В последнее время стало модно писать исторические экскурсы в собственный опыт использования разных языков и инструментов программирования. Я когда-то уже написал начало, не грех будет и продолжить.

В 92-94гг в очень сильной и до сих пор любимой школе №52 мы изучали Паскаль, Си, а потом, не особо глубоко FoxPro, Лисп, Форт и ассемблер-x86. С кучей задач. Из большого и светлого сделал интерактивную среду для исследования множества Мондельброта. Факультативно С++ по первому еще однотомному изданию Страуструпа. Экзамен в 11 классе принимал ныне весьма известный ученый С.М. Абрамов

94г-95. Универ -- Си и ассемблер, наверное, точно не помню. Спецкурс по Лиспу для старшекурсников, где я понял, что в школе были семечки. Курс компьютерной графики (на С++). Победа в олимпиаде. Борланд С++ на 24х 3" дискетах. Низкоуровневое программирование видео и ввода-вывода для души.

95-96. ФоксПро и Дельфи для халтуры (клиент-серверная система составления учебного расписания). Игрушка Дюна на C++ для души (в концепции Dune 2, но лучше). Не дописали. Smalltalk по верхам. OS/2 и виртуальная любовь к архитектуре AS/400, до сих пор оставшаяся виртуальной.

96-98. С 3го курса Матлаб и Математика -- мощнейшие инструменты, особенно первый. Всякие исследовательские задачи. Знакомство с маками (Mac 2) и мейнфреймами (RT-шки). Первая настоящая работа -- Дельфи+Sybase. Дипломная программа для друга-начальника (выч. модель какой-то краевой задачи). Вторая работа -- Clarion (кошмар) с Betrieve, плюс немного VB. Кризис. Оставляли, но ушел. Параллельно -- некоторые научные исследования.

98-2000. Первый мой стартап, Java (от 1.2) как инструмент, веб. Все вновинку, все интересно. Например, сделать push сообщения в апплет. Аспирантура.

99-2000. Проект в Германии, MSVC 5.0 -- тихий ужас после борландов. Но проект интересный, в компании Parsytec, которая когда-то была лидером на рынке ныне забытых транспьютеров. Не хватило запала и времени защитить диссертацию, хотя тема была интересная и актуальная, и, что удивительно, до сих пор, прошло 10 лет, она не закрыта. Всего лишь пару статей дописать надо.

2000-2005. Второй и третий стартапы (третий купил второй). Много проектов, разные технологии, C++, Java, интересные люди, например, создатели Демоса -- первого российского интернет-провайдера -- Вадим Антонов и Леша Руднев. Сначала реализовал амбиции менеджера. Потом надоело бумажки строчить, стал и код пописывать. Начал въезжать в базы данных. Научился работать с людьми.

2005-н.в. Очередной, пока последний, стартап. Начал менеджером-архитектором. Сейчас скорее эксперт (ну и директор заодно) по OLAP и производительности баз данных. Пофиг каких. Из MySQL выжимали все. Из Оракла меньше. Теперь насилуем Вертику. Неплохо разобрался в Скале для работы и для души. Задачки с ProjectEuler. Совсем для души -- J. Следующим будет R. Хотя новое дается уже сложнее. Перешел на Мак. Стал злее.

Вообще, оглядываясь назад -- я очень мало успел сделать и изучить. Можно было гораздо больше, но началась работа, и был дурак. С 92 по 97-98г было 5-6 лет интенсивного и продуктивного узнавания нового. Эта база мне колоссально помогает до сих пор. Как писал Гейзенберг, "образование -- это то, что остается, когда забудешь все, чему учили". Программисты, не получившие фундаментального образования, узнаются после пары вопросов на интервью, и делают порой "ужасные вещи". Интересно было бы поговорить со свежими выпускниками ВМК. Сильно ли просел или, наоборот, вырос уровень. Жаль, что студенты рано идут работать. Была бы моя воля -- не пускал бы. У нас студент сейчас, четверокурсник ФизТеха, но начал он работать в другой конторе год назад. И вряд ли это идет ему на пользу, но он не понимает. А как объяснишь, сам был таким же.

Вот такой вот взгляд назад через плечо.
kaipa: (Default)
Что-то часто я стал на эту тему писать, но вот нравится решать алгоритмические задачки, и все тут! Даже интереснейшую книжку Маркова "Рождение Сложности" про происхождение жизни и эволюцию в свете новейших достижений молекулярной биологии забросил. Но к ней я еще вернусь, а пока несколько красивых или познавательных задач.

8-я задача (максимальная сумма пяти подряд цифр длинного-длинного числа). The power of Scala:

(s sliding 5) map (_ map (_.toInt-48) product) max


55-я -- поиск чисел Лишрела. Это такие натуральные числа, которые, если их бесконечно переворачивать и складывать сами с собой, никогда не превратятся в палиндромы. Оказывается, большинство чисел "сходятся" к палиндромам очень быстро, буквально за 1-2-3 итерации. Трудно поверить, но это так, я проверял :) Однако, есть такие, которые не сходятся никогда. И хотя до сих пор математически доказать этот факт никто не смог, но эксперименты показали, что если за несколько десятков итераций последовательность не сходится, то она никогда не сойдется. Пример из экспериментальной математики.

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

93-я задача оказалась технически немного сложнее, и в красивые пару строчек не укладывается. Здесь требуется искать натуральные числа, составленные из разных наборов 4х фиксированных цифр, арифметических операций и скобок. Например, (1+2)*3+4. Оказывается, что с таким ограниченным набором можно получить несколько десятков разных чисел, и требуется найти заветную четверку цифр, которая бы дала максимально длинный последовательный ряд выразимых через них чисел, начиная от 1, т.е. 1,2,3,4. Задача опять на комбинаторный перебор, и вся суть, как обычно, в том, чтобы этот перебор сделать максимально просто и эффективно. Чтобы избежать скобок и проще вычислять выражения, я взял обратную польскую запись, и, конечно, решил сэкономить. 4 цифры и три операции можно в обратной польской записи расположить 5-ю разными способами, а именно.

1. XXXX+++
2. XXX+X++
3. XXX++X+
4. XX+XX++
5. XX+X+X+
(здесь 'X' обозначена любая цифра, а '+' -- операция)

Интуитивно мне показалось, что все пять пробовать -- это много, а одного мало. Я не прогадал, в итоге оказалось, что 1й и 4й вполне достаточны для правильного ответа, но интересно было бы строго доказать, что 2й, 3й и 5й варианты не могут дать результата, невыразимого через 1й и 4й, учитывая, что мы можем произвольно переставлять цифры. Что-то простое сходу в голову не приходит, а технически выписывать и сводить одно к другому неохота.

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

Update: 100я решена. Не могу не отметить грамотность условия, которое сильно облегчает решение. Программирования тут две строчки, остальное -- элементарная математика.

Euler 50

Nov. 6th, 2011 12:06 am
kaipa: (Default)
Хотя я и собирался перейти на J для разминки ума при помощи ProjectEuler, но на Скале мне пока нравится больше. 50я задача, три вечера, между делом:
- в первый, видимо, правильно, но медленно -- слишком сложная рекурсия, хотел все в одну функцию вложить, и она никак не оптимизировалась под хвостовую рекурсию.
- во второй, быстро, но не правильно
- в третий, наконец, и быстро и правильно, разложилось на два очень простых метода в две строчки каждый (генератор простых чисел сюда не входит)

Да, на J это можно написать в три понятные строчки точно, я видел вариант. А значит, и в одну, так как любую J-программу можно "свернуть" в одну емкую (но не всегда понятную) строчку.

P.S. Попутно оказалось, что разные варианты генераторов случайных чисел не являются tail-рекурсивными (в том числе и тот, который в качестве примера приведен в документации Scala класса Stream).
kaipa: (Default)
Спасибо уважаемому френду [livejournal.com profile] ivan_gandhi за ссылку на его изящную имплеменатацию теории множеств в аксиоматике Цермело-Френкеля с аксиомой выбора на Java: http://ivan-gandhi.livejournal.com/726465.html

Я восхищен. Нет, не то, чтобы это что-то очень сложное само по себе, но сама идея! Теория выводится способом, который я бы ждал от Пролога, но тут все на Джаве. Красота! Даже континуум "вывелся" естественным образом.

Интересно поэкспериментировать с разными аксиоматиками. Но сначала портировать на Скалу, должно получится раза в два короче.
kaipa: (Default)
Последние пару недель игрался на Скале с задачами с http://projecteuler.net/, и заодно подсадил на это дело жену. Мне программы писать неинтересно, интересно сделать в пару функциональных строчек в интерпретаторе, благо у Скалы есть консоль, и она хорошо оптимизирует tail-рекурсию. Когда одна из задач в пару скала-строчек не укладывалось, плюнул, и сделал на J в одну. Для J большинство задач просто семечки.

Эйлер 10 (сумма простых чисел, не превышающих 2,000,000):
+/ (#~ <&2000000) p: i.1000000x

Несмотря на то, что уже полгода с J не игрался, принципы все помню, и основное время ушло на поиск глагола для фильтра. Генератор простых чисел в J встроенный, так что по-началу я сгоряча просуммировал все 2,000,000 простых чисел, что тоже заняло всего несколько секунд.

P.S. Скоро мне привезут оригинальные книжки по J, купил остатки на Амазоне, больше там нет.
kaipa: (Default)
Прошу прощения, если эта тема избита и изъезжена вдоль и поперек, но мне стоило немалого труда "переварить" в себе, зачем это нужно. Начну с конца, вернее, с середины. В Скале функциональный трейт Function1 -- контрвариантный по аргументу, и ковариантный по результату.

trait Function1[-P, +R] {
def apply(p: P): R
}


Это не какая-то экзотика, любая параметризированная функция от одного переменного в Скале ведет себя именно так. Что это значит? На уровне "наивных" определений, ковариантность, обозначаемая модификатором "+", -- это естественное движение "вниз" по иерархии типов, от более общих к более частным, а контрвариантность, обозначаемая модификатором "-", -- наоборот, вверх, от производных типов к базовым. Вроде бы все просто, но не совсем.

Сами параметры или аргументы функций -- естественно, ковариантны. Т.е. F(p: T) можно вызвать для любого p, производного от T типа. Однако сам функциональный тип ведет себя совершенно по-другому, проще всего это продемонстрировать таким выражением:

val f: Function1[P, R] = new Function1[Psup, Rsub] { … }, где Psup -- супер-тип от P, а Rsub -- производный тип от R.

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

Пусть F: P → R, т.е. p ∈ P => F(p) ∈ R

Рассмотрим, F' : P` → R' : P` ⊃ P, R` ⊂ R.

Отсюда, p ∈ P => p ∈ P` => F`(p) ∈ R`=> F`(p) ∈ R.

То есть F` -- частный случай F на ее области определения.

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

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

trait List[+A] {
def cons(hd: A): List[A]
}

То есть у нас совершенно естественное желание, чтобы List[String] был подтипом List[Object], и поэтому используем ковариантный модификатор '+'. Однако, параметризированная функция cons содержит тип A в контрвариантной позиции, и компилятор выдаст ошибку. Что делать? Для этого в Скале есть трюк, позволяющий определять границы типов, а именно:

trait List[+A] {
def cons[B >: A](v: B): List[B]
}

Это означает, что метод cons определен для некоторого типа B, который является супер-типом от А, или A -- нижняя граница или lower bound для типа B. В частном случае, B может совпадать с A, но в общем случае функция cons может вернуть более общий тип B, что удовлетворяет естественному ощущению, что если в один список добавлять числа и строки, то получится список из более общих объектов.

Аналогичным образом в некоторых случаях целесообразно определять верхнюю границу или upper bound параметризированного типа.

Несколько англоязычных ссылок:
Scala Type System
Scala covariance/contrvariance at StackOverflow

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

Profile

kaipa: (Default)
kaipa

April 2017

S M T W T F S
       1
2345678
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 21st, 2017 04:45 pm
Powered by Dreamwidth Studios