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-выражения[1]: 
(((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].

См. также

Напишите отзыв о статье "S-выражение"

Примечания

  1. ↑ Gazdar / MelisH, Natural Language Processing in Lisp
  2. ↑ theory.lcs.mit.edu/~rivest/sexp.txt
  3. ↑ [scholar.google.com/scholar?hl=en&lr=&safe=off&q=rivest+sexp&btnG=Search rivest sexp — Google Scholar]

Отрывок, характеризующий S-выражение

– Нет, я считал ее несправедливою, и не следовал ей, – сказал Пьер так тихо, что ритор не расслышал его и спросил, что он говорит. – Я был атеистом, – отвечал Пьер.
– Вы ищете истины для того, чтобы следовать в жизни ее законам; следовательно, вы ищете премудрости и добродетели, не так ли? – сказал ритор после минутного молчания.
– Да, да, – подтвердил Пьер.
Ритор прокашлялся, сложил на груди руки в перчатках и начал говорить:
– Теперь я должен открыть вам главную цель нашего ордена, – сказал он, – и ежели цель эта совпадает с вашею, то вы с пользою вступите в наше братство. Первая главнейшая цель и купно основание нашего ордена, на котором он утвержден, и которого никакая сила человеческая не может низвергнуть, есть сохранение и предание потомству некоего важного таинства… от самых древнейших веков и даже от первого человека до нас дошедшего, от которого таинства, может быть, зависит судьба рода человеческого. Но так как сие таинство такого свойства, что никто не может его знать и им пользоваться, если долговременным и прилежным очищением самого себя не приуготовлен, то не всяк может надеяться скоро обрести его. Поэтому мы имеем вторую цель, которая состоит в том, чтобы приуготовлять наших членов, сколько возможно, исправлять их сердце, очищать и просвещать их разум теми средствами, которые нам преданием открыты от мужей, потрудившихся в искании сего таинства, и тем учинять их способными к восприятию оного. Очищая и исправляя наших членов, мы стараемся в третьих исправлять и весь человеческий род, предлагая ему в членах наших пример благочестия и добродетели, и тем стараемся всеми силами противоборствовать злу, царствующему в мире. Подумайте об этом, и я опять приду к вам, – сказал он и вышел из комнаты.
– Противоборствовать злу, царствующему в мире… – повторил Пьер, и ему представилась его будущая деятельность на этом поприще. Ему представлялись такие же люди, каким он был сам две недели тому назад, и он мысленно обращал к ним поучительно наставническую речь. Он представлял себе порочных и несчастных людей, которым он помогал словом и делом; представлял себе угнетателей, от которых он спасал их жертвы. Из трех поименованных ритором целей, эта последняя – исправление рода человеческого, особенно близка была Пьеру. Некое важное таинство, о котором упомянул ритор, хотя и подстрекало его любопытство, не представлялось ему существенным; а вторая цель, очищение и исправление себя, мало занимала его, потому что он в эту минуту с наслаждением чувствовал себя уже вполне исправленным от прежних пороков и готовым только на одно доброе.
Через полчаса вернулся ритор передать ищущему те семь добродетелей, соответствующие семи ступеням храма Соломона, которые должен был воспитывать в себе каждый масон. Добродетели эти были: 1) скромность , соблюдение тайны ордена, 2) повиновение высшим чинам ордена, 3) добронравие, 4) любовь к человечеству, 5) мужество, 6) щедрость и 7) любовь к смерти.
– В седьмых старайтесь, – сказал ритор, – частым помышлением о смерти довести себя до того, чтобы она не казалась вам более страшным врагом, но другом… который освобождает от бедственной сей жизни в трудах добродетели томившуюся душу, для введения ее в место награды и успокоения.
«Да, это должно быть так», – думал Пьер, когда после этих слов ритор снова ушел от него, оставляя его уединенному размышлению. «Это должно быть так, но я еще так слаб, что люблю свою жизнь, которой смысл только теперь по немногу открывается мне». Но остальные пять добродетелей, которые перебирая по пальцам вспомнил Пьер, он чувствовал в душе своей: и мужество , и щедрость , и добронравие , и любовь к человечеству , и в особенности повиновение , которое даже не представлялось ему добродетелью, а счастьем. (Ему так радостно было теперь избавиться от своего произвола и подчинить свою волю тому и тем, которые знали несомненную истину.) Седьмую добродетель Пьер забыл и никак не мог вспомнить ее.
В третий раз ритор вернулся скорее и спросил Пьера, всё ли он тверд в своем намерении, и решается ли подвергнуть себя всему, что от него потребуется.
– Я готов на всё, – сказал Пьер.
– Еще должен вам сообщить, – сказал ритор, – что орден наш учение свое преподает не словами токмо, но иными средствами, которые на истинного искателя мудрости и добродетели действуют, может быть, сильнее, нежели словесные токмо объяснения. Сия храмина убранством своим, которое вы видите, уже должна была изъяснить вашему сердцу, ежели оно искренно, более нежели слова; вы увидите, может быть, и при дальнейшем вашем принятии подобный образ изъяснения. Орден наш подражает древним обществам, которые открывали свое учение иероглифами. Иероглиф, – сказал ритор, – есть наименование какой нибудь неподверженной чувствам вещи, которая содержит в себе качества, подобные изобразуемой.
Пьер знал очень хорошо, что такое иероглиф, но не смел говорить. Он молча слушал ритора, по всему чувствуя, что тотчас начнутся испытанья.
– Ежели вы тверды, то я должен приступить к введению вас, – говорил ритор, ближе подходя к Пьеру. – В знак щедрости прошу вас отдать мне все драгоценные вещи.
– Но я с собою ничего не имею, – сказал Пьер, полагавший, что от него требуют выдачи всего, что он имеет.
– То, что на вас есть: часы, деньги, кольца…
Пьер поспешно достал кошелек, часы, и долго не мог снять с жирного пальца обручальное кольцо. Когда это было сделано, масон сказал:
– В знак повиновенья прошу вас раздеться. – Пьер снял фрак, жилет и левый сапог по указанию ритора. Масон открыл рубашку на его левой груди, и, нагнувшись, поднял его штанину на левой ноге выше колена. Пьер поспешно хотел снять и правый сапог и засучить панталоны, чтобы избавить от этого труда незнакомого ему человека, но масон сказал ему, что этого не нужно – и подал ему туфлю на левую ногу. С детской улыбкой стыдливости, сомнения и насмешки над самим собою, которая против его воли выступала на лицо, Пьер стоял, опустив руки и расставив ноги, перед братом ритором, ожидая его новых приказаний.
– И наконец, в знак чистосердечия, я прошу вас открыть мне главное ваше пристрастие, – сказал он.
– Мое пристрастие! У меня их было так много, – сказал Пьер.
– То пристрастие, которое более всех других заставляло вас колебаться на пути добродетели, – сказал масон.


Источник — «http://wiki-org.ru/wiki/index.php?title=S-выражение&oldid=67271655»