С самого начала Лисп был предназначен не для проведения операций с числами, а для работы с символами и списками.
В Лиспе для построения, разбора и анализа списков существуют очень простые базовые функции, которые в этом языке являются примитивами. В определённом смысле они образуют систему аксиом языка (алгебру обработки списков), к которым в конце концов сводятся символьные вычисления. Базовые функции обработки списков можно сравнить с основными действиями в арифметических вычислениях или в теории чисел.
Простота базовых функций и их малое число - это характерные черты Лиспа. С этим связана математическая элегантность языка. Разумно выбранные примитивы образуют, кроме красивого формализма, также и практическую основу программирования.
Базовыми функциями обработки символьных выражений (атомов и списков) являются:
first, rest, cons, atom и eq
Функции по принципу их использования можно разделить на функции разбора, создания и проверки:
| ИСПОЛЬЗОВАНИЕ | ВЫЗОВ | РЕЗУЛЬТАТ |
|---|---|---|
| Разбор: | (список first) | s-выражение |
| (список rest) | список | |
| Создание: | (nil cons first rest) | список |
| Проверка: | (nil atom obj) | true или false |
| (nil eq x y) | true или false |
У функции cons и eq имеются два аргумента, у остальных примитивов - по одному. В качестве имён аргументов и результатов функций использовано названия типов, описывающих аргументы, на которых определена (т.е. имеет смысл) функция и вид возвращаемого функциями результата. S-выражение обозначает атом или список.
Функции atom и eq являются базовыми предикатами. Предикаты - это функции, которые проверяют выполнение некоторого условия и возвращают в качестве результата false в смысле логического отрицания, или другой объект в положительном смысле.
Первый элемент списка называется головой, а остаток списка, т.е. список без первого его элемента, называется хвостом списка. С помощью селекторов first и rest можно выделить из списка его голову и хвост.
Функция first возвращает в качестве значения первый элемент списка, т.е. головной элемент списка.
('(первый второй третий) first) → первый ; внимание, используется '
Обратите внимание на то, что не вычисляется значение аргумента (первый второй третий) и не применяется к нему операция first, а используется аргумент в таком виде, как он есть. Ситуация отличается, например, от следующего функционального вызова:
>(4 * (3 + 2))
20
где нужно умножить 4 на значение аргумента (3 + 2), т.е. на 5, а не на список (3 + 2). Вызов функции first с аргументом (первый второй третий) без апострофа был бы интерпретирован как вызов функции второй с аргументом третий, и была бы получена ошибка.
Функция first имеет смысл только для аргументов, являющихся списками, а следовательно, имеющих голову:
first: список → s-выражение
Для аргумента атома результат функции first не определён, и вследствие этого результат будет nil. Головной частью пустого списка считают для удобства nil.
(nil first) → nil ; голова пустого списка - пустой список
('nil first) → nil ; знак ' можно опускать
('(nil a) first) → nil ; голова списка nil
Функция rest применима к спискам. Значением её будет хвостовая часть, т.е. список, получаемый из исходного списка без головного элемента.
rest: список → список
('(a b c) rest) → (b c)
('(a (b c)) rest) → ((b c))
Функция rest не выделяет второй элемент списка, а берёт весь остаток списка, т.е. хвост. Если список состоит из одного элемента, хвостом будет пустой список (), т.е. nil.
('(a) rest) → nil
Из соображений удобства значением функции rest от пустого списка считается nil:
(nil rest) → nil
('(1 2 3 4) first) → 1
(('(1 2 3 4) rest) first) → 2
(('(1 2 3 4) rest) rest) → (3 4)
('('(1 2 3 4) rest) rest) → (rest)
Для того чтобы можно было включить первый аргумент функции cons в качестве первого элемента значения второго аргумента этой функции, второй аргумент должен быть списком. Значением функции cons всегда будет список.
cons: s-выражение × список → список
Селекторы first и rest являются обратными для конструктора cons. Список, разбитый с помощью функций first и rest на голову и хвост, можно восстановить с помощью функции cons.
| ('(a b c) first) | → a | |
| cons → (a b c) | ||
| ('(a b c) rest) | → (b c) |
Чтобы осуществлять допустимые действия со списками и избежать ошибочных ситуаций, нам необходимы, кроме конструирующих функций, средства опознавания выражений. Функции, решающие эту задачу, в Лиспе называются предикатами.
Предикат - это функция, которая определяет, обладает ли аргумент определенным свойством и возвращает в качестве значения логическое значение "ложь", т.е. false, либо "истина", которое может быть представлено символом true или любым выражением, отличным от false.
atom и eq являются базовыми предикатами Лиспа. С их помощью и используя другие базовые функции, можно задать более сложные предикаты, которые будут проверять наличие более сложных свойств.
Несмотря на то что обычную обработку списков всегда можно свести к описанным ранее трём базовым функциям (cons, first и rest) и двум базовым предикатам (atom и eq), программирование лишь с их использованием было бы очень примитивным и похожим на программирование на внутреннем машинном языке. Поэтому в Лисп-систему включено множество встроенных функций для различных действий и различных ситуаций.