Вопрос 16) Базовые функции и предикаты. (Lisp)

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

1. 􀂃Функции-селекторы Car и Cdr;

2. 􀂃Функцию-конструктор Cons;

3. 􀂃Предикаты Atom, Eq, Equal.

Селектором – называется функция, осуществляющая выборку элемента объекта данных.

Функция Car возвращает в качестве значения голову списка :

Функция Cdr возвращает в качестве значения хвост списка.

Примеры:

Список Car Cdr

(a b c) a (b c)

((a)(b c)) (a) ((b c))

(a) a nil

() nil nil

Конструктором называется функция, осуществляющая построение объекта данных. Функция Cons строит новый список из переданных ей в качестве аргументов произвольного s-выражения (атомы и список) и списка. При этом первый аргумент включается в список-результат в качестве головы, второй –в качестве хвоста. Примеры

S-выражение список-аргумент результат

(a) (b c) ((a) b c)

(a) NIL ((a))

NIL (b c) (NIL b c)

a NIL (a)

a b (a.b)

Связь между конструкторами и селекторами.

Функции Car и Cdr являются обратными для конструктора CONS.

Пример.

(CONS (Car ‘(a b c))( Cdrt ‘(a b c))) дает исходный список ‘(a b c)

Композиция селекторов.

Путем комбинации селекторов Car и Cdr можно выделять произвольный элемент списка.

Пример.

Дан список списков:

‘((a b)(1 2)(3 4 5 6)(7 8 9) 10)

Выделить второй элемент третьего подсписка.

Решение.

Выделяем третий подсписок :

(Car (Cdr (Cdr ‘((a b)(1 2)(3 4 5 6)(7 8 9) 10))))

Выделяем второй элемент третьего подсписка:

(Car (Cdrt (Car (Rest (Rest ‘((a b)(1 2)(3 4 5 6)(7 8 9) 10))))))

Предикатные функции.

Предикаты - это функции, которые проверяют выполнение некоторого условия и возвращают в качестве результата false или nil в смысле логического отрицания, или другой объект в положительном смысле.

Atom, Eq и Equal являются базовыми предикатами Лиспа. С их помощью и используя другие базовые функции, можно задавать более сложные предикаты, которые будут проверять наличие более сложных свойств.

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

(atom s-выражение) возвращает true, если s-выражение является атомом, nil –в противном случае.

Предикат Eq проверяет тождественность двух атомарных s-выражений.

(eq‘a ‘b) дает NIL, (eq ‘a ‘a) дает T, (eq a a) дает T, (eq1 1) дает T, но (eq‘(1 2) ‘(1 2)) дает NIL.

Предикат Equal проверяет тождественность произвольных s-выражений.

Примеры : (equal ‘(1 2) ‘(1 2)) дает T, (equal ‘(1 2) ‘(2 1)) дает NIL.

Вопрос 17) Функции, определение функций.

В лиспе есть два вида функций:

• Не именованные

• Именованные

Не именованные функции используются для выполнения однократных преобразований или вычислений, такие действия носят локальный характер и используются только одной функцией. Наиболее часто не именованные функции используются в функционалах и макросах.

Определение функции в лиспе основано на лямбда исчислении Черча. Ламбда-вырожение – это определение вычислений и параметров в чистом виде без фактических параметров или аргументов которое имеет вид :

((lambda (список формальных параметров)

<Тело функции>)

<Список фактических параметров>)

Формальность параметров означает, что их можно заменить на любые другие символы, и это не отразится на вычислениях, определяемых функцией. (Аргументы внутри функции)

Телом функции является произвольная форма, значение которой может вычислить интерпретатор лиспа.

Список фактических параметров – параметры которые будут переданы в функцию в виде значений для аргументов.

Порядок вычисления лямбда-вызов

1. Вычисляются значение фактических параметров

2. Выполняется связывание фактических параметров с формальными. Первый формальный параметр связывается с первым фактическим и т.д.

3. Выполнение теля лямбда-выражения, полученное выражение возвращается в качестве значения всего лямбда-вызова.

4. Разрывается связь между формальными и фактическими параметрами.

Пример:

Функция увеличивает значение переданное ей переменной на 1. При этом вызов происходит единожды, для повторного вызова этой функции придется ввести заново весь код.

>((lambda (X) (+ X 1)) 0)

1

>((lambda (X) (+ X 1)) 1)

2

Именованные функции

Главное отличие именованной функции от не именованной состоит в том что единожды определив функции в программе мы можем ее вызывать только по ее имени, не вводя повторно полное ее описание.

Синтаксис:

Объявление: (defun <имя функции>(список формальных параметров)<Тело функции>)

Вызов: (<Имя><Список фактических параметров>)

Пример:

Определение: >(defun sum(x y)

(+ x y))

Вызов: >sum(5 6)

Ответ: 11