Zerop lisp что это
LISP. Атом первый
Привет, Хабр!
LISP заинтересовал меня уже давно, но, к сожалению, активно использовать свои знания и стремления на практике шанса не было. Скоро новый учебный год, а значит у меня опять будет возможность изучать и, уже второй год, преподавать студентам LISP. Еще одной проблемой, кроме традиционного отсутствия интереса к сложным вещам, кажется отсутствие литературы. Да и вообще, тема LISP-а в интернете, а тем более в рунете освещена слабо. Вот и на Хабре публикаций довольно мало.
Надеюсь, эта статья понравится общественности и откроет серию, повествующую об одном из наиболее интересных и наименее понятных (хотя до brainfuck и далеко) языков программирования – LISP. Ведь, как это не банально, еще один язык — еще одна жизнь
Начнем с базовых понятий LISP-а – атомов и списков. Немного позже, если будет интересно, в приквеле «Атоме нулевом» можно будет более подробно поговорить о философии и причинах возникновения LISP, а так же о современных направлениях его использования.
Краткая история
LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs.
Типы данных
Традиционно в LISP рассматривают два типа атомов: символы и числа. Символы могут обозначать числа, строки, сложные структуры, функции и другие объекты. Ограничения на имена символов зависят от используемого диалекта, но большинство из них не накладывает практически никаких ограничений на используемые в именах символы. Кроме того, опять же в большинстве диалектов, имена символов не зависят от регистра.
Некоторые символы имеют специальное назначение – это константы, встроенные функции, T (true, истина) и NIL (false, ложь).
Числа, в отличии от символов, не могут представлять другие объекты, таким образом число всегда является константным числом. Немного позже мы рассмотрим типы чисел в LISP.
Символы и числа представляют собой наиболее простые объекты LISP – атомы. Второй основной тип данных – точечные пары, которые синтаксически выражаются следующим образом:
Например, точечными парами являются выражения:
Атомы и точечные пары объединяют под общим названием S-выражения (S-expression, symbolic expression). Особым видом S-выражения является список, выражаемый следующим образом:
NIL в большинстве случаев определяется как пустой список, в таком случае определение списка можно переписать следующим образом:
Крылья, ноги… Главное хвост
И голова и хвост являются ключевыми понятиями в списочном контексте 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, предназначенную для блокирования вычисления выражения. Проще всего работу данной функции продемонстрировать простым примером:
Функцию QUOTE можно записать и короче:
Функция CAR
Предназначена для получения первого элемента точечной пары (или же головы списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.
Для удобство головой пустого списка считается NIL.
Фунция CDR
Предназначена для получения второго элемента точечной пары (или же хвоста списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.
Хвостом списка является весь список без первого элемента. Если список состоит из одного элемента, хвостом будет NIL. Хвостом пустого списка для удобства так же считается nil.
Несколько примеров:
Функции CAR и CDR реализованы во всех диалектах LISP, но в некоторых для них созданы и синонимы: FIRST и REST, HEAD и TAIL).
Функция CONS
Фактически функция CONS является антиподом функций CAR и CDR:
Функция ATOM
ATOM и EQ являются предикатами – т.е. функциями, проверяющих соответствие аргумента некоторому свойству и возвращающими T или NIL в зависимости от успешности проверки.
Предикат ATOM проверяет, является ли объект, переданный в качестве аргумента, атомом:
atom (S-выражение)
Функция EQ
Предикат, проверяющий идентичность двух символов.
eq (атом, атом)
Следует помнить, что предикат EQ применим лишь к атомарным аргументам и не может быть использован для списков. Так же не следует использовать EQ при сравнении чисел.
Более общим по сравнению с EQ является предикат EQL, позволяющий сравнивать однотипный числа:
Еще более общим для чисел является предикат =, позволяющий сравнивать значения чисел различных типов:
Более общим для списков является предикат EQUAL, позволяющий сравнивать идентичность двух списков:
Наиболее общим предикатом является EQUALP, позволяющий сравнивать произвольные объекты.
Функция NULL
NULL проверяет, является ли объект, переданный в качестве аргумента, пустым списком:
Судя по двум последним примером, можно сделать вывод, что функцию NULL можно использовать и как логическое отрицание. Для этих же целей в LISP существует и предикат NOT.
Что дальше?
Надеюсь, что смог заинтересовать. В следующий раз я планирую рассказать о существующих диалектах LISP (хотя на первых порах достаточно будет университетского XLisp), менее часто используемых базовых функциях, сворачивании CAR и CDR в что-то вроде CAAAADDAAR и определении собственных функций. Позже — рекурсия, управляющие структуры, область действия, ввод-вывод. Еще позже — если не надоем — о функционалах, макросах, свойствах символов и замыканиях. Ну и конечно, о том, о чем попросит общественность.
До встречи!
LISP — Предикаты
Предикаты — это функции, которые проверяют свои аргументы на наличие определенных условий и возвращают nil, если условие ложно, или если какое-либо значение, не равное nil, условие истинно.
В следующей таблице приведены некоторые из наиболее часто используемых предикатов —
Добавление единицы каждому второму элементу списка