Схема символической эквивалентности

Question

Платформа, с которой я работаю - DrScheme.

Я видел, что пара (a b) [созданная (cons a b)] реализована в языке как процедура, которая выглядит следующим образом:

(define (cons a b)
  (lambda(pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))

и селекторы:

(define (car x) (x 1))
(define (cdr x) (x 2))

Тогда есть списки, построенные с выражением типа (cons a (cons b (cons c (cons ...)))).

Теперь, что я пытался понять, это (напечатано в приглашении DrScheme):

> (define l1 '(a b c))
> (define l2 (list 'a 'b 'c))
> l1
(a b c)
> l2
(a b c)
> (eq? l1 l2)
#f

Хорошо, l2 - это просто список (то есть процедура, и т. Д.), Как я описал abode, но ... что такое , это l1? Символ? Последовательность символов? И что бы это ни было, как это реализовано в языке? Спасибо!

Answer 1

l1 также просто список, содержащий те же элементы. Обратите внимание, что это также возвращает #f:

(define l1 '(a b c))
(define l2 '(a b c))
(eq? l1 l2)

Пока возвращается #t:

(define l1 '(a b c))
(define l2 (list 'a 'b 'c))
(equal? l1 l2)

Причина в том, что eq? проверяет, являются ли l1 и l2 ссылками на один и тот же объект в памяти, в то время как equal? проверяет, имеют ли они одинаковое содержимое.

Answer 2

> > (define l1 '(a b c))
> > (define l2 (list 'a 'b 'c))
> > l1 (a b c)
> > l2 (a b c)
> > (eq? l1 l2)
> #f

Хорошо, l2 - это просто список (то есть процедура, т. Д.), Как я описал в abode, но ... что такое l1?Символ?Последовательность символов?И что бы это ни было, как это реализовано в языке?Спасибо!

Определение имеет вид:

(определить )

Во время выполнения вычисляется выражение , иРезультатом является значение.Это значение хранится где-то в памяти.Чтобы использовать это значение в других вычислениях, можно использовать имя .Терминология заключается в том, что связан со значением.

Важно отметить, что имя появляется только в вашем исходном коде.Его нет во время выполнения.Поэтому спрашивать, является ли имя l1 символом, не имеет смысла.

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

1. Резервирование ячейки памяти mдля указателя p
2. Выходной код, который вычисляет значение v из
3. Сохранение адреса ячейки памяти, содержащей v, в ячейке памяти m.

Примечание, что имя не появляется в этом списке.

Answer 3

Списки не атомы , это важная часть здесь.Хотя символы являются атомами, это означает, что когда они одинаковы, они находятся в одной и той же памяти, они похожи на числа и действительно могут рассматриваться как указатели.Символы также не являются изменяемыми, символ foo подобен числу 3.

Списки, однако, не являются атомами, два списка или строки векторов с одинаковым содержимым вполне могут находиться в двух разныхместа памяти.

eq? тесты только на месте памяти.eqv? проверяет эквивалентность, что является расплывчатым, и это зависит от того, какая реализация, стандарт Схемы, довольно либеральна с этим, он только говорит, что он должен быть по крайней мере надмножеством eq? в принципе.equal? на другом конце тестирует структурное равенство и делает это рекурсивно, поэтому это очень дорогая операция, и поэтому символы часто предпочитаются строкам для идентификаторов.

(define l1 (list 1 2 3))
(define l2 (list 1 2 3))
(eq? l1 l2) ; ===> #f in most implementations
(equal? l1 l2) ; ===> #t in all implementations
(eqv? l1 l2) ; ===> #t in some implementations
(define l3 (cdr l1))
(define l4 (cdr l1))
(eq? l3 l4) ; ===> #t, this means that they 'share memory', if you change l3 or l4, l1 will change with it, beware. This is how car and cdr work, they do not copy.
(define l6 (cons 1 l4));
(eq? l1 l6) ; ===> #f again, cons does allocate new memory, but the tails may very well share it, s in this case, l6 does share its tail with all lists except l2 here in memory. 

Кроме того, немного терминологии,cons создает пару, это отличается от списка из двух элементов, создает пару (a . b), список (a b) фактически идентичен паре (a . (b . ()))

Кроме того, cons и car и cdrявляются примитивами, реализация, которую вы видите ниже, является демонстрацией в Структура и реализация компьютерных программ , которая показывает, что они не являются строго необходимыми как они, но использование их в качестве примитивов значительно повышает производительность, поэтому лучше не переопределятьВаши минусы, машина и CDR.