Шаг 51.
Функциональная парадигма

    На этом шаге мы рассмотрим возникновение и развитие функциональной парадигмы.

    Языки функционального программирования (Functional Languages, Applicative Languages) - класс языков программирования и подкласс декларативных языков, основанных на идеях лямбда-исчисления и теории рекурсивных функций. Они основаны на понятии функции, - описания зависимости результата от аргументов с помощью других функций и элементарных операций. В функциональных языках нет понятия переменной и присваивания, поэтому значение функции зависит только от ее аргументов и не зависит от порядка вычислений. Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает функции, входящие в ее определение и т.д. в соответствии с иерархией определений и структурой условных предложений. Функции часто либо прямо, либо опосредованно вызывают сами себя. Каждый вызов возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока запустившая вычисления функция не вернет конечный результат пользователю. "Чистое" функциональное программирование не признает присваиваний и передач управления. Разветвление вычислений основано на механизме обработки аргументов условного предложения. Повторные вычисления осуществляются посредством рекурсии, являющейся основным средством функционального программирования. Наиболее известным представителем языков, опирающихся на функциональную парадигму, является язык LISP.

    В современные LISP-системы, как правило, включается одно или несколько средств объектно-ориентированного программирования: Flavors, Common Loops (для диалекта Common Lisp), SCOOPS. Они доведены почти до такой же "чистоты идей" объектно-ориентированного программирования, как и язык Smalltalk, но возможность параллельно пользоваться иными средствами языка LISP позволяет писать более эффективные программы. В США разрабатывается стандарт объектно-ориентированного программирования для диалекта Common Lisp - CLOS (Common Lisp Object System).

    Взгляните на объединенное генеалогическое дерево языка LISP и языка Smalltalk:


