Искусственный Интеллект, 03 лекция (от 12 сентября)
Материал из eSyr's wiki.
Предыдущая лекция | Следующая лекция
Содержание |
Лисп
Доп. информация
- М. Ю. Семёнов «Язык Лисп для персональных ЭВМ», recyclebin.ru — Lisp
Собственно Лисп
Как представляются в Лиспе данные
В Лиспе все данные подразделяются на две категории:
- Атомы — неделимые вещи
- Числа
- Символы — нкие идентификаторы, которые могут содержать практически всё, кроме пробелов, и они не должны быть числами. Примеры: «a», «b», «1+2»
- Строки
- Списки. Синтаксис: (выражение выражение ююю выражение). Пример: «(1 2 a)», «((1 2) 3)»
Как устроены списки
Внутри списки представляются в виде набора списочных ячеек — пары ссылок.
Кроестиком обозначается специальный элемент: nil
- nil = ()
Альтернативный синтаксис: точечные пары
«s-expr> ::= «atom> | («s_expr> . «s_expr>)
(1 2 a) == (1 . (2 . (a . nil)))
Программа в лиспе — последовательность выражений, таких, что их можно вычислить.
Вычисляемое выражение — форма.
Формы:
- Число — само число
- Символ — значение, связанное с символом
Далее в таком формате: форма → значение
- 1 → 1
- t → t —истина
- nil → nil — ложь
Список является вычисляемым, когда он имеет такой формат:
- (F a1 ... an)
- F — функция
- a1 ... an — аргументы
Есть два вида функций: обычные и особые. Обычные сначала вычисляют свои аргументы перед передаячей, особые могут не вычислять.
Пример:
- (+ 1 2) → 3
- (< 5 4) → nil
- (× 2 (+ 3 4)) → (× 2 7) → 14
Базовый лисп
Набор из нескольких функций, из которых всё сделано. Остальные пишутся через них, а которые не пишутся, мы их рассматривать не будем.
quote
Функция не вычисляет свой аргумент и возвращает его невычисленным:
(quote a) → a
Пример: (quote (+ 1 2)) → (+ 1 2)
Сокращённая запись:
'(a b c) == (quote (a b c))
car
car возвращает первый элемент списка.
(car '(a b c)) → a
Если car будет вызван от атома, то это ошибка.
(car ((1 2) 3)) → (1 2)
cdr
Возвращает хвост списка.
(cdr '(a b c)) → (b c)
cons
Конструирование списка:
(cons 'a nil) → (a)
(cons 1 2) → (1 . 2)
eq
Сравненивает объекты и возвращает t, если они идентичны.
- (eq 'a 'a) → t
- (eq '(1 2) '(1 2)) → nil
eql
Сравнение чисел. Если аргументы — числа, то она берёт =, иначе eq
equal
Сравнение списков.
(equal '(1 2) '(1 2)) → t
cond
Особая операция. Условие.
(cond (p1 ... e1) ... (pn en))
Первый элемент каждого списка — условия, второй — выражение.
Как это работает: последовательно вычисляются p1, p2 ... . Как только pi возвращает t, cond возвращает ei.
Пример:
(cond (x y) (t z)) — аналог if x then y else z
Если не будет найдено ни одного выражения, то cond вернёт nil.
defun
Опеределние новой функции.
(defun f (a1 ... an) e)
функции с именем f будет сопоставлено тело e.
Пример:
(defun min (x y) (cond ((< x y) x) (t y)))
После того, как эта фрма будет вычислена, её можно будет использовать:
(min 5 3) → 3
null
(null x) = (eq x nil)
atom
Проверяет, атом ли её аргумент.
- nil — атом — t
- атом — t
- список — nil
Примеры
Вместо циклов будем использвать рекурсию.
Сумма аргументов-чисел
(defun add (x) (cond ((null x) 0) (t (+ (car x) (add (cdr x)) ) ) ) )
Это так назыввемая простая рекурсия.
Проверка, является ли атом членом списка
(defun member (a l) (cond ((atom l) nil) ((eq a (car l)) l) (t (member a (cdr l))) ) )
Пример
- (member nil '(a () b)) → (nil b)
- (member 'a '(b (a) c . a)) → nil
Слияние списков
(defun append (x y) (cond ((atom x) y) (t (cons (car x) (append (cdr x) y) ) ) ) )
Примеры
- (append '(1 2) '(3 4)) → (1 2 3 4)
- (append '(a b) '(c (d) e)) → (a b c (d) e)
Подстановка
(defun substitute (x y l) (cond ((atom l) l) ((eq y (car l)) (cons x (substitute x y (cdr l)))) (t (cons y (substitute x y (cdr l)))) ) )
Примеры
- (substitute 1 0 '(0 2 (0 2) 0)) → (1 2 (0 2) 1)
Подстановка с полным обходом дерева
(defun subst ( x y l ) (cond ( (eq y l ) x ) ( (atom l ) l ) (t (cons (subst x y (car l ) ) (subst x y (cdr l ) ) ) ) ) )
Примеры
- (substitute 1 0 '(0 2 (0 2) 0)) → (1 2 (1 2) 1)
01 02 03 04 04 06 ... -3 -2 -1
Календарь
вт | вт | ср | вт | ср | вт | |
Сентябрь
| 04 | 11 | 12 | 18 | 19 | 25 |
Ноябрь
| 20 | 27 | ||||
Декабрь
| 04 |
Материалы
Фактический материал | Вопросы на экзамене