Материал из 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.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

Примеры

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

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

(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)