S-выражение - S-expression

Дерево структура данных представляющий S-выражение (* 2 (+ 3 4))

В компьютерное программирование, S-выражения (или символические выражения, сокращенно sexprs) являются обозначением вложенных список (дерево -структурированные) данные, изобретенные и популяризируемые языком программирования Лисп, который использует их для исходный код а также данные. В обычных скобках синтаксис в Лиспе S-выражение определяется классически^[1] так как

1. атом, или
2. ан выражение формы (Икс . у) где Икс и у являются S-выражениями.

Секунда, рекурсивный часть определения представляет собой упорядоченная пара, что означает, что S-выражения могут представлять любые двоичное дерево, хотя S-выражения, содержащие циклы, наоборот, не могут быть представлены в виде двоичных деревьев.

Определение атома варьируется в зависимости от контекста; в исходном определении Джон Маккарти,^[1] предполагалось, что существует «бесконечное множество различимых атомные символы "представлены как" строки капитала Латинские буквы и цифры с одиночными вставленными пробелами "(т. е. строка символов и числовой литералы ). В большинстве современных обозначений sexpr для обозначения списки в S-выражениях, так что

(Икс у z)

означает

(Икс . (у . (z . НЕТ)))

где Ноль это специальный конец списка объект (альтернативно написано (), которое является единственным представлением в Схема^[2]).

В семействе языков программирования Lisp S-выражения используются для представления как исходного кода, так и данных. Другие варианты использования S-выражений находятся в языках, производных от Lisp, таких как DSSSL, и в качестве наценка в протоколы связи любить IMAP и Джон Маккарти с CBCL. Он также используется как текстовое представление WebAssembly. Подробная информация о синтаксисе и поддерживаемых типы данных различаются на разных языках, но наиболее распространенной особенностью этих языков является использование S-выражений и префиксной нотации.

Типы данных и синтаксис

Существует множество вариантов формата S-выражения, поддерживающих множество различных синтаксисов для разных типов данных. Наиболее широко поддерживаются:

• Списки и пары: (1 () (2 . 3) (4))
• Символы: с дефисом ?@!$ символ с пробелами
• Струны: "Привет мир!"
• Целые числа: -9876543210
• Числа с плавающей запятой: -0.0 6.28318 6.022e23

Персонаж # часто используется для префикса расширений синтаксиса, например # x10 для шестнадцатеричных целых чисел или # C для персонажей.

Использование в Лиспе

При представлении исходного кода в Лиспе первым элементом S-выражения обычно является имя оператора или функции, а любые оставшиеся элементы рассматриваются как аргументы. Это называется «префиксная запись» или «Польская нотация ". Например, Булево выражение написано 4 == (2 + 2) в C, представлен как (= 4 (+ 2 2)) в нотации префиксов Lisp на основе s-expr.

Как отмечалось выше, точное определение «атома» зависит от LISP-подобных языков. Строка в кавычках обычно может содержать что угодно, кроме кавычек, в то время как атом идентификатора без кавычек обычно может содержать что угодно, кроме кавычек, пробелов, круглых скобок, скобок, фигурных скобок, обратной косой черты и точки с запятой. В любом случае запрещенный символ обычно может быть включен путем экранирования его предыдущей обратной косой чертой. Unicode поддержка варьируется.

Рекурсивный случай определения s-expr традиционно реализуется с использованием противные ячейки.

S-выражения изначально предназначались только для данных, которыми должен управлять М-выражения, но первая реализация Lisp была интерпретатором кодировок S-выражений для M-выражений, и программисты Lisp вскоре привыкли использовать S-выражения как для кода, так и для данных. Это означает, что Lisp является гомоиконный; то есть первичным представлением программ также является структура данных в примитивном типе самого языка.

Примеры S-выражений данных

Вложенные списки можно записать как S-выражения: ((молочный сок) (медовый мармелад)) представляет собой двухэлементное S-выражение, элементы которого также являются двухэлементными S-выражениями. Нотация, разделенная пробелами, используемая в Лиспе (и в этой статье), является типичной. Разрывы строк (символы новой строки) обычно квалифицируются как разделители.

Это простой контекстно-свободная грамматика для небольшого подмножества английского языка, записанного как S-выражение (Gazdar / Melish, Natural Language Processing in Lisp), где S = предложение, NP = словосочетание существительное, VP = фраза глагола, V = глагол:

(((S) (НП Вице-президент)) ((Вице-президент) (V)) ((Вице-президент) (V НП)) ((V) умер) ((V) нанятый) ((НП) медсестры) ((НП) пациенты) ((НП) Медикентер) ((НП) "Доктор Чан"))

Пример S-выражений исходного кода

Программный код может быть записан в S-выражениях, обычно с использованием префиксной записи.

Пример в Common Lisp:

(defun факториал (Икс)   (если (нулевой Икс)       1       (* Икс (факториал (- Икс 1)))))

S-выражения можно читать в Лиспе с помощью функции READ. READ читает текстовое представление S-выражения и возвращает данные Lisp. Функцию PRINT можно использовать для вывода S-выражения. Затем вывод можно прочитать с помощью функции READ, когда все объекты напечатанных данных имеют читаемое представление. В Лиспе есть удобочитаемые представления чисел, строк, символов, списков и многих других типов данных. Программный код можно отформатировать как красиво напечатанные S-выражения с помощью функции PPRINT (примечание: с двумя буквами P, сокращенно от довольно-Распечатать).

Программы на Лиспе являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Лиспе. (1.0 + 3.1) является допустимым S-выражением, но не допустимой программой Lisp, поскольку Lisp использует префиксную нотацию, а число с плавающей запятой (здесь 1.0) недопустимо как операция (первый элемент выражения).

S-выражение, которому предшествует одинарная кавычка, как в 'Икс, является синтаксический сахар для цитируемое S-выражение, в таком случае (цитата x).

Парсинг

S-выражения часто сравнивают с XML: ключевое отличие состоит в том, что S-выражения имеют только одну форму включения, точечную пару, и их намного легче анализировать, в то время как теги XML могут содержать простые атрибуты, другие теги или CDATA, каждый из которых использует свой синтаксис.

Стандартизация

Стандарты для некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. Они включают Common Lisp (Стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Схема (R5RS и R6RS^[3]), и ISLISP.

Вариант Ривеста

В мае 1997 г. Рон Ривест представил Интернет-проект^[4] будет рассматриваться для публикации как RFC. В проекте определен синтаксис, основанный на S-выражениях Лиспа, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был утвержден в качестве RFC, но с тех пор он цитировался и использовался другими RFC (например, RFC 2693 ) и ряд других публикаций.^[5] Первоначально он предназначался для использования в СПКИ.

Формат Ривеста определяет S-выражение как строку октетов (последовательность байты ) или конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Один из них - это «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Лиспа, но не идентичны. Расширенный транспорт, например, позволяет дословно представлять строки октетов (длина строки, за которой следует двоеточие и вся необработанная строка), форма в кавычках позволяет использовать escape-символы, шестнадцатеричный, Base64, или размещается непосредственно как «жетон», если он соответствует определенным условиям. (Токены Ривеста отличаются от токенов Lisp тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как и другие строки, в то время как последние имеют определенное синтаксическое значение.)

Проект Ривеста определяет каноническое представление «для целей электронной подписи». Он должен быть компактным, более простым для анализа и уникальным для любого абстрактного S-выражения. Он разрешает только дословные строки и запрещает пробелы как форматирование вне строк. Наконец, есть «базовое транспортное представление», которое является либо канонической формой, либо такой же кодировкой, как Base64 и окружено подтяжки, последний предназначен для безопасной транспортировки канонически закодированного S-выражения в системе, которая может изменять интервал (например, система электронной почты, которая имеет строки шириной 80 символов и переносит все, что длиннее).

Этот формат не получил широкого распространения для использования вне SPKI (некоторые из пользователей GnuPG, libgcrypt, Крапива, и GNU lsh). Веб-страница S-выражений Rivest предоставляет C исходный код парсера и генератора (доступен под Лицензия MIT ), которые можно было адаптировать и встроить в другие программы.^[6] Кроме того, нет ограничений на самостоятельную реализацию формата.

Смотрите также

• минусы
• CAR и CDR
• Fexpr
• Лямбда-исчисление
• М-выражение
• Канонические S-выражения
• Сравнение форматов сериализации данных

использованная литература

внешние ссылки

• sfsexp небольшая, быстрая библиотека S-выражений для C / C ++ на Github
• минилисп, автор: Леон Ботту.
• S-выражения на Rosettacode имеет реализации читателей и писателей на многих языках.