Lisps выражения и списки
Обновлено: 22.12.2024
Привет, Хабр!
LISP заинтересовал меня уже давно, но, к сожалению, активно использовать свои знания и стремления на практике шанса не было. Скоро новый учебный год, а значит у меня опять будет возможность изучать и, уже второй год, преподавать студентам LISP. Еще одной проблемой, кроме традиционного отсутствия интереса к сложным вещам, кажется отсутствие литературы. Да и вообще, тема LISP-а в интернете, а тем более в рунете освещена слабо. Вот и на Хабре публикаций довольно мало.
Надеюсь, эта статья понравится общественности и откроет серию, повествующую об одном из наиболее интересных и наименее понятных (хотя до brainfuck и далеко) языков программирования – LISP. Ведь, как это не банально, еще один язык — еще одна жизнь
Начнем с базовых понятий LISP-а – атомов и списков. Немного позже, если будет интересно, в приквеле «Атоме нулевом» можно будет более подробно поговорить о философии и причинах возникновения LISP, а так же о современных направлениях его использования.
Краткая история
LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs.
- Формы представления программ и обрабатываемых данных в LISP идентичны и являются списочными структурами. В связи с этим открывается несколько интересных возможностей – например, обработка программой других программ. Не говоря уже об универсальности, расширяемости и масштабируемости самого синтаксиса. Ядро LISP, написанное на LISP, занимает менее 200 строк, а интерпретатор ПРОЛОГа – чуть более 50 строк.
- Реализация списков позволяет не задумываться об управлении памятью, резервировании и освобождение ячеек происходит динамически. Таким образом можно говорить о появлении сборщика мусора уже в первых версиях LISP.
LISP не является строго типизированным языком программирования. Сегодня это мало кого удивит, однако стоит напомнить, что на начальным этапах данная концепция противостояла строготипизированному Фортрану. - Префиксная нотация дает широкие возможности для синтаксического анализа выражений, а так же обеспечивает возможность использования единого списочного контекста для программ и данных.
- Использование огромного количества скобок. Именно поэтому наряду с традиционной расшифровкой LISP (LISt Processing) существует и Lots of Idiotic Silly Parentheses.
- Не следует забывать про существования LISP-машин – вычислительных машин, архитектура которых оптимизирована для эффективного выполнения программ на языке LISP. LISP-машины не слишком распространены, по некоторым данным их количество во всем мире не превышает 10000. (Насколько мне известно, в Украине нет ни одной. Лично я видел за свою жизнь лишь одну – в Бухарестском университете, активно используемые на лабораторных работах студентами). LISP-машины исследовательского центра Xerox стали прародителями некоторых распространенных идей и технологий: сборка мусора, лазерная печать, многооконные системы и т.д.). Надеюсь, у меня появится шанс поговорить об этом подробнее в одном из следующих выпусков.
Типы данных
Традиционно в LISP рассматривают два типа атомов: символы и числа. Символы могут обозначать числа, строки, сложные структуры, функции и другие объекты. Ограничения на имена символов зависят от используемого диалекта, но большинство из них не накладывает практически никаких ограничений на используемые в именах символы. Кроме того, опять же в большинстве диалектов, имена символов не зависят от регистра.
Некоторые символы имеют специальное назначение – это константы, встроенные функции, T (true, истина) и NIL (false, ложь).
Числа, в отличии от символов, не могут представлять другие объекты, таким образом число всегда является константным числом. Немного позже мы рассмотрим типы чисел в LISP.
Символы и числа представляют собой наиболее простые объекты LISP – атомы. Второй основной тип данных – точечные пары, которые синтаксически выражаются следующим образом:
<точечная пара> ::= (<атом | точечная пара>.<атом | точечная пара>)
Например, точечными парами являются выражения:
Атомы и точечные пары объединяют под общим названием S-выражения (S-expression, symbolic expression). Особым видом S-выражения является список, выражаемый следующим образом:
<список> ::= NIL | (<S-выражение>.<список>)
NIL в большинстве случаев определяется как пустой список, в таком случае определение списка можно переписать следующим образом:
<список> ::= <пустой список> | (<голова>.<хвост>)
<пустой список> :: = NIL
<голова> ::= <S-выражение>
<хвост> ::= <список>.
Крылья, ноги… Главное хвост
И голова и хвост являются ключевыми понятиями в списочном контексте LISP. Первый элемент списка именуется головой списка, все остальные элементы – хвостом. Для работы с головой и хвостом существует набор базовых функций, рассмотренный немного ниже.
Пустой список эквивалентен паре пустых скобок:
NIL <-> ().
Непустой список, состоящий из элементов a1, a2, a3… в соответствии с правилами записи S-выражений может быть записан следующим образом:
В LISP список можно записать и последовательностью элементов, заключенных в скобки и разделенных пробелами. По большему счету, список – это многоуровневая структура данных, для которой архиважна последовательность открывающих и закрывающих скобок.
Элементами списка могут быть атомы и списки, в том числе и пустой список. Например, () – пустой список, а (NIL) – список, состоящий из одного элемента NIL – что эквивалентно (()).
Следует понимать, что обычный синтаксис S-выражений может использоваться наравне со списочным синтаксисом, например, следующие выражение эквивалентны:
(a.(b.nil)), (a b.nil), (a b nil), (a b)
Если кому-нибудь интересно – можно будет рассказать и о внутреннем представлении списков в памяти. Это вполне самостоятельная и по интересу и по объему тема.
Основные функции и предикаты
В LISP существует довольно небольшой набор примитивных функций, обеспечивающий полноценную возможность обработки списков. В контексте списочных структур данные функции являются аналогом основных арифметических действий и образуют некую систему правил, к которой сводятся абсолютно все символьные вычисления.
Традиционном к базовым функциям относят QUOTE, CAR, CDR, CONS, ATOM, EQ.
Функция QUOTE
Для начала рассмотрим функцию QUOTE, предназначенную для блокирования вычисления выражения. Проще всего работу данной функции продемонстрировать простым примером:
(+ 5 10) -> 15 ; происходит вычисления выражения 5+10 и вывод результата
(quote (+ 5 10)) -> (+5 10) ; вычисление блокируется
Функцию QUOTE можно записать и короче:
‘(+ 5 10) -> (+ 5 10) ; ‘ – равноценно quote
Функция CAR
Предназначена для получения первого элемента точечной пары (или же головы списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.
car (список) -> S-выражение.
(car ‘(a b c)) -> a
(car ‘(a)) -> a
(car ‘a) -> ERROR: a is not a list
(car ‘(nil)) -> nil
(car nil) -> nil
(car ‘(nil a)) -> nil
Для удобство головой пустого списка считается NIL.
Фунция CDR
Предназначена для получения второго элемента точечной пары (или же хвоста списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.
cdr (список) -> список
Хвостом списка является весь список без первого элемента. Если список состоит из одного элемента, хвостом будет NIL. Хвостом пустого списка для удобства так же считается nil.
Несколько примеров:
(cdr ‘(a b c)) -> (b c)
(cdr ‘(a)) -> nil
(cdr ‘a) -> ERROR: a is not a list
(cdr ‘(a (b c))) -> ((b c))
(cdr ‘(nil a)) -> (a)
(cdr ()) -> nil
Функции CAR и CDR реализованы во всех диалектах LISP, но в некоторых для них созданы и синонимы: FIRST и REST, HEAD и TAIL).
Функция CONS
Предназначена для создания нового списка из переданных ей в качестве аргументов головы и хвоста:
cons (s-выражение, список) -> список
(cons ‘a ‘(b c)) -> (a b c)
(cons ‘a nil) -> (a)
(cons nil ‘(b c)) ->(nil b c)
(cons nil nil) ->(nil)
(cons ‘(a b) ‘(c)) ->((a b) c)
Фактически функция CONS является антиподом функций CAR и CDR:
(cons (car '(a b c)) (cdr '(a b c))) -> (a b c)
Функция ATOM
ATOM и EQ являются предикатами – т.е. функциями, проверяющих соответствие аргумента некоторому свойству и возвращающими T или NIL в зависимости от успешности проверки.
Предикат ATOM проверяет, является ли объект, переданный в качестве аргумента, атомом:
atom (S-выражение)
(atom ‘a) -> t
(atom ‘(a b c)) -> nil
(atom ()) -> t ;Т.к. пустой список равен nil, а следовательно атомарен
Функция EQ
Предикат, проверяющий идентичность двух символов.
eq (атом, атом)
(eq ‘a ‘b) -> nil
(eq ‘a ‘a) -> t
(eq ‘a (car ‘(a b)) -> t
(eq () nil) -> t
Следует помнить, что предикат EQ применим лишь к атомарным аргументам и не может быть использован для списков. Так же не следует использовать EQ при сравнении чисел.
Более общим по сравнению с EQ является предикат EQL, позволяющий сравнивать однотипный числа:
(eq 1.0 1.0) -> nil
(eql 1.0 1.0) -> t
Еще более общим для чисел является предикат =, позволяющий сравнивать значения чисел различных типов:
(eql 1 1.0) -> nil
(= 1 1.0) -> t
Более общим для списков является предикат EQUAL, позволяющий сравнивать идентичность двух списков:
(equal ‘a ‘a) -> t
(equal ‘(a b) ‘(a b)) -> t
Наиболее общим предикатом является EQUALP, позволяющий сравнивать произвольные объекты.
Функция NULL
NULL проверяет, является ли объект, переданный в качестве аргумента, пустым списком:
(null ‘()) -> t
(null ‘(a b c)) -> nil
(null nil) -> t
(null t) -> nil
Судя по двум последним примером, можно сделать вывод, что функцию NULL можно использовать и как логическое отрицание. Для этих же целей в LISP существует и предикат NOT.
Что дальше?
Надеюсь, что смог заинтересовать. В следующий раз я планирую рассказать о существующих диалектах LISP (хотя на первых порах достаточно будет университетского XLisp), менее часто используемых базовых функциях, сворачивании CAR и CDR в что-то вроде CAAAADDAAR и определении собственных функций. Позже — рекурсия, управляющие структуры, область действия, ввод-вывод. Еще позже — если не надоем — о функционалах, макросах, свойствах символов и замыканиях. Ну и конечно, о том, о чем попросит общественность.
До встречи!
Читайте также: