Архив‎ > ‎Весна 2011‎ > ‎

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

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



Доклады

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

Курсовая

TODO

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

Код заданий должен быть красиво оформлен.
  • Обязательное наличие заголовка файла (ФИО, копирайт, год, описание задания)
  • Именование идентификаторов - camelCase или PascalCase
  • Разумное форматирование
  • К программе должны прилагаться тесты
  • Не надо посылать бинарные и объектные файлы, файлы-кэши Intelli-Sense, и т.п.
  • Этот список не полон, но за не надлежащее оформление могут быть применены штрафные санкции
ċ
Async.rar
(60k)
Victor Polozov,
10 мая 2011 г., 00:25
ć
Victor Polozov,
17 мая 2011 г., 01:28
Ċ
Victor Polozov,
17 мая 2011 г., 01:16
Ċ
dotnet.pdf
(199k)
Victor Polozov,
17 мая 2011 г., 00:57
ć
frp.ppt
(67k)
Victor Polozov,
10 мая 2011 г., 00:23
Ċ
fslang.pdf
(355k)
Victor Polozov,
17 мая 2011 г., 00:45
Ċ
Victor Polozov,
15 мар. 2011 г., 03:18
Ċ
Victor Polozov,
22 мар. 2011 г., 10:45
Comments