с/с «Программирование на 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, и вычислитель для получившегося кода.

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

F#.2011

Доклады

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

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

Темы

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

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

Курсовая

TODO

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

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

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