Функциональное программирование Доклад на семинаре по специальности Студент гр.4057/2 Олег Хабаров

Содержание Введение 1.Лямбда-исчисление как база парадигмы 2.Основы функционального программирования 3.Преимущества и недостатки 4.Языки 1.Lisp 2.Haskell 3.Erlang 4.ML 5.OCaml 6.F# 5.Ссылки Заключение Хабаров О.В. 4057/22

Введение Импертивное программирование как основная парадигма программирования Описывает порядок действий (как получить результат?) Декларативное программирование описывает свойства (каким должен быть результат?) Функциональное программирование – противоположность императивному Хабаров О.В. 4057/23

Лямбда-исчисление Формальная система для описания функций, их приложений и рекурсии Термами являются(и только они) – переменные – абстракции(описание функции) – приложения(вызов функции) Альфа-эквивалентность Свободные переменные Хабаров О.В. 4057/24

Основы функционального программирования Объекты вычисления - функции Отсутствие хранения состояния программы в явном виде Функции высших порядков Чистые функции Рекурсия Подход к вычислению аргументов – Строгое – Отложенное(ленивое) Оптимизация хвостовой рекурсии Хабаров О.В. 4057/25

Преимущества и недостатки Преимущества – Повышение надёжности кода – Удобство тестирования – Лучшая оптимизация при компиляции – Автоматическая оптимизация на параллельные вычисления Недостатки – Интенсивное использование динамической памяти – Отсутствие «синтаксического сахара» Хабаров О.В. 4057/26

Языки Главная проблема «чистого языка» - побочные эффекты Чистые реализации используют монады для взаимодействия с окружающим миром Большинство языков поддерживают парадигму функционального программирования, но не ограничиваются ей Хабаров О.В. 4057/27

Языки(2) Хабаров О.В. 4057/28

Lisp ФП - опорная парадигма Главные диалекты – Common Lisp и Scheme Допускается императивность Steel Bank Common lisp – стандартизован ANSI, компилируемый. Показывает отличную производительность Пример – вычисление факториала (defun factorial (n) (if (

Haskell Стандартизованный чистый язык ФП Реализует отложенные вычисления Монады позволяют использовать графику, ввод/вывод, … Пример простой функции – на С int foo (int x){ return x * ; } – на Haskell foo :: Int -> Int foo bar = bar * Хабаров О.В. 4057/210

Haskell(2) Использование OpenGL – рисование точек import Graphics.Rendering.OpenGL import Graphics.UI.GLUT myPoints :: [(GLfloat,GLfloat,GLfloat)] myPoints = map (\k -> (sin(2*pi*k/12),cos(2*pi*k/12),0.0))[1..12]mapsinpicospi main = do (progname, _) vertex$Vertex3 x y z) myPoints$mapM_ flush Хабаров О.В. 4057/211

Erlang Назначение – распределённые вычислительные системы Текущая реализация интерпретируемая, хотя поддерживается компилятор Куски кода могут заменяться в run-time Старая и новая версия модуля могут использоваться одновременно Пример – вычисление факториала -module(fact). -export([fac/1]). factorial(0) -> 1; factorial(N) -> N*factorial(N-1) Хабаров О.В. 4057/212

Erlang(2) Виртуальная машина - узел, обладающей именем Узлы на одной машине и на разных не имеют различий Каждый процесс может создавать потоки на разных узлах Отсутствие присваиваний облегчает параллельное программирование Хабаров О.В. 4057/213

ML ML – meta language, Не скрывает побочных эффектов Строгие вычисления Статическая типизация Основные диалекты – Standart ML и Caml Применения – финансовые системы – приложения peer-to-peer – иерархические базы данных Хабаров О.В. 4057/214

OCaml Objective Caml – найболее используемая реализация диалекта Caml Объединяет функциональное, императивное и объектно- ориентированное программирование Совместимость типов объектов также определяется по сигнатуре методов Quick sort let rec qsort = function | [] -> [] | pivot :: rest -> let is_less x = x < pivot in let left, right = List.partition is_less rest in qsort qsort righ t Хабаров О.В. 4057/215

Ocaml(2) Пример объединения(С) struct foo { int type; #define TYPE_INT 1 #define TYPE_PAIR_OF_INTS 2 #define TYPE_STRING 3 union { int i;// If type == TYPE_INT int pair[2]; // If type == TYPE_PAIR_OF_INTS char *str; // If type == TYPE_STRING } u; }; Пример объединения(OCaml) type foo = Nothing | Int of int | Pair of int * int | String of string;; Хабаров О.В. 4057/216

F# F# - диалект ML от Microsoft Интегрирован в MSVS 10 Согласован с.NET Функциональная часть поддерживает кортежи, структуры и списки Императивная часть языка позволяет использовать конструкции for, while и массивы Поддержка объектно-ориентированных конструкций Хабаров О.В. 4057/217

F#(2) Пример на создание окна open System open System.Windows.Forms let form = new Form(Visible=true, TopMost=true, Text="Welcome to F#") let label = let temp = new Label() let x = 3 + (4 * 5) temp.Text

Заключение Развитие функциональных языков в производственной сфере Модульность и функции высших порядков – ключ к успеху Нет однозначного мнения насчёт ленивых вычислений Хабаров О.В. 4057/219

Ссылки Functional Programming//Wikipedia. Haskell//Wikipedia. Haskell OpenGL. Erlang//Wikipedia. F#//Wikipedia. guage) Практика функционального программирования. – Хабаров О.В. 4057/220

Спасибо за внимание!