Искусственный Интеллект, 03 лекция (от 12 сентября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1264 участника 88.191.57.15 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Искусственный Интеллект, 02 лекция (от 11 сентября)|Предыдущая лекция]] | [[Искусственный Интеллект, 04 лекция (от 18 сентября)|Следующая лекция]] |
- | + | ||
- | + | = Лисп = | |
- | + | ||
+ | == Доп. информация == | ||
+ | |||
+ | # М. Ю. Семёнов «Язык Лисп для персональных ЭВМ», 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) | ||
+ | |||
+ | |||
+ | {{Искусственный Интеллект}} | ||
+ | {{Lection-stub}} |
Версия 17:37, 3 февраля 2008
Предыдущая лекция | Следующая лекция
Содержание |
Лисп
Доп. информация
- М. Ю. Семёнов «Язык Лисп для персональных ЭВМ», 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 |
Материалы
Фактический материал | Вопросы на экзамене