Базовые функции

  С самого начала Лисп был предназначен не для проведения операций с числами, а для работы с символами и списками.

Основные функции обработки списков

  В Лиспе для построения, разбора и анализа списков существуют очень простые базовые функции, которые в этом языке являются примитивами. В определённом смысле они образуют систему аксиом языка (алгебру обработки списков), к которым в конце концов сводятся символьные вычисления. Базовые функции обработки списков можно сравнить с основными действиями в арифметических вычислениях или в теории чисел.
  Простота базовых функций и их малое число - это характерные черты Лиспа. С этим связана математическая элегантность языка. Разумно выбранные примитивы образуют, кроме красивого формализма, также и практическую основу программирования.
  Базовыми функциями обработки символьных выражений (атомов и списков) являются:

  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 возвращает в качестве значения головную часть списка

  Первый элемент списка называется головой, а остаток списка, т.е. список без первого его элемента, называется хвостом списка. С помощью селекторов 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 применима к спискам. Значением её будет хвостовая часть, т.е. список, получаемый из исходного списка без головного элемента.

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 строит новый список из переданных ей в качестве аргументов головы и хвоста.
(nil cons голова хвост)(голова . хвост)
  Функция добавляет новое выражение в список в качестве первого элемента:
(nil cons 'a '(b c)) → (a b c)
(nil cons '(a b) '(c d)) → ((a b) c d)
(nil cons (1 + 2) '(+ 4)) → (3 + 4) ; первый аргумент без апострофа, поэтому он вычисляется
(nil cons '(1 + 2) '(+ 4)) → ((1 + 2) + 4) ; с апострофом
  Нужно аккуратно пользоваться данной функцией, не забывая что первый аргумент будет первым элементом списка.
(nil cons '(a b c) nil) → ((a b c))
(nil cons nil '(a b c)) → (nil a b c)
(nil cons nil nil) → (nil)

  Для того чтобы можно было включить первый аргумент функции cons в качестве первого элемента значения второго аргумента этой функции, второй аргумент должен быть списком. Значением функции cons всегда будет список.

cons: s-выражение × список → список

Связь между функциями FIRST, REST и CONS

  Селекторы 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 являются базовыми предикатами Лиспа. С их помощью и используя другие базовые функции, можно задать более сложные предикаты, которые будут проверять наличие более сложных свойств.

Предикат ATOM проверяет, является ли аргумент атомом

  При работе с выражениями необходимо иметь возможность проверить, является ли выражение атомом или списком. Это может потребоваться, например, перед применением функции first и rest, так как эти функции определены лишь для аргументов, являющихся списками. Базовый предикат atom используется для идентификации лисповских объектов, являющихся атомами:
(nil atom 'x) → x - символ это атом
(nil atom '(a b c)) → false
(nil atom ('(a b c) rest)) → false
  С помощью предиката atom можно убедиться, что пустой список nil, или (), является атомом:
(nil atom nil) → true
(nil atom ()) → true - то же самое, что и nil
(nil atom '()) → true - пустой список с апострофом всё равно есть nil
(nil atom '(nil)) → false - аргумент - одноэлементный список
  В Лиспе существует целый набор предикатов, проверяющих тип являющегося аргументом выражения или любого другого лисповского объекта и таким образом идентифицирующих используемый тип данных. Например, listp идентифицирует списки, vectorp - вектора и т.д.

EQ проверяет тождественность двух символов

  Предикат eq можно применять к списочным и числовым аргументам, не получая сообщения об ошибке; он не проверяет логического равенства чисел, строк или других объектов, а лишь смотрит, представлены ли лисповские объекты в памяти вычислительной машины физически одной и той же структурой. Одноимённые символы представлены в одном и том же месте памяти, так что той же проверкой предикатом eq символы можно сравнить логически.
(nil eq 'x 'cat) → false
(nil eq 'cat ('(cat dog) first)) → cat
(nil eq () nil) → true
(nil eq true 'true) → true
(nil eq 'my (nil atom 'my)) → my
(nil eq '(a b c) '(a b c)) → false
(nil eq 3.14 3.14) → false

Предикат = сравнивает числа

  Сложности, возникающие при сравнении чисел, легко преодолимы с помощью предиката =, значением которого является данный объект в случае равенства аргумента.
(3 = 3.0) → 3
(3.00 = 0.3e1) → 3
  Обеспечить применение к числовым аргументам может предикат numberp, который истинен для чисел:
(nil numberp 3e-34) → 3e-34
(nil numberp true) → false

Другие примитивы

  Несмотря на то что обычную обработку списков всегда можно свести к описанным ранее трём базовым функциям (cons, first и rest) и двум базовым предикатам (atom и eq), программирование лишь с их использованием было бы очень примитивным и похожим на программирование на внутреннем машинном языке. Поэтому в Лисп-систему включено множество встроенных функций для различных действий и различных ситуаций.

NIL = проверяет на пустой список

  Встроенный метод = для объекта nil проверяет, является ли аргумент пустым списком:
(nil = '()) → true
(nil = (('(a b c) rest) rest)) → false
(nil = nil) → true
(nil = false) → false
(nil = true) → false
  Есть также похожая логическая функция not:
(nil not nil) → nil
(nil not false) → true - не такой смысл как у функции =
(nil not true) → false

Вложенные вызовы FIRST и REST можно записывать в сокращённом виде

  Для взятия значения элементов списка используется и более наглядные имена second и third.
('(a b c) second) → b
('(a b c) third) → c
((('(a b c) rest) rest) first) → c
  Последний элемент списка можно выделить с помощью функции last:
('(1 2 3) last) → (3)
('(1 2 3 . 4) last) → (3 . 4)

LIST создаёт список из элементов

  Другой часто используемой встроенной функцией является
(nil list x1 x2 x3)
которая возвращает в качестве своего значения список из значений аргументов. Количество аргументов функции list произвольно:
(nil list 1 2) → (1 2)
(nil list 'a 'b (1 + 2)) → (a b 3)
(nil list 'a '(b c) 'd) → (a (b c) d)
(nil list (nil list 'a) 'b nil) → ((a) b nil)
(nil list nil) → (nil)
  Построение списков нетрудно свести к вложенным вызовам функции cons, причём вторым аргументом последнего вызова является nil, служащий основой для наращивания списка:
(nil cons 'c nil) ≡ (nil list 'c) → (c)
(nil cons 'b (nil cons 'c nil)) ≡ (nil list 'b 'c) → (b c)
(nil cons 'a (nil cons 'b (nil cons 'c nil))) ≡ (nil list 'a 'b 'c) → (a b c)