LISP. Атом первый

    Привет, Хабр!
    LISP заинтересовал меня уже давно, но, к сожалению, активно использовать свои знания и стремления на практике шанса не было. Скоро новый учебный год, а значит у меня опять будет возможность изучать и, уже второй год, преподавать студентам LISP. Еще одной проблемой, кроме традиционного отсутствия интереса к сложным вещам, кажется отсутствие литературы. Да и вообще, тема LISP-а в интернете, а тем более в рунете освещена слабо. Вот и на Хабре публикаций довольно мало.

    Надеюсь, эта статья понравится общественности и откроет серию, повествующую об одном из наиболее интересных и наименее понятных (хотя до brainfuck и далеко) языков программирования – LISP. Ведь, как это не банально, еще один язык — еще одна жизнь

    Начнем с базовых понятий LISP-а – атомов и списков. Немного позже, если будет интересно, в приквеле «Атоме нулевом» можно будет более подробно поговорить о философии и причинах возникновения LISP, а так же о современных направлениях его использования.

    Краткая история


    LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs.

    Чем же отличается LISP от традиционных языков программирования? Рассмотрим ключевые особенности:
    • Формы представления программ и обрабатываемых данных в 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 – атомы. Второй основной тип данных – точечные пары, которые синтаксически выражаются следующим образом:

    <точечная пара> ::= (<атом | точечная пара>.<атом | точечная пара>)

    Например, точечными парами являются выражения:

    (a.b), (a.(b.c)), ((a.b).(c.NIL)).

    Атомы и точечные пары объединяют под общим названием S-выражения (S-expression, symbolic expression). Особым видом S-выражения является список, выражаемый следующим образом:

    <список> ::= NIL | (<S-выражение>.<список>)

    NIL в большинстве случаев определяется как пустой список, в таком случае определение списка можно переписать следующим образом:

    <список> ::= <пустой список> | (<голова>.<хвост>)
    <пустой список> :: = NIL
    <голова> ::= <S-выражение>
    <хвост> ::= <список>.


    Крылья, ноги… Главное хвост



    И голова и хвост являются ключевыми понятиями в списочном контексте LISP. Первый элемент списка именуется головой списка, все остальные элементы – хвостом. Для работы с головой и хвостом существует набор базовых функций, рассмотренный немного ниже.
    Пустой список эквивалентен паре пустых скобок:
    NIL <-> ().
    Непустой список, состоящий из элементов a1, a2, a3… в соответствии с правилами записи S-выражений может быть записан следующим образом:

    (a1.(a2.(a3…))) <-> (a1,a2,a3…)

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

    P.S. Критикуйте, но не слишком, публикуюсь впервые :)
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 64

      +6
      Спасибо, давно хотел почитать про Lisp!
        +1
        Мне нравится, когда пишут в таком конкретном и точном стиле, как у вас. Я бы почитал, чтобы покрыть пробелы в знаниях. Для того, чтобы привлечь внимание аудитории, посоветовал бы написать небольшие примеры, которые показывают преимущества лиспа. Ну и бэнчмарки)
          0
          к черту диалекты — это можно нагуглить. Хочется макросов, хороших и разных! :)
            +3
            Перенесите, например, в «Языки программирования». Этой статье место на главной, а не затерянной в личном блоге.
              +2
              Спасибо. Перенес, накопив кармы.
                0
                Почему же не в блог «Lisp»?
              +4
              Перевод Practical Common Lisp, очень неплохой учебник, по нему сейчас изучаю
                +1
                Кстати, там очень неплохо написано про макросы ;)
                  0
                  «Листал» немного электронную английскую версию. Книжка отличная, но все таки именно по Common Lisp-у, а не по Лиспу вообще.
                    +2
                    Это плохо? Я думаю, кроме него сейчас можно встретить только емаксовский диалект да AutoLisp, нет?
                    А вообще я больше пишу на SKILL, это диалект лиспа, используемый в САПР Cadence. В некоторой степени радует то, что он одновременно умеет и алгебраическую, и префиксную нотацию — уж когда как удобней :)
                      0
                      >кроме него сейчас можно встретить только емаксовский диалект да AutoLisp, нет?
                      Нет конечно, scheme не забываем.
                      • UFO just landed and posted this here
                          0
                          Много кого удивляет, ведь мог бы занять нишу питона и раби :) Скажем так основные факторы это отпугивающий непосвящённых синтаксис, не самая лучшая стандартизация и маленькое коммьюнити.
                          Зато Scheme любимый язык для написания компиляторов Scheme :) Серьёзно, очень хороший язык для изучения компиляции, последнии главы sicp это подтверждают.
                      0
                      А что вам ещё нужно? Ну да, есть ещё Scheme и Clojure. AutoLisp — это такое убожество, в нём от лиспа остались только скобки. Даже макросов нет (замыкания-то хоть есть, интересно?). А нет макросов — нет Лиспа. Насчёт SKILL не знаю, что за зверь.
                    +2
                    Замечательная книга про Лисп — «On LISP» Пола Грэхема (одного из известнейших Лисп-хакеров): www.paulgraham.com/onlisptext.html
                    Кстати, Грэхем в своё время написал первый в мире SaaS — Viaweb, причём именно на Лиспе.
                      +2
                      Согласен, «On Lisp» — одна из лучших!
                        0
                        progn.podzone.net:3000/book

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

                        +2
                        Лично я в свое время изучал лисп по книжкам Э.Хювёнена и И. Сеппянена: «Мир лиспа» (том первый и второй).
                        Язык интересный. Хотел помочь просящим примерами, но не нашел их у себя :( Я конечно еще поищу и, если найду, выложу.
                          0
                          Очаровательная книжка, помню такую. Еще в универе из библиотеки вытащил древнюю такую брошюрку :)
                            +1
                            info.fenster.name/clisp/lisp1.pdf
                            info.fenster.name/clisp/lisp2.pdf

                            Вот, нашёл у своего семинариста на страничке =)
                            +4
                            Спасибо. побольше бы таких добротных и умных постов в этом море копипаста.
                              +1
                              Большое спасибо! Надеюсь, серия будет продолжаться.
                                0
                                LISP — язык хороший, но есть несколько факторов, из-за которых я на нем до сих пор ничего не пишу.
                                Основной из них заключается в том, что я не могу что то делать бесплатно :) как бы уже привык, что знаю на нужном уровне java и с++ и на них пишу, если что то другое нужно заказчику, то делаю (и изучаю) это за их счет. Если бы была (или будет) возможность на практике на рабочем живом проекте заняться этим языком, то я бы это сделал с удовольствием.
                                Автору спасибо за пост, было интересно ознакомиться.
                                  +2
                                  Можно я задам каверзный вопрос, раз уж все упирается в бабло? Можно? Спасибо :)

                                  Вопрос: во сколько Вы себя оцениваете как лиспер?
                                  • UFO just landed and posted this here
                                    0
                                    Я правильно понял что раз «активно использовать свои знания и стремления на практике шанса не было», вы решили преподавать его студентам?
                                      0
                                      При всем желании, одного моего решения было бы явно недостаточно :)
                                      +1
                                      Интересно, очень интересно. Давно на нем не писал

                                      Автор пользовался Емаксом? Я специально для написания прилады под программу изучал Лисп в целом и Elisp в частности.
                                        –5
                                        Ядро LISP, написанное на LISP, занимает менее 200 строк
                                        Ядро Ruby, написанное на Ruby, занимает всего одну строку — eval
                                          –1
                                          Вы понимаете разницу между eval и полноценным интерпретатором/компилятором?
                                            0
                                            а Вы понимаете, что ядро лисп на самом деле — это тот же eval, который занимает 200 строчек, а не полноценный интерпретатор/компилятор?
                                              0
                                              Согласен, с «полноценным» я погорячился :)
                                                0
                                                Есть замечательная книжечка: Lisp In Small Pieces. — собственно, книжка про eval в лиспах :)
                                                  0
                                                  Благодарю, давно к ней присматривался. Теперь после получения рекомендаций уж грех не купить.
                                                0
                                                Хех, видел интерпретатор подмножества Scheme (бОльшей его части, но не всего) на Haskell, там что-то около 400 строк.
                                                  0
                                                  Этот интерпретатор описан в учебнике по Хаскелю. Книжка называется Write Yourself a Scheme in 48 Hours ;-)
                                              0
                                              Во многих (во всех?) диалектах лиспа тоже есть функция eval. Сюрприз. Однако речь как бы не об этом. А ваш коммент из разряда «Зачем таблица умножения, если есть калькулятор».
                                              • UFO just landed and posted this here
                                                  0
                                                  Не катит, лисп компилируемый язык. И это ядро в 200 строк не тащит за собой интерпретатор. А на руби?
                                                  Ну и не забываем, что интерпретатор лиспа на Си++ будет занимать строк 500-600.
                                                  0
                                                  danteus, хорошая статья, в последующих обязательно нужно написать про slime.
                                                    0
                                                    Про предикат NULL лучше бы написать тоже в этой статье, который с NIL сравнивает :) Было бы весьма к месту. В целом — хорошо, легко и понятно :)
                                                      0
                                                      Спасибо, добавил
                                                    • UFO just landed and posted this here
                                                        0
                                                        Лисп и его понятия могут сначала показаться немного непривычными, но после пары-тройки вечеров и экспериментов, и написания первого собственного интерпретатора Лиспа на Лиспе же — все оказывается очень просто.

                                                        Хотя полное погружение в CLisp — другой разговор. Easy to learn, hard to master :)
                                                        • UFO just landed and posted this here
                                                            0
                                                            О решаемых задачах я постараюсь рассказать в одной из следующих публикаций.
                                                            • UFO just landed and posted this here
                                                              0
                                                              Что запрограммируете, то и решит :)
                                                          0
                                                          Всем спасибо за отзывы, критику и поддержку.
                                                            0
                                                            Скажите, в каких областях применяется Лисп, или просто функциональные языки программирования?
                                                            Я слышал, что на Эрланге пишут торговые системы для бирж. Но, насколько я понимаю, выбор Эрлагна обусловлен его возможностями, раскрывающимися в многопоточных приложениях.
                                                            Спасибо.
                                                            +1
                                                            Написание «LISP» уже давно вышло из моды. Lisp и только Lisp! :)
                                                              0
                                                              Долго выбирал между LISP, Lisp и Лисп, в результате выбрал наиболее классическое написание.
                                                              Но в следующих статьях буду выбирать между Lisp и Лисп, спасибо :)
                                                            • UFO just landed and posted this here
                                                              • UFO just landed and posted this here
                                                                • UFO just landed and posted this here
                                                                    +1
                                                                    Нет кода кроме функций и lambda пророк его ;-)
                                                                    • UFO just landed and posted this here
                                                                    0
                                                                    Сборку мусора придумал Маккарти в 1959 (Mark'n'Sweep, если не ошибаюсь), а не сотрудники исследовательского центра Xerox. Может, они придумали какие-то другие алгоритмы, но используем сборщики мусора мы скорее благодаря Маккарти.

                                                                    Да, и почему ничего не упомянуто про макросы и метапрограммирование?
                                                                      0
                                                                      Подскажите IDE под Лисп. Лет 13 назад писал на лиспе для автокада, а других сред под него не знаю.
                                                                      0
                                                                      сколько можно статей типа «смотрите дети — это лисп, в нем много скобочек».

                                                                      интересно было бы если бы автор описал как хорошо/плохо в лиспе с библиотеками, с деплойментом, поделился опытом в написании какой-то сложной подсистемы, взаимодействии с другими языками, потому что любой человек, который действительно хочет познакомится с языком сделает это без статьи на хабре, а из всех кто пишет — «о, лисп, экзотичненько, надо будет пописать» сделают шаги в этом направлении единицы.
                                                                        0
                                                                        Спасибо за хорошую статью.

                                                                        Only users with full accounts can post comments. Log in, please.