Рис.1. Генеалогическое дерево

    Расшифруем некоторые акронимы, приведенные на схеме:

    Расскажем немного об истории развития парадигмы функционального программирования.

    1931 год. Американский математик и логик Алонзо Черч описывает лямбда-исчисление, оперирующее тремя элементами: символами, скобками и обозначениями функций, выражаемыми греческой буквой "лямбда". Лямбда-исчисление легло в основу системы обозначений языка LISP.

    1956 год. Американский математик Джон Маккарти (McCarthy) разработал основы языка LISP во время работы в Летнем исследовательском проекте по искусственному интеллекту (Дартмут). Ранние реализации были сделаны для IBM 704, IBM 7090, DEC PDP-1, DEC PDP-6 и DEC PDP-10. PDP-6 и PDP-10 имели 18-битные адреса и 36-битные слова, при этом допускалось хранение CONS-ячейки в одном слове, с простыми командами для извлечения частей ячейки CAR и CDR. Ранние PDP-машины имели небольшое адресное пространство, что ограничивало размер LISP-программ.

    1960 год. Опубликована статья Джона Маккарти "Рекурсивные функции и символьные вычисления", в которой излагалось математическое обоснование языка программирования LISP - основного языка программирования в исследованиях по искусственному интеллекту.

    1960 - 1965 гг. Появление и распространение Lisp1.5 - первого диалекта языка LISP.

    1967 год. Уроженец Южной Африки профессор математики и педагогики Массачусетского технологического института Сеймур Пейперт создал на основе языка LISP язык LOGO ("лого" по гречески означает "слово").

    1969 год. Э.Херн (Anthony Hearn) и М.Грис (Martin Griss) использовали Standard Lisp для того, чтобы сделать систему символьной алгебры REDUCE более компактной для разных архитектур.

    Конец 60-х годов. Lisp1.5  порождает на два основных диалекта: Interlisp и MacLisp.

    Начало 70-х годов. Развитие специализированных компьютеров, известных как Lisp-машины, сконструированных специально для ускорения выполнения LISP-программ. Например, LISP-машина Xerox D-series использовалась для программ, написанных на языке Interlisp-D.

    1977 год. Тьюринговская лекция Джона Бэкуса, посвященная тотальной критике положения, сложившегося в программировании. Приведем длинную выдержку из работы [1, стр.54-56] (см. также [2]).

    Как ни странно, Тьюринговская лекция была посвящена тотальной критике положения, сложившегося в программировании, - причем именно в тех его разделах, за успешную работу в которых ему и была присуждена престижная премия:

    "Императивные языки программирования становятся все более громоздкими, но не более сильными. Они оказываются "толстыми" и "рыхлыми" из-за своих фундаментальных наследственных пороков: примитивного стиля программирования "слово-за-шаг", унаследованного от их общего предка - фон-неймановского компьютера; порочной связи с семантикой переходов состояний; разграничения программирования на мир выражений и мир операторов; неспособность эффективно использовать мощь комбинирующих форм для построения новых программ из уже существующих; наконец скудости полезных математических свойств, позволяющих рассуждать о программах".

    "В то время как разбухание языков приводит лишь к минимальному увеличению их возможностей, небольшие и элегантные языки - такие, как Паскаль, - остаются популярными. Но мы остро нуждаемся в мощной методологии, способной помочь нам мыслить о программах, и нет ни одного императивного языка, который близко подходил бы к осуществлению этой цели".

    Конечно, удивительно слышать подобную речь из уст человека, стоящего у истоков именно фон-неймановского стиля программирования, главы группы, разрабатывавшей в свое время первый императивный язык программирования высокого уровня - Фортран, придумавшего фундаментальные конструкции, которые по наследству переходили от одного языка к другому и захватили сегодня весь программистский мир. Недаром индекс цитирования этой статьи перешел всякие границы. Вот уже более двадцати лет на эту работу считает долгом сослаться каждый уважающий себя специалист, касаясь проблем оснований программирования. Очень жаль, что эта статья по ряду причин до сих пор не была опубликована на русском языке.

    Что же заставило мэтра фон-неймановского стиля "предать" свое детище? Увы, причин для этого оказалось достаточно. Еще в конце 60-х годов ряд ведущих специалистов начал бить тревогу по поводу кризисных явлений в программировании (об этом упоминается в книге Д.Гриса "Наука программирования"). Истинным бичом стали ошибки в программном обеспечении. Не так страшно, когда ошибки встречаются в программах-играх. Куда хуже, если ошибка обнаруживается в программной поддержке космического аппарата как раз во время его полета (к сожалению, такие прецеденты были - и с трагическим финалом). Еще одним проявлением кризиса стали несравнимые темпы роста производительности и других характеристик вычислительных машин с одной стороны и роста производительности труда программиста - с другой. За 30 лет развития программирования производительность труда программиста поднялась от силы в 10-15 раз.

    В своей критике Бэкус постоянно подчеркивает, что императивные языки переняли основные пороки от своего "духовного предка" - фон-неймановского компьютера.

    "В простейшем виде компьютер фон-Неймана состоит из трех частей: центрального процессора (ЦП), памяти и соединяющей их трубки, которая может за один шаг переслать одно слово между ЦП и памятью... Я предпочитаю называть эту трубку "узким горлышком" (Bottleneck) фон Неймана...

    Оператор присваивания - это и есть "узкое горлышко" языков программирования, которое заставляет нас мыслить категориями "слово-за-шаг" совершенно так же, как это делает горлышко вычислительной машины".

    И как вывод:

    "Проблемой является не только и не столько узкое горлышко для передачи информации, но и (что куда более важно) узкое интеллектуальное горлышко, в котором мы крепко засели со своими рассуждениями "слово-за-шаг" вместо того, чтобы подняться до мышления более общими концептуальными категориями решаемой в данный момент задачи".

    Выход, по его мнению, один: использование нестандартного программирования. В своей Тьюринговской лекции Бэкус впервые систематически излагает идею FP-стиля (Functional Programming Style).

    Конец 70-х гг.

    Группа "Максима" (Macsyma) из MIT спроектировала язык NIL (New Implementation of Lisp) - язык Lisp для компьютеров семейства VAX.

    Национальная лаборатория (Stanford and Lawrence Livermore) спроектировала S-1 Lisp для суперкомпьютера Mark IIA.

    Franz Lisp (диалект языка MacLisp) начал работать на Unix-машинах.

    Г.Суссман (G.Sussman) и Г.Стил (G.Steele) разработали язык Scheme - простой диалект языка Lisp.

    "Пришествие" в LISP объектно-ориентированного программирования.  Для Lisp-машины в MIT была разработана система Flavors. На компьютере Xerox был реализован LOOPS (Lisp Object Oriented Programming System).

    1981 г., апрель. Появление языка Common Lisp, содержащего общие аспекты различных версий языка LISP (Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp, Scheme).

    1984 год. Выход в свет книги Г.Л.Стила (Guy L.Steele) "Common Lisp: The Language". Common Lisp становится стандартом de facto.

    1990 год. Г.Л.Стил публикует книгу "Common Lisp: The Language and Edition", в которую включена информация о CLOS.

    1992 год. X3J13 разработала проект, предложенный Американским национальным стандартом (American National Standard) для Common Lisp. Этот документ является первым официальным "последователем" книги Г.Л.Стила "Common Lisp: The Language". X3J13 - это подкомитет комитета ANSI (Американский национальный институт стандартов), который работал над ANSI-стандартизацией языка Common Lisp.

(1)Математическая логика в программировании: Сб.статей 1980-1988 гг.: Пер.с англ. - М.: Мир, 1991. - 408с.
(2)Лекции лауреатов премии Тьюринга за первые двадцать лет. 1966-1985. - М.: Мир, 1993. - 560с.


    На следующем шаге мы рассмотрим продукционную парадигму.




Предыдущий шаг Содержание Следующий шаг