QUOTE блокирует вычисление выражения

В некоторых случаях не надо вычислять значение выражения, а нужно само выражение. Нас, например, может не интересовать значение функционального вызова (+ 2 3), равное 5, а мы хотим обрабатывать форму (+ 2 3) как список. В таких случаях выражения, которые интерпретатору не надо вычислять, помечаются особым образом. Чтобы предотвратить вычисление значения выражения, нужно перед этим выражением поставить апостроф «’» (quote). В Лиспе начинающееся с апострофа выражение соответствует заключению в кавычки в обыкновенном тексте, и в обоих случаях это означает, что цитату нужно использовать в том виде, как она есть. Например:

_ ’(+ 2 3)

(+ 2 3)

_’y

Y

Апостроф перед выражением – это на самом деле сокращение лисповской формы QUOTE, записываемой в единообразной для Лиспа префиксной нотации:

 

’выражение ó (QUOTE выражение)

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

 

_(quote (+ 2 3))

(+ 2 3)

_(quote y)

Y

Интерпретатор Лиспа, считывая начинающиеся с апострофа выражение, автоматически преобразует его в соответствующий вызов функции QUOTE/

 

_’(a b ’(c d)); QUOTE внутри QUOTE

(A B (QUOTE (C D)))

_’(quote ’y); все апострофы преобразуются в вызов

(QUOTE Y); QUOTE

_’’y

(QUOTE Y)

_(quote quote)

QUOTE

_’quote

QUOTE

Числа не надо предварять апострофом, так как интерпретатор считает, что число и его значение совпадают. Однако в принципе использование апострофа перед числом не запрещено. Перед другими константами (Т и NIL), как и перед числами, тоже не надо ставить апостроф, поскольку и они представляют самих себя.

Однако заметим, что в приведенных примерах на месте имени функции в функциональном вызове апостроф не использовался. Интерпретатор Коммон Лиспа не допускает использование в качестве первого элемента вызова функции вычисляемого выражения. В некоторых других Лисп-системах имя функции допустимо задавать с помощью вычисляемого выражения.

_’ 317.0; апостроф не нужен

317.0

_(+ ’ 2 3)

_t; значением Т является Т

Т

_’t; апостроф не нужен

Т

_nil; NIL представляет самого себя

NIL

 

ЛАБОРАТОРНАЯ РАБОТА №2

 

1. Сколько значений может быть у функции? Может ли функция принимать одно и то же значение на разных аргументах?

 

 

2. Проделайте следующие вычисления с помощью интерпретатора Лиспа:

a) 3.234*(4.56+21.45)

b) 5.67+6.342+12.97

c) (454-214-675)/(456+678*3)

 

3. Определите значения следующих выражений:

a) ’(+ 2 (* 3 4))

b) (+ 2 ’(* 3 4))

c) (+ 2 (’* 3 4))

d) (+ 2 (* 3 ’4))

e) (quote ’quote)

f) (quote 2)

g) ’(quote NIL)

 

4. Напишите выражение, вычисляющее среднее арифметическое чисел 23, 5, 43 и 17

 

БАЗОВЫЕ ФУНКЦИИ

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

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

Функция CDR возвращает в качестве значения хвостовую часть списка

Функция CONS включает новый элемент в начало списка

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

Предикат проверяет наличие некоторого свойства

Предикат АТОМ проверяет, является ли аргумент атомом

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

EQL сравнивает числа одинаковых типов

47. Предикат = сравнивает числа различных типов

EQUAL проверяет идентичность записей

EQUALP проверяет наиболее общее логическое равенство

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

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

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

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

 

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

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

Простота базовых функций и их малое число – это характерные черты Лиспа. С этим связана математическая элегантность языка. Разумно выбранные примитивы образуют, кроме красивого формализма, также и практическую основу программирования.

Базисными функциями обработки символьных выражений (атомов и списков) являются:

 

CAR, CDR, CONS, ATOM, EQ

Функции по принципу их использования можно разделить на функции разбора, создания и проверки:

 

