Шпора (Шпоры к первому коллоквиуму), страница 5

Значением функции является N-й от начала элемент этого списка. Например,(nth 2 '(AT ROBOT (a 6)) ) → ROBOT.(last l)Функция выбирает последний (от начала) элемент списка, являющегося значением ее аргумента.Например, (last '(AT ROBOT (a 6)) ) → (a 6).(cons e l)В отличие от предыдущих функций эта функция является конструктором, т.е. строит новый список,который и выдает в качестве своего результата.

Первым элементом этого списка будет значениеаргумента e, а хвостом списка – значение аргумента l. Например, (cons '(A B C) '(D E F) ) →((A B C) D E F).(append l1 l2)Эта функция осуществляет конкатенацию двух списков, являющихся значением ее аргументов.Например, (append '(A B C) '(D E F) ) → (A B C D E F).(list e1 e2 . . . en)(n≥1)Эта функция имеет произвольное количество аргументов, из значений которых она строит список(количество элементов на верхнем уровне результирующего списка равно количествуаргументов).Например, если переменная X имеет своим значением список (p (q r)), а переменная Y –список (t), тозначение формы (cons X Y) равно ((p (q r)) t),значение формы (append X Y) равно (p (q r) t),значение формы (list X Y)равно ((p (q r)) (t)).Арифметические функции(length l)Значением аргумента l должен быть список, функция вычисляет количество элементов (верхнегоуровня) этого списка. К примеру, значение (length X) равно 2, если переменная X имеет значение(p(q r)).Значениями аргументов нижеследующих функций должны быть числа, над которымипроизводятся арифметические операции.(add1 n)Функция прибавляет число 1 к числу-аргументу и выдает результат в качестве своего значения.(sub1 n)Эта функция вычитает 1 из значения своего аргумента и выдает результат в качестве своегозначения.(+ n1 n2)Значением функции является сумма значений ее аргументов.(- n1 n2)Значением этой функции является разность значений ее аргументов.(mod n1 n2)Функция выполняет деление нацело значение первого аргумента на значение второго, и результатвыдает в качестве своего значения.(rem n1 n2)Результат вычисления этой функции – остаток от деления первого числа на второе.ПредикатыПредикатом обычно называется форма, значение которой рассматривается как логическоезначение «истина» или «ложь».

Особенностью языка Лисп является то, что «ложью» считаетсяпустой список, записываемый как () или nil, а «истиной» – любое другое выражение (частоатом T).(null e)Эта функция проверяет, является ли значение ее аргумента пустым списком: если да, то значениефункции равно T, иначе – ().(eq e1 e2)Функция сравнивает значения своих аргументов, которые должны быть атомамиидентификаторами. В случае их совпадения (идентичности) значение функции равно T, иначе –().(eql e1 e2)В отличие от предыдущей функции, данная функция сравнивает значения своих аргументов,которыми могут быть не только атомы-идентификаторы, но и атомы-числа.

Если они равны, тозначение функции равно T, иначе – ( ). Отметим, что во многих версиях Лиспа для сравнениялюбых атомов используется функция eq.(neq e1 e2)Аналог предыдущей функции, но значения аргументов сравниваются на «не равно».(equal e1 e2)Функция производит сравнение двух произвольных S-выражений – значений своих аргументов.Если они равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значениефункции равно T, иначе – ().(member a l)Значением первого аргумента должен быть атом, а второго – список. Функция производит поискзаданного атома на верхнем его уровне заданного списка. В случае успеха поиска значениефункции равно T, иначе – ( ).(gt n1 n2) или (> n1 n2)Значениями аргументов этой функции должны быть числа. Если первое из них больше второго, тозначение функции равно T, иначе – ().(lt n1 n2) или (< n1 n2)Аналог предыдущей функции, но числа сравниваются на «меньше».Логические функцииТак называются три функции, реализующие основные логические операции.(not e)Эта функция, реализующая «отрицание», является дубликатом функции null: если значениеаргумента равно ( ) («ложь»), то функция выдает результат T («истина»), а при любом другомзначении аргумента выдает результат ( ).(and e1 e2 … ek)(k≥1)Это «конъюнкция».

Функция по очереди вычисляет свои аргументы. Если значение очередного изних равно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работусо значением ( ), а иначе переходит к вычислению следующего аргумента. Если функция дошла довычисления последнего аргумента, то с его значением она и заканчивает свою работу.(or e1 e2 … ek)(k≥1)Это «дизъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного изних не равно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает своюработу со значением этого аргумента, в противном случае она переходит к вычислениюследующего аргумента.

Если функция дошла до вычисления последнего аргумента, то с егозначением она и заканчивает свою работу.К числу логических функций можно отнести и лисповское условное выражение:(cond (p1 e1,1 e1,2 … e1,k1) … (pn en,1 en,2 … en,kn))(n≥1, ki≥1)Функция cond последовательно вычисляет первые элементы своих аргументов – обращения кпредикатам pi. Если все они имеют значение ( ) («ложь»), тогда функция заканчивает свою работусо значением ( ). Но если был обнаружен предикат pi, значение которого отлично от ( ), т.е. онимеет значение «истина», тогда функция cond уже не будет рассматривать остальные предикаты,а последовательно вычислит формы ei,j из этого i-го аргумента и со значением последнего из нихзакончит свою работу.

