Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 156
Текст из файла (страница 156)
Функциональные языки программирования Для указания обстоятельств, при которых можно применять это определение, к строкам определения функции можно добавить защиту. Например: йасС п п == 0 = 1 и > 0 и * йаст(п - 1) Это — более точное определение факториала, чем предыдущее, поскольку оно ограничивает область фактических параметров, при которых она работает. Соответствие образцов при таком использовании, конечно, может нарушаться, поскольку образец параметра равен и при обоих значениях выражения. Этот вид определения функции называется условным выражением.
Зарезервированное слово от)зетндве может появляться в качестве последнего условия в условном выражении. Оно имеет очевидный смысл. Например: топ и ! и < 100 = 0 ) и > 100 = 2 ( оКЬекмз.ве = 1 Списки записываются в квадратных скобках, как показано ниже: со1огя = ['Ь1ие", "Огееп", "тес(", "уе11ои"] Язык НазЕей содержит набор операторов для работы со списками. Например. списки можно соединять с помощью оператора ++, оператор: служит в качестве иификсной версии функции СОНЯ, а оператор ..
используется для указания арифметических рядов. Например: 5:[2, 7, 9] дает результат [5, 2, 7, 9] [1, 3..11] дает результат [1, 3, 5, 7, 9, 11] [1, 3 ,5] ++ [2, 4, б] дает результат [1, 3, 5, 2, 4, б! Ниже приведены два примера функций, работающих со списками: зппп[] = 0 зов (а:х) = а + зим х ргос(иск [] = 1 ргобосс (а:х) = а * ргобосс х В обоих этих функциях выражение а: х означает список, в котором элемент а является первым, или головой, а х означает остальную часть, или хвост. Функция зим возвращает сумму элементов заданного списка. Функция ргобисс возвращает произведение элементов заданного списка. И функция воль и функция ргос(иск являются стандартными функциями языка Назкей.
Используя функцию ркос(иск, функцию, вычисляющую факториал, можно записать в более простом виде: йаст и = ргос(ост [1..п] Функция 1епОСИ возвращает число элементов в заданном списке. Например; 1еп9с)з(со1огз) возврашает 4 ] 4.8. Язык Наз[се[1 В языке НазкеП оператор нЬеге похож на операторы 1ек и згв1 в языке М[., за исключением того, что связывания указываются после выражений, которые их используют. Например, мы могли бы написать с)пас)гагзс гоог а Ь с = [тфпия Ь очег 2а — гоос рагс озгег 2а, вз1иця Ь обжег 2а + гоог рагс очег 2а] нЬеге т1пия Ь обжег 2а = -Ь / (2.0 * а) гоог рагс очег 2а = яс)гг(Ь " 2 — 4.0 * а ь с] / ( 2.0 " а) Полные списки обеспечивают метод описания списков, представляющих собой множества. Синтаксис полных списков аналогичен синтаксису, часто используемому для описания множеств в математике, общий вид которого приведен ниже: [тело 1 квалификаторы) Например, следующее выражение определяет список кубов чисел от 1 до 50: [и * и ~ и 1 и <- (1..50]) Это выражение читается как "список всех и*и*и, где п изменяется в диапазоне от 1 до 50".
В данном случае квалификатор имеет вид генератора (йепегазог). Он генерирует числа от 1 до 50. В других случаях квалификаторы принимают форму булевского выражения и называются проверками ()езгз). Эти обозначения можно использовать для описания записи алгоритмов, выполняющих такие действия, как поиск перестановок в списке и сортировка списка. Например, рассмотрим следующую функцию, которая для заданного числа и возвращает список всех его множителей: йастогя и = (' 1 з.
<- [1..и с[зч 2], п жос! 1 == О] Краткость языка Назке[1 иллюстрируется следующим примером реализации алгоритма быстрой сортировки: яогг (] = [] яогг (а:х) = яогг[Ь 1 Ь<-х, Ь< а] (а] ++ яогт(Ь)Ь<-х,Ь>а Это определение алгоритма быстрой сортировки значительно короче, чем тот же алгоритм. описанный на императивном языке. Вернемся к теме ленивых вычислений.
Напомним, что в языке Бс)зете параметры функции полностью вычисляются перед ее вызовом. Ленивые вычисления означают, что параметры функции вычисляются только тогда, когда это будет необходимо для вычисления функции. Таким образом, если функция имеет два параметра, но при конкретном выполнении функции первый параметр не используется, фактический параметр, переданный лля выполнения, не будет вычисляться.
Более того, если при выполнении функции должна вычисляться только определенная часть фактического параметра, остальная часть параметра вычисляться не будет. Итак, фактический параметр вычисляется только один раз, если вообще вычисляется. Использование в языке ленивых вычислений открывает некоторые интересные возможности.
Одна из них состоит в возможности определять бесконечные структуры данных. Рассмотрим следующий код: 60В Глава 14. Функцнональныв языки программирования ровдсдчея = (0..] ечепв = [2, 4...] вс(цагев = [и * п) и <- [О.. ] Конечно, ни один компьютер не может действительно представить все числа из этих списков, но это не мешает их использованию. если применяются ленивые вычисления. Например, чтобы узнать, является ли какое-либо число полным квадратом, следует проверить список квадратов с помощью функции, проверяюшей принадлежность элемента заданному спислу.
Допустим, что мы имеем предикатную функцию с именем п~епЬег, для того чтобы определить, солержит ли список данный атом. Тогда мы могли бы использовать ее следуюшим образом: мелчЬег вс(цаге 16 В результате мы получим булевское значение Тгце. Определение структуры вг(иагев вычислялось бы до тех пор. пока не было бы найдено число 16. Функция межЬег должна быть написана очень аккуратно. В частности. рассмотрим следлюший ее вид: мемЬег [) Ь = Га1яе тетЬег (а:х) Ь = (а = Ь) () иеиЬ г х Ь В этом случае оиа работает с квалратами чисел правильно. только если заданное число является полным квалратом.
В противном случае структура яс(негев продолжала бы генерировать числа бесконечно до тех пор, пока не исчерпала бы ресурсы памяти в поисках заданного числа в списке квадратов. Приведенная ниже функция выполняет проверку приналлежности заданного числа упорядоченному списку. прекрашая поиск и возвращая булевское значение Га1ве, если найдено число, больше чем заданное. телчЬег2 (лч: х) и м<п = мелчЬег2 х и в==и = Тгце ( оКЬегнаве = Га1яе Ленивые вычисления имеют свою цену. Было бы просто удивительно. если бы такая выразительная мошь и гибкость досталась бы бесплатно. В данном случае ценой стала сложная семантика, замедляюшая выполнение программы. 14.9. Применение функциональных взыков За последние 35 лет истории языков программирования высокого уровня лишь несколько функциональных языков получили широкое распространение. Наиболее известным нз них является язык Б!5Р.
Несмотря на неуклюжее использование операторов присваивания, язык АР[. также часто рассматривается как функционачьный язык, частично из-за наличия в нем функциональных форм. Язык АР(. широко использовался в различных приложениях — от описания аппаратного обеспечения до информационных систем управления предприятиями. Вследствие того, что читать программы, написанные на языке АР[.. обычно очень трудно, более естественным было бы отнести его в категорию одноразового программирования.
Благодаря наличию в нем мощного набора операций для работы с массивами, он представляет собой отличное средство лля получения быстрых, но 'сырых" решений проблем, связанных с большим количеством л~анипуляций с массивами, 14.9. Применение функциональных языков Язык ЫБР— многогранный и мощный язык. Первые 15 лет он считался странным и трудным для использования языком, в основном людьми, не применявшими его в своей работе.
Действительно, в 1960-х и начале 1970-х голов было принято думать, что языки программирования разделяются на две категории: к одной из них принадлежал язык ЫБР, а к другой — все остальные языки программирования. Как описано в этой главе, язык ЫБР был разработан для символьных вычислений и приложений, связанных с обработкой списков, относящихся в основном к области создания искусственного интеллекта. В приложениях, связанных с созданием искусственного интеллекта, язык ЫБР и производные от него языки программирования остаются стандартными языками.
В области создания искусственного интеллекта было разработано много направлений, в основном с применением языка ЫБР. Хотя можно использовать и другие виды языков (в, основном языки логического программирования), большинство существующих экспертных систем, например, были разработаны на языке ЫБР. Язык ЫБР также доминирует в областях, связанных с представлением знаний, машинным обучением, обработкой естественных языков, интеллектуальными обучающими системами, а также моделированием речи и зрения.
Язык ЫБР успешно применялся и вне области, связанной с созданием искусственного интеллекта. Например, текстовый редактор ЕМАСБ и символьная математическая система МАСБ г'МА, выполняющая, помимо всего прочего, символьные вычисления, написаны на языке ЫБР. ЫБР-машина — это персональный компьютер, системы которого полностью написаны на языке ЫБР.
Язык ЫБР также успешно использовался при разработке экспериментальных систем в различных прикладных областях. Язык Бенеше широко применяется для обучения функциональному программированию. Он также используется в некоторых университетах в рамках вводных курсов по программированию. Функционирование языков МЬ и НазкеП большей частью ограничивается исследовательскими лабораториями и университетами. 14. 10.