ИСПОЛЬЗОВАНИЕ ВЫЗОВ РЕЗУЛЬТАТ

Разбор: (CAR список) s–выражение

(CDR список) список

Создание: (CONS s– выражение список) список

Проверка: (ATOM символ символ)Т или NIL

(EQ символ символ) Т или NIL

У функций CONS и EQ имеются два аргумента, у остальных примитивов – по одному. В качестве имен аргументов и результатов функций мы использовали названия типов, описывающих аргументы, на которых определена (т.е. имеет смысл) функция и вид возвращаемого функциями результата. S-выражение обозначает атом или список.

Функции ATOM и EQ являются базовыми предикатами. Предикаты (predicate) –это функции, которые проверяют выполнение некоторого условия и возвращают в качестве результата логическое значение Т (в более общем виде, произвольное выражение, отличное от NIL) или NIL.

Рассмотрим базовые функции более подробно.

 

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

Первый элемент списка называется головой (head), а остаток списка, т.е. список без первого его элемента, называется хвостом списка (tail). С помощью селекторов CAR и CDR можно выделить из списка его голову и хвост.

Функция CAR возвращает в качестве значения первый элемент списка, т.е. головной элемент списка:

 

_(car ’ (первый второй третий)); внимание, используется ’

ПЕРВЫЙ

_(car ’ ((head) tail))

HEAD

Обратите внимание на то, что в первом примере мы не вычисляем значение аргумента (ПЕРВЫЙ ВТОРОЙ ТРЕТИЙ) и не применяем к нему операцию CAR, а используем аргумент в таком виде, как он есть. Ситуация отличается, например, от следующего функционального вызова:

 

_(* 4 (+ 3 2))

где нужно умножить 4 на значение аргумента (+ 3 2), т.е. на 5, а не на список (+ 3 2). Вызов функции CAR с аргументом (ПЕРВЫЙ ВТОРОЙ ТРЕТИЙ) без апострофа был бы проинтерпретирован как вызов функции ПЕРВЫЙ с аргументом ВТОРОЙ и ТРЕТИЙ, и было бы получено сообщение об ошибке.

Функция CAR имеет смысл только для аргументов, являющихся списками, а следовательно имеющих голову:

 

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

Для аргумента атома результат функции CAR не определен, и вследствие этого появляется следующее сообщение об ошибке:

 

_(car ’ кот)

Error: KOT is not a list

(т.е. КОТ не является списком).

Головной частью пустого списка считают для удобства NIL:

 

_(car nil); голова пустого списка -

NIL; пустой список

_(car ’ nil); знак ’ можно опускать

NIL

_(car ’ (nil a)); голова списка NIL

NIL

Функция CDR возвращает в качестве значения хвостовую часть списка

Функция CDR применима к спискам. Значением ее будет хвостовая часть списка, т.е. список, получаемый из исходного списка после удаления из него головного элемента:

 

сdr: список → список

_(cdr ’ (a b c))

(B C)

_(cdr ’ (a (b c)))

((B C))

Функция CDR не выделяет второй элемент списка, а берет весь остаток списка, т.е. хвост. Заметим, что хвост списка – тоже список, если только список не состоял из одного элемента. В последнем случае хвостом будет пустой список (), т.е. NIL:

 

_(cdr ’ (a))

NIL

Из соображений удобства значением функции CDR от пустого списка считается NIL:

 

_(cdr nil)

NIL

Так же как и CAR, функция CDR определена только для списков. Значение для атомов не определено, что может приводить к сообщению об ошибке:

 

_(cdr ’ кот)

Error: KOT is not list

Необычные имена функций CAR и CDR возникли по историческим причинам. Эти имена являются сокращениями от наименований регистров Contents of Address Register (CAR) и Contents of Decrement Register (CDR) вычислительной машины IBM 605. Автор Лиспа Джон Маккарти реализовал первую Лисп-систему именно на этой машине и использовал регистры CAR и CDR для хранения головы и хвоста списка.

В некоторых других диалектах Лиспа наряду с CAR и CDR используются и более наглядные имена FIRST и REST, а также HEAD и TAIL.