Курс лекций для студентов Computer Science центра

2 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Глава 1. Элементы функционального программирования Архитектура фон Неймана диктует стиль программирования? Средства программирования: Арифметические и логические операции; Присваивания; Последовательное исполнение шагов алгоритма; Управление (управляющие конструкции); Процедуры и функции; Модули, исключительные ситуации, структуры данных,... Программа: описание процесса (алгоритма) или «черный ящик»? Действие Выбор Если «да»Если «нет» Алгоритм «Черный ящик» ВходВыход Функция 1.1. Введение в функциональное программирование

3 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Задача о вычислении значений квадратных корней уравнения (процедурный стиль программирования) /** Процедура вычисляет вещественные или комплексные корни квадратного трехчлена, * в предположении, что первый коэффициент (a) отличен от нуля. * Аргументы: a, b, c – коэффициенты квадратного трехчлена; * Результаты: complexFlag – признак комплексных корней; * r1, r2 – вещественные корни, если complexFlag = False и * вещественная и мнимая части двух корней, если complexFlag = True */ class Result { boolean complexFlag; double r1; double r2; } static double discriminant (double a, double b, double c) { return b * b – 4 * a * c; } static Result squareRoots (double a, double b, double c) { Result result = new Result(); double discr = discriminant (a, b, c); // Вычисляем дискриминант result.complexFlag = discr < 0; // Определяем, вещественные или мнимые корни if (result.complexFlag) { result.r1 = (-b) / (2*a); // Вещественная часть корней result.r2 = Math.sqrt(-discr) / (2*a); // Мнимая часть корней } else { result.r1 = (-b + Math.sqrt(discr)) / (2*a); // Первый вещественный корень result.r2 = (-b – Math.sqrt(discr)) / (2*a); // Второй вещественный корень } return result; }

4 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Та же программа, написанная в функциональном стиле программирования (на псевдоязыке с Java-подобным синтаксисом) /** Функция вычисляет вещественные или комплексные корни квадратного трехчлена, * в предположении, что первый коэффициент (a) отличен от нуля. * Аргументы: a, b, c – коэффициенты квадратного трехчлена; * Результаты: признак комплексных корней; * вещественные корни, если они вещественные, и * вещественная и мнимая части двух корней, если мнимые */ double discriminant (double a, double b, double c) { return b * b – 4 * a * c; } (boolean, double, double) squareRoots (double a, double b, double c) { final double discr = discriminant(a, b, c); // Значение дискриминанта final double complexFlag = discr < 0; // Определяем, вещественные или мнимые корни (complexFlag, (complexFlag ? ((-b) / (2*a), sqrt(-discr) / (2*a)) : ((-b + sqrt(discr)) / (2*a), (-b – sqrt(discr)) / (2*a)) ); }

5 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Особенности этой программы Вместо переменных и присваиваний используются константы Составные значения легко описываются......и создаются Широко используются условные выражения Константы получают динамически вычисляемые значения Тело функции представляет собой суперпозицию применений функций для описания функциональной зависимости результата от входных данных Результаты не зависят от порядка вычислений (возможны параллельные вычисления) double discriminant (double a, double b, double c) { return b * b – 4 * a * c; } (boolean, double, double) squareRoots (double a, double b, double c) { final double discr = discriminant(a, b, c); // Значение дискриминанта final double complexFlag = discr < 0; // Определяем, вещественные или мнимые корни (complexFlag, (complexFlag ? ((-b) / (2*a), sqrt(-discr) / (2*a)) : ((-b + sqrt(discr)) / (2*a), (-b – sqrt(discr)) / (2*a)) ); }

6 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Функциональное представление множеств boolean intSet (int); // описание функционального типа данных boolean emptySet (int n) { return false; } // пустое множество boolean oddSet (int n) { return n % 2 == 1; } // множество нечетных чисел Несколько полезных операций над множествами intSet addElement (intSet s; int newElem) { boolean newSet (int n) { return s(n) || (n == newElem); } return newSet; } intSet buildInterval (int min, int max) { boolean newSet (int n) { return (n >= min) && (n

7 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Попробуем вычислить выражение difference (oddSet, addElement (emptySet, 3)) (7) { Принадлежит ли 7 множеству [odds] \ [3] } addElement s = emptySet newElem = 3 boolean emptySet (int n) { return false; } intSet addElement (intSet s, int newElem) { boolean newSet (int n) { return s(n) || (n == newElem); } return newSet; } boolean oddSet (int n) { return n % 2 == 1; } intSet difference (intSet s1, intSet s2) { boolean newSet (int n) { return s1(n) && ! s2(n); } return newSet; } Стек вычислений newSet s2 = addElement.newSet s1 = oddSet difference newSet

8 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Функциональное представление множеств в языке Java В языке Java все же можно построить правильную программу для работы с функциональным представлением множеств: abstract class IntSet { abstract boolean has(int elem); public static IntSet addElement(final IntSet s, final int n) { return new IntSet() { public boolean has(int elem) { return elem == n || s.has(elem); } }; } public static IntSet buildInterval(final int n, final int m) { return new IntSet() { public boolean has(int elem) { return elem >= n && elem

9 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Подведение итогов Императивные языки служат для описания процессов; функциональные – для описания функций, вычисляющих результат по исходным данным. На традиционных языках можно писать в функциональном стиле, однако средств работы с функциями в традиционных языках недостаточно или они неудобны. Традиционные способы реализации языков программирования плохо подходят для программ, написанных в функциональном стиле. Традиционные языки не могут обеспечить удобных средств для распараллеливания вычислений: последовательное выполнение команд – узкое место традиционной архитектуры компьютеров («фон-Неймановское горлышко»). Для функционального программирования требуются специализированные языки

10 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Литература Основная Дополнительная 1.А. Филд, П. Харрисон. Функциональное программирование. М.: Мир, П. Хендерсон. Функциональное программирование. Применение и реализация. М.: Мир, А.А.Кубенский. Функциональное программирование. ИТМО, Пол Хьюдак, Джон Петерсон, Джозеф Фасел. Мягкое введение в Haskell. RSDN Magazin, и ( 2.Р. В. Душкин Функциональное программирование на языке Haskell (+ CD-ROM) Издательство: ДМК Пресс, 2007 г., Мягкая обложка, 608 стр. 3.Н.А.Роганова. Функциональное программирование. Учебник для вузов, Graham Hutton. Programming in Haskell г., Мягкая обложка, 184 стр. 5.Bryan O'Sullivan, John Goerzen, Donald Stewart. Real World Haskell: Code You Can Believe In. Издательство: O'Reilly Media, 2008 г., Мягкая обложка, 710 стр.

11 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования Введение в язык Haskell История языка Haskell 1960: John McCarthy, LISP – первый функциональный язык программирования 1978: John Backus, FP – система комбинаторного программирования конец 1970-х: Edinburgh univ., ML – meta-language : David Turner, Miranda – функциональный язык с «ленивыми» вычислениями начало 1930-х: Church, формализация функций в λ-исчислении 1990: Ericsson, Erlang – «коммерческий» функциональный язык 1988: Paul Hudak, Haskell – первая версия языка Haskell 1999: Haskell group, Haskell98 – «стандартная» версия языка Haskell Haskell – чисто функциональный язык программирования, названный в честь Хаскелла Карри (Haskell B. Curry – ), известного, главным образом, благодаря работам в области математической логики и комбинаторной логики в конце 1950-х – начале 1960-х годов - пересмотренное сообщение о языке Haskell «Нежное» введение в Haskell

12 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Типы данных и базовые конструкции языка Haskell Элементарные типы данных Integer, Int – целые значения (25, -17, ) Float, Double – вещественные значения (3.14, ) Char – символьные значения ( 'A', '*', '3' ) Bool – логические значения ( True, False ) Идентификаторы: fact, fAcToRiAl, fact_1, fact'' Знаки операций: +, -, *,

13 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Кортежи и функции Значения могут объединяться в более сложные с помощью кортежирования. Например: pair :: (Double, Double) pair = (2.7, 3.14) attributes :: (Char, (Int, Int, Int), Bool) attributes = ('M', (17, 4, 1955), True) Тип функции определяется типами аргументов и результата, например: sin :: Double -> Double -- аргумент и результат типа Double plusInt :: Int -> Int -> Int -- два аргумента типа Int, результат Int divMod :: (Int, Int) -> (Int, Int) -- аргумент и результат - кортежи Выражения составляются из констант применением операций и функций, например: result = sin ( / 4) c10 = 3 + plusInt 3 4 pair = divMod (1458, plusInt ) Операции и функции отличаются только формой записи. Следующие выражения эквивалентны: и (+) `div` 4 и div `plusInt` 11 и plusInt 7 11

14 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Определение функций с помощью уравнений Уравнения задают правила, по которым происходит вычисление функции, то есть каким образом результат получается из аргументов функции, например: plusInt :: Int -> Int -> Int plusInt a b = a + b divMod :: (Int, Int) -> (Int, Int) divMod (a, b) = (a `div` b, a `mod` b) Уравнения могут содержать условные выражения и рекурсивные обращения, например: factorial :: Integer -> Integer factorial n = if n == 0 then 1 else n * (factorial (n-1)) sum :: Integer -> Integer sum n = n + if n == 0 then 0 else sum (n-1) factorial1 :: Integer -> Integer factorial1 n | n == 0 = 1 | n > 0 = n * (factorial1 (n-1)) factorial2 :: Integer -> Integer factorial2 0 = 1 factorial2 n = n * (factorial2 (n-1)) Уравнений для одной функции может быть несколько, тогда аргументы последовательно сопоставляются с образцами:

15 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Подготовка и запуск программ factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1)) В лекциях всюду используется «краткий» синтаксис, при котором каждое новое определение начинается с новой строки. Этот синтаксис очень чувствителен к расположению строк. Каждое новое «предложение» должно начинаться ровно в той же позиции, что и предыдущее. Если требуется разместить «предложение» на нескольких строках, то «продолжения» должны начинаться с отступом от позиции предыдущей строки - ошибка factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1)) - ошибка Заметьте, что второе уравнение, в котором опущены имя функции и образец, синтаксически является продолжением первого уравнения. factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * factorial (n-1)) - нет ошибки

16 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Подготовка и запуск программ «Полный» синтаксис подразумевает, что последовательность «предложений» заключается в фигурные скобки, а отдельные предложения отделяются друг от друга точками с запятой. В случае использования «полного» синтаксиса соблюдать отступы не обязательно. { factorial :: Integer -> Integer; factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1)) } - нет ошибки В программе можно смешивать полный и краткий синтаксис. Анализатор переключается между ними по следующим правилам: анализ начинается в режиме полного синтаксиса; если там, где нужна открывающая фигурная скобка, ее нет, то она автоматически вставляется, а анализатор переходит в режим краткого синтаксиса; если в режиме краткого синтаксиса очередная строка начинается с той же позиции, что и начало всего предложения, то перед ней автоматически вставляется точка с запятой; если очередная строка начинается с отступом влево от начала текущего предложения, то вставляется закрывающая фигурная скобка; если очередная строка начинается с отступом вправо, то это – продолжение предыдущей строки (ничего не вставляется)

17 Исполнение программ с помощью текстовой подстановки factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1)) factorial 3 3 * (factorial (3-1)) 3 * (factorial 2) 3 * (2 * (factorial (2-1))) 3 * (2 * (factorial 1)) 3 * (2 * (1 * (factorial (1-1)))) 3 * (2 * (1 * (factorial 0))) 3 * (2 * (1 * 1)) 6 Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования.

18 Несколько определений простых арифметических функций Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. -- Вычисление наибольшего общего делителя двух натуральных чисел gcd :: Integer -> Integer -> Integer gcd m n | m < n = gcd n m | n < 0 = error "gcd: Wrong argument" gcd m 0 = m gcd m n = gcd n (m `mod` n) -- Проверка заданного натурального числа на простоту prime :: Integer -> Bool prime' :: Integer -> Integer -> Bool prime p | p p = True | p `mod` d == 0 = False | otherwise = prime' (d+1) p

19 Немного о явных и неявных преобразованиях типов Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. Язык Haskell – строго типизированный. Это означает, что во время компиляции тип любого выражения известен и контролируется. Тем не менее, многие функции и операции допускают в качестве аргументов (операндов) значения разных типов – сложение целых; – сложение вещественных; – сложение вещественных (первый операнд перед операцией преобразуется); n where n = 2 – сложение вещественных (тип первого операнда «выводится» как вещественное); fromIntegral n where { n :: Int; n = 2 } – сложение вещественных (тип первого операнда явно преобразован); a + b where { a :: Int; a = 2; b :: Integer; b = 12 } – ошибка (операнды имеют разные типы); n where { n :: Int; n = 2 } – ошибка (тип первого операнда явно указан как целый); a + fromIntegral b where { a :: Int; a = 2; b :: Integer; b = 12 } – сложение коротких целых; Некоторые функции преобразования типов: fromIntegral, fromRational, fromEnum, truncate, round, ceiling, floor