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

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

Содержание 1 Лисп 1.1 Доп. информация 1.2 Собственно Лисп 1.2.1 Как представляются в Лиспе данные 1.2.2 Как устроены списки 1.2.3 Альтернативный синтаксис: точечные пары 1.2.4 Базовый лисп 1.2.4.1 quote 1.2.4.2 car 1.2.4.3 cdr 1.2.4.4 cons 1.2.4.5 eq 1.2.4.6 eql 1.2.4.7 equal 1.2.4.8 cond 1.2.4.9 defun 1.2.4.10 null 1.2.4.11 atom 1.2.4.12 eval 1.2.5 Примеры 1.2.5.1 Сумма аргументов-чисел 1.2.5.2 Проверка, является ли атом членом списка 1.2.5.2.1 Пример 1.2.5.3 Слияние списков 1.2.5.3.1 Примеры 1.2.5.4 Подстановка 1.2.5.4.1 Примеры 1.2.5.5 Подстановка с полным обходом дерева 1.2.5.5.1 Примеры

[править] Лисп

[править] Доп. информация

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

[править] eval

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

(eval (quote (car (a b))) ) → 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)) → (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)