[Картонная Армия - от галеры до ракеты!]

Домой Вверх Содержание

Lisp -атомы и списки
Lisp - первые шаги Lisp -атомы и списки Lisp - переменные Lisp - вызов функций Программные блоки Структуры данных

 

 

horizontal rule

В.Водолазкий



Первые шаги в Common Lisp - атомы и списки


В статье рассматриваются основные "строительные кирпичики" языка Лисп - атомы и списки. Показывается, что этих компонентов в общем-то достаточно для решения многих практических задач. Объясняется понятие предиката и работа отдельных управляющих структур.

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

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

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

Конечно, за 40 лет эволюции языка Лисп в нем появилось немало производных типов данных, которые предназначены для решения тех или иных специфичных задач. Сегодня Common Lisp поддерживает работу с разнообразными типами объектов. Это важная оговорка --- в Лиспе тип имеют не переменные, а именно объекты, в которых размещены те или иные данные. При этом любая переменная может иметь в качестве значения объект произвольного типа.

Конечно, вы можете ввести объявление, указывающее на то, что переменная может принимать только ограниченный набор значений. Однако такие ограничения могут быть легко обойдены, но программа при этом все равно будет работать вполне корректно. Поэтому такие объявления используются просто в качестве подсказки системе от пользователя, направленной на повышение эффективности работы интерпретатора Лисп.


Алмазные россыпи - типы данных в Common Lisp

Тип данных в Common Lisp представляет собой множество (возможно, бесконечное), объектов Лиспа. Многие из объектов при этом принадлежат сразу к нескольким подобным множествам, поэтому на практике вопрос ``какому конкретному типу принадлежит тот или иной объект?'' оказывается не всегда корректным. Поэтому обычно вопрос задается иначе: ``Принадлежит ли тот или иной объект некоторому типу?'' Практическое воплощение этого вопроса представляет собой предикат typep, но можно использовать и функцию type-of, которая возвращает тип (или вернее, один из типов), которому принадлежит заданный объект.

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

(defun правильный-размерчик? (арг)
    (if (and (< арг 100) (> арг 50))   арг  nil)
)

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


Типы данных, определенные в Common Lisp, представляют собой частично упорядоченную иерархию, задаваемую в виде отношения подмножеств. Определенные множества объектов, такие как множество чисел или множество строк, используются достаточно часто, чтобы получить собственные обозначения. В качестве этих обозначений используются обычные символы (Под термином символ в Лиспе и в этой статье понимается некий атомарный объект, известный также под названием литерал.

Множество всех объектов объявляется с помощью символа T, который представляет собой сокращение от TRUE (истина). Соответственно, пустой тип данных, который не включает ни одного объекта, объявляется как NIL . Реализован также тип common, в котором объединяются все типы
данных, обязательных для всех реализаций Common Lisp. Впрочем, любая версия может поддерживать и дополнительные типы данных, которые не являются подтипами common. Проверка того или иного типа на принадлежность к этому множеству может быть выполнена с помощью предиката commonp .

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

Перечисленные выше категории, в тех случаях, когда они используются как типы данных, могут рассматриваться как ``реальные'' типы данных; фактически, эти категории формируют полезные срезы в иерархии типов, предназначенные для тех или иных конкретных задач.

Ниже приведены краткие описания различных типов данных Common Lisp. Конечно для практической работы этих знаний маловато, но вы должны по крайней мере представлять с чем придется столкнуться в ходе работы с Лиспом.

Числа в Лиспе, вопреки расхожему мнению о ``слабой поддержке арифметики'' в этом языке представлены широким набором форм и видов представлений. Common Lisp поддерживает полноценную работу с целыми: любое целое число , будь оно положительное или отрицательное, может быть представлено как объект Лиспа. Единственным ограничением на этом пути может служить только общий объем памяти, а не длина машинного слова. В Common Lisp реализована также поддержка дробей - результат деления двух целых чисел, представляет собой дробь, если только он не является целым числом. Точно так же в состав типов данных, поддерживаемых Лиспом, входят и числа с плавающей запятой
различных диапазонов и точностей, а также картезианские комплексные числа, знакомые всем нам по школьному курсу математики.

Буквы представляют собой печатные изображения, повсеместно используемые при форматировании текстов. Строки, в свою очередь, рассматриваются как одномерные массивы, состоящие из букв. В Common Lisp предусмотрена поддержка обширных наборов букв, включая механизмы представления букв различных типов стилей.

Символы (Иногда называемые также атомарными символами , чтобы подчеркнуть специфику их использования) представляют собой именованные объекты данных. Лисп содержит механизмы для выявления объекта по его имени (в формате строки). Символы имеют списки свойств, которые на практике позволяют интерпретировать символы как структуры с расширяемым множеством именованных компонентов, каждый из которых может представлять собой произвольный объект Лиспа. Символы используются также для именования функций и переменных внутри программ.

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

Массивы представляют собой индексированные собрания объектов. Массив может иметь любое неотрицательное число измерений и индексируется последовательностью целых чисел. В общем случае массив может содержать в качестве компонента любой объект Лиспа; однако предусмотрены и некоторые специализированные версии массивов, которые предназначены для хранения элементов только определенных типов. Допускается, чтобы два массива, возможно, имеющие различное количество измерений, использовали один и тот же набор элементов совместно (При этом модификация одного массива приводит к модификации и другого). Эта ситуация используется достаточно часто и называется смещением одного массива относительно другого. Одномерные массивы любого вида называются векторами. Одномерные массивы, содержащие буквы, называются строками. Одномерные массивы битов, то есть целых чисел, которые могут иметь значения только 0 или 1, называются битовыми векторами .

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

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

Пакеты представляют собой коллекции символов, работающих в пределах одного и того же пространства имен. Анализатор распознает принадлежность символов путем сопоставления последовательностей букв, эти имена образующие, с текущим пакетом.

Путевые имена представляют собой имена файлов более или менее независимым от реализации образом. Эти объекты используются для реализации интерфейса с внешней файловой системой.

Потоки представляют собой источники или приемники данных, обычно текста или байтов. Эти объекты используются для выполнения ввода/вывода, также как и для решения отдельных внутренних задач, таких как разбор строк.

Случайные ячейки представляют собой структуры данных, в которых сохраняется состояние встроенного генератора случайных чисел.

Структуры представляют собой записи, определяемые пользователем, которые являются объектами, имеющими именованные компоненты. Для ввода новых типов структур используется механизм defstruct. Некоторые реализации Common Lisp могут также использовать структуры для представления некоторых встроенных типов данных, таких как bignums}, readtables , streams, hash tables, и pathnames, но этот факт остается для
пользователя обычно незаметным.

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

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

