Искусственный Интеллект, 03 лекция (от 12 сентября)

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Предыдущая лекция | Следующая лекция

Содержание

Лисп

Доп. информация

  1. М. Ю. Семёнов «Язык Лисп для персональных ЭВМ», 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))

Используется для подавления вычислений других функций, например,

(cons (quote (a (b)) ) y) → ( (a (b)) 8 )

при вычислении функции cons поиск последовательно пойдёт по аргументам функции - сначала вычислит quote, получит (a (b)), потом вычислит 8 - просто возмёт атом - и потом создаст новый список. Без quote cons будет вычислять (a (b))

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

Материалы
Фактический материал | Вопросы на экзамене


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы