Lisp: список vs S-expression

Ответ 1

Во-первых, не все S-выражения представляют списки; выражение, такое как foobar, представляющее голодный атом, также считается S-выражением. Как и синтаксис "cons cell", (car . cons), используется, когда часть "cons" сама по себе не является другим списком (или nil). Более знакомое выражение списка, например (a b c d), является просто синтаксическим сахаром для цепочки вложенных cons-ячеек; этот пример расширяется до (a . (b . (c . (d . nil)))).

Во-вторых, термин "S-выражение" относится к синтаксису - (items like this (possibly nested)). Такое S-выражение представляет собой представление в исходном коде Lisp списка, но оно не является технически самым списком. Это различие является таким же, как между последовательностью десятичных цифр и их числовым значением, или между последовательностью символов в кавычках и результирующей строкой.

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

Например, рассмотрим это выражение:

(+ 1 2)

Вышеприведенное является прямым S-выражением, которое представляет собой плоский список, состоящий из атомов +, 1 и 2.

Однако в программе Lisp такой список будет интерпретироваться как вызов функции + с 1 и 2 в качестве аргументов. (Имейте в виду, что это список, а не S-выражение, которое интерпретируется так: оценщик передается спискам, которые были предварительно проанализированы читателем, а не текстом исходного кода.)

Итак, в то время как вышеприведенное S-выражение представляет список, его редко упоминает как "список" в контексте программы Lisp. Если не обсуждать макросы или внутреннюю работу читателя или заниматься метасинтетическим обсуждением из-за другого контекста генерации кода или синтаксического анализа, типичный программист Lisp вместо этого рассмотрит вышеуказанное как числовое выражение.

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

'(+ 1 2)
(quote (+ 1 2))
(list '+ 1 2)

Конечно, эквивалентность кода и данных является одной из интересных вещей о Lisp, поэтому различие является текучим. Но я считаю, что, хотя все вышеперечисленные являются S-выражениями и списками, только некоторые из них будут упоминаться как "списки" в случайном Lisp -speak.

Ответ 2

S-выражения - это обозначения для данных.

Исторически s-выражение (сокращенное для символического выражения) описывается как:

• символы, такие как FOO и BAR
• cons ячейки с s-выражениями в качестве первого и второго элементов: ( выражение-1 . выражение-2 )
• символ завершения списка NIL
• и соглашение для записи списков: ( A . ( B . NIL ) ) проще записать в виде списка (A B)

Обратите внимание также, что исторически текст программы был написан по-разному. Пример для функции ASSOC.

assoc[x;y] =
   eq[caar[y];x] -> cadar[y];
   T -> assoc[x;cdr[y]]

Исторически существовало также отображение из этих m-выражений (краткое для мета-выражений) в s-выражения. Сегодня большинство Lisp программных кодов написано с использованием s-выражений.

Это описано здесь: Маккарти, рекурсивные функции символических выражений

В языке программирования Lisp, таком как Common Lisp, s-выражения в настоящее время имеют больше синтаксиса и могут кодировать больше типов данных:

• Символы: symbol123, |This is a symbol with spaces|
• Числа: 123, 1.0, 1/3,...
• Строки: "This is a string"
• Символы: #\a, #\space
• Векторы: #(a b c)
• Концы и списки: ( a . b ), (a b c)
• Комментарии: ; this is a comment, #| this is a comment |#

и более.

Списки

Список - это структура данных. Он состоит из cons-элементов и маркера конца списка. Списки имеют в Lisp обозначение в виде списков в s-выражениях. Вы можете использовать некоторые другие обозначения для списков, но в Lisp для синтаксиса s-expression задано значение для записи.

Боковое примечание: программы и формы

На языке программирования, таком как Common Lisp, выражения языка программирования не являются текстовыми, а данными! Это отличается от многих других языков программирования. Выражения на языке программирования Common Lisp называются Lisp forms.

Например, вызов функции - это Lisp data, где вызов представляет собой список с символом функции в качестве его первого элемента, а следующие элементы - его аргументы.

Мы можем написать это как (sin 3.0). Но это действительно данные. Данные, которые мы также можем построить.

Функция для оценки форм Lisp называется EVAL и принимает данные Lisp, а не текст программы или строки текста программы. Таким образом, вы можете создавать программы, используя Lisp функции, возвращающие данные Lisp: (EVAL (LIST 'SIN 3.0)) оценивается до 0.14112.

Так как формы Lisp имеют представление данных, они обычно записываются с использованием внешнего представления данных Lisp - что это? - s-выражения!

Это s-выражения. Lisp формы как Lisp данные записываются внешне как s-выражение.

Ответ 3

Вы должны сначала понять главную функцию Lisp - программа может управляться как данные. В отличие от других языков (например, C или Java), где вы пишете программу с помощью специального синтаксиса ({, }, class, define и т.д.), В Lisp вы пишете код как (вложенный) list (btw, это позволяет напрямую выражать абстрактные синтаксические деревья). Еще раз: вы пишете программы, которые выглядят так же, как структуры данных языка.

Когда вы говорите об этом как данные, вы называете его "list" , но когда вы говорите о программном коде, вам лучше используйте термин "s-expression" . Таким образом, технически они похожи, но используются в разных контекстах. Единственным реальным местом, где эти термины являются смешанными, является метапрограммирование (обычно с макросами).

Также обратите внимание, что s-expression может также состоять только из atom (например, числа, строки и т.д.).

Ответ 4

Простым определением для S-выражения является

(define S-expression?
    (λ (object)
        (or (atom? object) (list? object))))

;; Where atom? is:

(define atom?
  (λ (object) 
    (and (not (pair? object)) (not (null? object)))))

;; And list? is:

(define list? (λ (object)
  (let loop ((l1 object) (l2 object))
    (if (pair? l1)
        (let ((l1 (cdr l1)))
          (cond ((eq? l1 l2) #f)
                ((pair? l1) (loop (cdr l1) (cdr l2)))
                (else (null? l1))))
        (null? l1)))))

Ответ 5

Оба написаны аналогичным образом: (бла-бла-бла), могут быть вложенными. с одним отличием - списки имеют префикс с апострофом.

Об оценке:

• S-выражение возвращает некоторый результат (может быть атом или список или нуль или что-то еще)
• Списки возврата Списки

Если нам нужно, мы можем конвертировать списки в s-exp и наоборот.

• (eval '(blah blah blah)) = > рассматривается как s-exp и возвращается результат.
• (quote (blah blah blah)) = > sexp преобразуется в список, и список возвращается без оценки

МСФО:

• Если список обрабатывается как данные, он называется List, если он рассматривается как код, он называется s-exp.