Заметим, что поскольку значения предыдущих форм из этого аргументанигде не запоминаются, то в качестве этих форм имеет смысл использовать только такие, которыеимеют побочный эффект, например, функции присваивания значений переменным или печати.Специальные функции(quote e) или 'eЭто функция блокировки вычислений: она выдает в качестве значения свой аргумент, не вычисляяего. Например, значением формы '(car (2)) является само выражение (car (2)).(gensym)Это функция генерации уникальных атомов (символов): при каждом обращении к ней выдаетсяновый атом-идентификатор. Этот идентификатор получается склеиванием специального префиксаи очередного номера (целого числа). Префикс и целое число, от которого начинается нумерациягенерируемых атомов, могут быть установлены заранее, как, например, в языке MuLisp:(setq *gensym-prefix* 'S) (setq *gensym-count* 2)После этого при последовательных обращениях к функции gensym она будет выдавать атомы S2,S3, S4 и т.д.Блочная и связанные с ней функции(prog (v1 v2 … vn) e1 e2 … ek) (n≥0, k≥1)Эту специальную функцию называют «блочной», поскольку ее вычисление напоминаетвыполнение блоков в других языках программирования.

Вычисление функции начинается с того,что вводятся локальные переменные vi, перечисленные в ее первом аргументе, и всем им вкачестве начального значения присваивается пустой список nil. После этого функцияпоследовательно вычисляет остальные свои аргументы – формы ei. Вычислив последнюю из них,функция prog заканчивает работу со значением этой формы, уничтожив перед этим все своилокальные переменные vi .Вычисленные значения всех форм ei, кроме последней, нигде не запоминаются, поэтомуимеет смысл использовать в качестве них только функции с побочным эффектом. Некоторые изэтих функций перечислены ниже.В качестве одной из форм ei может быть записан атом-идентификатор, в этом случае он невычисляется, а трактуется как метка, на которую будет производиться переход внутри этого блока(функцией go).(return e)Это функция досрочного выхода из блока. Она может использоваться только внутри блочнойфункции prog, поскольку завершает вычисление ближайшей объемлющей блочной функции,устанавливая ее значение равным значению аргумента e.(go e)Функция реализует переход по метке.

Аргумент ее не вычисляется, в качестве ее аргументадолжен быть задан идентификатор – одна из меток ближайшей объемлющей блочной функции.Функция go полностью завершает вычисление той формы этой блочной функции, в которую онавходит (на любом уровне), и осуществляет переход на вычисление формы, непосредственноследующей за указанной меткой.(setq v e)Это аналог оператора присваивания.

В качестве аргумента v (он не вычисляется) должно бытьзадано имя переменной, существующей в данный момент. Функция присваивает этойпеременной новое значение – вычисленное значение формы e. Это же значение являетсязначением и самой функции setq, однако оно, как правило, не используется.Следующие две особые функции используются для упрощения записи часто используемыхконструкций (setq V (cdr V)) и (setq V (cons (e V)).(pop v)Аргументом этой функции (он не вычисляется) должно быть имя переменной, существующей вданный момент и имеющей своим значением непустой список. Хвост этого непустого спискаприсваивается в качестве нового значения указанной переменной, а также выступает в качествезначения самой функции pop.(push е v)В качестве второго аргумента этой функции (он не вычисляется) должно быть задано имяпеременной, в качестве первого – произвольная форма. Функция вычисляет эту форму и строитновый список, первый элемент которого – вычисленное значение, а хвост – список, являющийсязначением переменной v.

Результирующий список становится новым значением переменной v изначением самой функции push.Например, если переменная X имеет значение (d (e) g), а переменная U – значение (1 2), тозначение формы (pop X) равно ((e) g), а значение (push U X) равно ((1 2) d (e) g).Основным средством реализации циклических программ в Лиспе является рекурсия.Рассмотрим примеры простейших рекурсивных программ на Лиспе:(listp l) – функция-предикат, проверяющая является ли значение ее аргумента списком (наверхнем уровне). Если да, то значение функции равно T, иначе – ().(defun listp (lambda (x)(cond ((null x) T)((atom x) ( ))( T (listp (cdr x))) )))(memb a l) - функция ищет атом, являющийся значением первого ее аргумента, в списке (наверхнем его уровне), являющемся значением второго аргумента.

В случае успеха поиска значениефункции равно T, иначе – ().(defun memb (lambda (a l)(cond ((null l) nil)((eq a (car l)) T)(T (memb a (cdr l)) ) ))(out a l) - функция удаляет из списка, являющегося значением ее второго аргумента, всевхождения (на верхнем) атома, являющегося значением первого аргумента.(defun out (lambda (a l)(cond ((null l) nil)((eq a (car l)) (out a (cdr l)))(T (cons (car l) (out a (cdr l))))) ))(equal e1 e2) – функция, сравнивающая два произвольных S-выражения – значения своихаргументов.