Классы определяют структуру и поведение других объектов, которые являются их экземплярами. Любой объект данных Common Lisp принадлежит к тому или иному объекту данных.

Методы представляют собой входящие в состав класс фрагменты кода, которые выполняются с набором аргументов, который удовлетворяет определенному шаблону. Методы не являются, как это можно было бы ожидать, функциями, они не могут вызываться непосредственно с набором аргументов, а лишь встраиваются в обобщенные функции.

Обобщенные функции являются разновидностью функций, которые, наряду с другой информацией, содержат набор методов. При вызове обобщенной функции выполняется некоторое подмножество содержащихся в ней методов. Подмножество, выбираемое для выполнения, определяется ее классом и составом переданных ей аргументов.

Возвращаясь к строительным кирпичикам

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

Атомы

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

(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        ; Этот символ содержит в имени ``косые''

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

+  -  *  /  @  $  %  ^  &  _  =  <  >  ~  .


Некоторые из этих букв используются вполне традиционным образом; например, символы, которые обозначают специальные переменные, обычно имеют имена, начинающиеся и заканчивающиеся звездочкой -  *. Последняя из перечисленных выше букв - точка, рассматривается как буква алфавита, что не позволяет создать имя, состоящее только из точек. Допускается использование только отдельной точки при описании точечных списков и cons-ячеек, но две точки подряд рассматриваются как ошибка.

Печатное имя символа может состоять из прописных, строчных букв или их смеси. что касается латинских букв, то Common Lisp при считывании обычно конвертирует входной поток в прописные буквы. Это приводит к тому, что символы, записанные латиницей к регистру нечувствительны. С кириллицей дел обстоит иначе. Поскольку, с точки зрения Лиспа, вторая половина 8-битной кодовой таблицы букв не содержит, то и преобразовывать из строчных букв в прописные там нечего. Поэтому, вы можете именовать свои символы и кириллицей --- еще раз замечу, что писать программы на русском языке очень приятно и удобно, но должны иметь в виду, что в отличие от традиционного подхода такие имена чувствительны к регистру букв.


В некоторых версиях Common Lisp для преодоления описанного выше ограничения предусмотрена специальная функция readtable-case , управляющая процессом преобразования регистров букв при вводе модулем read. Однако GNU Common Lisp к их числу не относится.

Еще раз отметим, что символы используются в Лиспе для унифицированного представления переменных любых типов. Фактически любому символу может быть присвоено значение любого из рассмотренных выше типов и в любой момент тип значения может быть изменен. В некотором отношении эта вакханалия подобна концепции старого доброго Basic, но в отличие от него вы в любой момент можете проконтролировать тип данных объекта, связанного с тем или иным символом.

Списки и cons-ячейки

Cons ячейка представляет собой запись, состоящую из двух компонентов, которые по традиции называются car и cdr. Обычно эти записи используются для представления списков.

Список представляет собой рекурсивную структуру данных, которая является либо пустым списком, либо cons-ячейку, cdr-частью которой является список. Поэтому список может интерпретироваться как цепочка cons-ячеек, связанных через их cdr-компоненты, и заканчивается символом NIL, соответствующему пустому списку. Компоненты car этих cons-ячеек называются элементами списка. Каждому элементу списка соответствует некоторая cons-ячейка. Пустой список не содержит ни одного элемента.

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


(a b c)                ; Список из трех символов 
(2.0s0 (a 1) \#\*)     ; Список из трех объектов: короткого числа 
                       ; с плавающей запятой, другого списка и буквы


Поэтому пустой список NIL может быть представлен как '(), поскольку представляет собой список без элементов.

Точечный список представляет собой вариант списка, в котором последняя cons-ячейка в cdr-части содержит не NIL, а некоторый другой объект, отличный от cons-ячейки. Название этого списка связано со специальной нотацией, принятой для его записи: элементы списка, как обычно, заключены в скобки, но последний элемент отделяется от предпоследнего не пробелом или иным разделителем, а точкой. В предельном случае так же может быть записана и ``отдельно стоящая'' cons-ячейка, в которой car- и cdr-части заключены в скобки и разделены точкой, окруженной пробелами. Например:

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

Работа функции cons


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

Теория утверждает (и подтверждается практикой), что для выполнения любых операций со списками достаточно рассмотренных выше функций. Но конечно же, использовать только их не слишком удобно. Достаточно часто возникает необходимость извлечь второй, третий или четвертый элемент списка, либо получить 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

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

 

 

horizontal rule

 

 

 

 

Послать письмо voldemarus@narod.ru  
Авторские права © 2003-2010 Картонная армия
Последнее изменение: июля 18, 2010