Лисп: список против S-выражения

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

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

Возможно, это слишком техническое различие; программисты обычно ссылаются на буквальные представления значений, как если бы они сами были значениями. Но с Лиспом и списками все становится немного сложнее, потому что все в программе на Лиспе технически является списком.

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

(+ 1 2)

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

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

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

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

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

Конечно, эквивалентность кода и данных — одна из замечательных особенностей Lisp, так что разница между ними незначительна. Но я хочу сказать, что, хотя все вышеперечисленное является S-выражениями и списками, только некоторые из них можно назвать «списками» в обычном языке Лиспа.

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-выражения. Сегодня большая часть программного кода на Лиспе написана с использованием s-выражений.

Это описано здесь: McCarthy, Recursive Functions of Symbolic Expressions

В современном языке программирования 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 |#

и больше.

Списки

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

Примечание: программы и формы

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

Например, вызов функции — это данные Лиспа, где вызов — это список с символом функции в качестве первого элемента, а следующие элементы — его аргументы.

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

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

Поскольку формы Лиспа имеют представление данных, они обычно пишутся с использованием внешнего представления данных Лиспа — а что? - с-выражения!

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

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

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

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

Простое определение 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)))))

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

По оценке:

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

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

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

МСФО:

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