Введение и основы синтаксиса

Лекция 1: введение и основы синтаксиса Функциональное программирование на Haskell Алексей Романов 14 февраля 2018 МИЭТ Организация курса • 8 лекций • 4 лабораторных • Итоговый проект 2/19 Парадигмы программирования • Что такое парадигма? 3/19 Парадигмы программирования • Что такое парадигма? «Совокупность идей и понятий, определяющих стиль написания компьютерных программ.» (Wikipedia) 3/19 Парадигмы программирования • Что такое парадигма? «Совокупность идей и понятий, определяющих стиль написания компьютерных программ.» (Wikipedia) • Основные парадигмы: 3/19 Парадигмы программирования • Что такое парадигма? «Совокупность идей и понятий, определяющих стиль написания компьютерных программ.» (Wikipedia) • Основные парадигмы: • • • • • Структурное программирование Процедурное программирование Функциональное программирование Логическое программирование Объектно-ориентированное программирование 3/19 Парадигмы программирования • Что такое парадигма? «Совокупность идей и понятий, определяющих стиль написания компьютерных программ.» (Wikipedia) • Основные парадигмы: • • • • • Структурное программирование Процедурное программирование Функциональное программирование Логическое программирование Объектно-ориентированное программирование • В парадигме важно не только то, что используется, но то, использование чего не допускается или минимизируется. 3/19 Парадигмы программирования • Что такое парадигма? «Совокупность идей и понятий, определяющих стиль написания компьютерных программ.» (Wikipedia) • Основные парадигмы: • • • • • Структурное программирование Процедурное программирование Функциональное программирование Логическое программирование Объектно-ориентированное программирование • В парадигме важно не только то, что используется, но то, использование чего не допускается или минимизируется. • Например, goto в структурном программировании, глобальные переменные в ООП. 3/19 record Descriptive declarative programming XML, S−expression Data structures only Turing equivalent Observable nondeterminism? Yes No The principal programming paradigms "More is not better (or worse) than less, just different." v1.08 © 2008 by Peter Van Roy + procedure First−order functional programming + cell (state) Imperative programming Pascal, C + closure Imperative search programming Functional programming + unification (equality) + search Relational & logic programming Scheme, ML + continuation Continuation programming Deterministic logic programming + by−need synchron. Prolog, SQL Lazy embeddings functional + solver programming Constraint (logic) Haskell SNOBOL, Icon, Prolog + name (unforgeable constant) ADT functional programming + cell ADT imperative programming Scheme, ML Haskell, ML, E CLU, OCaml, Oz + thread + single assign. + nondeterministic + port choice (channel) Monotonic dataflow Nonmonotonic Multi−agent programming dataflow dataflow programming programming Declarative programming concurrent Concurrent logic Oz, Alice, AKL programming programming CLP, ILOG Solver Pipes, MapReduce Oz, Alice, Curry, Excel, + thread + thread + by−need AKL, FGHC, FCP Concurrent + single assignment synchronization + synch. on partial termination constraint Lazy programming Functional reactive dataflow programming (FRP) LIFE, AKL programming Weak synchronous + by−need synchronization Lazy programming Lazy concurrent declarative FrTime, SL constraint concurrent programming programming + instantaneous computation Oz, Alice, Curry Oz, Alice, Curry Strong synchronous programming Logic and Esterel, Lustre, Signal Dataflow and Functional constraints message passing Unnamed state (seq. or conc.) More declarative + search Nondet. state + port (channel) + cell (state) Event−loop programming E in one vat + thread Multi−agent programming Message−passing concurrent programming Erlang, AKL + local cell Active object programming Object−capability programming + closure Sequential object−oriented programming Stateful functional programming Java, OCaml + thread Concurrent object−oriented programming Shared−state concurrent programming Smalltalk, Oz, Java, Alice + log CSP, Occam, E, Oz, Alice, publish/subscribe, tuple space (Linda) SQL embeddings Message passing Shared state Software transactional memory (STM) Named state Less declarative Peter Van Roy, "Programming Paradigms for Dummies: What Every Programmer Should Know", 2009 See "Concepts, T The chart classif languages (the s abstractions can the creative exte encoded with on the same paradig programmer, be programming te When a languag the language is i without interfere is a perfect fit be that libraries hav The language’s there is a family family is mentio not imply any ki State is the abili sequence of valu the paradigm tha which differ in w nondeterministic functional progr unnamed, determ declarative conc deterministic, an concurrent logic nondeterministic gives message p and concurrent). (e.g., client/serv Axes orthogonal Typing is not co Aspects should b program’s speci in any paradigm Metaprogrammi language. The t programming, sy programming co protocols and ge (introspection an tinkering in part as Scheme, are f native fashion. 4/19 Функциональное программирование • Значения лучше переменных. • Переменная даёт имя значению или функции, а не адресу в памяти. • Переменные неизменяемы. • Типы данных неизменяемы. • Выражения лучше инструкций. • Аналоги if, try-catch и т.д. — выражения. • Функции как в математике (следующий слайд) 5/19 Функциональное программирование • Функции как в математике 6/19 Функциональное программирование • Функции как в математике • Чистые функции: аргументу соответствует результат, а всё прочее от лукавого. • Нет побочных эффектов (ввода-вывода, обращения к внешней памяти, не связанной с аргументом, и т.д.) • При одинаковых аргументах результаты такой функции одинаковы • Функции являются значениями (функции первого класса) • Функции часто принимают и возвращают функции (функции высших порядков) 6/19 Функциональное программирование • Функции как в математике • Чистые функции: аргументу соответствует результат, а всё прочее от лукавого. • Нет побочных эффектов (ввода-вывода, обращения к внешней памяти, не связанной с аргументом, и т.д.) • При одинаковых аргументах результаты такой функции одинаковы • Функции являются значениями (функции первого класса) • Функции часто принимают и возвращают функции (функции высших порядков) • Опора на математические теории: лямбда-исчисление, теория типов, теория категорий 6/19 Языки ФП • семейство Lisp: первый ФП-язык и один из первых языков высокого уровня вообще • Erlang и Elixir: упор на многозадачность (модель акторов), надёжность • Scala, Kotlin, F#: гибриды с ООП для JVM и для CLR • Purescript, Elm, Ur/Web: для веба • Семейство ML: OCaml, SML, F# 7/19 Языки ФП • семейство Lisp: первый ФП-язык и один из первых языков высокого уровня вообще • Erlang и Elixir: упор на многозадачность (модель акторов), надёжность • Scala, Kotlin, F#: гибриды с ООП для JVM и для CLR • Purescript, Elm, Ur/Web: для веба • Семейство ML: OCaml, SML, F# • Haskell: • Чисто функциональный 7/19 Языки ФП • семейство Lisp: первый ФП-язык и один из первых языков высокого уровня вообще • Erlang и Elixir: упор на многозадачность (модель акторов), надёжность • Scala, Kotlin, F#: гибриды с ООП для JVM и для CLR • Purescript, Elm, Ur/Web: для веба • Семейство ML: OCaml, SML, F# • Haskell: • Чисто функциональный • Строго статически типизированный (с очень мощной и выразительной системой типов) 7/19 Языки ФП • семейство Lisp: первый ФП-язык и один из первых языков высокого уровня вообще • Erlang и Elixir: упор на многозадачность (модель акторов), надёжность • Scala, Kotlin, F#: гибриды с ООП для JVM и для CLR • Purescript, Elm, Ur/Web: для веба • Семейство ML: OCaml, SML, F# • Haskell: • Чисто функциональный • Строго статически типизированный (с очень мощной и выразительной системой типов) • Ленивый 7/19 Язык Haskell: начало • Установите Haskell Platform (https://www.haskell.org/platform/) • Запустите WinGHCi (или просто GHCi) • Это оболочка или REPL (Read-Eval-Print loop) • Read: Вы вводите выражения Haskell (и команды GHCi) • Eval: GHCi вычисляет результат • Print: и выводит его на экран • Пример: GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help Prelude> 2 + 2 4 Prelude> :t True -- команда GHCi True :: Bool 8/19 Язык Haskell: начало • 2 + 2, True — выражения • 4, True — значения • Bool — тип 9/19 Язык Haskell: начало • • • • • 2 + 2, True — выражения 4, True — значения Bool — тип Значение — «вычисленное до конца» выражение. Тип (статический) — множество значений и выражений, построенное по таким правилам, что компилятор может определить типы и проверить отсутствие ошибок в них без запуска программы. • От типа зависит то, какие операции допустимы: Prelude> True + False :12:1: error: No instance for (Num Bool) arising from a use of '+' In the expression: True + False In an equation for 'it': it = True + False • Это ошибка компиляции, а не выполнения. 9/19 Вызов функций • Вызов (применение) функции пишется без скобок: f x, foo x y. • Скобки используются, когда аргументы — сложные выражения: f (g x) • И внутри сложных выражений вообще. • Бинарные операторы (как +) это просто функции с именем из символов вместо букв и цифр. • Можно писать их префиксно, заключив в скобки: (+) 2 2. • А любую функцию двух аргументов с алфавитным именем можно писать инфиксно между обратными апострофами: 4 `div` 2. • Единственный небинарный оператор — унарный -. • Названия переменных и функций начинаются со строчной буквы (кроме операторов). 10/19 Определение функций и переменных • Определение переменной выглядит как в математике, даже без ключевых слов: название = значение • Определение функции почти такое же: название параметр1 параметр2 = значение • Тело функции это не блок, а одно выражение (но сколь угодно сложное). Prelude> x = sin pi Prelude> x 11/19 Определение функций и переменных • Определение переменной выглядит как в математике, даже без ключевых слов: название = значение • Определение функции почти такое же: название параметр1 параметр2 = значение • Тело функции это не блок, а одно выражение (но сколь угодно сложное). Prelude> x = sin pi Prelude> x 1.2246063538223773e-16 Prelude> square x = x * x Prelude> square 2 4 11/19 Базовые типы • Названия типов всегда с заглавной буквы. • Bool: логические значения True и False. • Целые числа: • Integer: неограниченные (кроме размера памяти); • Int: машинные1 , Word: машинные без знака; • Data.{Int.Int/Word.Word}{8/16/32/64}: фиксированного размера в битах, со знаком и без. • Float и Double: 32- и 64-битные числа с плавающей точкой, по стандарту IEEE-754. • Character: символы Unicode. • (): «Единичный тип» (unit) с единственным значением (). 1 по cтандарту минимум 30 бит, но в GHC именно 32 или 64 бита 12/19 Тип функций и сигнатуры • Типы функций записываются через ->. Например, Int -> Char это тип функции из Int в Char. • Для нескольких аргументов это выглядит как 13/19 Тип функций и сигнатуры • Типы функций записываются через ->. Например, Int -> Char это тип функции из Int в Char. • Для нескольких аргументов это выглядит как Bool -> Bool -> Bool. • :: читается как «имеет тип». • Запись выражение :: тип — «сигнатура типа». • При объявлении экспортируемой функции или переменной сигнатура обычно указывается явно: foo :: Int -> Char foo x = ... • Компилятор обычно может вывести типы сам, но это защищает от непреднамеренного изменения. 13/19 Арифметика • Это упрощённая версия. • Полное объяснение требует понятия, которое будет введено позже. • Например, команды :type 1 или :type (+) дадут тип, который понимать пока не требуется. • То же относится к ошибкам вроде No instance for (Num Bool)... на более раннем слайде. • Пока достаточно понимать, что есть несколько числовых типов. • Они делятся на целочисленные (Int, Integer) и дробные (Float, Double). 14/19 Числовые литералы • Числовые литералы выглядят, как в других языках: 0, 1.5, 1.2E-1, 0xDEADBEEF. • Целочисленные литералы могут иметь любой числовой тип, а дробные любой дробный. • Но это относится только к литералам. • Неявного приведения (например, Int в Double) в Haskell нет. 15/19 Приведение числовых типов • Используйте fromIntegral для приведения из любого целочисленного типа в любой числовой. Тип-цель можно указать явно: Prelude> let {x :: Integer; x = 2} Prelude> x :: Double :22:1: error: Couldn't match expected type 'Double' with actual type 'Integer' ... Prelude> fromIntegral x :: Double 2.0 • А может выводиться из контекста: Prelude> :t fromIntegral 2 / (4 :: Double) fromIntegral 2 / (4 :: Double) :: Double 16/19 Приведение числовых типов • toInteger переводит любой целочисленный тип в Integer. • fromInteger — наоборот. Если аргумент слишком велик, возвращает значение по модулю: Prelude> fromInteger (2^64) :: Int • toRational и fromRational — аналогично для Rational и дробных типов. • ceiling, floor, truncate и round — из дробных типов в целочисленные. 17/19 Арифметические операции • Операции +, -, * — как обычно (унарного + нет). • / — деление дробных чисел. • Использование / для целых чисел даст ошибку No instance... arising from a use of '/'. Нужно сначала использовать fromIntegral. • div — деление нацело • mod — остаток • quot и rem тоже, но отличаются от них поведением на отрицательных числах. • ^ — возведение любого числа в неотрицательную целую степень. • ^^ — дробного в любую целую. • ** — дробного в степень того же типа. 18/19 Операции сравнения и логические операции • Большинство операций сравнения выглядят как обычно: ==, >, <, >=, <=. • Но 6= обозначается как /=. • Функция compare возвращает Ordering: тип с тремя значениями LT, EQ и GT. • Есть функции min и max. • «и» это &&, а «или» — ||, как обычно. • «не» — not. 19/19