Монады в функциональном программировании Филипп Уодлер, Университет Глазго? Отдел Информационных Технологий, Университет Глазго, G12 8QQ, Шотландия (
[email protected]) Резюме. Описывается использование монад для структурирования функциональных программ. Монады обеспечивают удобную рабочую среду для моделирования эффектов, найденных в других языках, таких как глобальное состояние, обработка исключений, продукции, или недетерминизм. Подробно рассмотрены три исследования: как монады упрощают модификацию простого вычислителя; как монады действуют в качестве базиса типа данных массивов, подчиненных оперативному обновлению; и как монады могут использоваться, чтобы строить анализаторы. 1 Введение. Буду ли я чист или нечист? Функциональное программное сообщество делится на два лагеря. Чистые языки, такие как Miranda0 и Haskell, являются лямбда-исчислением, чистым и простым. Нечистые языки, такие как Scheme и Standard ML (Стандартный Стакан), увеличивают лямбда-исчисление с рядом возможных эффектов, таких как назначения, исключения, или продолжения. Чистые языки проще в относительных рассуждениях и могут извлечь выгоду из ленивой оценки, в то время как нечистые языки предлагают выгоды эффективности и иногда делают возможным более компактный способ выражения. Недавний прогресс в теоретической вычислительной науке, особенно в областях теории типа и теории категории, предложил новые подходы, которые могут объединить выгоды чистых и нечистых школ. Эти заметки описывают один из них - использование монад, чтобы внести нечистые эффекты в чистые функциональные языки. Понятие монады, которая является результатом теории категории, было применено Moggi, чтобы структурировать деописательную семантику языков программирования [13, 14]. Та же самая техника может быть применена, чтобы структурировать функциональные программы [21, 23]. Приложения монад будут иллюстрированы тремя исследованиями. Секция 2 вводит монады, показывая, как они могут использоваться для структурирования простого вычислителя с учётом облегчения дальнейших изменений. Секция 3 описывает законы, удовлетворенные ? Появляется в: J. Jeuring и E. Meijer, редакторы, Передовое Функциональное Программирование (Advanced Functional Programming), Слушания Весенней школы B*astad, в мае 1995, Springer Verlag Лекционные Заметки в Computer Science 925. Предыдущая версия этой заметки появилась в: M. Broy, редактор, Исчисления Проекта Программы (Program Design Calculi), Слушания Летней Школы Marktoberdorf, 30 июля - 8 августа 1992. Некоторые опечатки исправлены в августе 2001; благодарность Дэну Фридману за их обнаружение. 0 Miranda - торговая марка Research Software Limited (Ограниченного Программного обеспечения Исследования). монадами. Секция 4 показывает, как монады обеспечивают новое решение старой проблемы обеспечения обновляемого состояния в чистых функциональных языках. Секция 5 применяет монады к проблеме построения рекурсивных анализаторов спуска; это представляет интерес в его собственном праве, потому что это обеспечивает парадигму для последовательного выполнения операций и чередования, двух из центральных концепций вычисления. Сомнительно, что методы структурирования, представленные здесь были бы обнаружены без понимания, предоставленного в соответствии с теорией категории. Но когда-то обнаруженные они легко выражены без какой-либо ссылки на категориальные «вещи». Никакое знание теории категорий не обязательно для чтения этих заметок.
Примеры будут даваться на Haskell, но никакое его знание также не потребуется. То, что требуется, - мимолетные дружественные отношения с основами чистого и нечистого функционального программирования; для общего развития см. [3, 12]. Языки для ссылок Haskell [4], Miranda [20], Standard ML [11], и Scheme [17]. 2 Вычисление монад. Чистые функц