Lisps выражения и списки

Обновлено: 21.11.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 и определении собственных функций. Позже — рекурсия, управляющие структуры, область действия, ввод-вывод. Еще позже — если не надоем — о функционалах, макросах, свойствах символов и замыканиях. Ну и конечно, о том, о чем попросит общественность.
До встречи!

Читайте также: