Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 151
Текст из файла (страница 151)
Эю связывание имен указывалось в списке, состояшем иэ имени функции и списка, содержащего лямбда-выражение, как показано ниже: Глава 14. Функциональные языки программирования (имя функции(еА(чй11А(аргумент 1 ... аргумент и) выражение)) Если бы мы не имели никаких предварительных представлений о функциональном программировании, странно было бы даже рассматривать безымянные функции.
Однако безымянные функции в функциональном программировании (так же, как и в математике) иногда бывают полезными. Например, рассмотрим некую функцию, действие которой заключается в вырабатывании функции, немедленно применяющейся к списку параметров.
Для полученной в результате функции не требуется имени, чтобы применить ее только в той точке, где она была построена. Такой пример приведен в разделе 14.5.6. Функции языка Е!БР, представленные в таких обозначениях, вызывались с помощью Б-выражений, представляющих собой форму записи символьных выражений. В итоге все структуры языка !.!БР, и данные, и код, стали называться Б-выражениями. Б-выражение может быть либо списком, либо атомом. Мы будем часто называть Б-выражение просто выражением.
Мак-Карти успешно разработал универсальную функцию, способную вычислять любую другую функцию. Эта функция получила название ЕЧАЕ и сама имела внд выражения. Два сотрудника, привлеченных к реализации проекта по созланию искусственного интеллекта, Стефен Рассел (Б!ерйеп В. Ваьзе() н Дэниэл Эдвардс (Пап!е1 3.
Еджагбз), заметили, что реализация функции ЕЧАЬ могла бы служить в качестве интерпретатора, н немедленно создали такую реализацию (МсСапЬу е! а(., 1965). Скорость, легкость и неожиданность этой реализации привели к нескольким важным результатам. Во-первых, все ранние ! !БР-системы копировали функцию ЧАЕ.
и таким образом, были интерпретируюшими системами. Во-вторых, определение М-обозначений, которые планировалось использовать для записи программ на языке ЫБР. никогда не было завершено или реализовано, так что Б-выражения стали единственной системой обозначений в языке Е!БР. Применение одной и той же системы обозначений лля данных и кода программы имеет важные последствия, одно из которых булет обсуждаться в разделе 14.5.7.
В-третьих, многие свойства первоначальной разработки языка были успешно сохранены, включая и такие необычные свойства языка, как внд условного выражения, а также использование нуля для обозначения как нулевого адреса, так и логического значения "ложь". Другая особенность ранних Е!БР-систем, которая несомненно носит случайный характер, состоит в использовании динамического обзора данных. Функции вычислялись в тех программах, которые их вызывали. В то время об областях видимости данных было известно довольно мало, поэтому вряд ли при выборе способа обзора ланных разработчики долго размышляли. Динамический обзор данных использовался в большинстве диалектов языка ! !БР до 1975 года. Современные диалекты либо используют статический обзор данных, либо позволяют программисту делать выбор между статическим и динамическим обзором данных.
!4.5. Введение в язык Эстете В этом разделе описана часть языка БсЬеше (ОуЬч!я. 1996). Мы выбрали язык Бсйеше, потому что он относительно прост, популярен в колледжах и университетах, а интерпретаторы языка БсЬеве легкодоступны для любого типа компьютеров. В этом разделе описываются версии языка БсЬеше под названием Бсйеше 4. 14.5. Владение в язык БсЬеше 14.5.1. Пронской(гдение языка ЗсЬеязв Язык Бс)гегпе, являющийся диалектом языка !.!БР, появился в Массачусетском технологическом институте в середине 1970-х годов (Бингпап апг( 5(ее!е, 1975). Он невелик, использует исключительно статический обзор данных и обрабатывает функции как сущности первого класса (Вгм-с!азз епбйез). В качестве сущностей первого класса функции в языке Бс)геше могут быть значениями выражений и элементами списков, а также могут присваиваться переменным и передаваться как параметры. Ранние версии языка Е!БР не имели всех этих возможностей.
Будучи небольшим языком с простыми синтаксисом и семантикой, язык Бсйегле хорошо подходит для сферы образования, например, изучения функционального программирования, а также для общего ввеления в программирование. Заметим, что большинство функций на языке Бс)геше, приведенные в следующем разделе, могут потребовать лишь небольших изменений для того, чтобы переписать их в виде функций на языке 1!БР. 14.$.2. Элементарные функции Имена в языке Бс)геше могут состоять из букв, цифр и специальных символов, эа исключением скобок; они не зависят от регистра клавиатуры, но не должны начинаться с цифры. Интерпретатор языка Бс)гегпе представляет собой бесконечный цикл типа прочитать- вычислить-записать. Он непрерывно читает выражение, напечатанное пользователем (в виде списка), интерпретирует его и отображает результат.
Литералы вычисляют литералы. Таким образом, если вы ввели в интерпретатор число, то он просто отобразит его. Выражения, которые вызывают элементарные функции, вычисляются следующим образом: сначала вычисляется каждый из параметров выражения независимо от порядка их слелования. Затем элементарная функция применяется к значениям параметров, и отображается результат.
Язык Бс)геше содержит элементарные функции для выполнения основных арифметических операций. К ним относятся +, —, * и / для сложения, вычитания, умножения и деления. Функции * н + могут иметь несколько параметров, но могут и совсем не иметь их. Если ф> нкция * зш(ана без параметров, она возвращает 1; если функция + задана без параметров, она возвращает О. Функция + складывает все свои параметры вместе. Функции l и - могут иметь несколько параметров. При вычитании все параметры, кроме первого, вычитаются нз первого.
Деление похоже на вычитание. Примеры приведены ниже: ЕХРАЕЯЕ10(4 ЧАЛОЕ 42 42 (* 3 7) 21 (+ 5 7 8) 20 (-5 б) -1 (-15 7 2) б (-24 (* 4 3) ) 12 Функция 5ОЕт возвращает Квадратный кОрЕнь иэ ЧИслоВОго Параметра, есЛи значение параметра неотрицательно. Следующая элементарная конструкция языка 5с)зете, которую мы опишем,— зто служебная функция, необходимая в силу самой природы операции ЕЧАЬ применения ЗВЗ Глава 14.
Функциональныв языки программирования функций языка Бсйеше. Функция ЕЧАЕ является основой вычисления всех функций в языке Бсйеше, независимо от того, элементарная это функция или нет. Она вызывается для обработки вычислительной части лействия прочитать-вычислить-записать. выполняемого интерпретатором языка Бсйегле. При применении к элементарной функции функция ЕЧАЬ сначала вычисляет параметры заданной функции. Это необходимо.
если действительные параметры в вызове функции сами представляют собой вызовы других функций, что случается довольно часто. В некоторых вызовах, однако, параметрами являются данные, либо атомы, либо списки, а не ссылки на функции. В этих случаях параметры, очевидно, не лолжны вычисляться. Допустим, что мы имеем функцию, имеющую два параметра — атом и список, — лля определения, принадлежит ли заданный атом заданному списку. Ни атом, ни список не должны вычисляться.
Для того чтобы избежать вычисления параметра, он сначала передается как параметр элементарной функции ОООТЕ, которая просто возврашает его без изменения. Функция ОООТЕ иллюстрируется следуюшими примерами: (РВОТЕ А) возвращает А (ОРОТЕ (А В С)) возвращает (А В С)] В оставшейся части этой главы мы будем использовать обычное сокрашение для обозначения вызова функции ЯРО Е, которое заключается в прос~ом приписывании перед выражением символа апострофа (').
Таким образом, вместо (ОРОТЕ (А В) ) мы будем использовать обозначение ' (А В). Компьютерные программы манипулируют данными независимо от того, является ли язык, на котором они написаны. императивным или функциональным. Поскольку списки представляют собой основные структуры данных в языке Бсйеше, этот язык должен иметь элементарные конструкции для обработки списков. В частности, он должен обеспечивать операцию для выбора частеЯ списка, которая в некотором смысле разбирает список на составные части, и хотя бы одну операцию для создания списков. Поскольку основные операции в функциональных языках выполняются с помощью функций, в языке Бенеше предусмотрены элементарные функции лля этих операциЯ. Сушествуют две элементарные функции выбора элементов из списков в языке Бсйеше: САВ и СРВ (произносится как "куд-ер" ("соц!д-ег")).
Функция САВ возврашает первый элемент заданного списка. Она иллюстрируется следующими примерами. (САВ ' (А В С) ) возвращает А (САВ ' ( (А В) С Р) ) возвращает (А В) (САА 'А) — ошибка (А не является списком) (САВ '(А)) возвращает А (САВ '()) — ошибка Функция СРВ возврашает остаток заданного списка, полученного после удаления его первого элемента: (СРВ '(А В С)) возвращает (В С) (СРВ '((А В) С Р)] возвращает (С Р) (СРВ 'А) — ошибка (СРВ '(А)] возвращает () Имена функций САВ и СРВ являются, мягко говоря, необычными.
Происхождение этих имен восходит к первой реализации языка ).(БР на компьютере )ВМ 704. Память этого компьютера имела два поля, которые назывались декрементом н адресом и исполь- 14.5. Введение в язык БсЬепзе $89 зовались для реализации различных стратегий адресации операндов. Каждое из этих полей могло хранить адрес машинной памяти.
Компьютер 1ВМ 704 также имел две машинные инструкции, называвшиеся сАА (соп(еп( оГ аг]бгезз гей(згег — содержимое регистра адреса) и сОА (соп(епгз оГ с)есгешеп( геецпег — содержимое регистра декремента), которые извлекали солержимое соответствующих полей. Было естественно использовать эти поля лля хранения двух указателей на узел списка так, чтобы машинное слово точно хранило один узел. На основании этих соглашений инструкции САА и СОВ компьютера 1ВМ 704 обеспечивали эффективный выбор элементов из списков.
Эти имена впоследствии были перенесены во все диалекты языка ].(ЯР. Функция СО]ЧЯ вЂ” элементарный конструктор списка. Она создает список по двум своим аргументам, первый из которых может быть либо атомом, либо списком; второй обычно является списком. Эта функция вставляет свой первый параметр в качестве первого элемента своего второго параметра. Рассмотрим следующие примеры: (СО]ЧЯ 'А ' (] ) возвращает (А) (СО]ЧЯ 'А ' (В С) ) возвращает (А В С) (СО(ЧЯ ' () ' (А В) ) возвращает (() А В) (СО]ЧЯ ' (А В) ' (С О) ) возвращает ( (А В) С О) Результаты этих операций СОНЯ показаны на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
