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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

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

[[Искусственный Интеллект, 02 лекция (от 11 сентября)|Предыдущая лекция]] | [[Искусственный Интеллект, 04 лекция (от 18 сентября)|Следующая лекция]]

= Лисп =

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

# М. Ю. Семёнов «Язык Лисп для персональных ЭВМ», recyclebin.ru — Lisp

== Собственно Лисп ==

=== Как представляются в Лиспе данные ===

В Лиспе все данные подразделяются на две категории: 
* Атомы — неделимые вещи
** Числа
** Символы — нкие идентификаторы, которые могут содержать практически всё, кроме пробелов, и они не должны быть числами. Примеры: «a», «b», «1+2»
** Строки
* Списки. Синтаксис: (выражение выражение ... выражение). Пример: «(1 2 a)», «((1 2) 3)»

=== Как устроены списки ===

Внутри списки представляются в виде набора списочных ячеек — пары ссылок.

Кроестиком обозначается специальный элемент: nil
* nil = ()

=== Альтернативный синтаксис: точечные пары ===

&laquo;s-expr> ::= &laquo;atom> | (&laquo;s_expr> . &laquo;s_expr>)

(1 2 a) == (1 . (2 . (a . nil)))

Программа в лиспе — последовательность выражений, таких, что их можно вычислить.

Вычисляемое выражение — форма.

Формы:
* Число — само число
* Символ — значение, связанное с символом

Далее в таком формате: форма &rarr; значение
* 1 &rarr; 1
* t &rarr; t —истина
* nil &rarr; nil — ложь

Список является вычисляемым, когда он имеет такой формат:
* (F a1 ... an)
** F — функция
** a1 ... an — аргументы

Есть два вида функций: обычные и особые. Обычные сначала вычисляют свои аргументы перед передачей, особые могут не вычислять.

Пример:
* (+ 1 2) &rarr; 3
* (< 5 4) &rarr; nil
* (&times; 2 (+ 3 4)) &rarr; (&times; 2 7) &rarr; 14

=== Базовый лисп ===

Набор из нескольких функций, из которых всё сделано. Остальные пишутся через них, а которые не пишутся, мы их рассматривать не будем.

==== quote ====

Функция не вычисляет свой аргумент и возвращает его невычисленным:

(quote a) &rarr; a

Пример:
(quote (+ 1 2)) &rarr; (+ 1 2)

Сокращённая запись:

'(a b c) == (quote (a b c))

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

(cons (quote (a (b)) ) y) &rarr; ( (a (b)) 8 )

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

==== car ====

car возвращает первый элемент списка.

(car '(a b c))  &rarr; a

Если car будет вызван от атома, то это ошибка.

(car ((1 2) 3)) &rarr; (1 2)

==== cdr ====

Возвращает хвост списка.

(cdr '(a b c)) &rarr; (b c)

==== cons ====

Конструирование списка:

(cons 'a nil) &rarr; (a)

(cons 1 2) &rarr; (1 . 2)

==== eq ====

Сравненивает объекты и возвращает t, если они идентичны.

* (eq 'a 'a) &rarr; t
* (eq '(1 2) '(1 2)) &rarr; nil

==== eql ====

Сравнение чисел. Если аргументы — числа, то она берёт =, иначе eq

==== equal ====

Сравнение списков.

(equal '(1 2) '(1 2)) &rarr; 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) &rarr; 3

==== null ====

(null x) = (eq x nil)
==== atom ====

Проверяет, атом ли её аргумент.

* nil — атом — t
* атом — t
* список — nil

==== eval ====

Сначала вычисляет свой аргумент, потом вычисляет полученное выражение и выдаёт его значение в ответ

(eval (quote (car (a b))) ) &rarr; a

=== Примеры ===

Вместо циклов будем использвать рекурсию.

==== Сумма аргументов-чисел ====

(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)) &rarr; (nil b)
* (member 'a '(b (a) c . a)) &rarr; nil

==== Слияние списков ====

(defun append (x y) 
   (cond 
     ((atom x) y) 
     (t 
       (cons 
         (car x) 
         (append (cdr x) y)
       )
     )
   )
 )

===== Примеры =====

* (append '(1 2) '(3 4)) &rarr; (1 2 3 4)
* (append '(a b) '(c (d) e)) &rarr; (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)) &rarr; (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)) &rarr; (1 2 (1 2) 1)

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.us/wiki/%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%98%D0%BD%D1%82%D0%B5%D0%BB%D0%BB%D0%B5%D0%BA%D1%82%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_12_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 14: / Строка 14: @@
 * Атомы — неделимые вещи
 ** Числа
-** Символы — некие идентификаторы, которые могут содержать практически всё, кроме пробелов, и они не должны быть числами. Примеры: «a», «b», «1+2»
+** Символы — нкие идентификаторы, которые могут содержать практически всё, кроме пробелов, и они не должны быть числами. Примеры: «a», «b», «1+2»
 ** Строки
 * Списки. Синтаксис: (выражение выражение ... выражение). Пример: «(1 2 a)», «((1 2) 3)»