S-выражение
(* 2 (+ 3 4)) В компьютерном программировании ( S-выражение или символическое выражение , сокращенно sexpr или sexp ) представляет собой выражение в одноименной нотации для данных вложенного списка ( с древовидной структурой). S-выражения были изобретены и популяризированы языком программирования Lisp , который использует их как для исходного кода, так и для данных.
Характеристики
[ редактировать ]В обычном синтаксисе Lisp, заключенном в круглые скобки, S-выражение определяется классически. [1] как
- атом формы
x, или - выражение формы
(x . y)где x и y — S-выражения.
Это определение отражает представление списка в LISP как серии «ячеек», каждая из которых представляет собой упорядоченную пару . В простых списках y указывает на следующую ячейку (если она есть), образуя таким образом список . Рекурсивная двоичное часть определения означает, что и это представление, и нотация S-выражения могут представлять любое дерево . Однако представление в принципе может допускать циклические ссылки, и в этом случае структура вообще не является деревом, а циклическим графом , и не может быть представлена в классической нотации S-выражения. если не предусмотрено соглашение о перекрестных ссылках (аналог внешних ключей SQL , SGML / XML IDREF и т. д.). Современные диалекты Lisp, такие как Common Lisp. [2] и схема [3] обеспечить такой синтаксис с помощью меток данных , с помощью которых можно помечать объекты, которые затем могут повторяться в другом месте, указывая на общую, а не дублированную структуру, позволяя считывателю или принтеру обнаруживать и, таким образом, запускать оценку или отображение циклов без бесконечной рекурсии.
#n=(x y . #n#)
Определение атома варьируется в зависимости от контекста; в оригинальном определении Джона Маккарти , [1] предполагалось, что существует «бесконечное множество различимых атомарных символов », представленных как «строки заглавных латинских букв и цифр с одиночными встроенными пробелами» (подмножество строк символов и числовых литералов ).
Большинство современных нотаций sexpr допускают более общие строки в кавычках (например, включая знаки препинания или полный Unicode ) и используют сокращенную нотацию для представления списков, содержащих более двух членов, так что
(x y z)
означает
(x . (y . (z . NIL)))
NIL конца списка — это специальный объект (альтернативно записанный (), которое является единственным представлением в Scheme [4] ).
В семействе языков программирования Lisp S-выражения используются для представления как исходного кода, так и данных. S-выражения также используются в языках, производных от Lisp, таких как DSSSL , а также в качестве разметки в протоколах связи, таких как IMAP и Маккарти Джона CBCL . Он также используется в качестве текстового представления WebAssembly . Детали синтаксиса и поддерживаемых типов данных различаются в разных языках, но наиболее общей особенностью этих языков является использование S-выражений и префиксной записи.
Типы данных и синтаксис
[ редактировать ]Существует множество вариантов формата S-выражений, поддерживающих различные синтаксисы для разных типов данных. Наиболее широко поддерживаются:
- Списки и пары :
(1 () (2 . 3) (4)) - Символы :
with-hyphen?@!$|a symbol with spaces| - Строки :
"Hello, world!" - Целые числа :
-9876543210 - Числа с плавающей запятой :
-0.06.283186.022e23
Персонаж # часто используется для префикса расширений синтаксиса, например #x10 для шестнадцатеричных целых чисел или #\C для персонажей.
Использование в Лиспе
[ редактировать ]При представлении исходного кода в Lisp первым элементом S-выражения обычно является имя оператора или функции, а все остальные элементы рассматриваются как аргументы. Это называется «префиксной записью» или « польской записью ». Например, логическое выражение, записанное 4 == (2 + 2) в C представляется как (= 4 (+ 2 2)) в префиксной нотации Lisp на основе s-expr.
Как отмечалось выше, точное определение «атома» различается в разных LISP-подобных языках. Строка в кавычках обычно может содержать что угодно, кроме кавычек, тогда как атом идентификатора без кавычек обычно может содержать что угодно, кроме кавычек, пробелов, скобок, скобок, фигурных скобок, обратной косой черты и точки с запятой. В любом случае запрещенный символ обычно можно включить, экранируя его предшествующей обратной косой чертой. Поддержка Unicode варьируется.
Рекурсивный случай определения s-expr традиционно реализуется с использованием ячеек cons .
S-выражения изначально предназначались только для данных, которыми можно было манипулировать с помощью M-выражений , но первая реализация Lisp была интерпретатором S-выражений, кодирующих M-выражения, и программисты Lisp вскоре привыкли использовать S-выражения для обоих кодов. и данные. Это означает, что Лисп гомоиконичен ; то есть первичное представление программ также является структурой данных в примитивном типе самого языка.
Вложенные списки можно записать в виде S-выражений: ((milk juice) (honey marmalade)) представляет собой двухэлементное S-выражение, элементы которого также являются двухэлементными S-выражениями. Обозначение, разделенное пробелами, используемое в Лиспе (и в этой статье), является типичным. Разрывы строк (символы новой строки) обычно считаются разделителями. Это простая контекстно-свободная грамматика для небольшого подмножества английского языка, написанная в виде S-выражения (Газдар/Мелиш, обработка естественного языка в Лиспе), где S=предложение, NP=именная фраза, VP=глагольная фраза, V=глагол. :
(((S) (NP VP))
((VP) (V))
((VP) (V NP))
((V) died)
((V) employed)
((NP) nurses)
((NP) patients)
((NP) Medicenter)
((NP) "Dr Chan"))
Программный код может быть записан в S-выражениях, обычно с использованием префиксной записи. Пример в Common Lisp :
(defun factorial (x)
(if (zerop x)
1
(* x (factorial (- x 1)))))
S-выражения можно прочитать в Лиспе с помощью функции READ. READ считывает текстовое представление S-выражения и возвращает данные Lisp. Функция PRINT может использоваться для вывода S-выражения. Затем вывод можно прочитать с помощью функции READ, когда все напечатанные объекты данных имеют читаемое представление. В Lisp есть читаемые представления чисел, строк, символов, списков и многих других типов данных. Программный код можно отформатировать в виде красиво напечатанных S-выражений с помощью функции PPRINT (примечание: с двумя P, сокращением от beautiful -print).
Программы на Лиспе являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Лиспе. (1.0 + 3.1) является допустимым S-выражением, но не допустимой программой на Лиспе, поскольку Лисп использует префиксную запись, а число с плавающей запятой (здесь 1.0) недопустимо в качестве операции (первый элемент выражения).
S-выражению, которому предшествует одинарная кавычка, как в 'x, является синтаксическим сахаром для S-выражения в кавычках , в данном случае (quote x).
Разбор
[ редактировать ]S-выражения часто сравнивают с XML : одно ключевое отличие состоит в том, что S-выражения имеют только одну форму включения — точечную пару, тогда как теги XML могут содержать простые атрибуты, другие теги или CDATA , каждый из которых использует свой синтаксис. Другая причина заключается в том, что S-выражения не определяют механизм ссылок, где XML предоставляет понятие уникальных идентификаторов и ссылок на них. Для простых случаев использования S-выражения проще, чем XML, но для более сложных случаев использования XML имеет язык запросов, так называемый XPath , множество инструментов и сторонних библиотек для упрощения обработки данных XML.
Стандартизация
[ редактировать ]Стандарты некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS и R6RS). [5] ) и ISLISP .
В мае 1997 года Рон Ривест представил интернет-проект. [6] рассматриваться для публикации в качестве RFC . В проекте определен синтаксис, основанный на S-выражениях Lisp, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был утвержден в качестве RFC, но с тех пор его цитировали и использовали в других RFC (например, RFC 2693) и ряде других публикаций. [7] Изначально он предназначался для использования в SPKI .
Формат Ривеста определяет S-выражение как строку октетов (серию байтов ) или как конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Одним из них является «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Лиспа, но они не идентичны. Расширенный транспорт, например, позволяет представлять строки октетов дословно (длина строки, за которой следует двоеточие и вся необработанная строка), форма в кавычках, допускающая escape-символы, шестнадцатеричные символы , Base64 или помещаться непосредственно как «токен», если оно отвечает определенным условиям. (Токены Ривеста отличаются от токенов Лиспа тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как и другие строки, тогда как вторые имеют особое синтаксическое значение.)
Проект Ривеста определяет каноническое представление «для целей цифровой подписи». Он должен быть компактным, простым для анализа и уникальным для любого абстрактного S-выражения. Он допускает только дословные строки и запрещает пробелы при форматировании внешних строк. Наконец, существует «базовое транспортное представление», которое имеет либо каноническую форму, либо закодировано в формате Base64 и заключено в фигурные скобки . Последнее предназначено для безопасной транспортировки канонически закодированного S-выражения в систему, которая может изменить интервал (например, электронное письмо). система, которая имеет строки длиной 80 символов и переносит все, что длиннее этой).
Этот формат не был широко адаптирован для использования за пределами SPKI (некоторые пользователи — GnuPG , libgcrypt, Nettle и GNU lsh). На веб-странице S-выражений Ривеста представлен исходный код C для синтаксического анализатора и генератора (доступен по лицензии MIT ), который можно адаптировать и встроить в другие программы. [8] Кроме того, нет ограничений на самостоятельное внедрение формата.
См. также
[ редактировать ]- минусы
- АВТОМОБИЛЬ и CDR
- Фекспр
- Лямбда-исчисление
- М-выражение
- Канонические S-выражения
- Сравнение форматов сериализации данных
Ссылки
[ редактировать ]- ^ Jump up to: а б Джон Маккарти (1960/2006). Рекурсивные функции символьных выражений. Архивировано 2 февраля 2004 г. на Wayback Machine . Первоначально опубликовано в журнале «Сообщения ACM» .
- ^ «Common Lisp HyperSpec: 22.4 — Словарь принтера: *PRINT-CIRCLE*» . 2018-12-28.
- ^ «Пересмотренный 7 Отчет о схеме алгоритмического языка: Раздел 2.4: Метки данных» (PDF) . 06.07.2013.
- ^ «Пересмотренный отчет^5 об алгоритмической языковой схеме» . Schemers.org .
- ^ Спербер, Майкл; Дибвиг, Р. Кент; Флэтт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (12 августа 2009 г.). «Пересмотренный отчет 6 по алгоритмической языковой схеме». Журнал функционального программирования . 19 (С1): 1–301. CiteSeerX 10.1.1.372.373 . дои : 10.1017/S0956796809990074 . S2CID 267822156 .
- ^ S-выражения , Сетевая рабочая группа, Интернет-проект, срок действия истекает 4 ноября 1997 г. - Р. Ривест, 4 мая 1997 г., Draft-rivest-sexp-00.txt, Рональд Л. Ривест, веб-сайт CSAIL MIT
- ^ rivest sexp , Google Scholar (поиск)
- ^ «SEXP (S-выражения)» . люди.csail.mit.edu . Архивировано из оригинала 23 февраля 2023 г. Проверено 5 мая 2023 г.
Внешние ссылки
[ редактировать ]- sfsexp — небольшая и быстрая библиотека S-выражений для C/C++ на GitHub.
- minilisp , автор: Леон Ботту.
- S-выражения в Rosettacode имеют реализации чтения и записи на многих языках.
