книги / Функциональное программирование
..pdf
2. Запишем выражение D = b*b – 4ac, используя базовые функции:
минус(умн(b, b), умн(4, умн(a, c)))
1.3. Аппликативная структура
Аппликация – применение функции к своим аргументам. Выражение состоит из двух частей:
операция эквивалентна функции;
операнд эквивалентен значению.
Структура вычисляется просто: операция применяется к своим операндам.
Аппликативный (строго функциональный язык – СФЯ).
Вэтом языке допустимы только строгие функции. Строгая функция получает исходные данные через аргументы и возвращает результат через имя.
Строго функциональный язык:
не допускает побочных эффектов (если функция меняет значения внешних переменных);
не содержит операторов присваивания;не содержит переменных со значением, изменяемым
присваиванием.
Переменная в функциональном языке совпадает с понятием переменной в математике: любая переменная что-то временно обозначает.
Встрого функциональном языке есть:
структурирование данных;
функционалы.
Символьные структуры строятся из атомов.
Символы языка «Лисп» могут состоять из букв, цифр и некоторых других знаков1, а именно:
1 Знак «тильда» (~), вопросительный и восклицательный знаки, квадратные скобки лучше не использовать, так как они могут быть применены для специального использования в функциональных языках. Но это совсем не означает, что их нельзя использовать.
11
+ -*/@ $ % &_ \ <> ~?!()
Числа в «Лиспе», как и логические символы t и nil, представляют самих себя, т.е. числовые и логические значения, и ничего более. Разделителем между символами является пробел.
Как и в других языках программирования, в «Лиспе» для различных целей используется много различных типов чисел. Примеры чисел:
123 – целое;
– 4.56 – дробное; 7.08Е9 – число с плавающей точкой.
Символом t в «Лиспе» обозначают логическое значение «истина», а nil – имеет логическое значение «ложь» или «пустой список». В некоторых языках функционального программирования наряду с nil используется специальный символ f (false). Символы t и nil нельзя использовать в качестве имен других объектов.
Числа и логические значения t и nil являются константами, остальные символы – переменными, которые используются для обозначения других лисповских объектов.
Языки функционального программирования поддерживают использование глобальных динамических переменных (global special / dynamic variable). Например, символ PI представляет зна-
чение числа π.
При этом в «Лиспе» при помощи функции DEFCONSTANT возможен перевод абсолютно любого символа в константу, а значит, ему будет соответствовать лишь то значение, которое ему определили.
Символы и числа представляют собой те простейшие объекты «Лиспа», из которых строятся остальные структуры. Поэтому их называют атомарными объектами или просто атомами. Позднее мы увидим, что в «Лиспе», как и в физике, можно при необходимости расщепить атом на элементарные составляющие.
12
1.4. Области применения языка Lisp
Области применения языка функционального программирования Lisp многогранны, до сегодняшнего дня еще точно не определены границы применения.
Вот лишь некоторые из них:
обработка естественного языка;
системы, синтезирующие (speech synthesis) и распознаю-
щие речь (speech recognition);
распознаватели ошибок написания, программы, разбивающие на слоги, распознаватели форм слова и другие применения, связанные с морфологией;
интерфейсы пользователя (human interface) информационных, экспертных и других систем обработки данных;
машинный перевод (machine translation);
автоматическая интерпретация или генерация документов;
обучение языку (language learning);
экспертные системы;
символьные и алгебраические вычисления;
доказательства и логическое программирование;
программирование игр;
моделирование;
обработка сигналов и распознавание образов;
машинное зрение и обработка изображений;
робототехника и автоматизация производства;
машинное проектирование;
языки и средства программирования искусственного интеллекта;
повышение производительности программирования;
автоматическое программирование и обучение.
На рис. 2 показано, как искусственный интеллект объединяет различные области науки.
13
Рис. 2. Взаимосвязь искусственного интеллекта
иразличных областей науки
1.5.Лямбда-исчисление А. Чёрча
Одним из основополагающих механизмов функционального программирования являются параметризованные вычисления в виде λ-выражений.
Придумал эти параметризованные вычисления Алонзо Чёрч в своем λ-исчислении. Языки функционального программирования лишь адаптировали эту теорию под себя в виде λ-выражений.
В λ-исчислении Чёрча функция записывается в следующем виде:
lambda (xl, x2,…, хn). fn.
В «Лиспе» лямбда-выражение имеет вид
(LAMBDA (xl х2 … хn) fn).
Служебное слово LAMBDA означает, что это некая параметризованная функция, где xi – формальные параметры для вычисления функции fn. Аргументы функции составляют так называемый λ-список.
14
Тело функции записывается в произвольной форме. LAMBDA-функцию можно легко вызвать в «Лиспе».
Например, построим λ-функцию нахождения суммы квадратов чисел:
(lambda (х у) (+ (* х х) (* у у))).
Обратиться можно так:
((lambda (x y) (+ (* x x) (* y y))) 2 3).
Результат: 13.
Константами здесь являются связанный со значением символ или набор из вызовов функций.
Аргументами λ-функции являются формальные параметры x и y, которые внутри тела λ-функции заменяются на другие параметры с тем условием, чтобы это не повлияло на вычисления записанных функций.
У λ-функции есть две структурные интерпретации – λ-выражение и λ-вызов. Применительно к примеру расчета суммы квадратов λ-выражение – это первое определение, а λ-вызов – второе.
λ-вызов инициирует процесс выполнения функции, превращая формальные параметры в фактические значения.
λ-выражение представляется в виде безымянной функции (вернее сказать, имя у функции будет LAMBDA) без фактических параметров:
(λ-выражение а1 а2 … an),
где ai – формы, задающие фактические параметры, которые вычисляются как обычно. В общем смысле в языках функционального программирования функции принято отождествлять с некой формой или шаблоном, поэтому в этой книге часто будет встречаться слово «форма», а не «стандартная функция».
Например, сложение двух чисел, 2 и 3, в режиме диалога «Лиспа» выглядит так:
15
>(+ 2 3) 5
в виде λ-вызова будет выглядеть так: >((lambda (x y)
(+ x y)) : λ-выражение
2 3) : аргументы
5: результат
Вычисление λ-вызова, или λ-преобразование
При λ-вызове или применении λ-выражения к фактическим параметрам сначала вычисляются значения фактических параметров, а соответствующие формальные параметры заменяются фактическими. Затем, учитывая новые связи, вычисляется форма, которая является телом λ-выражения. После окончания вычисления значение функции передается значению λ-вызова, а связи внутри тела λ-выражения возвращаются к начальным. Данный процесс называется λ-преобразованием.
С λ-вызовами можно проводить композицию с другими формами в любом порядке. Их можно ставить вместо аргументов функции, можно внутри тела функции, в том числе λ-функции.
Например, тело λ-выражения содержит вложенный λ- вызов:
>((lambda(y)
((lambda(x) (list y x))
'первый)) 'второй)
Результат вычисления λ-выражения выглядит так: (второй первый)
Следующий пример, когда λ-выражение является λ-вызов: >((lambda(x)
(list ‘ВТОРОЙ x)) ((lambda(y)
(list y)) ‘ПЕРВЫЙ))
16
Результат вычисления λ-выражения выглядит так: (ВТОРОЙ (ПЕРВЫЙ))
Стандартная функция list создает новый список из своих аргументов.
λ-выражение без аргументов представляет описание функции без возможности ее исполнения. Простыми словами, это функция, у которой не будет никакого значения.
Абстрагирование записи для параметризации вычислений с использованием переменных осуществляется посредством формального представления λ-выражений. Формальное представление λ-выражений служит для связывания формальных и фактических параметров во время исполнения.
λ-выражения представляются в виде безымянной функции. Это выражение работает один раз, и по причине отсутствия имени ее невозможно использовать повторно. Однако λ-функции имеют универсальный формат и хорошо зарекомендовали себя во многих механизмах функционального программирования. Например, при передаче функции в качестве аргумента другой функции, при формировании функции в результате вычислений и т.д.
1.6. Стандартные функции
Определить новую функцию можно при помощи меха-
низма DEFUN (define function – определить функцию):
(DEFUN имя лямбда-список тело).
Служебное слово DEFUN соединяет символ с λ-выраже- нием, и символ начинает представлять заданные вычисления. Значением этой формы является имя новой функции:
(defun listl (x у) ; определение функции
(cons x (cons у nil)))
LIST1
> (list1 ‘a ‘b) ; вызов функции
(АB) ; результат
17
Следующий пример: |
|
> (defun расчет(что-то) |
; определение функции |
(*(/ что-то) 100)) |
; определение % части |
РАСЧЕТ |
|
> (расчет 4 20) 20
В языках функционального программирования принята префиксная форма записи. Это сделано для того, чтобы привести к единой форме данные и действия, которые можно проводить с этими данными. Это покажется абсурдно и неудобно, но на самом деле такое впечатление со временем пройдет, зато даст массу возможностей, которых нет ни в одном традиционном языке программирования.
BOUNDP – это предикат проверки связанности с конкретным значением. Предикат – это «функция», значением которой может быть только «истина» или «ложь». Значение функции BOUNDP истинно тогда, когда ее аргумент имеет какое-нибудь значение.
Например,
>(boundp 'без_значения) NIL
>(boundp 'вычисленная_функция)
Т
>(boundp 5)
Т
Предикат FBOUNDP проверяет наличие определения объекта внутри исполняемой программы.
Например,
> (fboundp 'listl) ; listl описан как функция выше
Т
Функция SYMBOL-VALUE позволяет получить значение некоего символа.
18
Функция SYMBOL-FUNCTION в качестве результата возвращает определение функции, связанное с этим символом. Например,
> (symbol-function 'listl) ; listl описан как функция выше (LAMBDA (X Y) (CONS X (CONS Y NIL)))
Получив, например, в качестве результата тело функции, его можно исправить или переписать во время исполнения программы. В императивных языках программирования это сделать практически невозможно. При этом место, где находится тот или иной символ, имеет важное значение. Если символ, например, стоит первым в списке, то его можно рассматривать как имя функции и запустить на исполнение во время исполнения другой или этой же программы. Это делается возможным как раз по причине использования префиксной формы записи.
Например, (setq listl 'a)
А
> (list listl 'b) (А В)
Эта форма унификации определений данных и исполняемых функций является лишь малой частью возможностей функциональных языков программирования. В некоторых средах функционального программирования, таких как FranzLisp, тело функции хранится как значение памяти и им можно оперировать как данными и как функцией. В «Коммон Лиспе» эта возможность отсутствует. Значение символа в таких системах интерпретируется как определение функции лишь тогда, когда с символом не связано определение функции.
В некоторых системах функцию можно задавать произвольным вычислимым выражением. В таких случаях говорят, что функции – это «полноправные граждане».
19
1.7. Задание параметров в λ-списке
При определении функции можно применять ключевые слова и использовать одни и те же аргументы одних и тех же функций по разному функциональному предназначению. Можно применять необязательные параметры. Можно использовать параметр, связываемый с хвостом списка аргументов изменяющейся длины. Использование вспомогательных переменных функций позволяет рассчитать или присвоить значение сразу в аргументе функции. Через ключевые слова можно переопределить формальные параметры как фактические. Также имеется возможность присвоения значений по умолчанию.
Ключевые слова в λ-списке начинаются со специального символа «&». Действие ключевых слов происходит до следующего ключевого слова или до конца объявления формальных аргументов.
Наиболее часто встречаемыми ключевыми словами являются:
&OPTIONAL |
Необязательные параметры |
&REST |
Переменное количество параметров |
&KEY |
Ключевые параметры |
&AUX |
Вспомогательные переменные |
Если в описании функции встречается ключевое слово &OPTIONAL, например в середине назначения аргументов, то до этого слова все параметры обязательны к назначению внутри вызова функции, а следующие аргументы после ключевого слова &OPTIONAL указывать необязательно. В этом случае их значением является значение по умолчанию или NIL.
Для справки. Использование ключевых слов является спецификой «Коммон Лиспа», отличающей его от других популярных систем, например Интерлиспа. Очевидно, что это сделано с целью добиться большей вычислительной эффективности работы лисп-системы.
20