S-выражение
Термин S-выражение или sexp (для символического выражения) относится к соглашению о способе записи полуструктурированных данных (англ.) в доступной для человеческого понимания текстовой форме. Символические выражения создаются, в основном, из символов и списков. S-выражения наиболее известны благодаря их использованию в языках программирования семейства Лисп. Также S-выражения применяют в языках-наследниках Лиспа, таких как DSSSL, и в разметке коммуникационных протоколов вроде IMAP и CBCL Джона Маккарти. Детали синтаксиса и поддерживаемых типов данных отличаются в различных языках, но общая особенность — использование S-выражений как префиксной нотации с использованием скобок (известных как кембриджская польская нотация) .
S-выражения используются в Лиспе как для кода, так и для данных (см. [www-formal.stanford.edu/jmc/recursive/recursive.html Маккарти «Рекурсивные функции символических выражений»]). S-выражения были первоначально предназначены только для представления данных, которыми должны были манипулировать M-выражения, но первая реализация Лиспа была интерпретатором S-выражений, в которые планировалось переводить М-выражения, и программисты Lisp вскоре привыкли к использованию S-выражений как для данных, так и для кода.
S-выражения могут быть как отдельными объектами (атомами), такими как числа, Символ (Lisp) (англ.), включая специальные символы nil
и t
, или точечными парами (англ.), в виде (x . y)
. Более длинные списки, состоящие из вложенных точечных пар, например (1 . (2 . (3 . nil)))
, можно написать более привычным способом, как (1 2 3)
. Вложенные списки также могут быть записаны в виде S-выражений: ((молоко сок) (мёд мармелад))
. S-выражения не зависят от пробелов и разрывов строк, пробелы используются только в качестве разграничителей между атомами.
(((S) (NP) (VP))
((VP) (V))
((VP) (V) (NP))
((V) died)
((V) employed)
((NP) nurses)
((NP) patients)
((NP) Medicenter)
((NP) Dr Chan))
Программный код также может быть записан в виде S-выражения (обычно с использованием префиксной нотации). Небольшой кусочек синтаксического сахара для написания программ на Лиспе заключается в том, что часто используемое выражение (quote x)
может заменить сокращением 'x
Пример на Common Lisp:
(defun factorial (x)
(if (zerop x)
1
(* x (factorial (- x 1)))))
Пример на Scheme:
(define (factorial x)
(if (zero? x)
1
(* x (factorial (- x 1)))))
S-выражения в Лиспе читаются с помощью функции READ. Эта функция читает текстовое представление S-выражения и возвращает Lisp-данные. Функция PRINT может быть использована для вывода S-выражения. То, что возвращает PRINT, можно прочитать с помощью функции READ при условии, что все выводимые объекты данных имеют представление для ввода-вывода. Lisp имеет такое представление для чисел, строк, символов, списков и ещё многих типов данных. Программный код может быть представлен в виде аккуратно форматированного (pretty printed) S-выражения с помощью функции PPRINT.
Lisp программы — это корректные S-выражения, но не все S-выражения являются правильными программами на Lisp. (1.0 + 3.1)
— это корректное S-выражение, но не корректная Lisp-программа, Lisp использует префиксную нотацию, поэтому число с плавающей точкой (1.0) не может быть распознано как операция (первый элемент выражения).
Стандартизация
В мае 1997 года, Рональд Ривест предложил Интернет-проект (англ.) [2] нового RFC. Проект определил синтаксис основанный на S-выражениях Лиспа, но предназначенный для хранения данных общего назначения и обмена ими по аналогии с XML, а не для программирования. Он так и не был утвержден в качестве RFC, но с тех пор цитируется и используется другими документами RFC (например RFC 2693) и в ряде других изданий.[3] Первоначально он был предназначен для использования в SPKI.
Формат Ривеста определяет S-выражение как некую октет-строку (серию байт) или конечный список других S-выражений. Он описывает три формата обмена для выражений с этой структурой. Один из них, «advanced transport» (расширенное транспортное представление), весьма гибок в плане форматирования, и синтаксически похож на выражения Lisp-стиля, но не является идентичным. Расширенное транспортное представление, к примеру, позволяет октет-строкам быть представленными дословно (длина строки, затем двоеточие и вся строка «как есть»), что позволяет избежать символы, шестнадцатеричного или base64 представления, октет-строка может быть размещена непосредственно в качестве «лексемы», если она отвечает определённым условиям. Лексемы Ривеста отличаются от лексем в Lisp тем, что существуют просто для удобства и эстетики, и трактуются так же, как и другие строки, а не имеют конкретный синтаксический смысл. Другой формат обмена данными, предназначенный быть более компактным, и проще анализируемым, а также уникальный для любого абстрактного S-выражения — это «каноническое представление», который допускает только дословные строки и запрещает использование пробелов как элементов форматирования вне строк. Наконец, есть ещё «базовое транспортное представление» (basic transport representation), которое является либо канонической формой, либо те же элементы в кодировке Base64, окруженные скобками, причём последний служит безопасным транспортом для канонически-закодированных S-выражений в системе, которая позволяет изменять пробельные промежутки (например, почтовая система, которая имеет строки 80-строчной ширины, налагаемые на нечто более длинное).
Этот формат не был широко принят к использованию за пределами SPKI. Ривест на своей [theory.lcs.mit.edu/~rivest/sexp.html веб-странице S-выражений] предоставляет исходный код на Си синтаксического анализатора и генератора, которые, теоретически, могут быть использованы в других программы, хотя лицензирование этих программ не ясно. Тем не менее, нет никаких ограничений на независимые реализации работы с этим форматом. Свободную реализацию можно найти по адресам [sexpr.sourceforge.net/ sexpr.sf.net] и [leon.bottou.org/projects/minilisp leon.bottou.org/projects/minilisp].
См. также
- M-выражение
- car и cdr (англ.)
- cons (англ.)
- Канонические S-выражения (англ.)
- Сравнение форматов сериализации данных (англ.)
Напишите отзыв о статье "S-выражение"
Примечания
Отрывок, характеризующий S-выражение
– Нет, я считал ее несправедливою, и не следовал ей, – сказал Пьер так тихо, что ритор не расслышал его и спросил, что он говорит. – Я был атеистом, – отвечал Пьер.– Вы ищете истины для того, чтобы следовать в жизни ее законам; следовательно, вы ищете премудрости и добродетели, не так ли? – сказал ритор после минутного молчания.
– Да, да, – подтвердил Пьер.
Ритор прокашлялся, сложил на груди руки в перчатках и начал говорить:
– Теперь я должен открыть вам главную цель нашего ордена, – сказал он, – и ежели цель эта совпадает с вашею, то вы с пользою вступите в наше братство. Первая главнейшая цель и купно основание нашего ордена, на котором он утвержден, и которого никакая сила человеческая не может низвергнуть, есть сохранение и предание потомству некоего важного таинства… от самых древнейших веков и даже от первого человека до нас дошедшего, от которого таинства, может быть, зависит судьба рода человеческого. Но так как сие таинство такого свойства, что никто не может его знать и им пользоваться, если долговременным и прилежным очищением самого себя не приуготовлен, то не всяк может надеяться скоро обрести его. Поэтому мы имеем вторую цель, которая состоит в том, чтобы приуготовлять наших членов, сколько возможно, исправлять их сердце, очищать и просвещать их разум теми средствами, которые нам преданием открыты от мужей, потрудившихся в искании сего таинства, и тем учинять их способными к восприятию оного. Очищая и исправляя наших членов, мы стараемся в третьих исправлять и весь человеческий род, предлагая ему в членах наших пример благочестия и добродетели, и тем стараемся всеми силами противоборствовать злу, царствующему в мире. Подумайте об этом, и я опять приду к вам, – сказал он и вышел из комнаты.
– Противоборствовать злу, царствующему в мире… – повторил Пьер, и ему представилась его будущая деятельность на этом поприще. Ему представлялись такие же люди, каким он был сам две недели тому назад, и он мысленно обращал к ним поучительно наставническую речь. Он представлял себе порочных и несчастных людей, которым он помогал словом и делом; представлял себе угнетателей, от которых он спасал их жертвы. Из трех поименованных ритором целей, эта последняя – исправление рода человеческого, особенно близка была Пьеру. Некое важное таинство, о котором упомянул ритор, хотя и подстрекало его любопытство, не представлялось ему существенным; а вторая цель, очищение и исправление себя, мало занимала его, потому что он в эту минуту с наслаждением чувствовал себя уже вполне исправленным от прежних пороков и готовым только на одно доброе.
Через полчаса вернулся ритор передать ищущему те семь добродетелей, соответствующие семи ступеням храма Соломона, которые должен был воспитывать в себе каждый масон. Добродетели эти были: 1) скромность , соблюдение тайны ордена, 2) повиновение высшим чинам ордена, 3) добронравие, 4) любовь к человечеству, 5) мужество, 6) щедрость и 7) любовь к смерти.
– В седьмых старайтесь, – сказал ритор, – частым помышлением о смерти довести себя до того, чтобы она не казалась вам более страшным врагом, но другом… который освобождает от бедственной сей жизни в трудах добродетели томившуюся душу, для введения ее в место награды и успокоения.
«Да, это должно быть так», – думал Пьер, когда после этих слов ритор снова ушел от него, оставляя его уединенному размышлению. «Это должно быть так, но я еще так слаб, что люблю свою жизнь, которой смысл только теперь по немногу открывается мне». Но остальные пять добродетелей, которые перебирая по пальцам вспомнил Пьер, он чувствовал в душе своей: и мужество , и щедрость , и добронравие , и любовь к человечеству , и в особенности повиновение , которое даже не представлялось ему добродетелью, а счастьем. (Ему так радостно было теперь избавиться от своего произвола и подчинить свою волю тому и тем, которые знали несомненную истину.) Седьмую добродетель Пьер забыл и никак не мог вспомнить ее.
В третий раз ритор вернулся скорее и спросил Пьера, всё ли он тверд в своем намерении, и решается ли подвергнуть себя всему, что от него потребуется.
– Я готов на всё, – сказал Пьер.
– Еще должен вам сообщить, – сказал ритор, – что орден наш учение свое преподает не словами токмо, но иными средствами, которые на истинного искателя мудрости и добродетели действуют, может быть, сильнее, нежели словесные токмо объяснения. Сия храмина убранством своим, которое вы видите, уже должна была изъяснить вашему сердцу, ежели оно искренно, более нежели слова; вы увидите, может быть, и при дальнейшем вашем принятии подобный образ изъяснения. Орден наш подражает древним обществам, которые открывали свое учение иероглифами. Иероглиф, – сказал ритор, – есть наименование какой нибудь неподверженной чувствам вещи, которая содержит в себе качества, подобные изобразуемой.
Пьер знал очень хорошо, что такое иероглиф, но не смел говорить. Он молча слушал ритора, по всему чувствуя, что тотчас начнутся испытанья.
– Ежели вы тверды, то я должен приступить к введению вас, – говорил ритор, ближе подходя к Пьеру. – В знак щедрости прошу вас отдать мне все драгоценные вещи.
– Но я с собою ничего не имею, – сказал Пьер, полагавший, что от него требуют выдачи всего, что он имеет.
– То, что на вас есть: часы, деньги, кольца…
Пьер поспешно достал кошелек, часы, и долго не мог снять с жирного пальца обручальное кольцо. Когда это было сделано, масон сказал:
– В знак повиновенья прошу вас раздеться. – Пьер снял фрак, жилет и левый сапог по указанию ритора. Масон открыл рубашку на его левой груди, и, нагнувшись, поднял его штанину на левой ноге выше колена. Пьер поспешно хотел снять и правый сапог и засучить панталоны, чтобы избавить от этого труда незнакомого ему человека, но масон сказал ему, что этого не нужно – и подал ему туфлю на левую ногу. С детской улыбкой стыдливости, сомнения и насмешки над самим собою, которая против его воли выступала на лицо, Пьер стоял, опустив руки и расставив ноги, перед братом ритором, ожидая его новых приказаний.
– И наконец, в знак чистосердечия, я прошу вас открыть мне главное ваше пристрастие, – сказал он.
– Мое пристрастие! У меня их было так много, – сказал Пьер.
– То пристрастие, которое более всех других заставляло вас колебаться на пути добродетели, – сказал масон.