Немножко отвлечемся... Под предикатом в Лиспе понимают функцию, которая предназначена для проверки выполнения некоторого условия и возвращает T в случае выполнения этого условия и NIL в противном случае. Кроме того, поскольку любое отличное от NIL значение в функциях сравнения интерпретируется как T,  предикат может выглядеть, например, следующим образом:

(defun правильный-размерчик? (арг)

    (if (and (< арг 100) (> арг 50))   арг  nil)

)

В этом примере функция возвращает аргумент, если его значение находится в диапазоне от 50 до 100, а если это ограничение не выполняется, возвращается NIL. Опознать предикат по имени функции обычно достаточно легко - в Common Lisp принято соглашение, по которому имена функций-предикатов заканчиваются буквой p (латинской). А в некоторых других диалектах, таких как например, Schema, имя предиката заканчивается вопросительным знаком.

(defun атом?  (арг)

    (or (numberp арг)

        (symbolp  арг))

)

Собственно говоря, с помощью подобного подхода вы можете легко определять собственные, производные типы данных - ведь предикаты легко встраиваются во многие служебные функции Лиспа. Но об этом как-нибудь в следующий раз, а сейчас давайте посмотрим, как работает созданный нами предикат:



Как видите. работает наш предикат вполне предсказуемо. Я хочу лишь обратить ваше внимание на ошибку, обнаруженную Лисп-системой при попытке проверить принадлежность некоего объекта с именем car. Во-первых, вы видите, что Лисп не делает различий между строчными и прописными буквами (это относится только к именам объектов, записанных латиницей), а во-вторых, пытается интерпретировать объект CAR как переменную (хотя в Лиспе имеется и встроенная функция с таким же именем!). При этом Лисп полагает, что это имя переменной, тип значения  которой необходимо определить. Но мы то такую переменную не вводили, и Лисп с возмущением нам об этом сообщает...

А вот теперь начинается самое интересное! Обнаружив ошибку, Лисп переходит а режим отладки, чтобы вы могли попытаться просмотреть содержимое переменных, просмотреть протокол трассировки и т.д. Но достаточно часто причина ошибки понятна и без дополнительной информации, и нам необходимо просто продолжить работу. Проблема у начинающих лисповодов обычно состоит в том, что выйти из этого режима не так-то просто. Чтобы вернуться в режим "нормальной" работы, вам необходимо ввести с клавиатуры последовательность :q - так же, как и в старом добром редакторе vi.

Теперь давайте подробнее поговорим о символах...

Символы

Символы представляют собой объекты Лиспа, которые используются сразу в нескольких целях и имеют ряд очень интересных характеристик. Но основное назначение символов - это использование их в качестве переменных для хранения атомов и любых других структур данных.
Каждый объект типа symbol имеет имя, которое называется его печатным именем. Для любого заданного символа вы можете получить его имя в форме строки. И наоборот, зная имя символа, мы можем, введя это имя в виде строки, получить в сам символ.

Забегая вперед, отметим, что символы не свалены в одну беспорядочную кучу, а распределены по пакетам , в каждом из которых имя символа уникально. Но об этом мы поговорим отдельно.

Символы имеют компонент, называемый списком свойств, который также обозначается как plist. Традиционно этот компонент всегда представляет собой список, в котором элементы с четными номерами (включая первый элемент, который имеет номер 0) являются символами --- именами свойств, а следующие за ними элементы --- значения этих свойств. Для манипулирования списком свойств реализованы специальные функции, которые фактически, позволяют интерпретировать любой символ как расширяемую структуру данных.

Кроме того, символы используются для представления определенных видов переменных Лисп-программ, для чего разработаны также специальные функции.

Как уже указывалось выше, для обращения к символу достаточно указать его имя. Если это имя отлично от пустой строки, и если имя состоит только из прописных букв, цифр или определенных псевдоалфавитных специальных знаков (К которым не относятся скобки и пробел) и если имя этого символа не может быть случайно перепутано с числом, то для обращения к символу достаточно указания последовательности букв, образующих его имя. Любые прописные буквы, которые используются для представления внутреннего имени символа в тексте программы могут быть записаны в любом регистре. Более подробно мы поговорим об этом ниже.
Например:

FROBBOZ                ; Имя этого символа - FROBBOZ

frobboz                ; Другое упоминание того же символа

fRObBoz                ; И это все о нем...

unwind-protect         ; Символ, содержащий в имени букву -

+\$                    ; Символ с именем +\$

1+                     ; Символ с именем 1+

+1                     ; А это число 1, а вовсе не символ!

