ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6830
Скачиваний: 51
356
результат - решение задачи.
Программы строятся из логически расчлененных определений функций. Определения со-
стоят из управляющих структур, организующих вычисления, и из вложенных вызовов функций.
Основными методами функционального программирования являются композиция и рекурсия. Все
это представляет собой реализацию идей теории рекурсивных функций.
Имеется большое число систем программирования на Лиспе, реализованных для компью-
теров различных типов. Как правило, это интерпретирующие системы, работающие в интерактив-
ном (диалоговом) режиме. Соответствующие описания и команды вводятся с клавиатуры после
приглашения ("_"), затем прочитывается результат.
8.2. ОСНОВНЫЕ ЭЛЕМЕНТЫ ПРОГРАММЫ НА ЛИСПЕ. СПИСКИ
Программы на языке Лисп строятся из простейших неделимых элементов, называемых
атомами. Символы и числа представляют собой атомы, из них состоят все остальные структуры.
Символ
- это имя, состоящее из букв, цифр и специальных знаков, которое обозначает ка-
кой-нибудь предмет или действие из реального мира, а также число, функцию (программу) и дру-
гие объекты. Наряду с символами используются и числа (значения), которые могут быть целыми
(например, 543), десятичными (например, 3.789) и в представлении с мантиссой и порядком (на-
пример, 1.0243Е-6).
Главной структурой в Лиспе является список.
Списком
называется упорядоченная последовательность, элементами
которой
являются
либо атомы, либо списки (подсписки). Списки заключаются в круглые списки, а
их элементы раз-
деляются пробелами. Например,
(ab(cd)e)
(В группе 18 студентов)
(((((первый) 2) третий) 4) 5).
Список, в котором нет ни одного элемента, называется пустым списком и обозначается "( )"
или специальным символом NIL. Список - это структура данных, представляющая некоторую ие-
рархическую связь (дерево) с помощью строго соответствующих друг другу открывающих и за-
крывающих скобок.
Имеется и альтернативный способ записи списков - с использованием, так называемой, то-
чечной нотации. Точка при этом отделяет начальный элемент списка -его голову - от остальной
части списка - хвоста: (голова, хвост) или
(а1 а2 ... aN) = (а1. (а2.... (aN.Nil)...)).
Здесь Nil - это предопределенная константа, означающая пустой список (и одновременно
логическое значение «Ложь»).
Атомы и списки называются
S-выражениями
. Все вышесказанное можно обобщить в сле-
дующих формах Бэкуса - Наура
<S-выражение>
:: = <атом> | <список>
<список>
:: = (<внутренняя часть>)
<внутренняя часть>
:: = NIL | <S-выражение> [{внутренняя часть}}
<атом>
:: = цепочка алфавитно-цифровых символов без пробелов
или специальных символов (,);.
Списки в Лиспе - основное средство представления знаний. Например,
с помощью вложен-
ных списков может быть представлена характеристика человека:
(
сотрудник
(имя Петр)
(отчество Петрович )
(фамилия Иванов)
( образование ( среднее (с 1969 по 1979))
(высшее ( ВГУ г.Воронеж (с 1979 по 1982)
(МГУ г. Москва (с 1982 по 1984)) ( специальность
357
(техническая кибернетика)
(программирование
)
(стаж (с 1984 по 1997)
)
8.3. ФУНКЦИИ
Функции в Лиспе аналогично математическим функциям ставят в соответствие элементам
из одного множества - определения (аргументов) - единственный элемент из множества значений.
В программах следует различать определение функций и вызов (применение) функции.
В языке Лисп принята единообразная префиксная форма записи, при которой как имя
функции или действия, так и аргументы записываются внутри скобок:
(f x)
(g x y) (сумма_квадратов 2 3).
Аналогично записываются и арифметические действия:
(+ х у)
(*x(+yz))
(+ (^ х х) (
+
у у)).
Определение функций и их вычисление в Лиспе основано на
лямбда-исчислении Черча
. В
1-исчислении Черча функция записывается в виде
1(х1,х2,... ,xn) .fn
В Лиспе 1-выражение имеет вид (LAMBDA (xl, x2,..., xn).fn).
Символ LAMBDA означает, что мы имеем дело с определением функции. Символы xi яв-
ляются формальными параметрами, они образуют список, называемый лямбда-списком; fn - это
тело функции, которая может иметь произвольную форму, допускаемую интерпретатором Лиспа.
Телом функции может быть, например, константа или композиция из вызовов функций. Функцию,
вычисляющую сумму квадратов двух чисел, можно, например, определить так:
(lambda(xy)(+(*xx)(*yy))).
Лямбда-выражение
- это безымянная функция, которая может быть использована для свя-
зывания формальных и фактических параметров на время вычислений. Вызов такой функции про-
исходит по форме
(лямбда-выражение а1 а2 ... an)
Здесь ai - фактические параметры, с которыми происходит вычисление.
Например
((lambda (х у) (+ (* х х) (* у у))) 3 4).
Результат: 25.
Определить новую функцию и дать ей имя для последующих вызовов можно с помощью
функции DEFUN (define function):
(DEFUN имя лямбда-список тело).
DEFUN соединяет символ с лямбда-выражением, и символ начинает представлять (имено-
вать) определенные этим лямбда-выражением вычисления. Значением этой формы является имя
358
новой функции:
(defun sumsquare (х у) (+ (* х х) (* у у))) .
Результат: sumsquare.
Вызов (применение) этой функции:
(sumsquare 34)
Результат: 25.
Определение функции задается списком, поэтому его можно модифицировать в ходе вы-
полнения программы. Кроме того, некоторый символ может быть и именем функции и перемен-
ной.
В Лиспе передача параметров происходит по значению. Формальные параметры функций
являются статическими и локальными, т.е. действительны только внутри той формы, в которой
они определены.
Основу для построения различных функций образует набор небольшого числа примитив-
ных встроенных функций. Базовыми функциями обработки S-выражений являются функции
CAR, CDR, CONS, ATOM, EQ, EQL, =
и другие, смысл которых отражен в табл. 3.7.
Таблица 3.7
Базовые функции обработки S-выражений
Функ-
ция
Вызов
Действие
Пример использования
CAR
(CAR спи-
сок)
Возвращает головною часть
(CAR(1 234))
списка - его 1-й элемент
Результат:1
CDR
(CDR спи-
сок)
Возвращает хвостовую часть
(CDR(! 234))
списка- все. кроме 1-го элемента
Результат:(2 3 4)
CONS
(CONS S-
выра-
Строит список из переданных в
(CONS I (2 3 4))
жение спи-
сок)
качестве аргументов головы и
хвоста
Результат: (1234)
ATOM
(ATOMS-
выра-
Предикат; проверяет, является ли
(ATOM A) : t
жение)
аргумент атомом, и возвращает
либо t
(ATOM (1 2 3)): Nil
(истина), либо Nil или ("(ложь)
EQ
(EQ символ
Предикат: проверяет тождест-
венность
(EQ A A): t
символ)
символов-аргументов, неприме-
ним
(EQ X (CAR (X Y Z))): t
для чисел
EQL
(EQL число
Предикат, проверяет тождест-
венность
(EQL 3.0 3.0): t
число)
чисел одного типа
=
(= число
Предикат, проверяет тождест-
венность
число)
чисел различных типов
(=30.3el):t
EQUA
L
(EQUAL
число
Аналогична EQL,
(EQUAL(xyz)(xyz)):t
или список
но, кроме того, проверяет иден-
тичность
число или
список)
Списков
EQUA
LP
(EQUALP
Проверка наиболее общего ра-
венства
объект объ-
ект)
NULL
(NULL спи-
сок)
Проверка, является ли аргумент
пустым списком
NOT
(NOT логи-
ческая
Логическое отрицание
величина)
NTH
(NTH n спи-
сок)
Выделение n-го элемента списка
(NTH 2 (1 2 3)): 3
(индексы начинаются с 0)
FIRST
Предикаты, выделяющие
SE-
COND
Соответствующие элементы спи-
ска
LAST
359
LIST
(LIST apr
Строит из аргументов список
(LIST a b (с)): (a b c)
арг2 ...)
Отметим, что в программах на Лиспе надо тщательно отличать значения от их обозначений.
В Лиспе константы обозначают самих себя. Выражения типа (* 2 2) сразу вычисляются.
Чтобы избежать нежелательного вычисления выражения используется функция QUOTE или знак
апострофа (') перед выражением:
(* 2 2) : 4
' (* 2 2) :' (* 2 2) – список
Произвольный символ можно использовать как переменную, и он может обозначать произ-
вольное выражение. При первом использовании символу должно быть присвоено или с ним связа-
но некоторое значение с помощью функции SET, например,
(SET 'операции
'
(+ - *
/))
Знак ' используется для подавления вычисления аргументов функции SET. Функция SETQ
не вычисляет значения 1-го аргумента (а 2-го вычисляет).
На значение символа можно сослаться, указав его без апострофа (').
Для занесения значений в ячейку памяти, связанной с символом, можно пользоваться
обобщенной функцией присваивания SETF, размещающей значения в соответствующей ячейке
памяти:
(SETF ячейка_памяти значение).
Переменная «ячейка_памяти» без апострофа указывает на ячейку памяти. Присвоение, вы-
полняемое функциям» SET, SETQ и SETF, является побочным эффектом , этих функций, помимо
того, данные функции возвращают присваиваемые значения.
8.4. ФОРМЫ. УПРАВЛЯЮЩИЕ КОНСТРУКЦИИ В ЛИСП-ПРОГРАММЕ
Программа состоит не только из функций, но и из форм. Простейшими формами являются
константы, переменные, лямбда-вызовы, вызовы функций.
Остановимся более подробно на специальных формах, предназначенных для управления
обработкой программы и контекстом. У каждой формы определенный синтаксис и семантика, ос-
нованные на едином способе записи и интерпретации.
Управляющие предложения Лиспа внешне выглядят как вызовы функций - в виде скобоч-
ных выражений, первый элемент которых действует как имя управляющей структуры, а остальные
элементы - как аргументы. Наиболее важные формы можно разделить на следующие группы:
работа с контекстом
• QUOTE или блокировка вычисления,
• вызов функции и лямбда-вызов,
• предложения LET и LET*;
последовательное исполнение
• предложения PROG1, PROG2 и PROGN;
разветвление исполнения
• условные предложения COND, IF, WHEN, UNLESS,
• выбирающее предложение CASE;
итерации
•
циклические предложения DO, DO*, LOOP, DOTIMES, DOUNTIL;
передачи управления
• предложения PROG, GO и RETURN;
динамическое управление вычислением
360
•
THROW, CATCH, а также BLOCK.
Эти управляющие формы (кроме QUOTE и лямбда-вызова, а также вызовов функций), в
основном, используются в теле лямбда-выражений, определяющих функции.
Предложение LET используется для создания связи переменных внутри формы:
(LET ((пep1 знач1) (пер2 знач2)...) форма1 форма2 ...).
При вычислении этого выражения статические переменные пep1, пер2, ... связываются (од-
новременно) с соответствующими значениями знач1, знач2, ..., а затем вычисляются значения
форм форма1, форма2, ... Значение последней формы возвращается как общий результат. Форма
LET* отличается от LET лишь тем, что связывание переменных и вычисление форм происходит не
одновременно, а последовательно, вначале 1-е, потом 2-е и т.д.
Например:
(let*((x2)(y(*3x)))
(list x у)
Результат: (2 6).
Предложения PROG1, PROG2 и PROGN позволяют организовывать последовательные вы-
числения из нескольких вычисляемых форм:
(PROG1 форма1 форма2 ... формаn)
(PROG2 форма1 форма2 .. формаn)
(PROGN форма1 форма2 . формаn).
Различие этих форм лишь в возвращаемых ими в качестве общего значения результатах.
Форма PROG1 возвращает значение формы1, PROG2-формы2, PROGN -последней формы n.
Например:
(progn (setq x 2) (setq у (* 3 х)))
Результат: 6.
Предложение COND является основным средством разветвления обработки. Структура ус-
ловного предложения такова:
(COND (р1 а1) (р2 а2)... (pn an)).
pi - это предикаты (выражения-условия, которые могут быть либо истинными (Т), либо
ложными (NIL)). Их значения вычисляются слева направо, пока не будет получено значение «ис-
тина» (Т), затем вычисляется и возвращается в качестве результата результирующее выражение ai.
соответствующее 1-му истинному предикату pi. Если истинного предиката нет. то значение COND
- NIL. Форма ai для соответствующего предиката может отсутствовать (тогда возвращается значе-
ние этого предиката в случае его истинности), или, наоборот, может быть задана последователь-
ность форм для предиката pi - тогда эти формы вычисляются последовательно и возвращается
значение последней.
В следующем примере с помощью предложения COND определена функция, устанавли-
вающая тип выражения:
(defun тип (1)
(cond ((null 1) 'пусто)
((atom 1) 'атом)
(t 'список)))
Результат: ТИП.
Примеры применения этой функции: