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

(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

Это функция блокировки вычислений: она выдает в качестве значения свой аргумент, не вычисляя его. Например, значением формы '(car (2)) является само выражение (car (2)).

(gensym)

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

(setq *gensym-prefix* 'S) (setq *gensym-count* 2)

После этого при последовательных обращениях к функции gensym она будет выдавать атомы S2, S3, S4 и т.д.

Блочная и связанные с ней функции

(prog (v₁ v₂ … v_n) e₁ e₂ … e_k) (n≥0, k≥1)

Эту специальную функцию называют «блочной», поскольку ее вычисление напоминает выполнение блоков в других языках программирования. Вычисление функции начинается с того, что вводятся локальные переменные v_i, перечисленные в ее первом аргументе, и всем им в качестве начального значения присваивается пустой список nil. После этого функция последовательно вычисляет остальные свои аргументы – формы e_i. Вычислив последнюю из них, функция prog заканчивает работу со значением этой формы, уничтожив перед этим все свои локальные переменные v_i .

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

В качестве одной из форм e_i может быть записан атом-идентификатор, в этом случае он не вычисляется, а трактуется как метка, на которую будет производиться переход внутри этого блока (функцией 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 e₁ e₂) – функция, сравнивающая два произвольных S-выражения – значения своих аргументов. Если они равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значение функции равно T, иначе – ().

(defun equal (lambda (x y)

(cond ((atom x) (eq x y))

((atom y) ( ))

((equal (car x) (car y)) (equal (cdr x) (cdr y)))

( T ( ) ) )))

Язык ПЛЭНЕР

Плэнер – один из потомков языка Лисп, созданный специально для реализации систем ИИ. Основные объекты языка (как и в Лиспе) – списки и атомы. Плэнер – очень громоздкий и сложный (для реализации и изучения) язык не нашедший, к сожалению, более или менее широкого практического применения.

Вспомним «Особенности задач ИИ (с точки зрения программирования)»:

1. сложные и динамически меняющиеся структуры данных;

2. большие по объему хранилища данных (базы знаний) и средства эффективной работы с ними;

3. символьные (в основном) данные;

4. модели, отражающие состояние проблемной среды;

5. переборные алгоритмы;

6. алгоритмы поиска по образцу;

7. гибкие структуры управления.

Основные составляющие языка Плэнер:

• средства для работы со списками (лисповская часть, используется для работы со списками)

• плэнерская база данных (используется для моделирования ситуаций проблемной среды)

• встроенный режим возвратов (реализует один из основных методов перебора – бэктрекинг)

• аппарат работы с образцами (используется для анализа структуры списков)

• аппарат теорем (используется при планировании решения)

позволяют достаточно эффективно (и быстро) реализовать соответствующие возможности.

Три типа процедур языка Плэнер:

- функции;

- сопоставители (для работы с образцами);

- теоремы (процедуры, вызываемые по образцу).

Примеры конструкций и процедур Плэнера:

Обращение к функции:

[ELEM -2 (A B C D)] → C

Выдать второй (2), считая с конца списка (знак "минус" при 2), элемент списка (A B C D).

Сопоставление образца с выражением:

[IS (*X ПРИШЕЛ !*Y) (САША ПРИШЕЛ ИЗ МАГАЗИНА)] → T

Сопоставление успешно, то есть образец (*X ПРИШЕЛ !*Y) соответствует выражению (САША ПРИШЕЛ ИЗ МАГАЗИНА). Побочный эффект: переменная X получает значение САША, а переменная Y получает значение (ИЗ МАГАЗИНА)

Утверждение плэнерской базы данных:

(BOX A (3 7)) - ящик с названием А находится на плоском квадратном поле с пронумерованными клетками в третьей строке (по горизонтали) и в седьмом столбце (по вертикали).

Запись утверждения в плэнерскую базу данных:

[ASSERT (BOX A) (WITH COL RED)] – в базу данных записывается утверждение (BOX A), то есть "А является ящиком"; записывается также, что "цвет" (COL) этого ящика "красный" (RED).

Поиск утверждения в плэнерской базе данных:

[SEARCH (BOX [ ]) (TEST COL [NON GREEN])] – в базе данных ищется утверждение о некотором ящике, цвет которого не (NON) зеленый (GREEN); возможный ответ (результат поиска) – (BOX A).

Определение плэнерской теоремы:

[DEFINE ОСВОБОДИЛИ (ERASING (X)

(=ЗАНЯТ= *X)

[ASSERT (=СВОБОДЕН= .X)])]

Если из базы данных вычеркивается утверждение о том, что "поверхность некоторого кубика X занята" (если так, то на него нельзя поставить другой кубик), то автоматически будет вызвана и выполнена эта теорема. Она запишет в базу данных утверждение: "поверхность этого кубика X освободилась" (теперь на него можно поставить другой кубик).

Перейдем к более детальному рассмотрению основных составляющих Плэнера.

Основные объекты языка, средства для работы со списками

Выражения:

• атомарные:

- обращения к переменным

- атомы: идентификаторы, числа, строки

• списковые:

- L-списки (списки в круглых скобках: ( и ) )

- P-списки (списки в квадратных скобках: [ и ] )

- S-списки (списки в «уголках»: < и > )

Ограничители: <пробел>, ( , ) , [ , ] , < , >; цифры; буквы; специальные литеры + , - , . , * , : , ! .

Префиксы: . , * , : - простое обращение к переменным; !. , !* , !: - сегментное обращение к переменным.

Простые формы:

- атомы (значением атома является сам этот атом),

- обращения к переменным с префиксом . ,

- обращения к константам с префиксом : ,

- L-списки (значением L-списка является список из значений его элементов),

- P-списки (обращения к процедурам).

Сегментные формы:

- обращения к переменным с префиксом !. ,

- обращения к константам с префиксом !: ,