Язык программирования Лисп (1086318), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

[among e]

Значением аргумента должен быть список. Если этот список пуст, функция вырабатывает неуспех, который автоматически возвращает программу к предыдущей ее развилке. Иначе функция запоминает развилку, альтернативами которой является то, что функция в качестве своего значения может выдать любой элемент из этого списка. Вначале функция выдает как свое значение первый элемент списка, завершает на этом работу, и программа продолжает свои вычисления. Но если позже в программе возникнет неуспех, который вернет ее к данной развилке, то функция возобновит свою работу и теперь как свое значение выдаст второй элемент списка, после чего программа снова "идет вперед". И так далее, пока в списке остаются нерассмотренные элементы. После выдачи в качестве своего значения последнего элемента списка, функция уничтожает свою развилку и потому последующий неуспех уже не будет здесь остановлен.

[fail]

Эта функция вырабатывает неуспех, по которому программа автоматически возвращается к последней (по времени) развилке. (Если развилок нет, то вычисление всего выражения самого верхнего уровня программы считается окончившимся неуспешно.)

[pset v e]

Это аналог функции set, т.е. переменной, имя которой является значением аргумента v, присваивается новое значение - значение аргумента e. Однако, если присваивание, осуществленное функцией set, отменяется при неуспехе, то действие функции pset при неуспехе не будет отменено. Функция pset (и ей подобные) применяется, когда надо сохранить информацию, полученную на неуспешном пути вычисления программы, для последующих путей.

[permex e f]

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

Язык программирования Лисп

К числу основных особенностей языка Лисп относится то, что программой является несколько определенных пользователем функций. С точки зрения синтаксиса лисп-функция, как и обрабатываемые ею данные, представляет собой так называемое S-выражение. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном - список, т.е. последовательность элементов, разделенных обычно пробелом и заключенных в круглые скобки. Лисповские списки имеют рекурсивную структуру: элементом списка может быть произвольное S-выражение - как атом, так и список , например: (1() (a b (c)) class).

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

(f a₁ a₂ ... a_n), где f - имя функции, а a_i - ее аргументы (n≥0). Программа на Лиспе представляет собой последовательность таких форм, и ее выполнение заключается в их вычислении.

В большинстве версий языка Лисп имеется много встроенных (стандартных) функций, на основе которых составляется программа. Ниже кратко описаны некоторые из них - те, что использованы в предыдущих разделах пособия. Все они есть в наиболее известных версиях Лиспа, таких как Common Lisp и MuLisp. [Семенов М.Ю. Язык Лисп для персональных ЭВМ. - М.: Издательство МГУ, 1989.]

Определение новых функций

Для этого служит встроенная функция defun, к которой возможны следующие (равноценные) обращения:

(defun f (lambda (v₁ v₂ ... v_n) e))

или (defun f (v₁ v₂ ... v_n) e).

Вычисление функции defun в качестве побочного эффекта приводит к появлению в программе новой функции с именем f ; v_i - формальные параметры новой функции (n≥0), а e - форма, зависящая от v_i. Заметим, что таким образом определяется обычная лисп-функция, т.е. функция с фиксированным количеством аргументов, которые всегда вычисляются при обращении к ней.

При последующем обращении к этой уже определенной функции

(f a₁ a₂ ... a_n)

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Значением данной формы становится значение функции f при аргументах a_i.

Операции над списками

(car l)

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

(cdr l)

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

Кроме этих двух функций-селекторов элементов списка часто используются функции, являющиеся их суперпозициями. Имена всех таких функций начинаются на букву c, а заканчиваются на букву r, между ними же может стоять произвольная комбинация из не более чем 5 букв a и d, например,

(cadar l)≡(car(cdr(car l))) .

Предполагается, что список-аргумент l всех этих функций, так же как и следующей функции nth, содержит необходимое число элементов (в противном случае вычисления прерываются).

(nth n l)

Значением аргумента n должно быть положительное целое число (обозначим его N), а значением аргумента l - список. Значением функции является N-й от начала элемент этого списка.

(last l)

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

(cons e l)

В отличие от предыдущих функций эта функция является конструктором, т.е. строит новый список, который и выдает в качестве своего результата. Первым элементом этого списка будет значение аргумента e, а хвостом списка - значение аргумента l . Например,

(append l₁ l₂)

Эта функция осуществляет слияние (конкатенацию) двух списков, являющихся значением двух ее аргументов.

(list e₁ e₂ ... e_n )

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

Арифметические функции

(add1 n)

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

(sub1 n)

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

(+ n₁ n₂)

Значениями обоих аргументов функции должны быть числа, результат вычисления функции - их сумма.

(- n₁ n₂)

Значениями аргументов должны быть числа, значение функции - их разность.

(length l)

Значением аргумента l должен быть список, значением функции является количество элементов (верхнего уровня) этого списка, например:

(mod n₁ n₂)

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

(rem n₁ n₂)

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

Предикаты

Предикатом обычно называется форма, значение которой рассматривается как логическое значение "истина" или "ложь". Особенностью языка Лисп является то, что "ложью" считается пустой список, записываемый как () или nil, а "истиной" - любое другое выражение (часто в этой роли выступает атом T).

(null e)

Эта функция проверяет, является ли значение ее аргумента пустым списком: если да, то значение функции равно T, иначе - ().

(eq e₁ e₂)

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

(eql e₁ e₂)

В отличие от предыдущей функции eql сравнивает значения своих аргументов, которыми могут быть не только атомы-идентификаторы, но и атомы-числа. Если они равны, то значение функции равно T, иначе - ().

(equal e₁ e₂)

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

(neq e₁ e₂)

Аналог, но значения аргументов сравниваются на "не равно".

(member a l)

Функция производит поиск атома, являющегося значением первого ее аргумента, в списке (на верхнем его уровне), являющемся вторым аргументом. В случае успеха поиска значение функции равно T, иначе - ().

(gt n₁ n₂) или (> n₁ n₂)

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

(lt n₁ n₂) или (< n₁ n₂)

Аналог, но числа сравниваются на "меньше".

Логические функции

Так называются три функции, реализующие основные логические операции.

(not e)

Эта функция, реализующая "отрицание", является дубликатом функции null: если значение аргумента равно () ("ложь"), то функция выдает результат T ("истина"), а при любом другом значении аргумента выдает результат ().

(and e₁ e₂ ... e_k) (k≥1)

Это "конъюнкция". Функция по очереди вычисляет свои аргументы. Если значение очередного из них равно () ("ложь"), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением (), а иначе переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

(or e₁ e₂ ... e_k) (k≥1)

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

К числу логических функций можно отнести и лисповское условное выражение:

[cond (p₁ e_1,1 e_1,2 ... e_1,k1) ... (p_n e_n,1 e_n,2 ... e_n,kn)] (n≥1, k_i≥1)

Функция cond последовательно вычисляет первые элементы своих аргументов - обращения к предикатам p_i. Если все они имеют значение () ("ложь"), тогда функция заканчивает свою работу с этим же значением. Но если был обнаружен предикат p_i, значение которого отлично от (), т.е. он имеет значение "истина", тогда функция cond уже не будет рассматривать остальные предикаты, а последовательно вычислит формы e_i,j из этого i-го аргумента и со значением последнего из них закончит свою работу. Заметим, что поскольку значения предыдущих форм из этого аргумента нигде не запоминаются, то в качестве этих форм имеет смысл использовать только такие, которые имеют побочный эффект, например, обращение к функции присвоения значения.

Специальные функции

(quote e) или 'e

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

(gensym)

Характеристики

Список файлов учебной работы