История возникновения и развития функциональных языков программирования

1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ И РАЗВИТИЯ ФУНКЦИОНАЛЬНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

1

2.

Проблемы архитектуры фон Неймана
К началу 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