Легенда:
- ★
- для выполнения работы достаточно творческих дней и практики
- ★★
- придётся потратить часть свободного времени
- ★★★
- на работу уйдёт всё свободное время, что вы готовы отдать
Contents
- Юрий Алексеевич Сыровецкий
- 0. Ваше предложение
- 1. Реализация любого CRDT ★
- 2. Доказательство теорем на языке программирования ★—★★
- 3. Универсальный синтаксис ★—★★
- 4. Моделирование вероятностных процессов с помощью списков ★—★★
- 5. Статически типизированная командная оболочка ★—★★★
- 6. Понятный расширяемый язык разметки ★—★★★
- 7. Генерация программ по условию ★—★★★
- 8. Вычислительный кластер по модели MapReduce на базе технологии Cloud Haskell ★★
- 9. Решение уравнений, записанных на языке программирования общего назначения ★★—★★★
- 10. Развитие инструментария построения графиков и визуализации для Haskell и IHaskell ★★★
- 11. Поисковая система по документации и исходному коду для библиотек языка Haskell ★★★
Выпускник Лицея 2002 года, работал в Яндекс.Директе над специализированными БД для рекламной статистики, сейчас в Лаборатории Касперского создаю безопасную ОС с помощью функционального программирования, организую встречи любителей ФП и выступаю на них.
Руковожу научными проектами лицеистов с 2012 года. Мои ученики выступали на конференциях и конкурсах.
Любимые темы — Computer Science, функциональное программирование (ФП), языки программирования (изучение старых и проектирование новых), распределённые системы.
Язык программирования Haskell, с которым я имею удовольствие работать уже несколько лет, — самый интересный представитель мира ФП, и практически — как средство для построения систем любой сложности, и теоретически — как полигон для научных изысканий.
Предварительное знакомство с языком Haskell и ФП не требуется, я всему обучу в процессе.
Некоторые слова в этом тексте могут показаться заумными и страшными, на самом деле все концепции простые и вполне под силу лицеисту (или команде лицеистов).
Сложность: определяете вы
Язык программирования: ∀.
Спросите у родителей, знакомых, какие проблемы возникают в их жизни или работе, и попробуйте придумать им IT-решение. Включите фантазию на всю катушку, придумывайте что угодно, я помогу развить то, что реализуемо, и отсечь то, что нереализуемо.
Механика, электричество, — что угодно.
Компьютерной или офлайновой.
Требования: любовь к алгебре, но не той, что с синусами и логарифмами, а той, что с буквами и множествами.
Язык программирования: ∀. Рекомендую Haskell.
CRDT (распределённый коммутативный/сходящийся тип) — это математическая основа современных распределённых баз данных. Например, без такой теории невозможно (или очень сложно) написать даже счётчик лайков под фоточкой в соцсети, если мы хотим чтобы он был достаточно быстрым и точным.
Требования: любовь к логике.
Язык программирования: Haskell или другой с достаточно сильной системой типов. Например, Agda и Idris подходят хорошо, С++ и Java подходят слабо, Python и JavaScipt не подходят вообще.
Базовая идея тут довольно простая — программа является доказательством теоремы (изоморфизм Карри — Ховарда). Тип программы — это, собственно, доказываемое утверждение. Мы просто формулируем теорему, пишем доказательство, а компьютер проверяет, правильное ли оно. [1], [2], [3], [4]
Требования: умение писать простые программы на нескольких (хотя бы двух) языках программирования.
Язык программирования: ∀. Рекомендую Haskell.
Цель — создать простейший человекочитаемый синтаксис для построения языков программирования.
Простейший синтаксис для построения языков программирования уже существует — это язык S-выражений (известный также как «лисп»), созданный американским информатиком Джоном Маккарти в 50-х годах прошлого века по мотивам лямбда-исчисления Алонсо Чёрча. На этом синтаксисе построены конкретные языки программирования Common Lisp, Scheme, Clojure, а также он имеет бесконечный потенциал к построению новых языков и новых абстракций в существующих языках.
Однако, мне он кажется недостаточно человекочитаемым. В частности, мне не нравятся
- обилие скобок и
- префиксная запись операторов (способствущая умножению скобок).
Есть у меня пара идей, как их побороть. Я предлагаю ученикам поэкспериментировать на этом поле вместе со мной, оценить существующие решения, изобрести новые и сравнить их.
Требования: базовые понятия теории вероятностей.
Язык программирования: Haskell.
Мотивационный пример: построение гистограммы распределения суммы выпавших очков для бросания трёх кубиков (3d6).
d6 = [1 .. 6 :: Integer]
roll3d6 = [a + b + c | a <- d6, b <- d6, c <- d6]
hist = [(NE.head g, length g) | g <- group (sort roll3d6)][ ( 3, 1), ( 4, 3), ( 5, 6), ( 6, 10), ( 7, 15), ( 8, 21), ( 9, 25), (10, 27), (11, 27), (12, 25), (13, 21), (14, 15), (15, 10), (16, 6), (17, 3), (18, 1) ]
Требования: знакомство с unix shell.
Язык программирования: ∀. Рекомендую Haskell.
Человеку свйственно ошибаться, а компьютеру свойственно исполнять всё, что велит человек. Чтобы последствия ошибок были менее ужасными, люди изобрели статический анализ программного кода. К сожалению, область командных оболочек и командных сценариев покрыта статическим анализом доволно плохо. Очень легко написать сценарий, который будет долго работать, а потом выдаст ошибку из-за какой-то ерунды, которую можно было предусмотреть заранее, и мы потеряем драгоценные часы—дни—недели. Но компьютер можно научить находить такие проблемы, значит, мы с вами должны это сделать!
Требования: знакомство с языками разметки, HTML или ТеХ.
Язык программирования: ∀. Рекомендую Haskell.
Сейчас для разметки текста используется множество машинных языков, из которых 2 самых широко используемых — это HTML и ТеХ.
У них есть множество проблем.
HTML имеет очень сложную модель отображения, не имеет средств абстракции, для оформления элементов HTML был изобретён другой язык — CSS — совершенно не похожий на первый, а для автоматизации работы с ними притянули третий — JavaScript — не только кардинально отличающийся от первых двух, но ещё и приносящий огромное множество собственных недостатков.
ТеХ использует вся научная среда, у него дела получше с отображением на бумаге и экране, почти хорошо с абстракцией, но он тоже далёк от идеала: он императивный, требует нескольких проходов, его синтаксис местами противоречив, местами просто странный. Для автоматизации в него притащили Lua, не такой ужасный, как JavaScript, но можно сделать ещё лучше.
Пришло время создать ТеХ двадцать первого века, декларативный, функциональный язык, хорошо подходящий как для разметки, так и для написания сценариев.
Требования: желание постичь глубину рекурсии.
Язык программирования: ∀. Рекомендую Haskell.
Написать (сгенерировать) 99 (разных) программ, выводящих "I love you".
По мотивам работы Уилльяма Бёрда.
Допустим, можно написать функцию generate такую,
что generate $ \x -> eval(x) == "I love you"
даст нам множество искомых значений.
Можно ли будет эту функцию применить для нахождения квайна?
То есть вычислить generate $ \x -> eval(x) == x
Требования: интерес к сетевым технологиям, параллельным и распределённым системам.
Язык программирования: Haskell
Функциональный подход даёт потрясающие возможности для параллельных вычислений! Отображение (map) и свёртка (reduce) — базовые понятия функционального подхода к построению алгоритмов, «кирпичики» функциональных программ. MapReduce — это способ легко параллелизовать алгоритмы, сформулированные в терминах отображений и свёрток, используя вычислительные кластеры любых масштабов.
Требования: желание близко познакомиться с логическим программированием.
Язык программирования: ∀ достаточно высокоуровневый. Рекомендую Haskell.
Мотивирующий пример:
Input:
solve $ \(k, b) ->
let f(c) = k * c + b in
f(0) == 32 && f(100) = 212
Result:
(1.8, 32)Требования: интерес к свободному ПО, желание сделать вклад в сообщество.
Язык программирования: Haskell
Они сейчас не дотягивают по возможностям и красоте до IPython и R, хотелось бы предоставить возможности учёным и бизнес-аналитикам инструменты для визуализации данных, в том числе из Haskell.
Возможности IHaskell сейчас:
- неинтерактивные рисунки из геометрических фигур,
- простые неинтерактивные графики,
- функциональная генерация неинтерактивных изображений.
Возможности IPython (к чему стремимся):
Требования: интерес к свободному ПО, желание сделать вклад в сообщество.
Язык программирования: Haskell
Альтернатива веб-интерфейсу Hackage. Существующий интерфейс хаскелльной системы документирования Haddock имеет множество возможностей для улучшения.
Например, можно сделать
- саджест по имени функции (и оператора),
- для заданного типа находить его ко- и контравариантные применения,
- сравнение (diff) программных интерфейсов между версиями пакетов.
Бонус: [1]