Similar presentations:
История возникновения и развития функциональных языков программирования
1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ И РАЗВИТИЯ ФУНКЦИОНАЛЬНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
12.
Проблемы архитектуры фон НейманаК началу XXI века перед производителями вычислительной техники встала
серьезная проблема, связанная с наращиванием производительности
компьютеров. Тенденции к миниатюризации процессоров привели к
возникновению естественных технологических ограничений и технических
трудностей:
При размерах транзисторов в десятые доли микрона, возникает
приближение различных областей проводимости друг к другу на
расстояния порядка 100 ангстрем и начинают проявляться побочные
квантовые эффекты, отрицательно влияющие на стабильность работы
всей транзисторной схемы.
Столь высокая плотность размещения транзисторов приводит к
критическому уровню температуры в процессоре.
Уменьшение размеров полевого транзистора обязательно
сопровождается усилением электрических полей, которые накачивают
проходящие сквозь них электроны энергией и создают тем самым сильный
электрический ток, разрушающий схему.
2
3.
Проблемы архитектуры фон НейманаПроизводительность вычислительной системы можно наращивать за счет
мультипроцессорной архитектуры, однако:
традиционные императивные языки программирования весьма плохо
приспособлены для обеспечения параллельных вычислений;
их абсолютное большинство привязано к конвейерной фонНеймановской архитектуре ЭВМ и нацелено на создание алгоритмических
программ с последовательным порядком команд.
Перспективный путь решения проблемы: использование
мультипроцессорной архитектуры вычислительных систем и
функциональных языков программирования для организации
параллельных вычислений.
3
4.
История развития ФП. 1958 - 1963 гг.Сотрудники Массачусетского технологического института Джон МакКарти
(John McCarthy) и Марвин Мински (Marvin Lee Minsky) разработали язык
LISP :
это развитие более раннего низкоуровневого языка IPL (от англ.
Information Processing Language – язык обработки информации), который,
начиная с 1956 года использовался для автоматического вывода теорем
математической логики;
принципиальное отличие LISPа от прочих языков второго поколения построение программы на основе списка функций и концепции
символьного представления данных (S-выражений);
в качестве теоретической модели языка был выбран формализм lисчисления и было доказано, что любая конструкция языка
программирования может быть сведена к понятию функции;
изменилось понимание концепции памяти как хранилища значений
переменных и понятия самой переменной: переменные нужны лишь для
обозначения (декларации) программных объектов, что полностью
соответствует понятию переменной в математике.
4
5.
История развития ФП. 1958 - 1963 гг.в обычных императивных языках примерно 80% исходного кода
составляют операции присваивания - при их отсутствии программа
обретает компактность и отсутствие побочных эффектов;
появлению в мире программирования таких новых языковых свойств как
рекурсия, использование функций в качестве аргументов для других
функций, возникновение функций как результата работы другой
функции;
появление LISP продемонстрировало тот факт, что вычисление может
быть не только численным, но и символьным – в отличие от мира чисел, в
мире символов важна не форма, а смысловое содержание. Перспектива
внесения подобной «осмысленности» в ход вычислений оказалась
окрыляющей для огромного числа энтузиастов и сторонников концепции
искусственного интеллекта;
изменилось мнение о сложности вычислительных задач. Если,
традиционно, вычислительная сложность определялась количеством
данных подлежащих обработке, то здесь возник новый аспект сложности –
сложность семантическая (относительно короткое символьное предложение может
иметь огромную семантическую сложность при своем разборе и интерпретации, оценивать
которую в обычных битах и байтах просто бессмысленно ).
5
6.
История развития ФПВ дальнейшем LISP был развит в целое семейство диалектов:
MacLisp (1964 г.),
Interlisp (1966 г.),
PSL (1968 г.),
Scheme (1976 г.),
Zetalisp (1978 г.),
NIL (1979 г.),
Franz Lisp (1981 г.).
В 1984 году в Университете Карнеги-Меллона (США) все разнообразие
видов LISP было сведено к общему стандарту - Common LISP.
Примечание: Common LISP нельзя в полной мере отнести к чисто функциональным
языкам. В попытке придать стандарту универсальность, разработчики совместили его с
традиционными императивными конструкциями: переменными, циклами, состояниями
объектов, ссылками, макросами и т.п. О таких языках принято говорить уже не как о
функциональных языках, а «языках общего назначения, поощряющих функциональный
стиль программирования».
6
7.
История развития ФПНаряду с семейством LISP развивалась и альтернативная ветвь языков
программирования с упором на полную чистоту в функциональном смысле.
Родоначальником этой ветви является, как ни странно, императивный язык
ISWIM (от англ. «If you See What I Mean» – «если ты понимаешь, что я имею
в виду»), описанный Питером Лэндином (Peter J. Landin) в 1966 году.
Это был абстрактный язык программирования (то есть, без компиляторной
реализации) очень похожий на чисто математическую запись.
Несмотря на ярко выраженные императивные свойства (присваивание,
изменяемые состояния, вызов по значению и др.), ISWIM имел и
функциональные свойства (например, функции высшего порядка), за счет
использования в своей основе модифицированного l-исчисления.
7
8.
История развития ФПВ 1977 году известный американский ученый Джон Бэкус (John Backus разработчик FORTRAN, ALGOL-60 и формы Бэкуса) опубликовал статью под
названием «Can Programming Be Liberated from the von Neumann style? A
Functional Style and its Algebra of Programs» («Возможно ли освободить
программирование от стиля фон Неймана? Алгебра программ в
функциональном стиле»).
В этой статье ученый показал ряд существенных недостатков программирования с
использованием переменных и предложил описание алгебраического языка
программирования FP (сокр. от англ. Functional Programming – функциональное
программирование). Его синтаксис включал три типа программных объектов:
атомы, представляющие собой константы различных типов;
функции, способные принимать в качестве аргумента ровно один атом;
функциональные формы, способные принимать в качестве аргументов
несколько атомов.
FP оказал серьезное влияние на последующее развитие функциональных
языков программирования.
8
9.
История развития ФПВо второй половине 1970-ых годов, группой специалистов из Эдинбурга под
руководством Робина Милнера (Robin Milner) разрабатывался функциональный язык
общего назначения ML (сокр. от MetaLanguage):
первоначально, разработка предназначалась для поддержки
вывода автоматических доказательств теорем LCF (Logic for Computable Functions);
первое использование алгоритма вывода типов Хиндли-Милнера (Hindley-Milner
type inference algorithm) - он позволяет автоматически определять типы выражений,
исходя из того, как они используются в программе и какие операции поддерживают.
При этом программист не обязательно должен явно декларировать типы выражений,
обеспечивая тем самым лаконичность и высокую степень читаемости кода программ.
таким образом, ML являлся строго типизированным языком, в котором всякое
допустимое выражение имело автоматически определяемый тип (с поддержкой
полиморфных и абстрактных типов данных);
передача в качестве аргументов функций, создание в качестве результата работы
функций;
основной способ организации повторных вычислений— рекурсивный вызов функций
Особенность: в языке ML (также как и в LISP) был реализован, так называемый, энергичный
порядок вычислений, согласно которому, перед вызовом функции должны быть вычислены все ее
аргументы (так называемый, вызов по значению – call by value). При этом, если какой-либо аргумент
не использовался в теле функции, то вычисления были произведены впустую.
9
10.
История развития ФППоявление первых функциональных языков Scheme и Hope с «ленивым»
порядком вычислений (вызов по необходимости - call by need): аргумент
функции вычисляется только тогда, когда впервые используется в теле
функции.
К концу 1980-ых годов существовало уже более десятка «ленивых» языков,
среди которых особенно выделялись Miranda, LazyML, Gofer. Такое
сложное языковое разнообразие оказывало скорее негативную роль в
международном развитии функциональной парадигмы программирования.
Требовалось наличие единого, открытого, свободно распространяемого
стандарта, доступного для широкого круга ученых, программистов,
студентов.
10
11.
История развития ФПВ 1987 году на конференции FPCA’87 (Functional Programming Languages and
Computer Architecture - функциональные языки программирования и
компьютерная архитектура, г. Портленд, США) был создан специальный
рабочий комитет для подготовки стандарта функционального языка.
Основными требованиями к разрабатываемому языку были названы:
пригодность для обучения, исследований и применения (в том числе для
создания крупных программных систем);
возможность полного публичного описания языка посредством
формального синтаксиса и семантики;
свободное и бесплатное распространение;
в основу языка должны быть положены идеи, принимаемые и
поддерживаемые большинством специалистов;
возможность сократить лишнее разнообразие функциональных языков
программирования.
В 1990 году была предложена первая версия такого языка - Haskell 1.0,
названного в честь Хаскелла Карри.
11
12.
Развитие стандартов языка HaskellВ 1999 году был опубликован открытый стандарт языка Haskell 98 - «The
Haskell 98 Report», который на протяжении почти 10 лет являлся стабильным
и неизменным формальным руководством для огромного сообщества
программистов и разработчиков во всем мире.
Наиболее популярные средства для компиляции и отладки функциональных
программ на языке Haskell 98:
HUGS – компактный кроссплатформенный интерпретатор, включающий графическую
интерактивную оболочку WinHugs (для ОС Windows);
GHC (Glasgow Haskell Compiler) – мощный компилятор, поставляемый в комплекте с
интерактивной средой программирования GHCi и имеющий развитые возможности
оптимизации кода с точки зрения скорости, компактности, поддержки многозадачности и
параллельных вычислений;
NHC98 (aNother Haskell Compiler) – легкий кроссплатформенный компилятор,
реализованный на том же языке Haskell 98;
UHC (Utrecht Haskell Compiler) – компилятор для unix-совместимых платформ, с
возможностью кодогенерации для виртуальных машин;
YHC (York Haskell Compiler) – компилятор с возможностью создания промежуточного
байт-кода для генерации программ на других языках программирования (таких,
например, как Python или Erlang).
12
13.
Развитие стандартов языка HaskellВ 2009 г. опубликован новый стандарт Haskell 2010:
добавлен интерфейс FFI (Foreign Function Interface - интерфейс вызова
функций, написанных на других языках);
создан стандартный базовый дистрибутив Haskell Platform, включающий
компилятор GHC, набор библиотек функций, систему сборки и
развёртывания пакетов (Cabal).
Важной особенностью развития Haskell является открытость этого
процесса, в ходе которого все желающие могут вносить на всеобщее
рассмотрение свои предложения по усовершенствованию языка (так
называемый процесс Haskell’ или Haskell Prime).
Наиболее удачные предложения отбираются специальным комитетом и на
этой основе, по итогам каждого года, формируется новая версия языка.
13
14.
Основные характеристики языка Haskellнедопустимость побочных эффектов (чистота языка);
возможность писать программы с побочными эффектами без нарушения
парадигмы ФП с помощью монад ;
статическая сильная полная типизация с втоматическим выведением
типов (основанная на типизации Хиндли — Милнера);
функции высшего порядка, в том числе лямбда-абстракции;
частичное применение функций;
ленивые вычисления;
алгебраические типы данных, в том числе бесконечные (за
счёт ленивости);
возможность интеграции с программами, реализованными
на императивных языках программирования посредством открытых
интерфейсов FFI;
мощная поддержка объектно-ориентированной парадигмы.
14
15.
F#Параллельно с языком Haskell (и во многом под его влиянием) активно
развивается функциональный язык F#, который был представлен фирмой
Microsoft в 2005 году как один из языков семейства .NET Framework и
включен в пакет Visual Studio 2010/2012/2013.
F# является «дальним родственником» Haskell, поскольку оба языка в своем
происхождении, так или иначе, отталкиваются от диалектов ML.
Непосредственными предшественниками F# считаются объектноориентированный язык Caml (Categorical Abstract Machine Language) и
объектно-ориентированный язык функционального программирования
OCaml.
15
16.
F#Основные характеристики:
Строгая типизация и автоматический вывод типов на основе
алгоритма Хиндли-Милнера.
Поддержка парадигмы обобщенного программирования (generic
programming), позволяющей описывать данные и алгоритмы независимо
от используемых типов данных.
Поддержка функций высшего порядка.
Возможность работы с переменными, а также изменяемыми ссылками и
объектами, что является нарушением чисто функционального подхода.
Возможность гибко комбинировать эффективный и ленивый способы
вычислений.
16
17.
ВыводыТаким образом, можно констатировать постоянно растущую популярность
функционального подхода, особенно в сфере разработки web-приложений.
Основные преимущества:
компактность кода;
отсутствие наведенных ошибок;
автоматический вывод типов;
удобство реализации асинхронных процессов передачи данных;
красота и математическая выразительность функциональных конструкций.
17