с/с «Программирование на F#»

Описание курса

Тема курса: функциональное программирование на примере языка F#

В курсе рассматриваются основы функционального программирования на языке F#, в том числе некоторые концепции, которые принято ассоциировать с ФП, такие как алгебраические типы данных, сопоставление с образцом, ленивые вычисления, автоматический вывод типов, и др. Дается общее представление о платформе разработки Microsoft.NET

Требования к слушателям

Умение программировать на любом алгоритмическом ЯП, знакомство с циклами, функциями и рекурсией. Желательно знакомство с языком C#.

Знакомство с функциональным программированием и платформой .NET не является обязательным.

Технические требования

Язык F# включен в платформу разработки Visual Studio 2010. Так же, интеграция F# возможна с платформой Visual Studio 2008 shell (Integrated Mode). С помощью проекта mono (http://www.mono-project.com) F# доступен для разработки и запуска на POSIX платформах.

Зачет

Зачет состоит из трех частей: текущие задачи, доклад, курсовая и письменный экзамен в конце, по вопросам из докладов. Максимум 35 + 20 + 25 + 20 = 100 баллов. Для зачета требуется не менее 55 65 баллов.

Задания

Задания посылаются на email (victorp@math.spbu.ru). На выполнения задания дается неделя (до 24:00 понедельника) + ещё неделя с прогрессивным штрафом. Один раз можно воспользоваться бесштрафовой отсрочкой на одну неделю, явно указав это в письме с заданием.

1. До 28.02.2011, 6 баллов.
2. Реализовать следующие функции.
   1. length - длина списка
   2. map
   3. filter
   4. Сумма чётных чисел Фибоначчи, не превосходящих 4000000
   5. Любые две задачи с http://projecteuler.net, с количеством решений < 50000
3. До 08.03.2011, 4 балла
4. Описать тип для арифметических выражений над числами и идентификаторами с операциями +, -, *, / и реализовать функцию вычисления константных подвыражений (включая сумму и умножение на ноль).
5. Дополнительные баллы за другие интересные оптимизации
6. До 22.03.2011, 5 баллов
7. Описать тип, соответствующий λ-выражениям: функция, вызов, переменная.
8. Реализовать алгоритм подстановки, β-редукции, и две стратегии вычисления - любую одну активную и одну ленивую.
9. Используя полученные вычислители проверить какое из двух различных реализаций функции возведения числа в степень для чисел Чёрча (явного и выраженного через умножение) эффективнее в смысле количества β-редукций.
10. До 29.03.2011, 4 балла
11. Реализовать вычисление арифметических выражений в инфиксной форме, реализовав разбор методом рекурсивного спуска. Выражения могут содержать числа, арифметические операции, скобки и любое количество пробелов и знаков переноса строки. Явно выделить лексический и синтаксический анализаторы (lexer и parser).
12. Уделить внимание локализации изменяемого состояния, если такое возникнет.
13. +2 балла + неделя на доработку предыдущего задания на устранения явных ref из парсера
14. До 12.04.2011, 4 балла
15. Реализовать ассоциативный массив со строковыми ключами как чистую структуру данных.
16. Оформить в виде параметрического класса с операциями добавления, возвращающей новый ассоциативный массив, и поиска, возвращающего 'a option.
17. Между реализациями будет проведено соревнование по производительности: за 1 место - +3 балла, 2 - +2, 3 - +1.
18. До 19.04.2011, 5 баллов
19. Реализовать "пристойное*" приложение с графическим пользовательским интерфейсом, используя принципы реактивного программирования. (В коде должны быть использованы по крайней мере 3 комбинатора событий)
20. * творческое задание
21. До 26.04.2011, 5 баллов
22. Реализовать концепт WebCrawler'а: программу, принимающую на вход URL, и в несколько потоков рекурсивно считающая количество страниц, доступных с данного URL таких, адрес которых начинается с оригинального URL.
23. (Аналог "wget -r --no-parent <url>", только вместо сохранения файла увеличивающий аккумулятор, и скачивающий в несколько потоков)
24. До 10.05.2011, 7 баллов
25. Реализовать парсер ассемблера StudentAsm, используя FParsec, и вычислитель для получившегося кода.

Текущая успеваемость

Доклады

В докладе оценивается:

• полнота раскрытия материала
• доступность для слушателей
• план доклада
• умение уложиться в отведенное время

Темы

• История функционального программирования
• Лямбда-исчисление
• Типизированное лямбда-исчисление
• Обзор платформы .NET
• ?Система типов Хиндли-Милнера, вывод типов, алгоритм унификации.
• *События в F#, реактивное программирование
• *Асинхронное и параллельное программирование в F#
• *Создание GUI приложений в F#
• to be continued...

* - ещё не взят, ? - пропал докладчик

Курсовая

TODO

Рекомендации по оформлению кода

Код заданий должен быть красиво оформлен.

• Обязательное наличие заголовка файла (ФИО, копирайт, год, описание задания)
• Именование идентификаторов - camelCase или PascalCase
• Разумное форматирование
• К программе должны прилагаться тесты
• Не надо посылать бинарные и объектные файлы, файлы-кэши Intelli-Sense, и т.п.
• Этот список не полон, но за не надлежащее оформление могут быть применены штрафные санкции