pascal_style           ; Имя символа содержит знак подчеркивания

b^2-4*a*c              ; Все это один символ!

                       ; В имени содержится несколько специальных букв

file.rel.43            ; А в этом имени символа есть точки

/usr/games/zork        ; Этот символ содержит в имени ``косые''

(a b c)                ; Список из трех символов 

(2.0s0 (a 1) \#\*)     ; Список из трех объектов: короткого числа 

                       ; с плавающей запятой, другого списка и буквы

(a . 4          ; cons-ячейка, car-часть которой является символом,

                ; а  cdr-часть - целое число

(a b c . d)     ; Точечный список с тремя элементами, последняя

                ; cons-ячека содержит в  cdr-части d 

Допускается использовать запись вида (a b . (c d)), которая обозначает то же самое, что и (a b c d). В стандартных программах вывода Лиспа первый формат вывода не используется, но это не мешает вам баловаться ``нестандартным представлением''.

В литературе (к сожалению, преимущественно иностранной, поскольку на русском языке о Лиспе пишут мало) довольно часто термин list используется как по отношению к обычным, так и к точечным спискам. В тех случаях, когда различие между этими типами списков имеет значение, мы будем использовать название ``обычные списки'' по отношению к спискам, заканчивающимся символом NIL. Большинство функций, работающих со списками, ориентированы именно на такие, обычные списки. Поэтому использовать в этих функциях вместо обычных точечные списки как правило не допускается.

Со стороны международного комитета по стандартизации рекомендуется использовать для проверки достижения конца списка предикат endp или его эквивалент. Как правило, эта функция сигнализирует об ошибке, если обнаруженный список заканчивается атомом, отличным от NIL. На самом деле такая экстремистская реакция вовсе не обязательна, поскольку в Лиспе нередко используются циклические списки. В таких ситуациях для проверки достижения конца списка удобнее использовать предикат atom , который воспимет как признак конца списка любой атом, который может быть и не равен nil.

В ряде случаев по отношению к некоторым cons-ячейкам используется термин дерево, если эти ячейки доступны в результате последовательного применения car и cdr преобразований (см. ниже) исходной структуры данных. При этом элементы структуры, отличные от cons-ячеек (то есть такие, к которым нельзя применить функции car и cdr называются листьями дерева.

Списки, точечные списки и деревья не являются взаимоисключающими типами данных. Это просто несколько способов взглянуть на одну и
ту же структуру данных. В качестве примера еще одного альтернативного подхода можно упомянуть ассоциативные списки. Еще раз подчеркну, что ни один из этих терминов не обозначает реальный тип данных в Лиспе. К базовому типу данных относятся только cons-ячейки, а также nil, который является единственным объектом, принадлежащему типу null. Тип данных Лиспа list обозначает только объединение объектов типов
cons и null, и лишь с этой точки зрения к нему могут быть отнесены как обычные, так и точечные списки.

Работа со списками

Понятно, что поскольку списки являются основной "составной" структурой данных, то большая часть функций Лиспа работает именно со списками. Но как ни удивительно, все многообразие функций языка основано на трех китах - трех основных функциях с помощью которых можно реализовать все остальные. Вот эти киты - CAR, CDR и CONS.

CAR

Функция CAR предназначена для извлечения первого элемента списка, который возвращается в качестве ее результата. Например,

(car '(1 2 3 4 5))

вернет 1, а

(car '((1 2 3) (4 5) 6))

вернет список - (1 2 3).

CDR

CDR выполняет "оставшуюся" часть работы - эта функция возвращает список , содержащий все элементы кроме первого. Поэтому, применительно к приведенным выше примерам, вы получите:

(cdr '(1 2 3 4 5))

(2 3 4 5)

(cdr '((1 2 3) (4 5) 6))

((4 5) 6)

Как вы увидите ниже, из этих строительных кирпичиков можно построить действительно интересные конструкции!

CONS

Приведенные выше функции используются для разбиения списка на отдельные фрагменты. А функция CONS, наоборот, производит слияние двух аргументов, формируя из них список, который возвращается в качестве результата.  Функция принимает ровно 2 (!) аргумента, первый из которых используется в качестве CAR-части списка, а второй - в качестве его CDR-части. Это очень важно - первый аргумент рассматривается функцией cons именно как элемент вновь формируемого списка (см. рис.2)

 Производные функции

Теория утверждает (и подтверждается практикой), что для выполнения любых операций со списками достаточно рассмотренных выше функций. Но конечно же, использовать только их не слишком удобно. Достаточно часто возникает необходимость извлечь второй, третий или четвертый элемент списка, либо получить CDR-часть первого элемента списка. Конечно же для решения этих задач программисты разрабатывали специальные функции. Например, для извлечения второго элемента списка можно использовать

(defun cadr (арг)
   (car (cdr арг))
)

Хитрость состоит в том, что подобные функции определять вам не нужно - они входят в состав языка уже лет двадцать пять, как минимум. Более того, их имена стандартизованы, что позволяет их даже не запоминать. Взгляните, например, на приведенное выше определение - выполнение функции осуществляется "справа-налево" - вначале мы выполняем операцию cdr, а потом car к полученному результату. Название функции "проглатывает" конечные и начальные буквы последовательно применяемых функций, в результате чего мы получаем cadr. Аналогичным образом в Common Lisp реализовано десятка два функций, которые позволяют извлечь любой элемент или фрагмент списка глубиной до 4 степеней вложенности. Кроме того, имеется еще одна полезная функция:

(nth i список)

которая возвращает i-й элемент списка (отсчет начинается с нуля). Фактически, с использованием этой функции списки могут интерпретироваться как одномерные массивы.


На этом давайте закончим теоретическую часть урока и перейдем к практическому примеру. Когда-то, во время учебы в физико-математической школе N145 г. Киева я столкнулся с тем, что каждый преподаватель, будь то биология или география, искренне полагал, что именно его предмет является самым важным, и именно на него надо обращать особое внимание. Английский язык не был исключением, и неправильные глаголы нужно было знать наизусть... Поэтому в память о тех деньках я хочу предложить вашему вниманию программу, которая будет анализировать английский глагол в произвольной форме и возвращать его инфинитив. Для тех кто не владеет языком поясню, что как правило, в английском языке глагольные формы образуются приставкой суффикса "s" или "es" для третьего лица настоящего времени (в нашей программе для упрощения не рассматривается) или  суффикса "ed" для форм прошедшего времени. Но дело в том, что в языке имеется также несколько десятков глаголов, которые этому правилу не подчиняются - для них используются специальные формы прошедшего времени. Эти то глаголы и называются неправильными. При построении систем автоматического анализ текстов на естественном языке чаще всего тонкости представления времен особой роли не играют, и нам достаточно использовать инфинитивную форму глагола. Поэтому мы определим функцию, которая и будет решать эту задачу.


Конечно, это не одна единственная функция, а набор, который выглядит следующим образом:

;;;
;;; Программа приведения глагольных форм английского языка
;;; к инфинитиву
;;;
;;; (С) В.Водолазкий,  2002,   http://come.to/vodolaz
;;;

(setq плохие-глаголы
   '(
         ("be" ("was" "were") "been"  "быть")
("become" "became" "become" "стать")
("begin" "began" "begun" "начать")
("blow" "blew" "blown" "дуть")
("break" "broke" "broken" "ломать")
("bring" "brought" "brought" "приносить")
("build" "built" "built" "строить")
("buy" "bought" "bought" "покупать")
("catch" "caught" "caught" "ловить")
("choose" "chose" "chosen" "выбирать")
("come" "came" "come" "приходить")
("cost" "cost" "cost" "стоить")
("cut" "cut" "cut" "резать")
("do"   "did" "done" "делать")
("draw" "drew" "drawn" "рисовать")
("drink"  "drank" "drunk" "пить")
("drive" "drove" "driven" "водить")
("eat" "ate" "eaten" "есть")
("fall" "fell" "fallen" "падать")
("feel" "felt" "felt" "чувствовать")
("fight" "fought" "fought" "бороться")
("find" "found" "found" "находить")
("fly" "flew" "flown" "летать")
("forget" "forgot" "forgotten" "забывать")
("forgive" "forgave" "forgiven" "прощать")
("get" "got" "got" "получать")
("give" "gave" "given" "давать")
("go" "went" "gone" "идти")
("grow" "grew" "grown" "расти")
("have" "had" "had" "иметь")
("hear" "heard" "heard" "слышать")
("hide" "hid" "hidden" "прятать")
("hold" "held" "held" "держать")
("keep" "kept" "kept" "хранить")
("know" "knew" "known" "знать")
("leave" "left" "left" "оставлять")
("lend" "lent" "lent" "одалживать")
("let" "let" "let" "разрешать")
("lose" "lost" "lost" "терять")
("make" "made" "made" "делать")
("mean" "meant" "meant" "означать")
("meet" "met" "met" "встречать")
("pay" "paid" "paid" "платить")
("put" "put" "put" "класть")
("read" "read" "read" "читать")
("ring" "rang" "rung" "звонить")
("rise" "rose" "risen" "подниматься")
("run" "ran" "run" "бежать")
("say" "said" "said" "говорить")
("see" "saw" "seen" "видеть")
("sell" "sold" "sold" "продавать")
         ("send" "sent" "sent" "посылать")
("shake" "shook" "shaken" "трясти")
("shine" "shone" "shone" "сиять")
("show" "showed" "shown" "показывать")
("shut" "shut" "shut" "закрывать")
("sing" "sang" "sung" "петь")
("sit" "sat" "sat" "сидеть")
("sleep" "slept" "slept" "спать")
("speak" "spoke" "spoken" "говорить")
("spend" "spent" "spent" "тратить")
("stand" "stood" "stood" "стоять")
("stick" "stuck" "stuck" "клеить")
("swim" "swam" "swum" "плавать")
("take" "took" "taken" "брать")
("teach" "taught" "taught" "учить")
("tell" "told" "told" "рассказывать")
("think" "thought" "thought" "думать")
("wake" "woke" "woken" "будить")
("wear" "wore" "worn" "носить")
("win" "won" "won" "побеждать")
("write" "wrote" "written" "писать")
   )
)

;;
;; Функции просмотра содержимого списка плохих глаголов
;; и выделения инфинитивной формы
;;

(defun просмотр-плохих (глагол список)
; формируем временную переменную
(setq формы (car список))
; (prin1 глагол)(princ " - ")(prin1 формы)(terpri)
(cond 
  ((equal глагол (car формы)) глагол)        ; это 1 форма
  ((equal глагол (caddr формы)) (car формы)) ; это 3-я форма
  ((equal глагол (cadr формы)) (car формы))  ; это 2-я форма 
  ; особый случай - раздвоенная форма was-were
  ((listp (cadr формы))    
    (cond
     ((equal глагол (car (cadr формы))) (car формы))
     ((equal глагол (cadr (cadr формы))) (car формы))
     ((> (length список) 0 ) (просмотр-плохих глагол (cdr список)))
     )
    ) 
  ; список просмотрен, глагол не найден
  ;рекурсивный просмотр всего списка
  ((> (length список) 0 ) (просмотр-плохих глагол (cdr список)))
  (t break)
)
)


(defun плохой? (глагол)
"Функция последовательно просматривает все содержимое
 структуры плохие-глаголы и возвращает инфинитивную форму
 если глагол оказался плохим или nil, если такой формы в
 таблице не оказалось. Может использоваться как автономный предикат."
 
 (просмотр-плохих глагол плохие-глаголы)
)

;;
;; в случае правильного глагола отрезаем ему суффикс ed
;;

(defun отрезать-суффикс (строка)
  "Функция отрезает суфикс для глагольной формы, преобразуя
   правильный глагол в инфинитив"
   ; простейшее решение 
   (string-right-trim "ed" строка)  
)

;;
;; выделение инфинитива, если глагольная форма не найдена,
;; возвращает исходный глагол с "отрезанным" суффиксом ed
;;
(defun инфинитив (глагол)
  (if (setq результат (плохой? глагол)) 
      результат
      (отрезать-суффикс глагол)
  )
)

Вначале мы определяем список плохие-глаголы, каждый элемент которого представляет собой также список, содержащий инфинитивную форму неправильного глагола, а затем его вторую и третью формы. Завершает список русский перевод глагола (в программе пока не используется).
Чтобы решить задачу нам необходимо понять, с каким глаголом мы имеем дело - с правильным или неправильным. Поэтому мы определяем предикат плохой? , который возвращает инфинитивную форму глагола, если он оказался неправильным (интерпретируется системой как T) или NIL, если такого глагола в списке нет (а следовательно, это правильный глагол).

Обратите внимание на построение функции инфинитив. Проверяя аргумент глагол на принадлежность к числу неправильных, мы помещаем результат проверки в переменную результат. Если ее значение отлично от NIL, то и значение функции setq также будет отлично от NIL. В этом случае функция if вернет в качестве значения переменную результат. Если же переменная результат равна NIL, функция if выполнит оценку следующей формы (ветка else) - и попросту отрежет суффикс у глагола (впрочем, стоит ли повторять текст программы теми же словами :-)).

Для проверки работы функции можно выполнить несколько запросов:

(princ "shown -> ")
(prin1 (инфинитив "shown"))(terpri)
(princ "rose -> ")
(prin1 (инфинитив "rose"))(terpri)
(princ "walked -> ")
(prin1 (инфинитив "walked"))(terpri)

shown -> show

rose  -> rise

walked -> walk