Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 149
Текст из файла (страница 149)
В 1958-1959 годах Мак-Карти создал язык ПЗР, который вошел в практику в 1959 году. Мак-Карти работал темке в команде по разработке языка А)ЛО).. 14.10. Сравнение функциональных и императивных языков Функциональные языки программирования ЗУ9 В этой главе рассматривается функциональное программирование, а также некоторые языки программирования, созданные для реализации этого подхода к разработке программного обеспечения.
Поскольку эти языки основаны на л1атематических функциях, начинаем с обзора основных математических идей, включая функциональное лямбда-исчисление Черча, Эта глава также содержит краткое описание функциональных форм и несколько примеров наиболее распространенных из них. Далее излагается идея функционального языка программирования. обзор первого языка программирования ЫБР, а также его структуры данных в виде списков и синтаксис функций, основанный на лямбда-исчислении.
Следующий большой раздел посвящен введению в язык Зевеке и содержит описание его элементарных функций, специальных и функциональных форм, а также примеры простых функций, написанных на языке Болеее. Затем мы обсудим некоторые императивные свойства языка Зс1зеше. Далее приводится краткое введение в языки СОММОХ ЫЗР, М1. и НазкеП, для того чтобы показать отличие идей разработки языков функционального программирования от идей, положенных в основу языка Бенете. В следующем разлеле описывается применение функциональных языков программирования. В заключение мы сделаем краткий сравнительный анализ функциональных и императивных языков программирования.
й4. й. Введение Первые 13 глав этой книги касались в основном императивных и объектноориентированных языков программирования. За исключением языка Бша1йаук, рассмотренные нами языки программирования внешне были похожи на императивные языки. В данной главе впервые в центре внимания находятся неимперативные языки. Высокая степень схожести между императивными языками частично объясняется тем, что они разработаны на основе общего принципа — неймановской архитектуры компьютера, рассмотренной в главе 1. Мы можем считать императивные языки в целом шагом вперед в направлении улучшения базовой модели, которой являлся язык РОКТКАХ 1.
Все. что было разработано в этой области, направлено на эффективное использование неймановской архитектуры компьютера. Несмотря на то что императивный стиль программирования получил признание большинства программистов, некоторые специалисты считают, что его зависимость от архитектуры компьютеров, лежащей в основе этого стиля, ограничивает процесс разработки программного обеспечения. Существуют другие принципы разработки языков, многие из которых более ориентированы на конкретные парадигмы или методологии программирования. чем на эффективное выполнение в рамках конкретной компьютерной архитектуры.
До сих пор. однако, вследствие невысокой эффективности выполнения программ, написанных на этих языках, они не получили такой же популярности, как императивные языки. Парадигма функционального программирования, основанная на математических функциях. лежит в основе многих важных неимперативных стилей программирования. Эти стили поддерживаются функциональными, или аппликативными, языками программирования. Язык ЫВР возник как чисто функциональный, но вскоре приобрел некоторые важные императивные свойства.
увелнчнвшне эффективность выполнения программ, написанных на этом языке. Язык ЫБР остается наиболее важным из функциональных языков, по крайней мере, в том смысле, что только он получил широкое распространение. Язык депеше является небольшим диалектом языка ЫЯР, использующим статический обзор 660 Глава 14. Функциональные языки программирования данных. Язык СОММО)ч Е15Р— смесь нескольких диалектов языка Ы5Р, разработанных в начале 1980-х годов.
Язык М) — строго типизированный функциональный язык с более традиционным синтаксисом, чем у языков 115Р и 5сйеше. Язык Наз(сеП частично основывается на языке М(., но при этом является чисто функциональным языком. Цель этой главы — рассмотреть концепцию (а не процесс) функционального программирования. Мы также опишем несколько способов разработки языка. обеспечивающих традиционные средства функционального программирования. Сначала иы опишем математические функции и функциональное программирование, а затем рассмотрим подмножество языка 5сйете, являющегося чисто функциональным языком.
для того чтобы проиллюстрировать функциональный стиль программирования. В главе содержится материал, достаточный для того, чтобы читатель смог написать некоторые простые, но интересные программы. Трудно усвоить функциональный стиль программирования без реального опыта. 14.2. Математические функции Математическая функция — это отображение (гпарр!пй) элементов одного множества, называемого областью определения (доша!и зег), в другое множество. называемое множеством значений (гапйе зег). В определении функции явно или неявно указываются множество определения н множество значений вместе с самим отображением. Отображение описывается выражением или, в некоторых случаях, таблицей.
Функции часто применяются к отдельному элементу множества определения. Заметим, что множество определения может быть результатом пересечения нескольких множеств. Функция вырабатывает, или возвращает, элемент из множества значений. Одно из основных свойств математических функций заключается в том, что порядок вычисления выражений, задающих отображения, управляется рекурсивными и условными выражениями, а не итеративным повторением и последовательностью выполнения операций, как в императивных языках программирования. Другое важное свойство математических функций состоит в том, что они всегда определяют одно и то же значение при заданном наборе аргументов. поскольку онн не имеют побочных эффектов.
Побочные эффекты в языках программирования связаны с переменными, моделирующими ячейки памяти. Математическая функция опрелеляет значение, а не указывает последовательность операций над числами, хранящимися в ячейках памяти, для вычисления некоторого значения. Здесь нет переменных, как в императивных языках программирования, поэтому не может быть побочных эффектов. 1Я.2.1. Простые функции Определения функций часто записываются в виде имени функции, за которым следует список параметров в скобках и выражение, задающее отображение. Например, свое(х)их'х'х, где х — действительное число.
В этом определении областью определения и областью значений является множество всех действительных чисел. Символ и используется в качестве сокрашения выражения "определяется как". Параметр х может быть любым элементом из множества определения, но во время вычисления выражения, определяемого функцией, он представляет собой только один конкретный элемент.
В этом заключается отличие параметров математических функций от переменных в императивных языках. 581 14.2. Мптамптичаскиа функции Функции применяюгся с помошью образования пар, состояших из имени функции и конкретного элемента из множества определения. Элемент, являющийся значением функции. получается путем вычисления выражения, задаюшего отображение, применительно к элементу из области определения, замененного значением параметра.
Например, сцЬе(2.0) в результате равно 8.0. Здесь снова важно отметить, что во время вычисления данное отображение, определяемое функцией, не содержит несвязанных параметров, где связанный параметр — это имя конкретного значения. Каждое появление параметра связывается со значением из области определения и рассматривается как константа во время вычисления. Ранние теоретические работы, посвяшенные функциям, отделяли задачу определения функции от задачи именования функции. Метод определения безымянных функций реализуется с помошью лямбда-исчисления, разработанного Алонзо Черчем (А!опхо СЬцгсЬ) (СЬпгсЬ, 1941). Параметр н отображение, определенное функцией, задается лимбдавыраженнем (1ашЬда ехргеззюп). Само по себе лямбда-выражение является функцией.
Например, рассмотрим выражение Л(х)х'х'х Как указывалось выше, перед вычислением параметр представляет собой любой элемент множества определения функции, однако во время вычисления он связан с конкретным элементом. Прн вычислении лямбда-выражения для заданного параметра говорят, что выражение применяется к данному параметру. Механизм такого применения тот же самый, что и при вычислении любой функции.
Применение лямбда-выражения, указанного выше, обозначается так, как это показано в следуюшем примере: Л(х)х"хьх(2). Результат этого выражения равен 8. Подобно другим определениям функций, лямбла-выражения могут иметь несколько параметров. 14.2.2. Функцикзнсзльныв формы Функции более высокого порядка, илн функциональные формы (бзпсзюпа! Гоппз), отличаются тем, что они либо получают функции в виде параметров, либо некая функция является результатом их работы, либо имеет место и то, и другое.
Наиболее распростра- ненным видом функциональных форм является композиция функциЯ (бзпсг(оп сошрозйюп), параметрами которой служат лве функции. Результат композиции функ- ций — это функция, значения которой являются, в свою очередь, результатом примене- ния первой функции-параметра к результату работы второй функции-параметра. Компо- зиция функций записывается как выражение с помошью оператора ', как показано ниже л -~'8 Например, если Ях) и х + 2, Ях)м3 ьх, то л определяется как )г(х) -=Яй(х)), или А(х) е (Зьх)+2. ЗВ2 Глава 14. Функциональные языки программирования Конструкция (сопзгпкйоп) — это функциональная форма, получающая в качестве параметра список функций. В результате применения к своему аргументу конструкция применяет каждую нз своих функций-параметров к этому аргументу н обьеднняет ре- зультаты в список нлн последовательность. Конструкция синтаксически обозначается за- ключением функций в квадратные скобки, например [Гй).
Рассмотрим следующий при- мер: пусть д(х) - =х ' х, л(х) - =2 ' х. )(х) и х/2, тогда [й,й.!](4) вырабатывает значение (! 6.8.2). Функция применить-ко-всем (арр!учо-ай) — это функциональная форма, имеющая в качестве параметра одну функцию.
Если она применяется к списку аргументов, то функция прнменнть-ко-всем применяет свою функцию-параметр к каждому нз значений в списке аргументов н объединяет результаты в список нлн последовательность. Функция применить-ко-всем обозначается как а. Рассмотрим следующий пример: пусть Ь(х) = т'х, тогда а()),(2,3,4)) вырабатывает значения (4,9,16). Существует много других функциональных форм, но этих примеров должно быть достаточно, чтобы проиллюстрировать нх свойства.
14.3. Основы функциональных языков программирования Функциональные языки программирования разрабатываянсь с целью как можно более точной имитации математических функций. В результате возник подход к решению залач, в корне отличающийся от методов, применяемых нмператнвнымн языками. В императивном языке вычисляется некое выражение, н результат помещается в ячейку памяти. представленную переменной в программе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
